Mituhiro Fukuda – Page 2 – Optimization Online

Preprocessing sparse semidefinite programs via matrix completion

Published: 2004/03/16, Updated: 2004/07/02

Semi-definite Programming clique tree, matrix completion, numerical experiments, preprocessing, semidefinite programming, sparsity

Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more

The Reduced Density Matrix Method for Electronic Structure Calculations and the Role of Three-Index Representability Conditions

Published: 2003/10/16

Basic Sciences Applications, Convex Optimization, Semi-definite Programming large scale semidefinite programming

The variational approach for electronic structure based on the two-body reduced density matrix is studied, incorporating two representability conditions beyond the previously used $P$, $Q$ and $G$ conditions. The additional conditions (called $T1$ and $T2$ here) are implicit in work of R.~M.~Erdahl [Int.\ J.\ Quantum Chem.\ {\bf13}, 697–718 (1978)] and extend the well-known three-index diagonal … Read more

Lagrangian dual interior-point methods for semidefinite programs

Published: 2001/04/03, Updated: 2004/04/29

Mituhiro Fukuda

Masakazu Kojima

Masayuki Shida

Convex Optimization, Second-Order Cone Programming, Semi-definite Programming bfgs quasi-newton method, central trajectory, conjugate gradient method, lagrangian dual, linear program over convex cones, predictor-corrector method, primal-dual interior-point method, second-order cone program, semidefinite programming

This paper proposes a new predictor-corrector interior-point method for a class of semidefinite programs, which numerically traces the central trajectory in a space of Lagrange multipliers. The distinguished features of the method are full use of the BFGS quasi-Newton method in the corrector procedure and an application of the conjugate gradient method with an effective … Read more

Exploiting Sparsity in Semidefinite Programming via Matrix Completion II: Implementation and Numerical Results

Published: 2001/03/06, Updated: 2004/04/30

Convex Optimization, Semi-definite Programming clique tree, matrix completion problem, numerical results, primal-dual interior-point method, semidefinite programming

In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods. This framework is based on some results about positive semidefinite matrix completion, and it can be embodied … Read more