The Semidefinite Program (SDP) is a fundamental problem in mathematical programming. It covers a wide range of applications, such as combinatorial optimization, control theory, polynomial optimization, and quantum chemistry. Solving extremely large-scale SDPs which could not be solved before is a significant work to open up a new vista of future applications of SDPs. Our … Read more
We propose a primal-dual path-following Mehrotra-type predictor-corrector method for solving convex quadratic semidefinite programming (QSDP) problems. For the special case when the quadratic term has the form $\frac{1}{2} X \bul (UXU)$, we compute the search direction at each iteration from the Schur complement equation. We are able to solve the Schur complement equation efficiently via … Read more
SparesPOP is a MATLAB implementation of a sparse semidefinite programming (SDP) relaxation method proposed for polynomial optimization problems (POPs) in the recent paper by Waki et al. The sparse SDP relaxation is based on a hierarchy of LMI relaxations of increasing dimensions by Lasserre, and exploits a sparsity structure of polynomials in POPs. The efficiency … Read more
We describe an approach to the parallel and distributed solution of large-scale, block structured semidefinite programs using the spectral bundle method. Various elements of this approach (such as data distribution, an implicitly restarted Lanczos method tailored to handle block diagonal structure, a mixed polyhedral-semidefinite subdifferential model, and other aspects related to parallelism) are combined in … Read more
We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix *-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending … Read more
The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note we show that the SQO problem may be reformulated as an (exponentially sized) linear program. Citation … Read more
We present a practical approach to Anstreicher and Lee’s masked spectral bound for maximum-entropy sampling, and we describe favorable results that we have obtained with a Branch-&-Bound algorithm based on our approach. By representing masks in factored form, we are able to easily satisfy a semidefiniteness constraint. Moreover, this representation allows us to restrict the … Read more
Primal–dual interior point methods and the HKM method in particular have been implemented in a number of software packages for semidefinite programming. These methods have performed well in practice on small to medium sized SDP’s. However, primal–dual codes have had some trouble in solving larger problems because of the method’s storage requirements. In this paper … Read more
When solving large-scale semidefinite programming problems by second-order methods, the storage and factorization of the Newton matrix are the limiting factors. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable … Read more
We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the … Read more