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