Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-08T21:33:27.352Z Has data issue: false hasContentIssue false

Optimization of Polynomial Functions

Published online by Cambridge University Press:  20 November 2018

M. Marshall*
Affiliation:
Algebra and Logic Research Unit University of Saskatchewan Saskatoon, Saskatchewan S7N 5E6
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper develops a refinement of Lasserre's algorithm for optimizing a polynomial on a basic closed semialgebraic set via semidefinite programming and addresses an open question concerning the duality gap. It is shown that, under certain natural stability assumptions, the problem of optimization on a basic closed set reduces to the compact case.

Keywords

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 2003

References

[1] Berg, C., Christensen, J. P. R. and Jenson, C. U., A remark on the multidimensional moment problem. Math. Ann. 243 (1979), 163169.Google Scholar
[2] Haviland, E. K., On the momentum problem for distribution functions in more than one dimension. Amer. J. Math. 57 (1935), 562572.Google Scholar
[3] Haviland, E. K., On the momentum problem for distribution functions in more than one dimension II. Amer. J. Math. 58 (1936), 164168.Google Scholar
[4] Jacobi, T., A representation theorem for certain partially ordered commutative rings. Math. Z. 23(2001).Google Scholar
[5] Jacobi, T. and Prestel, A., Distinguished representations of strictly positive polynomials. J. Reine Angew.Math. 532 (2001), 223235.Google Scholar
[6] Kuhlmann, S. and Marshall, M., Positivity, sums of squares and the multidimensional moment problem. Trans. Amer.Math. Soc. 354 (2002), 42854301.Google Scholar
[7] Lasserre, J. B., Optimization globale et théorie des moments. C. R. Acad. Sci. Paris Sér. I Math. 331 (2000), 929934.Google Scholar
[8] Lasserre, J. B., Global optimization with polynomials and the problem of moments. SIAM J. Optim. (3) 11(2000/01), 796817 (electronic).Google Scholar
[9] Marshall, M., Approximating positive polynomials using sums of squares. to appear.Google Scholar
[10] Parrilo, P. A., Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology, May, 2000.Google Scholar
[11] Parrilo, P. A. and Sturmfels, B., Minimizing polynomial functions. DIMACS Series in Discrete Math. Theor. Comput. Sci., to appear.Google Scholar
[12] Powers, V. and Scheiderer, C., The moment problem for non-compact semialgebraic sets. Adv. in Geom. 1 (2001), 7188.Google Scholar
[13] Putinar, M., Positive polynomials on compact semialgebraic sets. Indiana Univ.Math. J. (3) 43 (1993), 969984.Google Scholar
[14] Schmüdgen, K., The K-moment problem for compact semialgebraic sets. Math. Ann. 289 (1991), 203206.Google Scholar
[15] Schmüdgen, K., On the moment problem of closed semi-algebraic sets. J. Reine Angew.Math. 558 (2003), 225234.Google Scholar
[16] Shor, N. Z., A class of global minimum bounds of polynomial functions. Cybernetics (6) 23 (1987), 731734.Google Scholar
[17] Shor, N. Z. and Stetsyuk, P. I., The use of a modification of the r-algorithm for finding the global minimum of polynomial functions. Cybernet. Systems Anal. 33 (1997), 482497.Google Scholar
[18] Wolkowicz, H., Saigal, R. and Vandenberghe, L. (eds), Handbook of Semidefinite programming. Kluwer, 2000.Google Scholar