TL;DR
This paper introduces a new algorithm, Feasible Point Pursuit - Successive Convex Approximation (FPP-SCA), to efficiently find feasible and near-optimal solutions for a class of challenging optimization problems called non-convex Quadratically Constrained Quadratic Programs (QCQPs). Unlike existing methods that often struggle with feasibility, FPP-SCA uses slack variables and a penalty mechanism to guarantee finding a feasible point with high probability, even for complex problems.
What Problem Does This Paper Address?
Many real-world problems in areas like signal processing and wireless communications can be modeled as Quadratically Constrained Quadratic Programs (QCQPs). While QCQPs with positive semi-definite matrices are relatively easy to solve, the problem becomes NP-hard and significantly more difficult when the matrices involved are indefinite. Existing approaches to tackle these non-convex QCQPs include Semi-Definite Relaxation (SDR) and Reformulation-Linearization Technique (RLT). However, these methods often fail to find a feasible solution, especially when the problem's constraints are "indefinite." This paper addresses the critical need for an algorithm that can reliably find feasible solutions for these difficult non-convex QCQPs, a capability that current state-of-the-art methods lack.
Methods
The core contribution is the Feasible Point Pursuit - Successive Convex Approximation (FPP-SCA) algorithm. It builds upon the Successive Convex Approximation (SCA) framework but introduces two key innovations:
- Slack Variables: To overcome the challenge of finding an initial feasible point (a common stumbling block for SCA), FPP-SCA augments the original problem with slack variables. These variables allow the algorithm to temporarily "violate" constraints, ensuring that the modified problem is always feasible.
- Penalty Term: A penalty term is added to the objective function, weighted by a parameter $\lambda$. This penalty encourages the algorithm to minimize the use of slack variables, effectively pushing the solution towards the feasible region of the original problem as the algorithm progresses.
The algorithm iteratively linearizes the non-convex parts of the constraints around a current point. The resulting convex problem, which includes the slack variables and penalty, is solved to obtain a new point. This new point is then used as the linearization center for the next iteration. The process continues until convergence. The paper also notes that the FPP-SCA problem can be formulated as a Second-Order Cone Program (SOCP), which can be efficiently solved.
Datasets
Not discussed in the paper. The paper uses synthetic problem instances generated according to specific parameters (e.g., dimensions $n$, number of constraints $M$, and random entries for matrices and right-hand sides) for evaluation.
Key Insights and Ideas
- Feasibility is Paramount: The paper strongly emphasizes that for many practical applications, finding any feasible solution is often more critical than finding the absolute optimal solution, especially when dealing with non-convex problems where optimality is hard to guarantee.
- Slack Variables as a Feasibility Bridge: The introduction of slack variables is a clever way to bridge the gap between potentially infeasible original problems and the convex subproblems that SCA relies on. The penalty term then guides the solution back towards feasibility.
- SDR as a Potential Initialization: While FPP-SCA aims to be an alternative to SDR, the paper suggests that SDR can sometimes provide a good starting point for FPP-SCA, offering a way to leverage the strengths of both methods.
- High Probability of Success: The FPP-SCA algorithm demonstrates a significantly higher probability of finding feasible solutions compared to traditional SDR followed by randomization, particularly as problem complexity increases.
Key Results
- Superior Feasibility: FPP-SCA consistently achieved a much higher percentage of feasible solutions compared to SDR with randomization across various problem dimensions ($n$) and numbers of constraints ($M$). For instance, with $n=8$ and $M=32$, FPP-SCA found feasible solutions in 92.8% of runs, while SDR found them in only 0.3%.
- Close to Lower Bound: The feasible solutions found by FPP-SCA were also closer to the lower bound provided by the (higher-rank) SDR solution, indicating better solution quality.
- Efficient Convergence: The algorithm typically required a small number of iterations to reach feasibility and convergence.
- Illustrative Example: A 2D example visually demonstrates how the algorithm iteratively refines the solution, eventually finding a feasible point. It also highlights cases where the algorithm might converge to an undesirable point if not initialized carefully.
- Multicast Beamforming Success: In a practical multicast beamforming problem, FPP-SCA successfully found feasible solutions for all instances where SDR failed, with only a minor increase in the objective function value.
Limitations and Future Work
- Initialization Sensitivity: While FPP-SCA is more robust than conventional SCA, the paper acknowledges that the quality of the final solution can still depend on the initial point ($z_0$). The paper suggests using multiple random initializations or leveraging SDR for initialization to mitigate this.
- Convergence to KKT: The paper states that FPP-SCA converges to a Karush-Kuhn-Tucker (KKT) point of the augmented problem (П₂). While this is a strong theoretical guarantee, ensuring convergence to a KKT point of the original problem (П₁) relies on the slack variables becoming zero, which is encouraged but not strictly guaranteed in all scenarios.
- Future Work: The authors suggest that FPP-SCA holds promise for a broad range of applications and could be further explored for various engineering design problems that can be formulated as non-convex QCQPs. The potential for parallel and distributed implementations could also be an avenue for future research.
Summary updated