×

zbMATH — the first resource for mathematics

Alternative SDP and SOCP approximations for polynomial optimization. (English) Zbl 1428.90116
Summary: In theory, hierarchies of semidefinite programming (SDP) relaxations based on sum of squares (SOS) polynomials have been shown to provide arbitrarily close approximations for a general polynomial optimization problem (POP). However, due to the computational challenge of solving SDPs, it becomes difficult to use SDP hierarchies for large-scale problems. To address this, hierarchies of second-order cone programming (SOCP) relaxations resulting from a restriction of the SOS polynomial condition have been recently proposed to approximate POPs. Here, we consider alternative ways to use the SOCP restrictions of the SOS condition. In particular, we show that SOCP hierarchies can be effectively used to strengthen hierarchies of linear programming relaxations for POPs. Specifically, we show that this solution approach is substantially more effective in finding solutions of certain POPs for which the more common hierarchies of SDP relaxations are known to perform poorly. Furthermore, when the feasible set of the POP is compact, these SOCP hierarchies converge to the POP’s optimal value.
MSC:
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ahmadi AA, Majumdar A (2014) DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization. In: 2014 48th Annual conference on information sciences and systems (CISS). IEEE, pp 1-5
[2] Anjos MF, Lasserre JB (eds) (2012a) Handbook on semidefinite, conic and polynomial optimization handbook on semidefinite, conic and polynomial optimization, volume 166 of international series in operations research & management science. Springer
[3] Anjos MF, Lasserre JB (2012b) Introduction to semidefinite, conic and polynomial optimization. In: Handbook on semidefinite, conic and polynomial optimization. Springer, pp 1-22 · Zbl 1334.90095
[4] Blekherman G, Parrilo PA, Thomas RR (2012) Semidefinite optimization and convex algebraic geometry. In: SIAM
[5] Boyd S, Vandenberghe L (2009) Convex optimization. Cambridge University Press, Cambridge
[6] de Klerk E, Pasechnik DV (2002) Approximation of the stability number of a graph via copositive programming. SIAM J Optimim 12(4):875-892 · Zbl 1035.90058
[7] de Klerk E, Sotirov R (2010) Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math Program 122(2):225-246 · Zbl 1184.90120
[8] Dickinson PJ, Povh J (2013) New linear and positive semidefinite programming based approximation hierarchies for polynomial optimisation. Preprint (submitted).http://www.optimization-online.org/DB_HTML/2013/06/3925.html
[9] Dickinson PJ, Povh J (2015) On an extension of Pólyas positivstellensatz. J Glob Optim 61(4):615-625 · Zbl 1379.11037
[10] Gatermann K, Parrilo PA (2004) Symmetry groups, semidefinite programs, and sums of squares. J Pure Appl Algebra 192(1-3):95-128 · Zbl 1108.13021
[11] Ghaddar B (2011) New conic optimization techniques for solving binary polynomial programming problem. Ph.D. thesis
[12] Ghaddar B, Marecek J, Mevissen M (2016) Optimal power flow as a polynomial optimization problem. IEEE Trans Power Syst 31(1):539-546
[13] Ghaddar B, Vera JC, Anjos MF (2011) Second-order cone relaxations for binary quadratic polynomial programs. SIAM J Optim 21(1):391-414 · Zbl 1242.90153
[14] Ghaddar B, Vera JC, Anjos MF (2016) A dynamic inequality generation scheme for polynomial programming. Math Program 156(1-2):21-57 · Zbl 1342.90143
[15] Hardy GH, Littlewood JE, Pólya G (1988) Inequalities. Cambridge Mathematical Library, Cambridge
[16] Josz C, Molzahn DK (2015) Moment/sum-of-squares hierarchy for complex polynomial optimization. arXiv preprint. arXiv:1508.02068
[17] Kleniati PM, Parpas P, Rustem B (2010) Partitioning procedure for polynomial optimization. J Glob Optim 48(4):549-567 · Zbl 1226.90077
[18] Kojima M, Kim S, Waki H (2003) Sparsity in sums of squares of polynomials. Math Program 103(1):45-62 · Zbl 1079.90092
[19] Kuang X, Ghaddar B, Naoum-Sawaya J, Zuluaga LF (2017) Alternative LP and SOCP hierarchies for ACOPF problems. IEEE Trans Power Syst 32(4):2828-2836
[20] Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J Optim 11(3):796-817 · Zbl 1010.90061
[21] Lasserre JB (2002) Semidefinite programming versus LP relaxations for polynomial programming. Math Oper Res 27(2):347-360 · Zbl 1082.90554
[22] Lasserre JB (2009) Moments and sums of squares for polynomial optimization and related problems. J Glob Optim 45(1):39-61 · Zbl 1177.90324
[23] Lasserre JB, Toh KC, Yang S (2017) A bounded degree SOS hierarchy for polynomial optimization. EURO J Comput Optim 5(1-2):87-117 · Zbl 1368.90132
[24] MOSEK A (2015) The MOSEK optimization toolbox for MATLAB manual. Version 7.1 (Revision 28)
[25] Murty KG, Kabadi SN (1987) Some NP-complete problems in quadratic and nonlinear programming. Math Program 39(2):117-129 · Zbl 0637.90078
[26] Parrilo P (2003) Semidefinite programming relaxations for semialgebraic problems. Math Program 96(2):293-320 · Zbl 1043.14018
[27] Peña J, Vera JC, Zuluaga LF (2017) Positive polynomials on unbounded domains. arXiv preprint. arXiv:1709.03435
[28] Putinar M (1993) Positive polynomials on compact semi-algebraic sets. Indiana Univ Math J 42:969-984 · Zbl 0796.12002
[29] Sahinidis NV, Tawarmalani M (2005) Baron 7.2.5: global optimization of mixed-integer nonlinear programs. Users manual
[30] Schmüdgen K (1991) The \[KK\]-moment problem for compact semi-algebraic sets. Math. Ann. 289:203-206 · Zbl 0744.44008
[31] Sturm JF (1999) Using SeDuMi 1.02, a matlab toolbox for optimization over symmetric cones. Optim Methods Softw 11(1-4):625-653 · Zbl 0973.90526
[32] Todd M (2001) Semidefinite optimization. Acta Numer 10:515-560 · Zbl 1105.65334
[33] Waki H, Kim S, Kojima M, Muramatsu M (2006) Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J Optim 17(1):218-242 · Zbl 1109.65058
[34] Waki H, Kim S, Kojima M, Muramatsu M, Sugimoto H (2008) Algorithm 883: SparsePOP—a sparse semidefinite programming relaxation of polynomial optimization problems. ACM Trans Math Softw 35(2):15
[35] Yang B, Anstreicher K, Purer S (2018) Quadratic programs with hollows. Math Program 170:541-553 · Zbl 1401.90147
[36] Zuluaga L, Vera J, Peña J (2006) LMI approximations for cones of positive semidefinite forms. SIAM J Optim 16:1076-1091 · Zbl 1131.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.