Penalized semidefinite programming for quadratically-constrained quadratic optimization

Ramtin Madani (), Mohsen Kheirandishfard (), Javad Lavaei () and Alper Atamtürk ()
Additional contact information
Ramtin Madani: University of Texas
Mohsen Kheirandishfard: University of Texas
Javad Lavaei: University of California
Alper Atamtürk: University of California

Journal of Global Optimization, 2020, vol. 78, issue 3, No 2, 423-451

Abstract: 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; 65K05; 90-08; 90C26; 90C22 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00918-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:78:y:2020:i:3:d:10.1007_s10898-020-00918-8

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00918-8

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().