# 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] Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050 [2] Manuel de León, Víctor M. Jiménez, Manuel Lainz. Contact Hamiltonian and Lagrangian systems with nonholonomic constraints. Journal of Geometric Mechanics, 2021, 13 (1) : 25-53. doi: 10.3934/jgm.2021001 [3] Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080 [4] Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030 [5] Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068 [6] Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 [7] Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055 [8] Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $O(n)$ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082 [9] Patrick Henning, Anders M. N. Niklasson. Shadow Lagrangian dynamics for superfluidity. Kinetic & Related Models, 2021, 14 (2) : 303-321. doi: 10.3934/krm.2021006 [10] Tianyu Liao. The regularity lifting methods for nonnegative solutions of Lane-Emden system. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021036 [11] Yuri Chekanov, Felix Schlenk. Notes on monotone Lagrangian twist tori. Electronic Research Announcements, 2010, 17: 104-121. doi: 10.3934/era.2010.17.104 [12] Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2543-2557. doi: 10.3934/dcds.2020374 [13] Mengyao Chen, Qi Li, Shuangjie Peng. Bound states for fractional Schrödinger-Poisson system with critical exponent. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021038 [14] Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061 [15] Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2021, 13 (1) : 55-72. doi: 10.3934/jgm.2020031 [16] David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002 [17] Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199 [18] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [19] 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 [20] Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058

2019 Impact Factor: 1.366