zbMATH — the first resource for mathematics

Partitioning procedure for polynomial optimization. (English) Zbl 1226.90077
Summary: We consider the problem of finding the minimum of a real-valued multivariate polynomial function constrained in a compact set defined by polynomial inequalities and equalities. This problem, called polynomial optimization problem (POP), is generally nonconvex and has been of growing interest to many researchers in recent years. Our goal is to tackle POPs using decomposition, based on a partitioning procedure. The problem manipulations are in line with the pattern used in the generalized Benders decomposition, namely projection followed by relaxation. Stengle’s and Putinar’s Positivstellensätze are employed to derive the feasibility and optimality constraints, respectively. We test the performance of the proposed partitioning procedure on a collection of benchmark problems and present the numerical results.

90C26 Nonconvex programming, global optimization
PDF BibTeX Cite
Full Text: DOI
[1] GLOBAL Library. http://www.gamsworld.org/global/globallib/globalstat.htm (2008)
[2] Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization. MPS/SIAM Series on Optimization, SIAM, Philadelphia, PA (2001) · Zbl 0986.90032
[3] Benders J.F.: Partitioning procedures for solving mixed-variables programming problems. Comput. Manag. Sci. 2(1), 3–19 (2005) reprinted from Numer. Math. 4(1962), pp. 238–252 · Zbl 1115.90361
[4] Boyd S., Vandenberghe L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[5] Cox D., Little J., O’Shea D.: Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer, New York (1992)
[6] Floudas, C.A.: Deterministic global optimization, Nonconvex Optimization and its Applications, vol 37. Kluwer, Dordrecht, Theory, methods and applications (2000)
[7] Floudas C.A., Pardalos P.M.: A Collection of Test Problems for Constrained Global Optimization Algorithms, Lecture Notes in Computer Science, vol 455. Springer, Berlin (1990) · Zbl 0718.90054
[8] Floudas C.A., Visweswaran V.: A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: I. Theory Comput. Chem. Eng. 14(12), 1397–1417 (1990)
[9] Geoffrion A.M.: Elements of large-scale mathematical programming. I. Concepts. Manag. Sci. 16, 652–675 (1970) · Zbl 0209.22801
[10] Geoffrion A.M.: Generalized benders decomposition. J. Optim. Theory Appl. 10, 237–260 (1972) · Zbl 0229.90024
[11] Henrion D., Lasserre J.B.: GloptiPoly: global optimization over polynomials with Matlab and SeDuMi. ACM Trans. Math. Softw. 29(2), 165–194 (2003) · Zbl 1070.65549
[12] Hogan W.W.: Point-to-set maps in mathematical programming. SIAM Rev. 15, 591–603 (1973) · Zbl 0256.90042
[13] Kleniati, P.M., Parpas, P., Rustem, B.: Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems. J. Optim. Theory Appl. doi: 10.1007/s10957-009-9624-2 (2009) · Zbl 1197.90332
[14] Lasserre J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (2000/2001) · Zbl 1010.90061
[15] Lasserre J.B.: Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17(3), 822–843 (2006) · Zbl 1119.90036
[16] Laurent M.: Sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds) Emerging applications of algebraic geometry, IMA Vol. in Math. and its Appl., vol 149., pp. 157–270. Springer, New York (2009) · Zbl 1163.13021
[17] Meyer R.: The validity of a family of optimization methods. SIAM J. Control 8, 41–54 (1970) · Zbl 0194.20501
[18] Nie J., Schweighofer M.: On the complexity of Putinar’s Positivstellensatz. J. Complex. 23(1), 135–150 (2007) · Zbl 1143.13028
[19] Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology (2000)
[20] Parrilo P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2, Ser. B), 293–320 (2003) · Zbl 1043.14018
[21] Prestel A., Delzell C.N.: Positive Polynomials. Springer Monographs in Mathematics. Springer, Berlin (2001) · Zbl 0987.13016
[22] Putinar M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3), 969–984 (1993) · Zbl 0796.12002
[23] Schmüdgen K.: The K-moment problem for compact semi-algebraic sets. Math. Ann. 289(2), 203–206 (1991) · Zbl 0744.44008
[24] Schweighofer M.: Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 15(3), 805–825 (2005) · Zbl 1114.90098
[25] Stengle G.: A nullstellensatz and a positivstellensatz in semialgebraic geometry. Math. Ann. 207, 87–97 (1974) · Zbl 0263.14001
[26] Sturm J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12(1–4), 625–653 (1999) · Zbl 0973.90526
[27] Tind J., Wolsey L.A.: An elementary survey of general duality theory in mathematical programming. Math. Program. 21(3), 241–261 (1981) · Zbl 0467.90061
[28] Tuy H.: Convex Analysis and Global Optimization, Nonconvex Optimization and its Applications, vol 22. Kluwer, Dordrecht (1998) · Zbl 0904.90156
[29] Visweswaran V., Floudas C.A.: A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: II. Application of theory and test problems. Comput. Chem. Eng. 14(12), 1419–1434 (1990)
[30] Visweswaran V., Floudas C.A.: Unconstrained and constrained global optimization of polynomial functions in one variable. J. Global Optim. 2(1), 73–99 (1992) · Zbl 0781.90084
[31] Waki H., Kim S., Kojima M., Muramatsu M.: Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1), 218–242 (2006) · Zbl 1109.65058
[32] Wolsey L.A.: A resource decomposition algorithm for general mathematical programs. Math. Program. Stud. 14, 244–257 (1981) · Zbl 0449.90085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.