A multilevel analysis of the Lasserre hierarchy
File(s)Campos_Misener_Parpas.pdf (356.74 KB)
Accepted version
Author(s)
Campos, JS
Misener, R
Parpas, P
Type
Journal Article
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 relaxation. 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.
Date Issued
2019-08-01
Online Publication Date
2021-02-12T00:01:34Z
Date Acceptance
2019-02-06
Citation
European Journal of Operational Research, 2019, 277 (1), pp.32-41
ISSN
0377-2217
Publisher
Elsevier
Start Page
32
End Page
41
Journal / Book Title
European Journal of Operational Research
Volume
277
Issue
1
Copyright Statement
© 2019 Elsevier Ltd. All rights reserved. This manuscript is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Licence http://creativecommons.org/licenses/by-nc-nd/4.0/
Source Database
crossref
Sponsor
Engineering & Physical Science Research Council (E
Engineering and Physical Sciences Research Council
Grant Number
EP/M028240/1
EP/P016871/1
Subjects
Social Sciences
Science & Technology
Technology
Management
Operations Research & Management Science
Business & Economics
Global optimization
Conic programming and interior point methods
Semidefinite programming
Polynomial optimization
POLYNOMIAL OPTIMIZATION
SEMIDEFINITE PROGRAM
RELAXATIONS
Operations Research
Publication Status
Published
Date Publish Online
2019-02-12