Minimizing Rational Functions: : A Hierarchy of Approximations via Pushforward Measures
Abstract
This paper is concerned with minimizing a sum of rational functions over a compact set of high dimension. Our approach relies on the second Lasserre hierarchy (also known as the upper bounds hierarchy) formulated on the pushforward measure in order to work in a space of smaller dimension. We show that in the general case, the minimum can be approximated as closely as desired from above with a hierarchy of semidefinite programs problems or, in the particular case of a single fraction, with a hierarchy of generalized eigenvalue problems. We numerically illustrate the potential of using the pushforward measure rather than the standard upper bounds hierarchy. In our opinion, this potential should be a strong incentive to investigate a related challenging problem interesting on its own, namely, integrating an arbitrary power of a given polynomial on a simple set (e.g., unit box or unit sphere) with respect to the Lebesgue or Haar measure.
References
[1]
MOSEK ApS, The MOSEK Optimization Toolbox, Version 8.1, http://docs.mosek.com/8.1/toolbox/index.html, 2017.
[2]
V. Baldoni, N. Berline, J. de Loera, M. Köppe, and M. Vergne, How to integrate a polynomial over a simplex, Math. Comp., 80 (2010), pp. 297--325.
[3]
D. Bigoni, Y. Marzouk, C. Prieur, and O. Zahm, Nonlinear Dimension Reduction for Surrogate Modeling Using Gradient Information, preprint, arXiv:2102.10351, 2021.
[4]
F. Bugarin, D. Henrion, and J. B. Lasserre, Minimizing the sum of many rational functions, Math. Program. Comput., 8 (2016), pp. 83--111.
[5]
E. De Klerk, R. Hess, and M. Laurent, Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization, SIAM J. Optim., 27 (2017), pp. 347--367.
[6]
E. de Klerk, D. Kuhn, and K. Postek, Distributionally robust optimization with polynomial densities: Theory, models and algorithms, Math. Program., (2019), pp. 1--32.
[7]
E. de Klerk and M. Laurent, A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis, in World Women in Mathematics 2018, Springer, New York, 2019, pp. 17--56.
[8]
E. de Klerk and M. Laurent, Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere, Math. Program., (2020), pp. 1--21.
[9]
E. de Klerk and M. Laurent, Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube, Math. Oper. Res., 45 (2020), pp. 86--98.
[10]
E. de Klerk, M. Laurent, and Z. Sun, Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization, Math. Program. A, (2016), pp. 1--30.
[11]
E. de Klerk and F. Vallentin, On the Turing model complexity of interior point methods for semidefinite programming, SIAM J. Optim., 26 (2016), pp. 1944--1961.
[12]
I. Dunning, J. Huchette, and M. Lubin, JuMP: A modeling language for mathematical optimization, SIAM Rev., 59 (2017), pp. 295--320.
[13]
A. Grundmann and H. M. Moller, Invariant integration formulas for the n-simplex by combinatorial methods, SIAM J. Numer. Anal., 15 (1978), pp. 282--290.
[14]
D. Henrion, M. Korda, and J. B. Lasserre, The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs, Vol. 4, World Scientific, Singapore, 2020.
[15]
J. B. Lasserre, Convex optimization and parsimony of $L_p$-balls representation, SIAM J. Optim., 26 (2016), pp. 247--273.
[16]
D. Jibetean and E. de Klerk, Global optimization of rational functions: A semidefinite programming approach, Math. Program., 106 (2006), pp. 93--109.
[17]
P. Lairez, M. Mezzarobba, and M. Safey El Din, Computing the volume of compact semi-algebraic sets, in Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, 2019, pp. 259--266.
[18]
J. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796--817.
[19]
J. Lasserre, Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17 (2006), pp. 822--843.
[20]
J. Lasserre, Moments, Positive Polynomials and their Applications, Vol. 1, Imperial College Press, London, 2010.
[21]
J. Lasserre, Bounding the support of a measure from its marginal moments, Proc. Amer. Math. Soc., 139 (2011), pp. 3375--3382.
[22]
J. Lasserre, Volume of sublevel sets of homogeneous polynomials, SIAM J. Appl. Algebra Geom., 3 (2019), pp. 372--389.
[23]
J. Lasserre, Connecting optimization with spectral analysis of tri-diagonal matrices, Math. Program., (2020), pp. 1--15.
[24]
J. B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim., 21 (2011), pp. 864--885.
[25]
M. Laurent and L. Slot, Near-Optimal Analysis of Lasserre's Univariate Measure-based Bounds for Multivariate Polynomial Optimization, preprint, arXiv:2001.11289, 2020.
[26]
V. Magron, Interval enclosures of upper bounds of roundoff errors using semidefinite programming, ACM Trans. Math. Softw., 44 (2018), pp. 1--18.
[27]
V. Magron, P.-L. Garoche, D. Henrion, and X. Thirioux, Semidefinite approximations of reachable sets for discrete-time polynomial systems, SIAM J. Control Optim., 57 (2019), pp. 2799--2820.
[28]
V. Magron, D. Henrion, and J. Lasserre, Semidefinite approximations of projections and polynomial images of semialgebraic sets, SIAM J. Optim., 25 (2015), pp. 2143--2164.
[29]
Y. Nesterov and A. Nemirovski, Interior Point Polynomial Methods in Convex Programming: Theory and Applications, SIAM, Philadelphia, 1994.
[30]
G. Primolevo, O. Simeone, and U. Spagnolini, Towards a joint optimization and beamforming for mim downlink, IEEE Ninth International Symposium on Spread Spectrum Techniques and Applications, 2006, pp. 493--497.
[31]
L. Slot and M. Laurent, Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets, Math. Program., (2020), pp. 1--41.
[32]
L. N. Trefethen, Spectral Methods in MATLAB, SIAM, Philadelphia, 2000.
[33]
L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev., 38 (1994), pp. 49--95.
[34]
H. Waki, S. Kim, M. Kojima, and M. Muramatsu, Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., 17 (2006), pp. 218--242.
[35]
J. Wang, V. Magron, and J.-B. Lasserre, Chordal-TSSOS: A moment-SOS hierarchy that exploits term sparsity with chordal extension, SIAM J. Optim., 31 (2021), pp. 114--141.
[36]
J. Wang, V. Magron, and J.-B. Lasserre, TSSOS: A moment-SOS hierarchy that exploits term sparsity, SIAM J. Optim., 31 (2021), pp. 30--58.
[37]
J. Wang, V. Magron, J. B. Lasserre, and N. H. A. Mai, CS-TSSOS: Correlative and Term Sparsity for Large-Scale Polynomial Optimization, preprint, arXiv:2005.02828, 2020.
[38]
M. Wu, L. Zhang, Z. Wang, D. Christiani, and X. Lin, Sparse linear discriminant analysis for simultaneous testing for the significance of a gene set/pathway and gene selection, Bioinformatics, 25 (2009), pp. 1145--1151.
Index Terms
- Minimizing Rational Functions: A Hierarchy of Approximations via Pushforward Measures
Index terms have been assigned to the content through auto-classification.
Recommendations
Quadratic programs with hollows
Let $$\mathcal {F}$$F be a quadratically constrained, possibly nonconvex, bounded set, and let $$\mathcal {E}_1, \ldots , \mathcal {E}_l$$E1,ý,El denote ellipsoids contained in $$\mathcal {F}$$F with non-intersecting interiors. We prove that minimizing ...
Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
We consider the problem of minimizing a continuous function f over a compact set $${\mathbf {K}}$$K. We analyze a hierarchy of upper bounds proposed by Lasserre (SIAM J Optim 21(3):864---885, 2011), obtained by searching for an optimal probability ...
Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre, and a related hierarchy by de Klerk, Hess, and Laurent. For polynomial optimization over the hypercube, we show a refined convergence ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
DOI:10.1137/sjope8.31.3
Issue’s Table of Contents© 2021, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 2021
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Dec 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in