-

 

 

 




Optimization Online





 

A multilevel analysis of the Lasserre hierarchy

Juan S Campos(jsc12***at***ic.ac.uk)
Ruth Misener(r.misener***at***ic.ac.uk)
Panos Parpas(p.parpas***at***ic.ac.uk)

Abstract: This paper analyzes the relation between different orders of the Lasserre hierarchy for polynomial optimization (POP). Although for some cases solving the semidefinite programming relaxation corresponding to the first order of the hierarchy is enough to solve the underlying POP, other problems require sequentially solving the second or higher orders until a solution is found. For these cases, and assuming that the lower order semidefinite programming relaxation has been solved, we develop prolongation operators that exploit the solutions already calculated to find initial approximations for the solution of the higher order. We can prove feasibility in the higher order of the hierarchy of the points obtained using the operators, as well as convergence to the optimal as the relaxation order increases. Furthermore, the operators are simple and inexpensive for problems where the projection over the feasible set is "easy" to calculate (for example integer {0,1} and {-1,1} POPs). Our numerical experiments show that it is possible to extract useful information for real applications using the prolongation operators. In particular, we illustrate how the operators can be used to increase the efficiency of an infeasible interior point method by using them as an initial point. We use this technique to solve quadratic integer {0,1} problems, as well as MAX-CUT and integer partition problems.

Keywords: Semidefinite Programming, Polynomial Optimization

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Department of Computing, Imperial College London, London, SW7 2AZ. 06/2018

Download: [PDF]

Entry Submitted: 06/28/2018
Entry Accepted: 06/29/2018
Entry Last Modified: 06/28/2018

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society