Penalized semidefinite programming for quadratically-constrained quadratic optimization
From MaRDI portal
Publication:2022173
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 (QPLIB) demonstrate the ability of the proposed penalized semidefinite programs in finding near-optimal solutions for non-convex QCQP.
Recommendations
- Positive semidefinite penalty method for quadratically constrained quadratic programming
- Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods
- A sequential quadratic penalty method for nonlinear semidefinite programming
- scientific article; zbMATH DE number 1559105
- scientific article; zbMATH DE number 1380758
- Semidefinite programming relaxation for nonconvex quadratic programs
- scientific article; zbMATH DE number 4204120
- Penalty and barrier methods for convex semidefinite programming
- Semidefinite relaxation and nonconvex quadratic optimization
Cites work
- A Characterization of Convex Problems in Decentralized Control$^ast$
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS
- A polyhedral branch-and-cut approach to global optimization
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A rounding procedure for semidefinite optimization
- A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables
- A System-Level Approach to Controller Synthesis
- Algebraic aspects of the advanced encryption standard.
- Ambiguity Function Shaping for Cognitive Radar Via Complex Quartic Optimization
- Angular synchronization by eigenvectors and semidefinite programming
- Applications of cut polyhedra. II
- Approximating global quadratic optimization with convex quadratic constraints
- Approximating quadratic programming with bound and quadratic constraints
- Approximation algorithms for homogeneous polynomial optimization with quadratic constraints
- Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints
- Approximation Methods for Polynomial Optimization
- Blind constant modulus equalization via convex optimization
- Complex Quadratic Optimization and Semidefinite Programming
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Convex Relaxation for Optimal Distributed Control Problems
- Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
- Cuts for Conic Mixed-Integer Programming
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Exact matrix completion via convex optimization
- Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Fast Software Encryption
- Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
- Global optimization with polynomials and the problem of moments
- Globally solving nonconvex quadratic programming problems via completely positive programming
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1942409 (Why is no real title available?)
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- scientific article; zbMATH DE number 6744339 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Lasserre hierarchy for large scale polynomial optimization in real and complex variables
- LP formulations for polynomial optimization problems
- MIMO Radar Waveform Optimization With Prior Information of the Extended Target and Clutter
- On the complexity of purely complex μ computation and related problems in multidimensional systems
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Phase retrieval via matrix completion
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- QPLIB: a library of quadratic programming instances
- Quadratic maximization and semidefinite relaxation
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- Second Order Cone Programming Relaxation of a Positive Semidefinite Constraint
- Second-order cone programming
- Semidefinite characterization of sum-of-squares cones in algebras
- Semidefinite relaxation and nonconvex quadratic optimization
- Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- Separable and Localized System-Level Synthesis for Large-Scale Systems
- The geometric measure of multipartite entanglement and the singular values of a hypermatrix
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Transformation of Optimal Centralized Controllers Into Near-Globally Optimal Static Distributed Controllers
Cited in
(6)- Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods
- An Algorithm for Unconstrained Quadratically Penalized Convex Optimization
- PENNON: A code for convex nonlinear and semidefinite programming
- A sequential quadratic penalty method for nonlinear semidefinite programming
- Positive semidefinite penalty method for quadratically constrained quadratic programming
- An iterative rank penalty method for nonconvex quadratically constrained quadratic programs
Describes a project that uses
Uses Software
This page was built for publication: Penalized semidefinite programming for quadratically-constrained quadratic optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022173)
