Recognizing Underlying Sparsity in Optimization

Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem’s functions can be improved by performing a nonsingular linear transformation in the space corresponding … Read more

Dynamic Enumeration of All Mixed Cells

The polyhedral homotopy method, which has been known as a powerful numerical method for computing all isolated zeros of a polynomial system, requires all mixed cells of the support of the system to construct a family of homotopy functions. Finding the mixed cells is formulated in terms of a linear inequality system with an additional … Read more

A Note on Sparse SOS and SDP Relaxations for Polynomial Optimization Problems over Symmetric Cones

This short note extends the sparse SOS (sum of squares) and SDP (semidefinite programming) relaxation proposed by Waki, Kim, Kojima and Muramatsu for normal POPs (polynomial optimization problems) to POPs over symmetric cones, and establishes its theoretical convergence based on the recent convergence result by Lasserre on the sparse SOS and SDP relaxation for normal … Read more

Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs

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

SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems

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

Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity

Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) … Read more

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems over Symmetric Cones

This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let ${\cal E}$ and ${\cal E}_+$ be a finite dimensional real vector space and a symmetric cone embedded in ${\cal E}$; examples of $\calE$ and $\calE_+$ include a pair of the … Read more

A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion

A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of … Read more

Sums of Squares Relaxations of Polynomial Semidefinite Programs

A polynomial SDP (semidefinite program) minimizes a polynomial objective function over a feasible region described by a positive semidefinite constraint of a symmetric matrix whose components are multivariate polynomials. Sums of squares relaxations developed for polynomial optimization problems are extended to propose sums of squares relaxations for polynomial SDPs with an additional constraint for the … Read more

Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems

Sequences of generalized Lagrangian duals and their SOS (sums of squares of polynomials) relaxations for a POP (polynomial optimization problem) are introduced. Sparsity of polynomials in the POP is used to reduce the sizes of the Lagrangian duals and their SOS relaxations. It is proved that the optimal values of the Lagrangian duals in the … Read more