×

Global optimality conditions for cubic minimization problems with cubic constraints. (English) Zbl 1329.90115

Summary: In this paper, we present global optimality conditions for cubic minimization involving cubic constraints and box or bivalent constraints, where the cubic objective function and cubic constraints contain no cross terms. By utilizing quadratic underestimators, we first derive sufficient global optimality conditions for a global minimizer of cubic minimization problems with cubic inequality and box constraints. Then we establish them for cubic minimization with cubic inequality and bivalent constraints. Finally, we establish sufficient and necessary global optimality condition for cubic minimization with cubic equality and binary constraints.

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming

Software:

GloptiPoly; SeDuMi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akrotirianakis IG, Floudas CA (2004) Computational experience with a new class of convex underestimators: box constrained NLP problems. J Glob Optim 29:249-264 · Zbl 1133.90420 · doi:10.1023/B:JOGO.0000044768.75992.10
[2] Akrotirianakis IG, Floudas CA (2004) A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J Glob Optim 30:367-390 · Zbl 1082.90090 · doi:10.1007/s10898-004-6455-4
[3] Beck A, Teboulle M (2000) Global optimality conditions for quadratic optimization problems with binary constraints. SIAM J Optim 11:179-188 · Zbl 0990.90089 · doi:10.1137/S1052623498336930
[4] Canfield RA (2004) Multipoint cubic surrogate function for sequential approximate optimization. Struct Multidiscipl Optim 27:326-336 · doi:10.1007/s00158-004-0391-2
[5] Chen W, Zhang L (2010) Global optimality conditions for quadratic 0-1 optimization problems. J Glob Optim 46:191-206 · Zbl 1209.90292 · doi:10.1007/s10898-009-9416-0
[6] Chesi G (2010) LMI techniques for optimization over polynomials in control: a survey. IEEE Trans Automat Control 55(11):2500-2510 · Zbl 1368.93496 · doi:10.1109/TAC.2010.2046926
[7] Dahl G (2000) A note on diagonally dominant matrices. Linear Algebra Appl 317:217-224 · Zbl 0970.15017 · doi:10.1016/S0024-3795(00)00178-6
[8] Dür M, Horst R, Locatelli M (1998) Necessary and sufficient global optimality conditions for convex maximization revisited. J Math Anal Appl 217:637-649 · Zbl 0909.90223 · doi:10.1006/jmaa.1997.5745
[9] Floudas CA, Visweswaran V (1995) Handbook of global optimization. Kluwer, The Netherlands
[10] Henrion D, Lasserre JB (2003) GloptiPoly: global optimization over polynomials with matlab and seDuMi. ACM Trans Math Softw 29(2):165-194 · Zbl 1070.65549 · doi:10.1145/779359.779363
[11] Hiriart-Urruty JB (2001) Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints. J Glob Optim 21:445-455 · Zbl 1172.90501 · doi:10.1023/A:1012752110010
[12] Horst R, Tuy H (1996) Global optimization: deterministic approaches, 3rd edn. Springer, Berlin · Zbl 0867.90105 · doi:10.1007/978-3-662-03199-5
[13] Jeyakumar V, Rubinov AM, Wu ZY (2006) Sufficient global optimality conditions for non-convex quadratic minimization problems with box constraints. J Glob Optim 36:471-481 · Zbl 1131.90060 · doi:10.1007/s10898-006-9022-3
[14] Jeyakumar V, Rubinov AM, Wu ZY (2007) Non-convex quadratic minimization problems with quadratic constraints: global optimalityconditions. Math Program Ser A 110:521-541 · Zbl 1206.90178 · doi:10.1007/s10107-006-0012-5
[15] Jeyakumar V, Li G, Srisatkunarajah S (2014) Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations. J Glob Optim 58(1):31-50 · Zbl 1319.90052 · doi:10.1007/s10898-013-0058-x
[16] Jeyakumar V, Huy NQ (2008) Global minimization of difference of quadratic and convex functions over box or binary constraints. Optim Lett 2:223-238 · Zbl 1161.90465 · doi:10.1007/s11590-007-0053-6
[17] Jeyakumar V, Srisatkunarajah S (2009) New sufficiency for global optimality and duality of mathematical programming problems via underestimators. J Optim Theory Appl 140:239-247 · Zbl 1191.90067 · doi:10.1007/s10957-008-9438-7
[18] Jeyakumar V, Srisatkunarajah S (2009) Lagrange multiplier necessary conditions for global optimality for non-convex minimization over a quadratic constraint via S-lemma. Optim Lett 3:23-33 · Zbl 1154.90574 · doi:10.1007/s11590-008-0088-3
[19] Jeyakumar V, Wu ZY (2007) Conditions for global optimality of quadratic minimization problems with LMI and bound constraints. Asia Pac J Oper Res 24(2):149-160 · Zbl 1118.41018 · doi:10.1142/S021759590700119X
[20] Li GL (2012) Global quadratic minimization over bivalent constraints: necessary and sufficient global optimality condition. J Optim Theory Appl 152:710-726 · Zbl 1262.90121 · doi:10.1007/s10957-011-9930-3
[21] Lin CS, Chang PR, Luh JYS (1983) Formulation and optimization of cubic polynomial joint trajectories for industrial robots. IEEE Trans Autom Control AC 28(12):1066-1074 · Zbl 0525.93035 · doi:10.1109/TAC.1983.1103181
[22] Mangasarian OL (1994) Nonlinear programming. Classics in applied mathematics. SIAM, Philadelphia
[23] Mangasarian OL, Rosen JB, Thompson ME et al (2006) Nonconvex piecewise-quadratic underestimation for global optimization. J Glob Optim 34:475-488 · Zbl 1099.90044 · doi:10.1007/s10898-005-3845-1
[24] Marcia RF, Mitchell JC, Rosen JB (2005) Iterative convex quadratic approximation for global optimization in protein docking. Comput Optim Appl 32:285-297 · Zbl 1125.90396 · doi:10.1007/s10589-005-4799-4
[25] Marcia RF, Mitchell JC, Wright SJ (2007) Global optimization in protein docking using clustering, underestimation and semidefinite programming. Optim Method Softw 22(5):803-811 · Zbl 1169.90422 · doi:10.1080/00207170701203756
[26] Mathews JH, Fink KK (2004) Numerical methods using matlab (4th Edition). Prentice-Hall Inc, New Jersey
[27] Murdukhovich BS (2006) Variational analysis and generalized differentiation, I: basic theory. Springer, Berlin
[28] Nesterov Y (2008) Accelerating the cubic regularization of Newtons method on convex problems. Math Program 112(1):159-181 · Zbl 1167.90013 · doi:10.1007/s10107-006-0089-x
[29] Nie J, Demmel J, Sturmfels B (2006) Minimizing polynomials via sum of squares over the gradient ideal. Math Program Ser A 106(3):587-606 · Zbl 1134.90032 · doi:10.1007/s10107-005-0672-6
[30] Parrilo PA (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. Thesis, California Institute of Technology Pasadena, California · Zbl 1070.65549
[31] Paschalidis ICh, Shen Y, Vakili P, Vajda S (2007) SDU: A Semidefinite programming-based underestimation method for stochastic global optimization in protein docking. IEEE Trans Automat Control 52(4):664-676 · Zbl 1366.90233 · doi:10.1109/TAC.2007.894518
[32] Pinar MC (2004) Sufficient global optimality conditions for bivalent quadratic optimization. J Optim Theory Appl 122:433-440 · Zbl 1091.90059 · doi:10.1023/B:JOTA.0000042530.24671.80
[33] Rubinov AM (2000) Abstract convexity and global optimization. Kluwer Academic, Dordrecht · Zbl 0985.90074 · doi:10.1007/978-1-4757-3200-9
[34] Tuy H (1998) Convex analysis and global optimization. Kluwer Academic Publishers, Dordrecht · Zbl 0904.90156 · doi:10.1007/978-1-4757-2809-5
[35] Wang Y, Liang Z (2010) Global optimality conditions for cubic minimization problem with box or binary constraints. J Glob Optim 47:583-595 · Zbl 1228.90088 · doi:10.1007/s10898-009-9480-5
[36] Wu ZY, Jeyakumar V, Rubinov AM (2007) Sufficient conditions for global optimality of bivalent nonconvex quadratic programs with inequality constraints. J Optim Theory Appl 133:123-130 · Zbl 1144.90458 · doi:10.1007/s10957-007-9177-1
[37] Wu ZY, Rubinov AM (2010) Global optimality conditions for some classes of optimization problems. J Optim Theory Appl 145:164-185 · Zbl 1196.90099 · doi:10.1007/s10957-009-9616-2
[38] Zhang XM, Wang YJ, Ma WM (2012) Global sufficient optimality conditions for a special cubic minimization problem. Math Prob Eng, Article ID 871741, 1-16 · Zbl 1264.90163
[39] Zhou XG, Cao BY (2012) New global optimality conditions for cubic minimization subject to box or bivalent constraints. Pac J Optim 8:631-647 · Zbl 1284.90061
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.