# American Institute of Mathematical Sciences

2007, 3(2): 293-304. doi: 10.3934/jimo.2007.3.293

## Solutions and optimality criteria to box constrained nonconvex minimization problems

 1 Department of Mathematics & Grado, Department of Industrial and System Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA, 24061, United States

Received  August 2006 Revised  January 2007 Published  April 2007

This paper presents a canonical duality theory for solving nonconvex polynomial programming problems subjected to box constraints. It is proved that under certain conditions, the constrained nonconvex problems can be converted to the so-called canonical (perfect) dual problems, which can be solved by deterministic methods. Both global and local extrema of the primal problems can be identified by a triality theory proposed by the author. Applications to nonconvex integer programming and Boolean least squares problems are discussed. Examples are illustrated. A conjecture on NP-hard problems is proposed.
Citation: David Yang Gao. Solutions and optimality criteria to box constrained nonconvex minimization problems. Journal of Industrial & Management Optimization, 2007, 3 (2) : 293-304. doi: 10.3934/jimo.2007.3.293
 [1] David Yang Gao. Sufficient conditions and perfect duality in nonconvex minimization with inequality constraints. Journal of Industrial & Management Optimization, 2005, 1 (1) : 53-63. doi: 10.3934/jimo.2005.1.53 [2] Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 [3] Mila Nikolova. Analytical bounds on the minimizers of (nonconvex) regularized least-squares. Inverse Problems & Imaging, 2008, 2 (1) : 133-149. doi: 10.3934/ipi.2008.2.133 [4] Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67 [5] M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407 [6] Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 [7] Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213 [8] Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020 [9] Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial & Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415 [10] Xinmin Yang. On symmetric and self duality in vector optimization problem. Journal of Industrial & Management Optimization, 2011, 7 (3) : 523-529. doi: 10.3934/jimo.2011.7.523 [11] Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1-12. doi: 10.3934/jimo.2017070 [12] H. D. Scolnik, N. E. Echebest, M. T. Guardarucci. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 175-191. doi: 10.3934/jimo.2009.5.175 [13] Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 [14] Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial & Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497 [15] Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057 [16] Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779 [17] Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881 [18] Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871 [19] Fengqiu Liu, Xiaoping Xue. Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels. Journal of Industrial & Management Optimization, 2016, 12 (1) : 285-301. doi: 10.3934/jimo.2016.12.285 [20] Xiuhong Chen, Zhihua Li. On optimality conditions and duality for non-differentiable interval-valued programming problems with the generalized $(F,\rho)$-convexity. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1-18. doi: 10.3934/jimo.2017081

2016 Impact Factor: 0.994