Unified global optimality conditions for smooth minimization problems with mixed variables

Jeyakumar, Vaithilingam; Srisatkunarajah, Sivakolundu; Huy, Nguyen Quang

RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 361-370.

In this paper we establish necessary as well as sufficient conditions for a given feasible point to be a global minimizer of smooth minimization problems with mixed variables. These problems, for instance, cover box constrained smooth minimization problems and bivalent optimization problems. In particular, our results provide necessary global optimality conditions for difference convex minimization problems, whereas our sufficient conditions give easily verifiable conditions for global optimality of various classes of nonconvex minimization problems, including the class of difference of convex and quadratic minimization problems. We discuss numerical examples to illustrate the optimality conditions

Classification : 90C30, 90C45
Mots clés : nonconvex optimization, global optimization, optimality conditions, discrete constraints, box constraints, difference of convex functions, quadratic minimization

[1] A. Beck and M. Teboulle, Global optimality conditions for quadratic optimization problems with binary constraints. SIAM J. Optim. 11 (2000) 179-188. | MR | Zbl

[2] E. Cela, The quadratic assignment problem: theory and algorithms. Kluwer Academic Publishers (1998). | MR | Zbl

[3] P. De Angelis, P. Pardalos and G. Toraldo, Quadratic programming with box constraints, in Developments in global optimization, edited by Bomze I. et al. Kluwer Acad. Publ., Dordrecht (1997) 73-93. | MR | Zbl

[4] C.A. Floudas and P.M. Pardalos, Optimization in computational chemistry and molecular biology: Local and global approaches. Kluwer Academic Publishers (2000). | MR | Zbl

[5] N.Q. Huy, V. Jeyakumar and G.M. Lee, Sufficient global optimality conditions for multi-extremal smooth minimization problems with bounds and linear matrix inequality constraints, The ANZIAM J. 47 (2006) 439-450. | MR | Zbl

[6] N.Q. Huy, V. Jeyakumar and G.M. Lee, Globally minimizing smooth functions with simple constraints: Necessary, and sufficient optimality conditions (submitted).

[7] V. Jeyakumar and N.Q. Huy, Global minimization of difference of quadratic and convex functions over box or binary constraints, To appear in Optimization Letters, DOI: 10.1007/s11590-007-0053-6 (2008). | MR

[8] V. Jeyakumar, A.M. Rubinov and Z.Y. Wu, Sufficient global optimality conditions for non-convex quadratic minimization problems with box constraints. J. Global Optim. 36 (2006) 461-468. | MR | Zbl

[9] V. Jeyakumar, A.M. Rubinov and Z.Y. Wu, Nonconvex quadratic minimization with quadratic constraints: Global optimality conditions. Math. Program. 110 (2007) 521-541. | MR

[10] M. Junger, A. Martin, G. Reinelt and R. Weismantel, 0/1 optimization and a decomposition approach for the placement of electronic circuits. Math. Program. 63 (1994) 257-279. | MR | Zbl

[11] R.F. Marcia, J.C. Mitchell and J.B. Rosen, Iterative convex quadratic approximation for global optimization in protein docking, Comput. Optim. Appl. 32 (2005) 285-297. | MR | Zbl

[12] P.M. Pardalos and G.P. Rodgers, Computational aspects of quadratic zero-one programming, Computing 45 (1990) 131-144. | MR | Zbl

[13] M.C. Pinar, Sufficient global optimality conditions for bivalent quadratic optimization, J. Optim. Theor. Appl. 122 (2004) 433-440. | MR | Zbl

[14] M.C. Pinar and M. Teboulle, On semidefinite bounds for maximization of a non-convex quadratic objective over $l_1$ unit ball. RAIRO Oper. Res. 40 (2006) 253-265. | Numdam | MR

[15] Z. Wu, V. Jeyakumar, A.M. Rubinov, Sufficient conditions for global optimality of bivalent nonconvex quadratic programs with inequality constraints. J. Optim. Theor. Appl. 133 (2007) 123-130. | MR | Zbl