Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming
| Autor: | Zhibin Deng, Ye Tian, Cheng Lu, Wenxun Xing |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Semidefinite programming
Mathematical optimization Quadratically constrained quadratic program 021103 operations research Control and Optimization Branch and bound Computer science Augmented Lagrangian method Applied Mathematics Strategy and Management 0211 other engineering and technologies 010103 numerical & computational mathematics 02 engineering and technology 01 natural sciences Atomic and Molecular Physics and Optics Quadratic equation Second-order cone programming Quadratic programming 0101 mathematics Business and International Management Electrical and Electronic Engineering Mixed complementarity problem MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Journal of Industrial & Management Optimization. 14:625-636 |
| ISSN: | 1553-166X |
| DOI: | 10.3934/jimo.2017064 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|