We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints.
- Authors
Luo, Hezhi; Zhang, Xianye; Wu, Huixian; Xu, Weiqiang
- Abstract
We consider in this paper a separable and nonconvex quadratic program (QP) with a quadratic constraint and a box constraint that arises from application in optimal portfolio deleveraging (OPD) in finance and is known to be NP-hard. We first propose an improved Lagrangian breakpoint search algorithm based on the secant approach (called ILBSSA) for this nonconvex QP, and show that it converges to either a suboptimal solution or a global solution of the problem. We then develop a successive convex optimization (SCO) algorithm to improve the quality of suboptimal solutions derived from ILBSSA, and show that it converges to a KKT point of the problem. Second, we develop a new global algorithm (called ILBSSA-SCO-BB), which integrates the ILBSSA and SCO methods, convex relaxation and branch-and-bound framework, to find a globally optimal solution to the underlying QP within a pre-specified ϵ -tolerance. We establish the convergence of the ILBSSA-SCO-BB algorithm and its complexity. Preliminary numerical results are reported to demonstrate the effectiveness of the ILBSSA-SCO-BB algorithm in finding a globally optimal solution to large-scale OPD instances.
- Subjects
NONCONVEX programming; QUADRATIC programming; ALGORITHMS; TABU search algorithm; SEARCH algorithms
- Publication
Computational Optimization & Applications, 2023, Vol 86, Issue 1, p199
- ISSN
0926-6003
- Publication type
Article
- DOI
10.1007/s10589-023-00485-0