Abstract
Given a polynomial function \(f :{\mathbb {R}}^n \rightarrow {\mathbb {R}}\) and an unbounded closed semi-algebraic set \(S \subset {\mathbb {R}}^n,\) we show that the conditions listed below are characterized exactly in terms of the so-called tangency variety of the restriction of f on S:
-
f is bounded from below on S;
-
f attains its infimum on S;
-
The sublevel sets \(\{x \in S \ | \ f(x) \le \lambda \}\) for \(\lambda \in {\mathbb {R}}\) are compact;
-
f is coercive on S.
Besides, we also provide some stability criteria for boundedness and coercivity of f on S.
Similar content being viewed by others
Notes
The computations are performed with the software Maple, using the command “puiseux” of the package “algcurves” for the rational Puiseux expansions.
References
Ahmadi, A.A., Zhang, J.: On the complexity of testing attainment of the optimal value in nonlinear optimization. Math. Program. Ser. A 184, 221–241 (2020)
Bajbar, T., Behrends, S.: How fast do coercive polynomials grow? Instituts für Numerische und Angewandte Mathematik, Georg-August-Universität Göttingen, Tech. rep. (2017)
Bajbar, T., Stein, O.: Coercive polynomials and their Newton polytopes. SIAM J. Optim. 25(3), 1542–1570 (2015)
Bajbar, T., Stein, O.: Coercive polynomials: stability, order of growth, and Newton polytopes. Optimization 68(1), 99–124 (2019)
Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry, vol. 36. Springer, Berlin (1998)
Bolte, J., Hochart, A., Pauwels, E.: Qualification conditions in semi-algebraic programming. SIAM J. Optim. 28(3), 2131–2151 (2018)
Demmel, J., Nie, J., Powers, V.: Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals. J. Pure Appl. Algebra 209(1), 189–200 (2007)
Grandjean, V.: On the limit set at infinity of a gradient trajectory of a semialgebraic function. J. Differ. Equ. 233(1), 22–41 (2007)
Hà, H.V., Phạm, T.S.: Global optimization of polynomials using the truncated tangency variety and sums of squares. SIAM J. Optim. 19(2), 941–951 (2008)
Hà, H.V., Phạm, T.S.: On the Łojasiewicz exponent at infinity of real polynomials. Ann. Polon. Math. 94(3), 197–208 (2008)
Hà, H.V., Phạm, T.S.: Solving polynomial optimization problems via the truncated tangency variety and sums of squares. J. Pure Appl. Algebra 213, 2167–2176 (2009)
Hà, H.V., Phạm, T.S.: Representation of positive polynomials and optimization on noncompact semialgebraic sets. SIAM J. Optim. 20, 3082–3103 (2010)
Hà, H.V., Phạm, T.S.: Genericity in Polynomial Optimization, vol. 3. Ser. Optim. Appl. World Scientific, Singapore (2017)
Hardt, R.M.: Semi-algebraic local-triviality in semi-algebraic mappings. Amer. J. Math. 102(2), 291–302 (1980)
Jeyakumar, V., Lasserre, J.B., Li, G.: On polynomial optimization over non-compact semi-algebraic sets. J. Optim. Theory Appl. 163, 707–718 (2014)
John, F.: Extremum problems with inequalities as side constraints. In: Studies and Essays, Courant Anniversary Volume (New York, 1948), Friedrichs, K. O., Neugebauer, O. E., Stoker, J. J. (eds.) Wiley (interscience), pp. 187–204
Karush, W.: Minima of functions of several variables with inequalities as side constraints. Master’s thesis, Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois (1939)
Kim, D.S., Phạm, T.S., Tuyen, N.V.: On the existence of Pareto solutions for polynomial vector optimization problems. Math. Program. Ser. A 177(1–2), 321–341 (2019)
Kuhn, H. W., Tucker, A. W.: Nonlinear programming. In: Proceedings of 2nd Berkeley Symposium (Berkeley, 1951), Neyman, J. (ed.) University of California Press, pp. 481–492
Kurdyka, K., Mostowski, T., Parusiński, A.: Proof of the gradient conjecture of R. Thom. Ann. of Math. (2) 152(3), 763–792 (2000)
Lasserre, J.B.: Moments. Positive Polynomials and their Applications. Imperial College Press, London (2010)
Lasserre, J.B.: An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge University Press, Cambridge, UK (2015)
Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry, Putinar, M., Sullivant, S. (eds.) vol. IMA Math. Appl. 149. Springer, New York, pp. 157–270 (2009)
Loi, T.L., Zaharia, A.: Bifurcation sets of functions definable in o-minimal structures. Illinois J. Math. 43(3), 449–457 (1998)
Mangasarian, O.L., Fromovitz, S.: The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17, 37–47 (1967)
Marshall, M.: Positive Polynomials and Sums of Squares, vol. 146 of Math. Surveys and Monographs. American Mathematical Society, Providence, RI (2008)
Motzkin, T.: The arithmetic-geometric inequalities. In Inequalities (Academic Press, 1967), Shisha, O. Ed. pp. 205–224
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)
Phạm, T.S.: Local minimizers of semi-algebraic functions from the viewpoint of tangencies. SIAM J. Optim. 30(3), 1777–1794 (2020)
Shor, N.Z.: Class of global minimum bounds of polynomial functions. Cybernetics 23(6), 731–734 (1987)
Spingarn, J.E., Rockafellar, R.T.: The generic nature of optimality conditions in nonlinear programming. Math. Oper. Res. 4, 425–430 (1979)
van den Dries, L., Miller, C.: Geometric categories and o-minimal structures. Duke Math. J. 84, 497–540 (1996)
Acknowledgements
The author would like to thank Jérôme Bolte for the useful discussions. He is also grateful to the anonymous referees for their careful reading with constructive comments and suggestions on the paper. The paper was partially written while the author had been visiting at the Vietnam Institute for Advanced Study in Mathematics (VIASM) from January 1 to 31 March, 2019. He would like to thank the Institute for hospitality and support.
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to Professor Gue Myung Lee on the occasion of his 70th birthday.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The author is supported by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grand number 101.04-2019.302 and by International Centre for Research and Postgraduate Training in Mathematics (ICRTM) under grant number ICRTM01_2022.01.
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Phạm, TS. Tangencies and polynomial optimization. Math. Program. 199, 1239–1272 (2023). https://doi.org/10.1007/s10107-022-01869-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-022-01869-6
Keywords
- Boundedness
- Coercivity
- Compactness
- Critical points
- Existence of minimizers
- Polynomial
- Semi-Algebraic
- Stability
- Sub-levels
- Tangencies