A penalty barrier framework for nonconvex constrained optimization

Alberto De Marchi, Andreas ThemelisJournal of Nonsmooth Analysis and Optimization 2025 · DOI

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:

  1. 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.
  2. 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

Abstract

We consider minimization problems with structured objective function and smooth constraints, and present a flexible framework that combines the beneficial regularization effects of (exact) penalty and interior-point methods. In the fully nonconvex setting, a pure barrier approach requires careful steps when approaching the infeasible set, thus hindering convergence. We show how a tight integration with a penalty scheme mitigates this issue and enables the construction of subproblems whose domain is independent of the explicit constraints. This decoupling allows us to leverage efficient solvers designed for unconstrained or suitably structured optimization tasks. The key behind all this is a marginalization step: closely related to a conjugacy operation, this step effectively merges (exact) penalty and barrier into a smooth, full domain functional object. When the penalty exactness takes effect, the generated subproblems do not suffer the ill-conditioning typical of barrier methods, nor do they exhibit the nonsmoothness of exact penalty terms. We provide a theoretical characterization of the algorithm and its asymptotic properties, deriving convergence results for fully nonconvex problems. Stronger conclusions are available for the convex setting, where optimality can be guaranteed. Illustrative examples and numerical simulations demonstrate the wide range of problems our theory and algorithm are able to cover.
BibTeX
@article{marchi2025penalty,
  author = {Alberto De Marchi and Andreas Themelis},
  title = {{A penalty barrier framework for nonconvex constrained optimization}},
  journal = {Journal of Nonsmooth Analysis and Optimization},
  year = {2025},
  doi = {10.46298/jnsao-2025-14585},
}
Figure