Penalized semidefinite programming for quadratically-constrained quadratic optimization
- PDF / 1,003,663 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 99 Downloads / 269 Views
Penalized semidefinite programming for quadratically-constrained quadratic optimization Ramtin Madani1 · Mohsen Kheirandishfard1 · Javad Lavaei2 · Alper Atamtürk2 Received: 4 June 2019 / Accepted: 30 May 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we give a new penalized semidefinite programming approach for non-convex quadratically-constrained quadratic programs (QCQPs). We incorporate penalty terms into the objective of convex relaxations in order to retrieve feasible and near-optimal solutions for non-convex QCQPs. We introduce a generalized linear independence constraint qualification (GLICQ) criterion and prove that any GLICQ regular point that is sufficiently close to the feasible set can be used to construct an appropriate penalty term and recover a feasible solution. Inspired by these results, we develop a heuristic sequential procedure that preserves feasibility and aims to improve the objective value at each iteration. Numerical experiments on large-scale system identification problems as well as benchmark instances from the library of quadratic programming demonstrate the ability of the proposed penalized semidefinite programs in finding near-optimal solutions for non-convex QCQP. Keywords Semidefinite programming · Non-convex optimization · Non-linear programming · Convex relaxation Mathematics Subject Classification 65K05 · 90-08 · 90C26 · 90C22
This work is in part supported by the NSF Award 1809454. Javad Lavaei is supported by an AFOSR YIP Award and ONR N000141712933. Alper Atamtürk is supported, in part, by Grant FA9550-10-1-0168 from the Office of the Assistant Secretary of Defense for Research & Engineering, NSF Award 1807260, DOE ARPA-E Grant 260801540061, and DOD ONR Grant 12951270.
B
Alper Atamtürk [email protected] Ramtin Madani [email protected] Mohsen Kheirandishfard [email protected] Javad Lavaei [email protected]
1
University of Texas, 517 Nedderman Hall, Arlington, TX 76019, USA
2
University of California, 4175 Etcheverry Hall, Berkeley, CA 94720, USA
123
Journal of Global Optimization
1 Introduction This paper studies a subclass of polynomial optimization, regarded as quadraticallyconstrained quadratic programming (QCQP), which is concerned with minimizing a multi-dimensional quadratic function within a feasible set that is also characterized by quadratic functions. QCQP arises in various scientific and engineering applications, such as electric power systems [52–54,56], imaging science [8,17,28,73], signal processing [2,7,19,47,50,58], automatic control [1,27,56,77], quantum mechanics [14,24,35,46], and cybersecurity [21–23,62]. The development of efficient optimization techniques and numerical algorithms for QCQP has been an active area of research for decades. Due to the barriers imposed by NP-hardness, the focus of some research efforts has shifted from designing general-purpose algorithms to specialized methods that are robust and scalable for specific application domains. Notable examples
Data Loading...
