Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Signomial and polynomial optimization via relative entropy and partial dualization

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

A Publisher Correction to this article was published on 09 February 2021

This article has been updated

Abstract

We describe a generalization of the Sums-of-AM/GM-Exponential (SAGE) methodology for relative entropy relaxations of constrained signomial and polynomial optimization problems. Our approach leverages the fact that SAGE certificates conveniently and transparently blend with convex duality, in a way which enables partial dualization of certain structured constraints. This more general approach retains key properties of ordinary SAGE relaxations (e.g. sparsity preservation), and inspires a projective method of solution recovery which respects partial dualization. We illustrate the utility of our methodology with a range of examples from the global optimization literature, along with a publicly available software package.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Change history

Notes

  1. See also August, Koeppl, and Craciun [23].

  2. See [16, Section 5] for discussion on this topic and related results by Wang [24].

  3. A FORTRAN implementation is accessible through SciPy’s optimize submodule. The arguments we pass to that implementation are RHOBEG=1, \({{\texttt {RHOEND}}}=10^{-7}\), and MAXFUN\(=10^5\).

  4. The objective and constraint functions are multiplied by \(10^4\) for numerical reasons; see equation environment (6.15) on page 106 of [35] for the original problem statement.

  5. Corollary 2 holds regardless of whether or not this is the case.

  6. The problem is referred to as “dense” in the Sparse-BSOS article because it does not satisfy the running-intersection property that Sparse-BSOS is built upon.

  7. Because f is homogeneous, \({\varvec{x}}^\intercal {\varvec{x}} = 1\) may be relaxed to \({\varvec{x}}^\intercal {\varvec{x}} \le 1\) without loss of generality

References

  1. Rountree, D.H., Rigler, A.K.: A penalty treatment of equality constraints in generalized geometric programming. J. Optim. Theory Appl. 38(2), 169–178 (1982). issn: 1573-2878

  2. Kirschen, P.G., et al.: Application of signomial programming to aircraft design. J. Aircr. 55(3), 965–987 (2018)

    Article  Google Scholar 

  3. Jabr, R.A.: Inductor design using signomial programming. COM-PEL Int. J. Comput. Math. Electr. Electron. Eng. 26(2), 461–475 (2007)

  4. Chiang, M.: Nonconvex optimization for communication networks. In: Honor of Gilbert Strang, Advances in Applied Mathematics and Global Optimization, Springer US, Boston, pp. 137–196. ISBN: 978-0-387-75714-8 (2009)

  5. Shen, P., Zhang, K.: Global optimization of signomial geometric programming using linear relaxation. Appl. Math. Comput. 150(1), 99–114 (2004)

    MathSciNet  MATH  Google Scholar 

  6. Wang, Y., Liang, Z.: A deterministic global optimization algorithm for generalized geometric programming. Appl. Math. Comput. 168(1), 722–737 (2005). issn: 0096-3003

  7. Shen, P., Jiao, H.: A new rectangle branch-and-pruning approach for generalized geometric programming. Appl. Math. Comput. 183(2), 1027–1038 (2006)

    MathSciNet  MATH  Google Scholar 

  8. Shao-Jian, Q., Zhang, K.-C., Ji, Y.: A new global optimization algorithm for signomial geometric programming via Lagrangian relaxation. Appl. Math. Comput. 184(2), 886–894 (2007)

    MathSciNet  MATH  Google Scholar 

  9. Shen, P., Ma, Y., Chen, Y.: A robust algorithm for generalized geometric programming. J. Global Optim. 41(4), 593–612 (2008). issn: 1573-2916

  10. Hou, X., Shen, P., Chen, Y.: A global optimization algorithm for signomial geometric programming problem. Abstract Appl. Anal. 2014, 1–12 (2014)

    Article  MathSciNet  Google Scholar 

  11. Gongxian, X.: Global optimization of signomial geometric programming problems. Eur. J. Oper. Res. 233(3), 500–510 (2014)

    Article  MathSciNet  Google Scholar 

  12. Shor, N.Z.: Class of global minimum bounds of polynomial functions. Cybernetics 23(6), 731–734 (1987)

    Article  Google Scholar 

  13. Parrilo, P.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology (2000)

  14. Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (2001)

    Article  MathSciNet  Google Scholar 

  15. Chandrasekaran, V., Shah, P.: Relative entropy relaxations for signomial optimization. SIAM J. Optim. 26(2), 1147–1173 (2016)

    Article  MathSciNet  Google Scholar 

  16. Murray, R., Chandrasekaran, V., Wierman, A.: Newton polytopes and relative entropy optimization (2018). arXiv:1810.01614

  17. Iliman, S., de Wolff, T.: Amoebas, nonnegative polynomials and sums of squares supported on circuits. Res. Math. Sci. 3, 9 (2016)

    Article  MathSciNet  Google Scholar 

  18. Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117–129 (1987). issn: 1436-4646

  19. MOSEK ApS. MOSEK 9.0.70(beta) (2019)

  20. Reznick, B.: Forms derived from the arithmetic-geometric inequality. Math. Ann. 283(3), 431–464 (1989)

    Article  MathSciNet  Google Scholar 

  21. Pébay, P.P., Rojas, J.M., Thompson, D.C.: Optimization and NP R-completeness of certain fewnomials. In: Proceedings of the 2009 Conference on Symbolic Numeric Computation, ACM Press (2009)

  22. Pantea, C., Koeppl, H., Craciun, G.: Global injectivity and multiple equilibria in uni- and bi-molecular reaction networks. Discrete Contin. Dyn. Syst. Ser. B 17(6), 2153–2170 (2012)

    Article  MathSciNet  Google Scholar 

  23. August, E., Craciun, G., Koeppl, H.: Finding invariant sets for biological systems using monomial domination. In: 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), IEEE (2012)

  24. Wang, J.: Nonnegative polynomials and circuit polynomials (2018). arXiv:1804.09455

  25. Katthän, L., Naumann, H., Theobald, T.: A unified framework of SAGE and SONC polynomials and its duality theory (2019). arXiv:1903.08966

  26. Seidler, H., de Wolff, T.: An experimental comparison of SONC and SOS certificates for unconstrained optimization (2018). arXiv:1808.08431

  27. Seidler, H., de Wolff, T.: POEM: effective methods in polynomial optimization, version 0.2.1.0(a) (2019). http://www.iaa.tu-bs.de/AppliedAlgebra/POEM/index.html

  28. Henrion, D., Lasserre, J.-B., Löfberg, J.: GloptiPoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24(4–5), 761–779 (2009)

    Article  MathSciNet  Google Scholar 

  29. Papachristodoulou, A., et al.: SOSTOOLS version 3.00 sum of squares optimization toolbox for MATLAB (2013). arXiv:1310.4716

  30. Powers, V., Reznick, B.: Polynomials that are positive on an interval. Trans. Am. Math. Soc. 352(10), 4677–4692 (2000)

    Article  MathSciNet  Google Scholar 

  31. Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, pp. 157–270. Springer, New York (2009). isbn: 978-0-387-09686-5

  32. Borwein, J., Lewis, A.: Convex Analysis and Nonlinear Optimization. Springer, New York (2006)

    Book  Google Scholar 

  33. Lasserre, J.B.: An Introduction to Polynomial and Semi-algebraic OptimizationCambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (2015)

    Book  Google Scholar 

  34. Powell, M.J.D.: A direct search optimization method that models the objective and constraint functions by linear interpolation. In: Advances in Optimization and Numerical Analysis, Springer, Dordrecht, pp. 51–67. ISBN: 978-94-015-8330-5 (1994)

  35. Yan, J.: Signomial programs with equality constraints: numerical solution and applications. PhD thesis, University of British Columbia (1976)

  36. Agrawal, A., Diamond, S., Boyd, S.: Disciplined geometric programming. Optim. Lett. 13(5), 961–976 (2019)

    Article  MathSciNet  Google Scholar 

  37. Bard, G.V.: Some basic facts about linear algebra over GF(2). In: Algebraic Cryptanalysis, Springer, Berlin, pp. 81–88 (2009)

  38. Verschelde, J.: Algorithm 795: PHCpack—a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. 25(2), 251–276 (1999). issn: 0098-3500

  39. Ray, S., Nataraj, P.S.V.: An efficient algorithm for range computation of polynomials using the Bernstein form. J. Global Optim. 45(3), 403–426 (2008)

    Article  MathSciNet  Google Scholar 

  40. Lasserre, J.B., Toh, K.-C., Yang, S.: A bounded degree SOS hierarchy for polynomial optimization. EURO J. Comput. Optim. 5(1), 87–117 (2017). issn: 2192- 4414

  41. Weisser, T., Lasserre, J.B., Toh, K.-C.: Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity. Math. Program. Comput. 10(1), 1–32 (2018). issn: 1867-2957

  42. Murray, R.: Sageopt 0.5.3 (2020). https://doi.org/10.5281/ZENODO.4017991

  43. Domahidi, A., Chu, E., Boyd, S.: ECOS: an SOCP solver for embedded systems. In: European Control Conference (ECC), pp. 3071–3076 (2013)

  44. Serrano, S.A.: Algorithms for unsymmetric cone optimization and an implementation for problems with the exponential cone. PhD Thesis, Stanford University, Palo Alto, CA (2015)

  45. Burnell, E., Damen, N.B., Hoburg, W.: GPkit: a human-centered approach to convex optimization in engineering design. In: Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems (2020)

  46. Rijckaert, M.J., Martens, X.M.: Comparison of generalized geometric programming algorithms. J. Optim. Theory Appl. 26(2), 205–242 (1978). issn: 1573-2878

  47. Surjanovic, S., Bingham, D.: Virtual library of simulation experiments: test functions and datasets. Retrieved April 18 from http://www.sfu.ca/~ssurjano (2019)

  48. Ahmadi, A.A., Majumdar, A.: DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization. SIAM J. Appl. Algebra Geom. 3(2), 193–230 (2019)

    Article  MathSciNet  Google Scholar 

  49. Vandenberghe, L.: The CVXOPT linear and quadratic cone program solvers (2010). http://www.seas.ucla.edu/~vandenbe/publications/coneprog.pdf

  50. Forsgård, J., de Wolff, T.: The algebraic boundary of the sonc cone (2019). arXiv:1905.04776

Download references

Acknowledgements

The authors thank Fangzhou Xiao and two anonymous referees for helpful feedback. R.M. was supported in part by an NSF Graduate Research Fellowship, NSF grants CCF-1350590 and CCF-1637598, and AFOSR grant FA9550-16-1-0210. V.C. was supported in part by NSF grants CCF-1350590 and CCF-1637598, AFOSR grant FA9550-16-1-0210, and a Sloan Research Fellowship. A.W. was supported in part by NSF grant CCF-1637598.

Author information

Authors and Affiliations

  1. California Institute of Technology, Pasadena, CA, 91125, USA

    Riley Murray, Venkat Chandrasekaran & Adam Wierman

Authors
  1. Riley Murray
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Venkat Chandrasekaran
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Adam Wierman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Riley Murray.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Appendix

figure c

As in the signomial case, Algorithm 3 always returns a vector \({\varvec{x}} \in X\). Assuming that \({\varvec{z}}\) from Line 7 are already computed as part of representing \({\varvec{{\hat{v}}}}\), the complexity of this algorithm is dominated by Line 12. The runtime of Line 12 is in turn negligible relative to solving a SAGE relaxation to obtain vectors \({\varvec{v}}\) and \({\varvec{{\hat{v}}}}\). Infeasibility errors encountered in Line 12 should be handled by jumping to Line 15.

figure d

Let us describe the ways in which Algorithm 4 differs from the discussion in Sect. 4.2.2. First- there are changes to the sets U and W. The set U now drops any rows \({\varvec{\alpha }}_i\) from \({{\varvec{\alpha }}}\) where \({\varvec{\alpha }}_i\) is even; it is easy to verify that this does not affect the set of solutions to the appropriate linear system. The set W changes by only considering j where at least one \(\alpha _{ij} \equiv 1 \mod 2\). This change is valid because if \(\alpha _{ij}\) is even for all i, then the sign of variable \(x_j\) is irrelevant to the underlying optimization problem, and we make take \(x_j \ge 0\) without loss of generality.

Next we speak to the “hueristic” sign recovery. We partly mean to leave this as open-ended, however for completeness we describe the algorithm used in sageopt. The goal is to find a vector \({\varvec{s}}\) in \(\{+1,-1\}\) so that the signs of \({\varvec{s}}^{{{\varvec{\alpha }}}} \doteq ({\varvec{s}}^{{\varvec{\alpha }}_1},\ldots ,{\varvec{s}}^{{\varvec{\alpha }}_m})\) match the signs of \({\varvec{v}}\) to the greatest extent possible. However, we consider how having \({\varvec{s}}^{{\varvec{\alpha }}_i}\) match the sign of \(v_i\) may not be very important if \(v_i\) is very small. Therefore we use a merit function \(M({\varvec{s}}) = {\varvec{v}}^\intercal {\varvec{s}}^{{{\varvec{\alpha }}}}\) to evaluate the quality of candidate signs \({\varvec{s}}\). We apply a greedy algorithm to maximize the merit function \(M({\varvec{s}})\) as follows: initialize \({\varvec{s}} = {\varvec{1}}\), and a set of undecided coordinates \(C = \{1,\ldots ,n\}\). As long as the set C is nonempty, find an index \(i^\star \in C\) so that changing \(s_{i^\star } = 1\) to \(s_{i^\star } = -1\) maximizes improvement in the merit function. If the improvement is positive, then perform the update \(s_{i^\star } \leftarrow -1\). Regardless of whether or not the improvement is positive, remove \(i^\star \) from C. Once C is empty, return \({\varvec{s}}\).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Murray, R., Chandrasekaran, V. & Wierman, A. Signomial and polynomial optimization via relative entropy and partial dualization. Math. Prog. Comp. 13, 257–295 (2021). https://doi.org/10.1007/s12532-020-00193-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-020-00193-4

Keywords

Search

Navigation