American Institute of Mathematical Sciences

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

Solutions and optimality criteria to box constrained nonconvex minimization problems

David Yang Gao 1,

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.
Keywords: NP-hard problems., Global optimization; Duality; Nonconvex minimization; Box constraints; Integer programming; Boolean least squares problem.
Mathematics Subject Classification: 49N15, 49M37, 90C26, 90C2.
Citation: David Yang Gao. Solutions and optimality criteria to box constrained nonconvex minimization problems. Journal of Industrial and Management Optimization, 2007, 3 (2) : 293-304. doi: 10.3934/jimo.2007.3.293
[1]

Zhuoyi Xu, Yong Xia, Deren Han. On box-constrained total least squares problem. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 439-449. doi: 10.3934/naco.2020043
[2]

David Yang Gao. Sufficient conditions and perfect duality in nonconvex minimization with inequality constraints. Journal of Industrial and Management Optimization, 2005, 1 (1) : 53-63. doi: 10.3934/jimo.2005.1.53
[3]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[4]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[5]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67
[6]

Mila Nikolova. Analytical bounds on the minimizers of (nonconvex) regularized least-squares. Inverse Problems and Imaging, 2008, 2 (1) : 133-149. doi: 10.3934/ipi.2008.2.133
[7]

Philipp Hungerländer, Barbara Kaltenbacher, Franz Rendl. Regularization of inverse problems via box constrained minimization. Inverse Problems and Imaging, 2020, 14 (3) : 437-461. doi: 10.3934/ipi.2020021
[8]

Hassan Mohammad, Mohammed Yusuf Waziri, Sandra Augusta Santos. A brief survey of methods for solving nonlinear least-squares problems. Numerical Algebra, Control and Optimization, 2019, 9 (1) : 1-13. doi: 10.3934/naco.2019001
[9]

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 and Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[10]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[11]

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033
[12]

Jutamas Kerdkaew, Rabian Wangkeeree, Rattanaporn Wangkeeree. Global optimality conditions and duality theorems for robust optimal solutions of optimization problems with data uncertainty, using underestimators. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 93-107. doi: 10.3934/naco.2021053
[13]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213
[14]

Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020
[15]

Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial and Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415
[16]

Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 2 (2) : 107-126. doi: 10.3934/mfc.2019009
[17]

Xinmin Yang. On symmetric and self duality in vector optimization problem. Journal of Industrial and Management Optimization, 2011, 7 (3) : 523-529. doi: 10.3934/jimo.2011.7.523
[18]

Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070
[19]

K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026
[20]

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 and Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (228)
  • HTML views (0)
  • Cited by (52)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy