New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation

  • We consider a quadratic program with a few negative eigenvalues (QP-r-NE) subject to linear and convex quadratic constraints that covers many applications and is known to be NP-hard even with one negative eigenvalue (QP1NE). In this paper, we first introduce a new global algorithm (ADMBB), which integrates several simple optimization techniques such as alternative direction method, and branch-and-bound, to find a globally optimal solution to the underlying QP within a pre-specified ϵ-tolerance. We establish the convergence of the ADMBB algorithm and estimate its complexity. Second, we develop a global search algorithm (GSA) for QP1NE that can locate an optimal solution to QP1NE within ϵ-tolerance and estimate the worst-case complexity bound of the GSA. Preliminary numerical results demonstrate that the ADMBB algorithm can effectively find a global optimal solution to large-scale QP-r-NE instances when r≤10, and the GSA outperforms the ADMBB for most of the tested QP1NE instances. The software reviewed as part of this submission was given the DOI (digital object identifier) https://doi.org/10.5281/zenodo.1344739.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Hezhi Luo, Xiaodi Bai, Gino Lim, Jiming Peng
DOI:https://doi.org/10.1007/s12532-018-0142-9
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2018
Tag:Software; Theoretical Computer Science
Volume:11
Issue:1
Page Number:53
First Page:119
Last Page:171
Mathematical Programming Computation :MPC 2019 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.