An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming.

*(English)*Zbl 1411.12003The authors use the theory of sums of non-negative circuit polynomials (‘sonc-theory’) developed in [S. Iliman and T. de Wolff, SIAM J. Optim. 26, No. 2, 1128–1146 (2016; Zbl 1380.12001)] to adress the problem of constrained polynomial optimization. This time they put ideas from M. Ghasemi and M. Marshall [“Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming”, Preprint, {\mathbf x: g_1({\mathbf x})\geq 0,..., g_s({\mathbf x})\geq 0\}\) be a basic semi-algebraic set. Let \(f_K^*:=\inf_{\mathbf x\in K} f(\mathbf x).\) The problem is to find good lower bounds for \(f_K^*.\)

The present setup is the following: Consider for \(\boldsymbol{\mu} \in [0,\infty[^s\) the linear form

\(G(\boldsymbol{\mu})({\mathbf x})= f-\sum_{i=1}^s \mu_i g_i= -\sum_{i=0}^s\mu_i g_i\) (with \(\mu_0=1, g_0=-f\)) and rewrite it as an ST-polynomial whenever a given \(\boldsymbol{\mu} \in [0,\infty[^s\) makes this possible: \[ G(\boldsymbol{\mu})({\mathbf x})= \sum_{j=0}^r G(\boldsymbol{\mu})_{\alpha(j)} {\mathbf x}^{\alpha(j)} + \sum_{\beta \in \Delta} G(\boldsymbol{\mu})_{\beta} {\mathbf x}^{\beta}. \] Sonc-theory allows, given \(\boldsymbol{\mu},\) to find via the fast method of geometric programming a maximal real value \(G(\boldsymbol{\mu})_{\text{sonc}}\) such that the polynomial \(G(\boldsymbol{\mu})({\mathbf x})-G(\boldsymbol{\mu})_{\text{sonc}}{\mathbf x}^{\alpha(0)}\) is sum of nonnegative circuit polynomials and hence nonnegative. The most important case for finding a lower bound for \(f_K^*\) is the case \(\alpha(0)=0\in\mathbb Z_{\geq 0}^n.\) (If \( G(\boldsymbol{\mu})({\mathbf x})\) cannot be written as ST-polynomial put \(G(\boldsymbol{\mu})_{\text{sonc}}=-\infty.\) )

Let \(s(f,{\mathbf g})=\sup\{G(\boldsymbol{\mu})_{\text{sonc}}: \boldsymbol{\mu} \in \mathbb{R}_{\geq 0}^s \}.\) Note that if \(\alpha(0)=0,\) then for every \(\mu\) we have \(f_K^*\geq G(\boldsymbol{\mu})_{\text{sonc}},\) and hence \(s(f,{\mathbf g})\) can be expected to be a particularly good lower bound for \(f_K^*;\) but unfortunately the fact that the values \(G(\boldsymbol{\mu})_{\text{sonc}}\) can be found fast by geometric programming does not mean \(s(f,{\mathbf g})\) can be found fast.

In the last section of Iliman de Wolff [loc. cit.] first inroads to to find good lower bounds for \(s(f,{\mathbf g})\) are made. The authors developed there a program which under specific conditions is signomial (i.e. geometric but with signs) and under much more stringent conditions is geometric. In the present paper they modify their previous program (which here carries the number (2.6)) into a program (3.2) which allows to weaken the assumptions for geometricity. They also present a further program (3.3) which is signomial again and which works almost without additional assumptions. The programs are small modifications of each other but the context and notation for any of them are far too technical to be presented here. As far as the reviewer knows signomial programs are unfortunately much slower than geometric ones. The authors also indicate conditions under which the programs (3.2) and (3.3) allow to get the exact value \(s(f,{\mathbf g})\).

In section 4 examples of constrained optimization via geometric programming and comparisons to Lasserre’s relaxations are given. Let \(f_{sos}^{(d)}\) be the \(d\)-th Lassere relaxation of the constrained problem. It yields better and better lower bounds for \(f_K^*\) as \(d\) increases (provided it converges, which is guaranteed e.g. if \(K\) is compact).

The authors report the following results:

1. An optimization of the famous Motzkin polynomial over a constrained but unbounded domain is tried. Lasserre’s 3rd relaxation yields \(-\infty\) while sonc-theory and \(f_{\text{sos}}^{(7)}\) yield the correct value \(f_K^*\).

2. Minimization of \(f=1+x^4y^2+xy\) over the variety defined by \(\frac{1}{2}+x^2y^4-x^2y^6=0\) is tried. The first few Lasserre relaxations yield \(-\infty\) while the eighth relaxation yields the correct value \(0.4474\). The program (3.2) is geometric in this case and yields the correct value via the Matlab CVX solver immediately. If one modifies \(f\) by multiplying the exponents by a factor 10, one gets with GloptiPoly (i.e. Lasserre’s relaxation) the correct result only after 18 minutes while the GP/SONC approach is insensitive to the degree augmentation and yields the result again after a second.

3. A 5-term 3-variable degree 4 polynomial \(f\) subjected to a condition \(g=0\) with another such polynomial \(g\) is minimized. Gloptipoly gives the answer after 10 hours in the 20-th relaxation without providing a certificate of optimality, while the GP/SONC approach yields the answer in a second.

4. A homogeneous Motzkin form on the unit sphere is minimized and on grounds of sonc theory one can say immediately that the minimum must be 0; although the problem is infeasible for program (3.2).

In section 5 the authors initiate a generalization of their theory to non-ST-polynomials. Consider unconstrained optimization. Assume \(f\) is a non-ST-polynomial. Then by ‘triangulating’ the set of exponents \(\{\alpha(0),\ldots,\alpha(d)\}\) pertaining to monomial squares in \(f\), it is still possible to write \(f\) as a sum \(f=\sum_{i=1}^k h_i\) where the \(h_i\) are \(ST\)-polynomials. For suitable triangulations, certain quantities \(m_i^*\) that can be extracted from applying program (2.6) to the \(h_i\) and can then be used to obtain a lower bound for \(f^*=\inf f({\mathbf x}).\) A first theoretical result is presented with proof. An example with constrained optimization is also given.

The authors promise a follow-up paper on the topic.

The present setup is the following: Consider for \(\boldsymbol{\mu} \in [0,\infty[^s\) the linear form

\(G(\boldsymbol{\mu})({\mathbf x})= f-\sum_{i=1}^s \mu_i g_i= -\sum_{i=0}^s\mu_i g_i\) (with \(\mu_0=1, g_0=-f\)) and rewrite it as an ST-polynomial whenever a given \(\boldsymbol{\mu} \in [0,\infty[^s\) makes this possible: \[ G(\boldsymbol{\mu})({\mathbf x})= \sum_{j=0}^r G(\boldsymbol{\mu})_{\alpha(j)} {\mathbf x}^{\alpha(j)} + \sum_{\beta \in \Delta} G(\boldsymbol{\mu})_{\beta} {\mathbf x}^{\beta}. \] Sonc-theory allows, given \(\boldsymbol{\mu},\) to find via the fast method of geometric programming a maximal real value \(G(\boldsymbol{\mu})_{\text{sonc}}\) such that the polynomial \(G(\boldsymbol{\mu})({\mathbf x})-G(\boldsymbol{\mu})_{\text{sonc}}{\mathbf x}^{\alpha(0)}\) is sum of nonnegative circuit polynomials and hence nonnegative. The most important case for finding a lower bound for \(f_K^*\) is the case \(\alpha(0)=0\in\mathbb Z_{\geq 0}^n.\) (If \( G(\boldsymbol{\mu})({\mathbf x})\) cannot be written as ST-polynomial put \(G(\boldsymbol{\mu})_{\text{sonc}}=-\infty.\) )

Let \(s(f,{\mathbf g})=\sup\{G(\boldsymbol{\mu})_{\text{sonc}}: \boldsymbol{\mu} \in \mathbb{R}_{\geq 0}^s \}.\) Note that if \(\alpha(0)=0,\) then for every \(\mu\) we have \(f_K^*\geq G(\boldsymbol{\mu})_{\text{sonc}},\) and hence \(s(f,{\mathbf g})\) can be expected to be a particularly good lower bound for \(f_K^*;\) but unfortunately the fact that the values \(G(\boldsymbol{\mu})_{\text{sonc}}\) can be found fast by geometric programming does not mean \(s(f,{\mathbf g})\) can be found fast.

In the last section of Iliman de Wolff [loc. cit.] first inroads to to find good lower bounds for \(s(f,{\mathbf g})\) are made. The authors developed there a program which under specific conditions is signomial (i.e. geometric but with signs) and under much more stringent conditions is geometric. In the present paper they modify their previous program (which here carries the number (2.6)) into a program (3.2) which allows to weaken the assumptions for geometricity. They also present a further program (3.3) which is signomial again and which works almost without additional assumptions. The programs are small modifications of each other but the context and notation for any of them are far too technical to be presented here. As far as the reviewer knows signomial programs are unfortunately much slower than geometric ones. The authors also indicate conditions under which the programs (3.2) and (3.3) allow to get the exact value \(s(f,{\mathbf g})\).

In section 4 examples of constrained optimization via geometric programming and comparisons to Lasserre’s relaxations are given. Let \(f_{sos}^{(d)}\) be the \(d\)-th Lassere relaxation of the constrained problem. It yields better and better lower bounds for \(f_K^*\) as \(d\) increases (provided it converges, which is guaranteed e.g. if \(K\) is compact).

The authors report the following results:

1. An optimization of the famous Motzkin polynomial over a constrained but unbounded domain is tried. Lasserre’s 3rd relaxation yields \(-\infty\) while sonc-theory and \(f_{\text{sos}}^{(7)}\) yield the correct value \(f_K^*\).

2. Minimization of \(f=1+x^4y^2+xy\) over the variety defined by \(\frac{1}{2}+x^2y^4-x^2y^6=0\) is tried. The first few Lasserre relaxations yield \(-\infty\) while the eighth relaxation yields the correct value \(0.4474\). The program (3.2) is geometric in this case and yields the correct value via the Matlab CVX solver immediately. If one modifies \(f\) by multiplying the exponents by a factor 10, one gets with GloptiPoly (i.e. Lasserre’s relaxation) the correct result only after 18 minutes while the GP/SONC approach is insensitive to the degree augmentation and yields the result again after a second.

3. A 5-term 3-variable degree 4 polynomial \(f\) subjected to a condition \(g=0\) with another such polynomial \(g\) is minimized. Gloptipoly gives the answer after 10 hours in the 20-th relaxation without providing a certificate of optimality, while the GP/SONC approach yields the answer in a second.

4. A homogeneous Motzkin form on the unit sphere is minimized and on grounds of sonc theory one can say immediately that the minimum must be 0; although the problem is infeasible for program (3.2).

In section 5 the authors initiate a generalization of their theory to non-ST-polynomials. Consider unconstrained optimization. Assume \(f\) is a non-ST-polynomial. Then by ‘triangulating’ the set of exponents \(\{\alpha(0),\ldots,\alpha(d)\}\) pertaining to monomial squares in \(f\), it is still possible to write \(f\) as a sum \(f=\sum_{i=1}^k h_i\) where the \(h_i\) are \(ST\)-polynomials. For suitable triangulations, certain quantities \(m_i^*\) that can be extracted from applying program (2.6) to the \(h_i\) and can then be used to obtain a lower bound for \(f^*=\inf f({\mathbf x}).\) A first theoretical result is presented with proof. An example with constrained optimization is also given.

The authors promise a follow-up paper on the topic.

Reviewer: Alexander Kovačec (Coimbra)

##### MSC:

12D15 | Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) |

90C22 | Semidefinite programming |

14P05 | Real algebraic sets |

52B20 | Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) |

##### Keywords:

semidefinite programming; sum of squares; triangulation; geometric programming; nonnegative polynomial; sum of nonnegative circuit polynomials; certificate##### References:

[1] | Anai, H.; Yanami, H., Synrac: a Maple-package for solving real algebraic constraints, (Computational Science—ICCS 2003. Part I, Lecture Notes in Comput. Sci., vol. 2657, (2003), Springer Berlin), 828-837 · Zbl 1033.68960 |

[2] | Blekherman, G., There are significantly more nonnegative polynomials than sums of squares, Isr. J. Math., 153, 355-380, (2006) · Zbl 1139.14044 |

[3] | Blekherman, G., Nonnegative polynomials and sums of squares, J. Am. Math. Soc., 25, 3, 617-635, (2012) · Zbl 1258.14067 |

[4] | Blekherman, G.; Parrilo, P. A.; Thomas, R. R., Semidefinite optimization and convex algebraic geometry, MOS-SIAM Series on Optimization, vol. 13, (2013), SIAM and the Mathematical Optimization Society Philadelphia · Zbl 1260.90006 |

[5] | Boyd, S.; Grant, M., Graph implementations for nonsmooth convex programs, (Blondel, V.; Boyd, S.; Kimura, H., Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, (2008), Springer-Verlag Limited), 95-110 · Zbl 1205.90223 |

[6] | Boyd, S.; Vandenberghe, L., Convex optimization, (2004), Cambridge University Press Cambridge · Zbl 1058.90049 |

[7] | Boyd, S.; Grant, M.; Ye, Y., Disciplined convex programming, (Global Optimization, Nonconvex Optim. Appl., vol. 84, (2006), Springer New York), 155-210 · Zbl 1130.90382 |

[8] | Boyd, S.; Kim, S. J.; Vandenberghe, L.; Hassibi, A., A tutorial on geometric programming, Optim. Eng., 8, 1, 67-127, (2007) · Zbl 1178.90270 |

[9] | de Klerk, E.; Laurent, M., Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube, SIAM J. Optim., 20, 6, 3104-3120, (2010) · Zbl 1229.90279 |

[10] | de Wolff, T., Amoebas, nonnegative polynomials and sums of squares supported on circuits, Oberwolfach Rep., 23, 1308-1311, (2015) |

[11] | Duffin, R. J.; Peterson, E. L.; Zener, C., Geometric programming: theory and application, (1967), John Wiley & Sons, Inc. New York-London-Sydney · Zbl 0171.17601 |

[12] | Fidalgo, C.; Kovacec, A., Positive semidefinite diagonal minus tail forms are sums of squares, Math. Z., 269, 3-4, 629-645, (2011) · Zbl 1271.11045 |

[13] | Ghasemi, M.; Marshall, M., Lower bounds for polynomials using geometric programming, SIAM J. Optim., 22, 2, 460-473, (2012) · Zbl 1272.12004 |

[14] | Ghasemi, M.; Marshall, M., Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming, (2013), Preprint |

[15] | Ghasemi, M.; Lasserre, J. B.; Marshall, M., Lower bounds on the global minimum of a polynomial, Comput. Optim. Appl., 57, 2, 387-402, (2014) · Zbl 1304.90163 |

[16] | Henrion, D.; Lasserre, J. B.; Löfberg, J., Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24, 4-5, 761-779, (2009) · Zbl 1178.90277 |

[17] | Iliman, S.; de Wolff, T., Amoebas, nonnegative polynomials and sums of squares supported on circuits, Res. Math. Sci., 3, 3, 9, (2016) · Zbl 1415.11071 |

[18] | Iliman, S.; de Wolff, T., Lower bounds for polynomials with simplex Newton polytopes based on geometric programming, SIAM J. Optim., 26, 2, 1128-1146, (2016) · Zbl 1380.12001 |

[19] | Kaltofen, E. L.; Li, B.; Yang, Z.; Zhi, L., Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, J. Symb. Comput., 47, 1, 1-15, (2012) · Zbl 1229.90115 |

[20] | Lasserre, J. B., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817, (2000/01) · Zbl 1010.90061 |

[21] | Lasserre, J. B., Moments, positive polynomials and their applications, Imperial College Press Optimization Series, vol. 1, (2010), Imperial College Press London · Zbl 1211.90007 |

[22] | Laurent, M., Sums of squares, moment matrices and optimization over polynomials, (Emerging Applications of Algebraic Geometry, IMA Vol. Math. Appl., vol. 149, (2009), Springer New York), 157-270 · Zbl 1163.13021 |

[23] | Nesterov, Y.; Nemirovskii, A., Interior point polynomial algorithms in convex programming, Studies in Applied Mathematics, (1994), Society for Industrial and Applied Mathematics · Zbl 0824.90112 |

[24] | Nie, J., Certifying convergence of Lasserre’s hierarchy via flat truncation, Math. Program., Ser. A, 142, 1-2, 485-510, (2013) · Zbl 1305.65151 |

[25] | Nie, J., An exact Jacobian SDP relaxation for polynomial optimization, Math. Program., Ser. A, 137, 1-2, 225-255, (2013) · Zbl 1266.65094 |

[26] | Nie, J., Optimality conditions and finite convergence of Lasserre’s hierarchy, Math. Program., Ser. A, 146, 1-2, 97-121, (2014) · Zbl 1300.65041 |

[27] | Nie, J.; Demmel, J.; Sturmfels, B., Minimizing polynomials via sum of squares over the gradient ideal, Math. Program., Ser. A, 106, 3, 587-606, (2006) · Zbl 1134.90032 |

[28] | Oxley, J., Matroid theory, Oxford Graduate Texts in Mathematics, vol. 21, (2011), Oxford University Press Oxford · Zbl 1254.05002 |

[29] | Papachristodoulou, A.; Anderson, J.; Valmorbida, G.; Prajna, S.; Seiler, P.; Parrilo, P. A., SOSTOOLS: sum of squares optimization toolbox for MATLAB, (2013), and |

[30] | Parrilo, P. A.; Sturmfels, B., Minimizing polynomial functions, (Algorithmic and Quantitative Real Algebraic Geometry, Piscataway, NJ, 2001, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 60, (2003), Amer. Math. Soc. Providence, RI), 83-99 · Zbl 1099.13516 |

[31] | Peyrl, H.; Parrilo, P. A., Computing sum of squares decompositions with rational coefficients, Theor. Comput. Sci., 409, 2, 269-281, (2008) · Zbl 1156.65062 |

[32] | Reznick, B., Extremal PSD forms with few terms, Duke Math. J., 45, 2, 363-374, (1978) · Zbl 0395.10037 |

[33] | Reznick, B., Some concrete aspects of Hilbert’s 17th problem, (Real Algebraic Geometry and Ordered Structures, Baton Rouge, LA, 1996, Contemp. Math., vol. 253, (2000), Amer. Math. Soc. Providence, RI), 251-272 · Zbl 0972.11021 |

[34] | Schweighofer, M., Global optimization of polynomials using gradient tentacles and sums of squares, SIAM J. Optim., 17, 3, 920-942, (2006) · Zbl 1118.13026 |

[35] | Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M.; Sugimoto, H., Algorithm 883: sparsepop—a sparse semidefinite programming relaxation of polynomial optimization problems, ACM Trans. Math. Softw., 35, 2, (2009), Art. 15, 13 |

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.