×

Global optimality conditions and optimization methods for constrained polynomial programming problems. (English) Zbl 1410.90206

Summary: The general constrained polynomial programming problem (GPP) is considered in this paper. Problem (GPP) has a broad range of applications and is proved to be NP-hard. Necessary global optimality conditions for problem (GPP) are established. Then, a new local optimization method for this problem is proposed by exploiting these necessary global optimality conditions. A global optimization method is proposed for this problem by combining this local optimization method together with an auxiliary function. Some numerical examples are also given to illustrate that these approaches are very efficient.

MSC:

90C30 Nonlinear programming
90C26 Nonconvex programming, global optimization
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Floudas, C. A.; Pardalos, P. M.A., Collection of test problems for constrained global optimization algorithms, (Goos, G.; Hartmanis, J., (1990), Springer-Verlag New York) · Zbl 0718.90054
[2] He, S.; Li, Z.; Zhang, S., Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Math. Program, 125, 2, 353-383, (2010) · Zbl 1206.90124
[3] Nie, J.; Wang, L., Regularization methods for SDP relaxations in large-scale polynomial optimization, SIAM J. Optim., 2, 408-428, (2012) · Zbl 1250.65080
[4] D. Han, Global optimization with polynomials, 2004. http://hdl.handle.net/1721.1/3883. Accessed 20 December 2013.
[5] J. Nie, Regularization methods for sum of squares relaxations in large scale polynomial optimization, No. arXiv:0909.3551 2009.
[6] Luo, Z. Q.; Zhang, S., A semidefenite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints, SIAM J. Optim., 20, 4, 1716-1736, (2010) · Zbl 1201.90147
[7] Kim, S.; Kojima, M.; Waki, H., Generalized Lagrangian duals and sums of squares relaxations of sparse polynomial optimization problems, SIAM J. Optim., 15, 3, 697-719, (2005) · Zbl 1114.90085
[8] JIANG, B.; LI, Z.; ZHANG, S., Approximation methods for complex polynomial optimization, Technical report, Department of Industrial and Systems Engineering, (2012), University of Minnesota
[9] Ling, C.; Zhang, X.; Qi, L., Semidefinite relaxation approximation for multivariate bi-quadratic optimization with quadratic constraints, Numer. Linear Algebr. Appl., 19, 1, 113-131, (2012) · Zbl 1274.65170
[10] Hiriart-Urruty, J. B.; Lemarechal, C., Testing necessary and sufficient conditions for global optimality in the problem of maximizing a convex quadratic funcion over a convex polyhedron, Preliminary Report, (1990), University of Paul Sabatier Toulouse
[11] Hiriart-Urruty, J. B., Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints, J. Glob. Optim., 21, 4, 443-453, (2001) · Zbl 1172.90501
[12] Peng, J.; Yuan, Y., Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J. Optim., 7, 3, 579-594, (1997) · Zbl 0891.90150
[13] Jeyakumar, V.; Rubinow, A. M.; Wu, Z. Y., Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions, Math. Program., 110, 3, 521-541, (2007) · Zbl 1206.90178
[14] Schichl, H.; Neumaier, A., Transposition theorems and qualification-free optimality conditions, SIAM J. Optim., 17, 4, 1035-1055, (2006) · Zbl 1136.90043
[15] Lasserre, J. B., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817, (2001) · Zbl 1010.90061
[16] Jeyakumar, V.; Li, G. Y., Necessary global optimality conditions for nonlinear programming problems with polynomial constraints, Math. Program., 126, 2, 393-399, (2011) · Zbl 1206.90126
[17] Visweswaran, V.; Floudas, C. A., Unconstrained and constrained global optimization of polynomial functions in one variable, J. Glob. Optim., 2, 1, 73-99, (1992) · Zbl 0781.90084
[18] Sherali, H. D.; Tuncbilek, C. H., New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems£, Oper. Res. Lett., 21, 1, 1-9, (1997) · Zbl 0885.90105
[19] 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)
[20] Fortune, S., An iterated eigenvalue algorithm for approximating roots of univariate polynomials, J. Symb. Comput., 33, 5, 627-646, (2002) · Zbl 1004.65060
[21] Bini, D. A.; Gemignani, L.; Pan, V. Y., Inverse power and durand-kerner iterations for univariate polynomial root-finding, Comput. Math. Appl., 47, 2, 447-459, (2004) · Zbl 1054.65046
[22] Bazaraa, M. S.; Sherali, H. D.; Shetty, C. M., Nonlinear programming: theory and algorithms, (2006), John Wiley and Sons, Inc. Hoboken, New Jersey · Zbl 1140.90040
[23] Wu, Z.; Lee, H. W.J.; Zhang, L. S.; M. Yang, X., A novel filled function method and quasi-filled function method for global optimization, Comput. Optim. Appl., 34, 2, 249-272, (2006) · Zbl 1121.90105
[24] Laguna, M.; Marti, R., Experimental testing of advanced scatter search designs for global optimization of multimodal functions, J. Glob. Optim., 33, 2, 235-255, (2005) · Zbl 1093.90092
[25] Henrion, D.; Lasserre, J. B., Gloptipoly: global optimization over polynomials with Matlab and sedumi, ACM Trans. Math. Softw. (TOMS)., 29, 2, 165-194, (2003) · Zbl 1070.65549
[26] Henrion, D.; Lasserre, J. B.; Lofberg, J., Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24, 4-5, 761-779, (2009) · Zbl 1178.90277
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.