Linearly Constrained Nonsmooth and Nonconvex Minimization

Marco Artina, Massimo Fornasier, Francesco Solombrino

TL;DR

This paper introduces a novel, general, and robust algorithm for solving nonsmooth and nonconvex minimization problems with linear constraints. This algorithm guarantees convergence to critical points without requiring a good initial guess, making it applicable to a wide range of problems in continuum mechanics and image processing.

What Problem Does This Paper Address?

Many real-world problems in areas like continuum mechanics and image processing involve minimizing objective functions that are both nonsmooth (due to singularities or sharp features) and nonconvex (leading to multiple local minima). These problems often come with additional linear constraints, such as boundary conditions. Existing methods struggle with this combination: convex optimization techniques fail on nonconvex problems, while standard nonconvex methods often require smooth functions and a good initial guess for convergence. This paper aims to bridge this gap by providing a unified, robust, and general algorithm that handles linearly constrained nonsmooth and nonconvex minimization problems.

Methods

The core of the paper is a new iterative algorithm designed for linearly constrained nonsmooth and nonconvex minimization. This algorithm is a generalization of the augmented Lagrangian method and features a nested double-loop structure. The inner loop performs an adaptive finite number of iterations of an augmented Lagrangian algorithm on a fixed quadratic perturbation of the objective function. The outer loop adapts this quadratic perturbation. This approach is designed to:

  • Handle Nonsmoothness: It works with locally Lipschitz functions, a less restrictive condition than C¹ or C¹¹ regularity required by many existing methods.
  • Guarantee Convergence: It converges to critical points of the objective energy regardless of the initial guess, a significant improvement over methods that require a good starting point.
  • Be Simple to Implement: The algorithm's structure is relatively straightforward.

The paper also leverages and extends the concept of iterative thresholding algorithms, particularly for the inner loop, which provides a computationally efficient way to handle the nonsmooth and nonconvex terms.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical examples rather than standard datasets.

Key Insights and Ideas

  • Unconditional Convergence: The algorithm's ability to converge to critical points without needing a good initial guess is a major breakthrough for nonsmooth and nonconvex optimization.
  • Generalization of Existing Methods: The proposed algorithm naturally extends well-known techniques like augmented Lagrangian methods and iterative thresholding, unifying them under a single framework.
  • Iterative Thresholding for Nonsmooth/Nonconvex Problems: The paper demonstrates how iterative thresholding, typically used for convex problems, can be adapted and extended to solve nonsmooth and nonconvex problems, offering a powerful computational tool.
  • Bridging Theory and Practice: The paper connects theoretical concepts like w-semi-convexity and growth conditions to the practical applicability of the algorithm, showing how these conditions can be met in real-world scenarios.

Key Results

  • The paper presents a novel algorithm for linearly constrained nonsmooth and nonconvex minimization that is guaranteed to converge to critical points.
  • The algorithm is shown to be versatile, with applications demonstrated for inverse free-discontinuity variational models, including the Mumford-Shah functional in image processing and models for brittle and cohesive fracture.
  • The paper derives and analyzes new iterative thresholding algorithms as a byproduct of the main algorithm's application.
  • Numerical experiments confirm the theoretical findings, showing the algorithm's ability to handle complex problems and converge to lower energy states.

Limitations and Future Work

  • Finite Dimensionality: The theoretical analysis is confined to finite-dimensional Euclidean spaces. While the authors suggest that much of the analysis could extend to infinite-dimensional Hilbert spaces, the proof of strong compactness in Theorem 2.10 specifically relies on finite dimensionality.
  • Coercivity: For certain applications, like the truncated polynomial minimization, the objective functional is not coercive on the affine space of constraints. The paper addresses this by showing that the algorithm can still converge to critical points under specific conditions (e.g., when T is injective on ker A) or by considering appropriate compact subsets.
  • Parameter Tuning: While the algorithm is robust, the performance and convergence rate can depend on the choice of parameters (γ, ε, r, ω). The paper provides some guidance but acknowledges that tuning might be necessary for optimal performance.
  • Future Work: The authors suggest that the algorithm has significant potential for further numerical applications in various fields involving nonsmooth and nonconvex energies with linear constraints. They also highlight the need for efficient implementation of matrix operations (like pseudoinverses) for practical applications.

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 Constrained Nonsmooth and Nonconvex Minimization}},
  journal = {SIAM J. Optim.},
  year = {2013},
  url = {https://openreview.net/forum?id=DnAs2_iP59t},
}
Figure