Hayato Waki – Page 2 – Optimization Online

Optimization Software and Modeling Systems, Semi-definite Programming numerical stability, polynomial optimization, semidefinite programming

Maho Nakata

We observe that in a simple one-dimensional polynomial optimization problem (POP), the `optimal’ values of semidefinite programming (SDP) relaxation problems reported by the standard SDP solvers converge to the optimal value of the POP, while the true optimal values of SDP relaxation problems are strictly and significantly less than that value. Some pieces of circumstantial … Read more

Exploiting Sparsity in SDP Relaxation for Sensor Network Localization

Published: 2008/01/15

Semi-definite Programming polynomial optimization problem, semidefinite relaxation, sensor network localization problem, sparsity

A sensor network localization problem can be formulated as a quadratic optimization problem (QOP). For quadratic optimization problems, semidefinite programming (SDP) relaxation by Lasserre with relaxation order 1 for general polynomial optimization problems (POPs) is known to be equivalent to the sparse SDP relaxation by Waki {¥it et al.} with relaxation order 1, except the … Read more

SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems

Published: 2005/03/09

Global Optimization, Optimization Software and Modeling Systems, Semi-definite Programming global optimization, matlab software package, polynomial optimization problem, semidefinite relaxation, sparsity, sums of squares optimization

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

Published: 2004/10/30, Updated: 2005/02/03

Constrained Nonlinear Optimization, Global Optimization, Linear, Cone and Semidefinite Programming global optimization, lagrangian dual, lagrangian relaxation, polynomial optimization problem, semidefinite relaxation, sparsity, sums of squares optimization

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

Sparsity in Sums of Squares of Polynomials

Published: 2003/09/29, Updated: 2005/05/21

Linear, Cone and Semidefinite Programming, Polyhedra polynomial optimization problem, semidefinite programming, sparsity, sums of squares of polynomials

Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and SDP (semidefinite programming) relaxation of polynomial optimization problems. We disscuss effective methods to obtain a simpler representation of a “sparse” polynomial as a sum of … Read more

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

Published: 2003/09/29

Global Optimization Theory, Semi-definite Programming global optimization, lagrangian dual, lagrangian relaxation, polynomial optimization problem, semidefinite programming, semidefinite relaxation, sparsity, sums of squares optimization

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

A General Framework for Convex Relaxation of Polynomial Optimization Problems over Cones

Published: 2002/06/09, Updated: 2004/04/29