• Previous Article
    A unified model for state feedback of discrete event systems I: framework and maximal permissive state feedback
  • JIMO Home
  • This Issue
  • Next Article
    Semismooth reformulation and Newton's method for the security region problem of power systems
January  2008, 4(1): 125-142. doi: 10.3934/jimo.2008.4.125

Canonical dual approach to solving 0-1 quadratic programming problems

1. 

Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC, United States

2. 

Department of Mathematics, Virginia Tech, Blacksburgh, VA, United States

3. 

Department of Mathematics, National Cheng Kung University, Taiwan, ROC, Taiwan

4. 

Department of Mathematics, National Cheng Kung University, Tainan, Taiwan

Received  February 2007 Revised  November 2007 Published  January 2008

By using the canonical dual transformation developed recently, we derive a pair of canonical dual problems for 0-1 quadratic programming problems in both minimization and maximization form. Regardless convexity, when the canonical duals are solvable, no duality gap exists between the primal and corresponding dual problems. Both global and local optimality conditions are given. An algorithm is presented for finding global minimizers, even when the primal objective function is not convex. Examples are included to illustrate this new approach.
Citation: Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125
[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

Deepak Singh, Bilal Ahmad Dar, Do Sang Kim. Sufficiency and duality in non-smooth interval valued programming problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 647-665. doi: 10.3934/jimo.2018063

[11]

Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1133-1151. doi: 10.3934/jimo.2018089

[12]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543

[13]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[14]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[15]

Xiuhong Chen, Zhihua Li. On optimality conditions and duality for non-differentiable interval-valued programming problems with the generalized (F, ρ)-convexity. Journal of Industrial & Management Optimization, 2018, 14 (3) : 895-912. doi: 10.3934/jimo.2017081

[16]

Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003

[17]

Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697

[18]

Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83

[19]

Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2019061

[20]

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

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (25)

[Back to Top]