Source-linked AI summary
Feasible Point Pursuit and Successive Approximation of Non-convex QCQPs
Omar Mehanna, Kejun Huang, Balasubramanian Gopalakrishnan, Aritra Konar, Nicholas D. Sidiropoulos
TL;DR
Non-convex QCQPs are generally NP-hard, and existing SDR or SCA-based methods can struggle to find feasible points. FPP-SCA addresses this by combining successive linearization with slack variables and a penalty, achieving feasible, near-optimal solutions more often than SDR with randomization in simulations.
Problem
General indefinite-matrix QCQPs are non-convex and NP-hard, while conventional SCA requires feasible initialization and SDR randomization can fail to find feasible points.
Method
FPP-SCA iteratively linearizes non-convex constraint parts, adds slack variables to maintain feasibility, and penalizes slacks to drive them toward zero.
Results
FPP-SCA obtained good feasible solutions for a much higher percentage of instances than SDR plus randomization, with lower worst-case complexity and a smaller gap to the relaxation lower bound.
Takeaways & Limitations
FPP-SCA provides a feasible-solution approach for general non-convex QCQPs and, after finding feasibility, ensures convergence to a KKT point.
Abstract
from arXiv · showhide
Quadratically constrained quadratic programs (QCQPs) have a wide range of applications in signal processing and wireless communications. Non-convex QCQPs are NP-hard in general. Existing approaches relax the non-convexity using semi-definite relaxation (SDR) or linearize the non-convex part and solve the resulting convex problem. However, these techniques are seldom successful in even obtaining a feasible solution when the QCQP matrices are indefinite. In this paper, a new feasible point pursuit successive convex approximation (FPP-SCA) algorithm is proposed for non-convex QCQPs. FPP-SCA linearizes the non-convex parts of the problem as conventional SCA does, but adds slack variables to sustain feasibility, and a penalty to ensure slacks are sparingly used. When FPP-SCA is successful in identifying a feasible point of the non-convex QCQP, convergence to a Karush-Kuhn-Tucker (KKT) point is thereafter ensured. Simulations show the effectiveness of our proposed algorithm in obtaining feasible and near-optimal solutions, significantly outperforming existing approaches.
I. INTRODUCTION
General indefinite-matrix QCQPs are non-convex and NP-hard, while common SDR, RLT, and SCA approaches struggle to produce feasible solutions because they require feasible initialization or rely on randomization. The paper introduces FPP-SCA, which uses linear restrictions, slack variables, and penalties to pursue feasible solutions.
- Problem setting: General QCQPs with indefinite matrices are non-convex and NP-hard, unlike the convex positive-semidefinite case.Efficient optimality is available when all constraint matrices are positive semidefinite, with limited additional special cases.
- Existing approaches: RLT and SCA approximate non-convex QCQPs, but their solutions or iterations depend on obtaining a feasible starting point.RLT can also create a much larger linear program, while SCA approximates concave parts around a feasible point.
- Existing approaches: SDR relaxes the rank-1 constraint after introducing X := xxH, producing a semidefinite program whose solution supplies a lower bound.When the relaxed solution is rank-1, the original solution can be recovered from its principal eigenvector; otherwise, randomization is used.
- Motivation: SDR with randomization often fails to find feasible points when constraint matrices are indefinite or constraints are two-sided positive semidefinite.This motivates an alternative approach with a high probability of finding feasibility when a feasible solution exists.
- Proposed approach: FPP-SCA iteratively linearizes non-convex constraint parts, adds slacks to sustain feasibility, and penalizes slacks so they are used sparingly.Each solution becomes the next linearization point, and the procedure repeats until convergence.
II. THE FPP-SCA APPROACH
FPP-SCA handles potentially infeasible non-convex QCQPs by combining slack-penalized feasibility restoration with successive convex restriction. It repeatedly solves convex approximations, yielding a non-increasing cost sequence and, in one illustration, either a feasible optimum or an infeasible stationary outcome depending on initialization.
- FPP-SCA formulation: Slack variables make the relaxed QCQP always feasible, while their penalty trades off the original objective against constraint violations.Using the l1 norm promotes sparse constraint violations.
- Successive convex approximation: SCA decomposes each indefinite quadratic matrix into positive- and negative-semidefinite parts, then linearizes the concave part around the current point.The resulting restriction is convex and is used to form the next subproblem.
- Algorithm: FPP-SCA initializes a point, repeatedly solves the convex penalized restriction, and uses the resulting optimizer as the next linearization point until convergence.The algorithm description specifies random initialization and iterative updates of z_k.
- Convergence properties: The optimal cost of the convex subproblem is non-increasing because each iteration’s solution remains feasible for the next restricted problem.Each new restriction is constructed around the preceding optimizer.
- Illustration: In the illustrated three-iteration example, one initialization reaches feasibility after iteration 2 and the optimum after iteration 3, whereas another converges to an infeasible point.Both runs converge, but the second initialization produces an undesirable outcome.
III. NUMERICAL RESULTS
The experiments evaluate SDR with randomization and FPP-SCA on non-convex QCQPs, including multicast beamforming and randomly generated instances. As constraints become more stringent, FPP-SCA obtains feasible solutions far more reliably than SDR-based randomization.
- Experimental setup: The experiments test FPP-SCA and SDR-based methods on QCQPs with n = 8 complex dimensions and varying numbers of constraints.The n = 8 setup uses M ∈{16, 24, 32}; related simulations also use M ∈{12, · · · , 24}, K = 4, τ = 10 and η = 1.
- SDR comparison: The SDR tables report rank-1 outcomes, infeasible randomizations, feasible randomizations, and gaps from the relaxation lower bound.Each SDR run generates 10^4 randomization points when the relaxed solution is not rank-1.
- SDR comparison: As M increases, the percentage of feasible solutions obtained by SDR, directly or after randomization, diminishes quickly.The SDR approach becomes less effective as the constraint set becomes more stringent.
- FPP-SCA results: With M = 32, FPP-SCA found a feasible point in 92.8% of cases, whereas SDR followed by randomization was almost never successful when the solution was not rank-1.FPP-SCA used λ = 10 and at most 30 iterations, with convergence based on a 10^-4 stopping criterion.
- Experimental setup: The multicast beamforming problem models secondary users requiring minimum signal power while primary users are protected from excessive interference.The channels are modeled using i.i.d. zero-mean complex Gaussian Rayleigh fading.
- FPP-SCA results: In a 1000-instance experiment, FPP-SCA found feasible solutions in every case, with average power increases from 1 to 2.2 dB as M ranged from 12 to 24.The comparison is against the generally unattainable relaxation lower bound provided by SDR.
IV. CONCLUSIONS
The conclusion presents FPP-SCA as an iterative method for approximately solving general QCQPs. Compared with SDR followed by randomization, it obtains feasible solutions more often with lower worst-case complexity and a smaller gap to the relaxation lower bound.
- FPP-SCA is an iterative approach for approximately solving general QCQPs.
- Compared with SDR followed by randomization, FPP-SCA succeeds on a much higher percentage of problem instances.
- FPP-SCA achieves lower worst-case complexity and a smaller gap to the relaxation lower bound than SDR followed by randomization.
- The results suggest that FPP-SCA may apply to engineering design problems formulated as non-convex QCQPs.