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

A Frank–Wolfe type theorem for nondegenerate polynomial programs

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper, we study the existence of optimal solutions to a constrained polynomial optimization problem. More precisely, let \(f_0\) and \(f_1, \ldots , f_p :{\mathbb {R}}^n \rightarrow {\mathbb {R}}\) be convenient polynomial functions, and let \(S := \{x \in {\mathbb {R}}^n \ : \ f_i(x) \le 0, i = 1, \ldots , p\} \ne \emptyset .\) Under the assumption that the map \((f_0, f_{1}, \ldots , f_{p}) :{\mathbb {R}}^n \rightarrow {\mathbb {R}}^{p + 1}\) is non-degenerate at infinity, we show that if \(f_0\) is bounded from below on \(S,\) then \(f_0\) attains its infimum on \(S.\)

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

Similar content being viewed by others

References

  1. Andronov, V.G., Belousov, E.G., Shironin, V.M.: On solvability of the problem of polynomial programming, Izvestija Akadem. Nauk SSSR, Tekhnicheskaja Kibernetika, no. 4, 194–197 (1982) (in Russian). Translation Appeared in News of the Academy of Science of USSR, Department of Technical Sciences, Technical. Cybernetics no. 4, 194–197 (1982)

  2. Auslender, A.: How to deal with the unbounded in optimization: theory and algorithms. Math. Program. Ser. B 79, 3–8 (1997)

    MathSciNet  MATH  Google Scholar 

  3. Bank, B., Mandel, R.: Parametric Integer Optimization, Mathematical Research, vol. 39, edn. Academie-Verlag, Berlin (1988)

  4. Belousov, E.G.: Introduction to Convex Analysis and Integer Programming. Moscow University Publ, Moscow (1977). (in Russian)

    MATH  Google Scholar 

  5. Belousov, E.G., Klatte, D.: A Frank–Wolfe type theorem for convex polynomial programs. Comput. Optim. Appl. 22(1), 37–48 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  6. Benedetti, R., Risler, J.: Real Algebraic and Semi-algebraic Sets. Hermann, Paris (1991)

    Google Scholar 

  7. Bertsekas, D.P., Tseng, P.: Set intersection theorems and existence of optimal solutions. Math. Program. Ser. A 110(2), 287–314 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bivia-Ausina, C.: Mixed Newton numbers and isolated complete intersection singularities. Proc. Lond. Math. Soc. 94(3), 749–771 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry, vol. 36. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  10. Bolte, J., Daniilidis, A., Lewis, A.S.: Generic optimality conditions for semialgebraic convex programs. Math. Oper. Res. 36(1), 55–70 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  11. Damon, J.: Topological invariants of \(\mu \)-constant deformations of complete intersection singularities. Q. J. Math. Oxf. Ser. 40(2), 139–159 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  12. Demmel, J., Nie, J.W., Powers, V.: Representations of positive polynomials on noncompact semi-algebraic sets via KKT ideals. J. Pure Appl. Algebra 209(1), 189–200 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  13. Dinh, S.T., Hà, H.V., Phạm, T.S.: A Frank-Wolfe type theorem and Holder-type global error bound for generic polynomial systems, preprint 2012, VIASM. Available online from http://viasm.edu.vn/wp-content/uploads/2012/11/Preprint_1227.pdf

  14. van den Dries, L., Miller, C.: Geometric categories and o-minimal structures. Duke Math. J. 84, 497–540 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  15. Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Q. 3, 95–110 (1956)

    Article  MathSciNet  Google Scholar 

  16. Gaffney, T.: Integral closure of modules and Whitney equisingularity. Invent. Math. 107, 301–322 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  17. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Publishers W.H. Freeman, San Francisco (1979)

    MATH  Google Scholar 

  18. Hà, H.V., Phạm, T.S.: Global optimization of polynomials using the truncated tangency variety and sums of squares. SIAM J. Optim. 19, 941–951 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  19. 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)

    Article  MathSciNet  MATH  Google Scholar 

  20. Hà, H.V., Phạm, T.S.: Representations of positive polynomials and optimization on noncompact semi-algebraic sets. SIAM J. Optim. 20, 3082–3103 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  21. Hà, H.V.: Global Hölderian error bound for non-degenerate polynomials. SIAM J. Optim. 23(2), 917–933 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  22. Jibetean, D., Laurent, M.: Semidefinite approximations for global unconstrained polynomial optimization. SIAM J. Optim. 16, 490–514 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  23. Khovanskii, A.G.: Newton polyhedra and toroidal varieties. Funct. Anal. Appl. 11, 289–296 (1978)

    Article  MATH  Google Scholar 

  24. Kouchnirenko, A.G.: Polyhedres de Newton et nombre de Milnor. Invent. Math. 32, 1–31 (1976)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  26. Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009)

    Book  Google Scholar 

  27. Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and its Applications, vol. 149, pp. 157–270. Springer, Berlin (2009)

    Chapter  Google Scholar 

  28. Luo, Z.-Q., Zhang, S.: On extensions of the Frank-Wolfe theorems. Comput. Optim. Appl. 13(1–3), 87–110 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  29. Marshall, M.: Positive Polynomials and Sums of Squares, Mathematical Surveys and Monographs, vol. 146. American Mathematical Society, Providence, RI (2008)

    Book  Google Scholar 

  30. Marshall, M.: Representations of non-negative polynomials, degree bounds and applications to optimization. Can. J. Math. 61(1), 205–221 (2009)

    Article  MATH  Google Scholar 

  31. Miller, C.: Exponentiation is hard to avoid. Proc. Am. Math. Soc. 122, 257–259 (1994)

    Article  MATH  Google Scholar 

  32. Milnor, J.: Singular Points of Complex Hypersurfaces, Annals of Mathematics Studies, vol. 61. Princeton University Press, Princeton (1968)

    Google Scholar 

  33. Némethi, A., Zaharia, A.: Milnor fibration at infinity. Indag. Math. 3, 323–335 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  34. 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)

    Article  MathSciNet  MATH  Google Scholar 

  35. Obuchowska, W.T.: On generalizations of the Frank-Wolfe theorem to convex and quasi-convex programmes. Comput. Optim. Appl. 33(2–3), 349–364 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  36. Oka, M.: Non-degenerate Complete Intersection Singularity. Actualités Mathématiques, Hermann, Paris (1997)

    MATH  Google Scholar 

  37. Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, Ph.D. thesis, California Institute of Technology, May 2000

  38. Parrilo, P.A., Sturmfels, B.: Minimizing polynomial functions. In: Algorithmic and Quantitative Real Algebraic Geometry (Piscataway, NJ, 2001). DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, vol. 60, pp. 83–99. American Mathematical Society, Providence, RI (2003)

  39. Parrilo, P.A.: Semidefinite Programming relaxations for semialgebraic problems. Math. Program. Ser. B 96(2), 293–320 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  40. Perold, A.F.: Generalization of the Frank–Wolfe Theorem. Math. Program. 18, 215–227 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  41. Rabier, P.J.: Ehresmann fibrations and Palais-Smale conditions for morphisms of Finsler manifolds. Ann. Math. 146, 647–691 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  42. Reznick, B.: Some concrete aspects of Hilbert’s 17th problem. Contemp. Math. 253, 251–272 (2000)

    Article  MathSciNet  Google Scholar 

  43. Shor, N.Z.: An approach to obtaining global extremums in polynomial mathematical programming problems. Kibernetika 5, 102–106 (1987)

    MathSciNet  Google Scholar 

  44. Schweighofer, M.: Global optimization of polynomials using gradient tentacles and sums of squares. SIAM J. Optim. 17(3), 920–942 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  45. Terlaky, T.: On \(l_p\) programming. Eur. J. Oper. Res. 22, 70–100 (1985)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to thank the referees, whose helpful comments and suggestions much improved the original manuscript. This research was performed while the authors had been visiting the Vietnam Institute for Advanced Study in Mathematics (VIASM). The authors would like to thank the Institute for hospitality and support.

Author information

Authors and Affiliations

  1. Institute of Mathematics, 18, Hoang Quoc Viet Road, Cau Giay District, 10307 , Hanoi, Vietnam

    Si Tiep Dinh & Huy Vui Ha

  2. Department of Mathematics, University of Dalat, 1 Phu Dong Thien Vuong, Dalat, Vietnam

    Tien Son Pham

Authors
  1. Si Tiep Dinh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Huy Vui Ha
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tien Son Pham
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tien Son Pham.

Additional information

Si Tiep Dinh and Huy Vui Ha: These authors were partially supported by Vietnam National Foundation for Science and Technology Development (NAFOSTED) Grant Numbers 101.01-2011.44.

Tien Son Pham: This author was partially supported by Vietnam National Foundation for Science and Technology Development (NAFOSTED) Grant Numbers 101.04-2013.07.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dinh, S.T., Ha, H.V. & Pham, T.S. A Frank–Wolfe type theorem for nondegenerate polynomial programs. Math. Program. 147, 519–538 (2014). https://doi.org/10.1007/s10107-013-0732-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-013-0732-2

Keywords

Mathematics Subject Classification (1991)

Search

Navigation