Enhancing Semidefinite Relaxation for Quadratically Constrained Quadratic Programming via Penalty Methods

Hezhi Luo (), Xiaodi Bai () and Jiming Peng ()
Additional contact information
Hezhi Luo: Zhejiang University of Technology
Xiaodi Bai: Zhejiang University of Technology
Jiming Peng: University of Houston

Journal of Optimization Theory and Applications, 2019, vol. 180, issue 3, No 15, 964-992

Abstract: Abstract Quadratically constrained quadratic programming arises from a broad range of applications and is known to be among the hardest optimization problems. In recent years, semidefinite relaxation has become a popular approach for quadratically constrained quadratic programming, and many results have been reported in the literature. In this paper, we first discuss how to assess the gap between quadratically constrained quadratic programming and its semidefinite relaxation. Based on the estimated gap, we discuss how to construct an exact penalty function for quadratically constrained quadratic programming based on its semidefinite relaxation. We then introduce a special penalty method for quadratically constrained linear programming based on its semidefinite relaxation, resulting in the so-called conditionally quasi-convex relaxation. We show that the conditionally quasi-convex relaxation can provide tighter bounds than the standard semidefinite relaxation. By exploring various properties of the conditionally quasi-convex relaxation model, we develop two effective procedures, an iterative procedure and a bisection procedure, to solve the constructed conditionally quasi-convex relaxation. Promising numerical results are reported.

Keywords: Quadratic programming; Conditionally quasi-convex relaxation; Iterative search; Bisection search; Penalty method; 90C20; 90C22; 90C26 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-018-1416-0 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:joptap:v:180:y:2019:i:3:d:10.1007_s10957-018-1416-0

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-018-1416-0

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

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