Abstract
Constrained optimization often struggles with the dual challenges of nonconvexity and nonsmoothness. Traditional interior-point methods require strict feasibility, while penalty methods often introduce numerical instability or non-differentiability. We present "Marge," a framework that integrates the benefits of both approaches through a marginalization step. By applying barrier functions to slack variables and analytically minimizing them, we create a smooth, full-domain envelope. This allows for the use of efficient unconstrained solvers on complex constrained problems. Our results demonstrate superior scalability and robustness across synthetic and real-world benchmarks, including matrix completion and sparse optimization.
Introduction
In engineering and data science, minimizing a function $f(x)$ subject to constraints $c(x) \le 0$ is a fundamental task. However, modern problems frequently involve nonsmooth objectives (e.g., sparsity-promoting terms) and nonconvex landscapes. Existing solvers generally fall into two categories:
- Barrier Methods (Interior Point): These require iterates to remain strictly within the feasible region. Finding an initial feasible point is often as difficult as the optimization itself, and approaching the boundary can lead to numerical instability.
- Penalty Methods: These allow constraint violations by adding a penalty term to the objective. While flexible, they often introduce "kinks" (nonsmoothness) or extreme ill-conditioning as the penalty parameter increases to enforce feasibility.
This paper introduces a novel framework that bridges this gap, providing the robustness of penalty methods with the numerical stability of barrier methods.
The Marge Framework: Marginalization and Smoothing
The core innovation of the proposed method, dubbed Marge, is a two-step transformation of the original constrained problem that eliminates the traditional trade-offs between feasibility and smoothness.
1. Relaxation and Slacks
First, the hard constraints are relaxed using an $L^1$ penalty, and slack variables are introduced to convert inequalities into equalities. This relaxation ensures that the solver can handle infeasible starting points and "roam" the search space freely.
2. The Marginalization Trick
Instead of applying a barrier function directly to the primary decision variables, Marge applies it to the slack variables. The framework then performs an analytical minimization—marginalization—over these slacks. This step is closely related to a conjugacy operation, effectively merging the penalty and barrier into a single functional object.
The result is a smooth penalty-barrier envelope. Unlike standard interior-point methods, the resulting subproblems possess a "full domain." This means the solver can traverse any part of the search space without the risk of "crashing" into constraint boundaries. This decoupling of the constraint difficulty from the search domain allows the use of high-performance, quasi-Newton solvers like PANOC+.
Key Innovations
The Log-Like Barrier
While various barrier functions can be used, the authors identify a specific "log-like" barrier that offers an optimal balance. Unlike traditional logarithmic or inverse barriers, this function maintains numerical stability and theoretical optimality even when the penalty parameter is large, preventing the ill-conditioning typical of barrier methods.
Handling Sparsity and $L^0$ Constraints
A significant advantage of Marge is its ability to handle the $L^0$ "pseudo-norm" (which counts non-zero entries) directly. Typically, $L^0$ constraints require a massive expansion of variables and constraints. Marge handles these without inflating the problem size, maintaining efficiency even in high-dimensional settings.
Exactness without Nonsmoothness
When the penalty parameter is sufficiently large, Marge behaves as an "exact penalty" method. Crucially, it achieves this "exactness" while remaining smooth, avoiding the derivative discontinuities that typically plague exact penalty formulations.
Experimental Evaluation
The framework was tested against several state-of-the-art solvers on diverse benchmarks:
- Nonnegative PCA: In scalability tests, Marge significantly outperformed IPprox (a pure interior-point method). As the required precision increased, Marge’s numerical stability allowed it to converge where other methods struggled.
- MovieLens 100k Matrix Completion: On this real-world, fully nonconvex task involving thousands of variables, Marge (using the log-like barrier) was approximately twice as fast as ALPS and Ipopt when handling sparsity-promoting terms.
- Quadratic Programming (QP): Marge demonstrated high robustness to "degenerate" constraints, such as equality constraints represented as two inequalities—a common scenario that often causes traditional solvers to fail or slow down significantly.
Conclusion
Marge represents a significant step forward in nonconvex constrained optimization. By merging penalty and barrier methods through marginalization, it creates a smooth, numerically stable landscape that is accessible to efficient unconstrained solvers. While future work remains in automating the tuning of homotopic updates and improving infeasibility detection, Marge provides a robust and scalable framework for some of the most challenging problems in modern optimization.
Summary updated