Imperial College London
Portrait Picture

ProfessorRuthMisener

Faculty of Engineering, Department of Computing

Professor in Computational Optimisation
 
 
 
//

Contact

 

+44 (0)20 7594 8315r.misener Website CV

 
 
//

Location

 

379Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Campos:2019:10.1016/j.ejor.2019.02.016,
author = {Campos, JS and Misener, R and Parpas, P},
doi = {10.1016/j.ejor.2019.02.016},
journal = {European Journal of Operational Research},
pages = {32--41},
title = {A multilevel analysis of the Lasserre hierarchy},
url = {http://dx.doi.org/10.1016/j.ejor.2019.02.016},
volume = {277},
year = {2019}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - 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.
AU  - Campos,JS
AU  - Misener,R
AU  - Parpas,P
DO  - 10.1016/j.ejor.2019.02.016
EP  - 41
PY  - 2019///
SN  - 0377-2217
SP  - 32
TI  - A multilevel analysis of the Lasserre hierarchy
T2  - European Journal of Operational Research
UR  - http://dx.doi.org/10.1016/j.ejor.2019.02.016
UR  - http://hdl.handle.net/10044/1/67650
VL  - 277
ER  -
Download