A bounded degree SOS hierarchy for polynomial optimization

被引：44

作者：

Lasserre J.B. ^{[1
]}

Toh K.-C. ^{[2
]}

Yang S. ^{[2
]}

机构：

[1] LAAS-CNRS and Institute of Mathematics, University of Toulouse, Toulouse, LAAS, Toulouse cédex 4

[2] Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, Singapore

来源：

EURO Journal on Computational Optimization | 2017年 / 5卷 / 1-2期

基金：

欧盟地平线“2020”; 欧洲研究理事会;

关键词：

convex relaxations; Global optimization; LP and semidefinite hierarchies; Polynomial optimization;

D O I：

10.1007/s13675-015-0050-y

中图分类号：

学科分类号：

摘要：

We consider a new hierarchy of semidefinite relaxations for the general polynomial optimization problem (P):f∗=min{f(x):x∈K} on a compact basic semi-algebraic set K⊂ Rn. This hierarchy combines some advantages of the standard LP-relaxations associated with Krivine’s positivity certificate and some advantages of the standard SOS-hierarchy. In particular it has the following attractive features: (a) in contrast to the standard SOS-hierarchy, for each relaxation in the hierarchy, the size of the matrix associated with the semidefinite constraint is the same and fixed in advance by the user; (b) in contrast to the LP-hierarchy, finite convergence occurs at the first step of the hierarchy for an important class of convex problems; and (c) some important techniques related to the use of point evaluations for declaring a polynomial to be zero and to the use of rank-one matrices make an efficient implementation possible. Preliminary results on a sample of non convex problems are encouraging. © 2015, EURO - The Association of European Operational Research Societies.

引用

页码：87 / 117

页数：30

共 26 条

[1]

Ahmadi A.A., Majumdar A (2014) DSOS and SDSOS Optimization: LP and SOCP-Based Alternatives to SOS Optimization, Proceedings of the 48th annual conference on information sciences and systems, pp. 1-5

[2]

Benabbas S., Magen A., Shepherd F.B., Extending SDP integrality gaps to Sherali–Adams with applications to quadratic programming and MaxCutGain, Integer programming and combinatorial optimization. Lecture Notes in Computer Science, pp. 299-312, (2010)

[3]

Curto R.E., Fialkow L.A., The truncated complex K-moment problem, Trans Amer Math Soc, 352, pp. 2825-2855, (2000)

[4]

Curto R.E., Fialkow L.A., Truncated K-moment problem in several variables, J Op Theory, 54, pp. 189-226, (2005)

[5]

Chlamtac E., Tulsiani M., Convex relaxations and integrality gaps, Handbook of semidefinite, conic and polynomial optimization, pp. 139-170, (2012)

[6]

de Klerk E., Laurent M., On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems, SIAM J Optim, 21, pp. 824-832, (2011)

[7]

Floudas C.A., Pardalos P.M., A collection of test problems for constrained global optimization algorithms, Lecture Notes in Computer Science, (1990)

[8]

Henrion D., Lasserre J.B., Detecting global optimality and extracting solutions in Gloptipoly, Henrion D, Garulli A(eds) Positive polynomials in control, Lecture Notes in Control and Information Science, 312, pp. 293-310, (2005)

[9]

Henrion D., Lasserre J.B., Lofberg J., GloptiPoly 3: moments, optimization and semidefinite programming, Optim Methods Softw, 24, pp. 761-779, (2009)

[10]

Helton J.W., Nie J., Semidefinite representations of convex sets, Math Program, 122, pp. 21-64, (2010)

← 1 2 3 →