Linearly contrained nonsmooth and nonconvex minimization

Marco Artina, Massimo Fornasier, Francesco Solombrino

Abstract

Motivated by variational models in continuum mechanics, this paper introduces a novel algorithm designed to perform nonsmooth and nonconvex minimizations subject to linear constraints in Euclidean spaces. The proposed method is a natural generalization of the non-stationary augmented Lagrangian method typically reserved for convex optimization. Key features include its applicability to a wide range of objective functions, guaranteed convergence to critical points regardless of the initial value, and a simple implementation structure. The algorithm operates via a nested double-loop iteration: the inner loop performs an adaptive finite number of iterations on a fixed quadratic and strictly convex perturbation of the objective energy, while the outer loop adapts the perturbation parameters. We demonstrate the algorithm's versatility through applications in inverse free-discontinuity variational models, such as the Mumford-Shah functional, and the derivation of new iterative thresholding algorithms.

Introduction

In fields ranging from continuum mechanics to image processing, researchers frequently encounter optimization problems characterized by a "triple threat": nonconvexity, nonsmoothness, and linear constraints. Nonconvexity leads to complex energy landscapes with multiple local minima, while nonsmoothness introduces singularities—such as cracks in materials or edges in images—where derivatives are undefined. Furthermore, physical conservation laws or boundary conditions often impose strict linear constraints on the solution.

Traditional solvers, such as Sequentially Quadratic Programming (SQP) or Newton-based methods, often struggle in these environments. They typically require high degrees of regularity (often $C^2$ smoothness) and are highly sensitive to initial conditions; if the starting point is not sufficiently close to the global minimum, these algorithms frequently fail to converge. This paper addresses these limitations by proposing a robust, globally convergent algorithm that is simple to implement and handles "rough" objective functions effectively.

Methodology

The Nested Double-Loop Framework

The core of the proposed approach is a nested double-loop iteration that leverages the stability of convex optimization to solve nonconvex problems.

  1. The Inner Loop: This loop utilizes an augmented Lagrangian (or Bregman) approach. The critical innovation here is the application of the algorithm to a quadratic perturbation of the original objective energy. By choosing a perturbation that is sufficiently large, the sub-problem becomes strictly convex, allowing for efficient and stable solving.
  2. The Outer Loop: The outer loop manages the parameters of the quadratic perturbation. It effectively "moves" the convex approximation based on the results of the previous iteration, guiding the system through the nonconvex landscape toward a critical point.

Handling Truncated Potentials

To manage particularly difficult "truncated" potentials common in fracture mechanics, we introduce a mild $C^1$ smoothing technique. This ensures the objective function satisfies the technical requirement of being $\omega$-semi-convex—meaning the function becomes convex when a specific quadratic term is added.

Iterative Thresholding with Constraints

For applications like the Mumford-Shah functional, the inner loop can be realized as a novel iterative thresholding algorithm. While thresholding is a staple in sparse optimization, it is usually restricted to unconstrained problems. Our framework provides a mathematically rigorous way to apply these simple "shrinkage" operators even in the presence of strict linear constraints.

Experimental Verification

The algorithm was verified using a combination of simulated physical data and image processing benchmarks:

  • Image Denoising: We tested the discrete Mumford-Shah functional on a 125x125 pixel "parrot" image corrupted with 6% noise. The algorithm successfully removed noise while preserving sharp edges, converging to a stationary point with significantly lower energy than the noisy input.
  • Brittle Fracture Simulation: A 1D rod model (51 discretization points) was used to simulate crack propagation under increasing load. The algorithm correctly captured the "elastic-to-fracture" phase transition, identifying the sudden collapse of elastic energy as the material reached its breaking point.
  • Numerical Convergence: Using synthetic 25x25 arrays, we observed that the discrepancy in satisfying linear constraints ($\|Av - f\|$) dropped toward zero at an exponential rate during the inner loop iterations.

Key Insights and Results

Global Convergence

The most significant theoretical contribution is the proof of unconditional convergence. We demonstrate that the sequence of iterations is bounded and that every limit point is a constrained critical point of the original energy. This eliminates the need for a "near-perfect" initial guess, making the solver highly reliable for automated applications.

Bridging the Convex-Nonconvex Gap

By using a moving convex approximation, the algorithm bridges the gap between the extreme stability of convex solvers and the complexity of nonconvex landscapes. It successfully captures physical instabilities, such as material fractures, which are often smoothed over or missed by less robust solvers.

Limitations and Future Work

While the algorithm shows great promise, several areas for development remain:

  • Dimensionality: The current convergence proof is situated in finite-dimensional Euclidean spaces. Extending this proof to infinite-dimensional Hilbert spaces is a primary goal for future research.
  • Conditioning: The core iterations involve operators that can become ill-conditioned. While preconditioned iterative methods can mitigate this, further analysis is needed to understand how spectral properties influence the speed of the outer loop.
  • Computational Intensity: Each step requires solving two systems of partial differential equations (PDEs). While competitive with other state-of-the-art Mumford-Shah solvers, the computational cost remains high for very high-resolution datasets.

Summary updated

Abstract

Motivated by variational models in continuum mechanics, we introduce a novel algorithm to perform nonsmooth and nonconvex minimizations with linear constraints in Euclidean spaces. We show how this algorithm is actually a natural generalization of the well-known non-stationary augmented Lagrangian method for convex optimization. The relevant features of this approach are its applicability to a large variety of nonsmooth and nonconvex objective functions, its guaranteed convergence to critical points of the objective energy independently of the choice of the initial value, and its simplicity of implementation. In fact, the algorithm results in a nested double loop iteration. In the inner loop an augmented Lagrangian algorithm performs an adaptive finite number of iterations on a fixed quadratic and strictly convex perturbation of the objective energy, depending on a parameter which is adapted by the external loop. To show the versatility of this new algorithm, we exemplify how it can be used for computing critical points in inverse free-discontinuity variational models, such as the Mumford-Shah functional, and, by doing so, we also derive and analyze new iterative thresholding algorithms.
BibTeX
@article{artina2013linearly,
  author = {Marco Artina and Massimo Fornasier and Francesco Solombrino},
  title = {{Linearly contrained nonsmooth and nonconvex minimization}},
  journal = {SIAM J. Optim.},
  year = {2013},
  url = {https://openreview.net/forum?id=DnAs2_iP59t},
}
Figure