1 January 2001 in SIAM Journal on Optimization
A critical disadvantage of primal-dual interior-point methods compared to dual interior-point methods for large scale semidefinite programs (SDPs) has been that the primal positive semidefinite matrix variable becomes fully dense in general even when all data matrices are sparse. Based on some fundamental results about positive semidefinite matrix completion, this article proposes a general method of exploiting the aggregate sparsity pattern over all data matrices to overcome this disadvantage. Our method is used in two ways. One is a conversion of a sparse SDP having a large scale positive semidefinite matrix variable into an SDP having multiple but smaller positive semidefinite matrix variables to which we can effectively apply any interior-point method for SDPs employing a standard block-diagonal matrix data structure. The other way is an incorporation of our method into primal-dual interior-point methods which we can apply directly to a given SDP. In Part II of this article, we will investigate an implementation of such a primal-dual interior-point method based on positive definite matrix completion, and report some numerical results.
15 May 2001 in The Journal of Chemical Physics
The ground-state fermion second-order reduced density matrix (2-RDM) is determined variationally using itself as a basic variable. As necessary conditions of the N-representability, we used the positive semidefiniteness conditions, P, Q, and G conditions that are described in terms of the 2-RDM. The variational calculations are performed by using recently developed semidefinite programming algorithm (SDPA). The calculated energies of various closed- and open-shell atoms and molecules are excellent, overshooting only slightly the full-CI energies. There was no case where convergence was not achieved. The calculated properties also reproduce well the full-CI results.
1 February 2003 in Mathematical Programming
1 January 2017 in Journal of the Operations Research Society of Japan
This paper proposes a method for eliminating multicollinearity from linear regression models. Specifically, we select the best subset of explanatory variables subject to the upper bound on the condition number of the correlation matrix of selected variables. We first develop a cutting plane algorithm that, to approximate the condition number constraint, iteratively appends valid inequalities to the mixed integer quadratic optimization problem. We also devise a mixed integer semidefinite optimization formulation for best subset selection under the condition number constraint. Computational results demonstrate that our cutting plane algorithm frequently provides solutions of better quality than those obtained using local search algorithms for subset selection. Additionally, subset selection by means of our optimization formulation succeeds when the number of candidate explanatory variables is small.
16 March 2013 in Optimization Letters