# American Institute of Mathematical Sciences

April 2018, 14(2): 625-636. doi: 10.3934/jimo.2017064

## Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming

 1 School of Economics and Management, University of Chinese Academy of Sciences, Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences, Beijing 100190, China 2 School of Business Administration, Southwestern University of Finance and Economics, Chengdu 611130, China 3 School of Economics and Management, North China Electric Power University, Beijing 102206, China 4 Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

* Corresponding author: Cheng Lu

Received  August 2016 Revised  April 2017 Published  June 2017

Quadratic programs with complementarity constraints (QPCC) are NP-hard due to the nonconvexity of complementarity relation between the pairs of nonnegative variables. Most of the existing solvers are capable of solving QPCC by finding stationary solutions, which are not able to be verified as global or local optimal ones. In this paper, we aim to globally solve QPCC by a branch-and-bound algorithm, in which the doubly nonnegative (DNN) relaxation in each node is efficiently solved via an augmented Lagrangian method. The method is practically efficient due to the fact that the augmented Lagrangian function can be decomposed into two easy-to-solve subproblems. Computational results demonstrate the effectiveness of the proposed algorithm, with a particular highlight in only a few nodes for some instances.

Citation: Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064
##### References:

show all references

##### References:
 Output: An approximate solution $Y$ and a valid lower bound $v$ of problem (DNP). 1. Set $(S, \sigma)=(S_0, \sigma_0)$ and $v=-\infty$. Initialize $Z=0$. 2: for $k=0, 1, ...$do 3:    Solve problem (Y-Block) to get Y. 4:    Solve problem (Z-Block to get Z. 5:    Update S according to (5). 6:    Update v by optimizing problem (Y-Block) with Z = 0 and σ = 0. 7:    Update σ if necessary. 8:    STOP, if termination criteria are met. 9: end for
 Output: An approximate solution $Y$ and a valid lower bound $v$ of problem (DNP). 1. Set $(S, \sigma)=(S_0, \sigma_0)$ and $v=-\infty$. Initialize $Z=0$. 2: for $k=0, 1, ...$do 3:    Solve problem (Y-Block) to get Y. 4:    Solve problem (Z-Block to get Z. 5:    Update S according to (5). 6:    Update v by optimizing problem (Y-Block) with Z = 0 and σ = 0. 7:    Update σ if necessary. 8:    STOP, if termination criteria are met. 9: end for
 Algorithm 2 A Branch-and-Bound Algorithm for Globally Solving Problem (QPCC) Input: Data (Q; q; A; b; E). Output: A global solution of (QPCC). 1: Preprocessing Step: Calculate the upper bound for variable x. 2: Initialization Step: The list $\mathcal{L}$ to be explored is initialized to contain the root node. Upper bound is set to +1, and lower bound is set to −1. 3: while $\mathcal{L}$ is not empty do 4:    Node Selection Step: Select and remove the best-first node from $\mathcal{L}$. 5:    Bounding Step: Solve the relaxation problem of the node by Algorithm 1. Update upper and lower bound if possible. If the node is not fathomed, go to the next step. 6:    Branching Step: Branch the node on the most violated complementarity constraint, generate two children nodes and add them to the list $\mathcal{L}$. 7: end while
 Algorithm 2 A Branch-and-Bound Algorithm for Globally Solving Problem (QPCC) Input: Data (Q; q; A; b; E). Output: A global solution of (QPCC). 1: Preprocessing Step: Calculate the upper bound for variable x. 2: Initialization Step: The list $\mathcal{L}$ to be explored is initialized to contain the root node. Upper bound is set to +1, and lower bound is set to −1. 3: while $\mathcal{L}$ is not empty do 4:    Node Selection Step: Select and remove the best-first node from $\mathcal{L}$. 5:    Bounding Step: Solve the relaxation problem of the node by Algorithm 1. Update upper and lower bound if possible. If the node is not fathomed, go to the next step. 6:    Branching Step: Branch the node on the most violated complementarity constraint, generate two children nodes and add them to the list $\mathcal{L}$. 7: end while
Computational results of six QPCC instances on MacMPEC
 Id $(m, n, |\mathcal{E}|)$ nodes time (sec.) bilevel2 (29, 13, 12) 13 4.86 bilevel2m (9, 21, 8) 5 1.74 flp4-1 (60,190, 80) 3 8.41 flp4-2 (110,270,110) 1 15.21 flp4-3 (170,380,140) 1 30.03 flp4-4 (250,550,200) 1 67.71
 Id $(m, n, |\mathcal{E}|)$ nodes time (sec.) bilevel2 (29, 13, 12) 13 4.86 bilevel2m (9, 21, 8) 5 1.74 flp4-1 (60,190, 80) 3 8.41 flp4-2 (110,270,110) 1 15.21 flp4-3 (170,380,140) 1 30.03 flp4-4 (250,550,200) 1 67.71
Computation results for randomly generated QPCC Instances
 $(m, n, |\mathcal{E}|)$ Ave. nodes Ave. CPU time (sec.) (4, 12, 3) 3 1.21 (15, 45, 10) 5 9.43 (25, 55, 20) 26 65.21 (30,100, 40) 121 310.66
 $(m, n, |\mathcal{E}|)$ Ave. nodes Ave. CPU time (sec.) (4, 12, 3) 3 1.21 (15, 45, 10) 5 9.43 (25, 55, 20) 26 65.21 (30,100, 40) 121 310.66
Computational results for binary quadratic programs from OR-Library
 $m=50, ~n=100, ~|\mathcal{E}|=50$ Id Optimal value Nodes {CPU time (sec.) bqp50-1 $\le-2160$ 3564 1800.00 bqp50-2 $-3702$ 3063 1570.22 bqp50-3 $-4626$ 69 19.53 bqp50-4 $-3544$ 767 330.86 bqp50-5 $-4012$ 531 226.87 bqp50-6 $-3693$ 107 49.31 bqp50-7 $-4520$ 605 247.22 bqp50-8 $-4216$ 771 363.41 bqp50-9 $-3780$ 3849 1692.21 bqp50-10 $\le-3507$ 3626 1800.00
 $m=50, ~n=100, ~|\mathcal{E}|=50$ Id Optimal value Nodes {CPU time (sec.) bqp50-1 $\le-2160$ 3564 1800.00 bqp50-2 $-3702$ 3063 1570.22 bqp50-3 $-4626$ 69 19.53 bqp50-4 $-3544$ 767 330.86 bqp50-5 $-4012$ 531 226.87 bqp50-6 $-3693$ 107 49.31 bqp50-7 $-4520$ 605 247.22 bqp50-8 $-4216$ 771 363.41 bqp50-9 $-3780$ 3849 1692.21 bqp50-10 $\le-3507$ 3626 1800.00
 [1] 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 [2] Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319 [3] X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287 [4] Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237 [5] Qingsong Duan, Mengwei Xu, Yue Lu, Liwei Zhang. A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-21. doi: 10.3934/jimo.2018094 [6] Tim Hoheisel, Christian Kanzow, Alexandra Schwartz. Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 49-60. doi: 10.3934/naco.2011.1.49 [7] Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041 [8] Liping Pang, Na Xu, Jian Lv. The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-21. doi: 10.3934/jimo.2018032 [9] Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499 [10] Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153 [11] Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65 [12] Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651 [13] Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185 [14] Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial & Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99 [15] Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086 [16] Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193 [17] Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems & Imaging, 2013, 7 (4) : 1409-1432. doi: 10.3934/ipi.2013.7.1409 [18] Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 [19] Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951 [20] Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

2017 Impact Factor: 0.994

## Tools

Article outline

Figures and Tables