Title:  A sub-gradient method for free material design problem

The free material design can be formulated as an optimization SDP problem. However, due to its large scale, second-order methods cannot solve it in a reasonable time. We formulate the free material design problem as a saddle-point problem, where the inverse to a large N by N matrix A(E) in the constraint is eliminated. We use the primal-dual sub-gradient method to solve the restricted saddle-point problem. Each iteration admits a closed-form implementation. While the inverse of A(E) requires O(N^3) arithmetic operations and an auxiliary vector storage of size O(N^2), each iteration of our algorithm takes a total of O(N^2) float-point operations and an auxiliary vector storage of size O(N). The iteration complexity bound of our algorithm is optimal for general gradient schemes.

In our algorithm we use a closed-form solution to a semi-definite least squares problem and apply an efficient parameter update scheme for the gradient method. We also approximate a solution to the bounded Lagrangian dual problem. Finally we present promising numerical results.

Joint work with Yu. Nesterov and M. Kocvara