Source-linked AI summary
Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Lojasiewicz inequality
Hedy Attouch, Jerome Bolte, Patrick Redont, Antoine Soubeyran
TL;DR
The paper studies how to guarantee convergence for proximal alternating minimization on structured nonconvex objectives. It develops a Kurdyka–Łojasiewicz-based analysis of the algorithm and shows convergence of bounded sequences to critical points, with extensions to alternating projections and applications.
Problem
The paper addresses convergence of alternating minimization for structured nonconvex functions and related feasibility problems.
Method
It analyzes a proximal regularization of a two-block Gauss–Seidel method under the Kurdyka–Łojasiewicz framework, including general coupling functions and tame objectives.
Results
Bounded sequences generated by the algorithm converge to critical points, with rates determined by local geometric properties; the projection specialization covers broad classes of tame and regular sets.
Takeaways & Limitations
The framework supports convergence analyses for nonconvex optimization, alternating projections, compressive sensing, and rank reduction problems.
Takeaways & Limitations
The convergence theorem requires the Kurdyka–Łojasiewicz property and does not assume standard local nondegeneracy conditions such as unique minimizers, second-order conditions, or transversality.
Abstract
from arXiv · showhide
We study the convergence properties of an alternating proximal minimization algorithm for nonconvex structured functions of the type: $L(x,y)=f(x)+Q(x,y)+g(y)$, where $f:\R^n\rightarrow\R\cup{+\infty}$ and $g:\R^m\rightarrow\R\cup{+\infty}$ are proper lower semicontinuous functions, and $Q:\R^n\times\R^m\rightarrow \R$ is a smooth $C^1$ function which couples the variables $x$ and $y$. The algorithm can be viewed as a proximal regularization of the usual Gauss-Seidel method to minimize $L$. We work in a nonconvex setting, just assuming that the function $L$ satisfies the Kurdyka-Łojasiewicz inequality. An entire section illustrates the relevancy of such an assumption by giving examples ranging from semialgebraic geometry to "metrically regular" problems. Our main result can be stated as follows: If L has the Kurdyka-Łojasiewicz property, then each bounded sequence generated by the algorithm converges to a critical point of $L$. This result is completed by the study of the convergence rate of the algorithm, which depends on the geometrical properties of the function $L$ around its critical points. When specialized to $Q(x,y)=|x-y|^2$ and to $f$, $g$ indicator functions, the algorithm is an alternating projection mehod (a variant of Von Neumann's) that converges for a wide class of sets including semialgebraic and tame sets, transverse smooth manifolds or sets with "regular" intersection. In order to illustrate our results with concrete problems, we provide a convergent proximal reweighted $\ell^1$ algorithm for compressive sensing and an application to rank reduction problems.
1 Introduction
The paper analyzes a proximal alternating minimization algorithm for structured nonconvex functions under the Kurdyka–Łojasiewicz property. It establishes convergence results, explains the relevance of tame geometry, and discusses projection, tractability, and application settings.
- Algorithm and problem structure: The algorithm targets L(x, y) = f(x) + Q(x, y) + g(y), with proper lower semicontinuous f and g and a smooth coupling function Q.Its updates are a proximal regularization of a two-block Gauss–Seidel method.
- Projection methods and applications: The approach applies to feasibility problems by choosing f and g as indicator functions, and its projection specialization converges for semialgebraic, definable, transverse-manifold, and regularly intersecting sets.These problems include finding common points of closed sets and have applications in approximation, image reconstruction, statistics, PDEs, and optimal control.
- Kurdyka–Łojasiewicz framework: The method operates in a nonconvex setting under the Kurdyka–Łojasiewicz property, which covers semialgebraic and other definable functions.Tame sets and functions are stable under finite unions, intersections, and compositions, and include many matrix sets and piecewise polynomial or analytic criteria.
- Algorithmic behavior: The convergence analysis applies for stepsizes above a fixed positive parameter, while smaller stepsizes make the method gradient-like; regularized versions converge with small constant stepsizes.The paper also presents applications to compressive sensing and rank reduction problems.
- Convergence results: If L has the Kurdyka–Łojasiewicz property at each point, every bounded generated sequence has finite length and converges to a critical point of L.The convergence rate depends on the Łojasiewicz exponent around the limiting critical point.
- Computational aspects: For suitable stepsizes, one block update can become a convex tractable problem, while several nonconvex cases reduce to explicit or standard computations.Inexact versions are identified as a matter for future research, outside the paper’s scope.
2 Elementary facts of nonsmooth analysis
This section introduces the nonsmooth-analysis objects used throughout the paper, including subdifferentials, critical points, point-to-set graphs, normal cones, indicator functions, and projections. It also gives the subdifferential decomposition for the structured objective.
- Subdifferentials: The limiting subdifferential ∂f(x) extends the Fréchet subdifferential and is closed, while the Fréchet subdifferential is convex and closed.The limiting version contains the Fréchet version.
- Criticality: A critical point is a point satisfying the paper’s limiting-subdifferential stationarity condition, and the set of such points is denoted crit f.The text calls these points limiting-critical or simply critical.
- Structured subdifferentials: For L satisfying the structural assumption, ∂L(x, y) equals the Cartesian product of the partial subdifferentials with respect to x and y.The decomposition adds the corresponding gradients of Q to ∂f(x) and ∂g(y).
- Normal cones: The section defines Fréchet and limiting normal cones for closed sets and notes that the limiting normal cone is closed but not necessarily convex.The normal cone is empty outside the set.
- Indicators and projections: For a closed set C, the indicator function is zero on C and +∞ outside it, while the projection PC maps a point to its nearest points in C.When C is nonempty, the projection mapping is nonempty everywhere.
3 Alternating proximal minimization algorithms
The paper analyzes an alternating proximal minimization algorithm under the Kurdyka–Łojasiewicz property, establishing convergence behavior for bounded iterates and characterizing rate dependence on local geometry.
- Algorithm and preliminary properties: The algorithm alternates proximal minimization steps with positive, bounded stepsizes under assumptions ensuring the subproblems are well defined.The objective is bounded below, and the stepsizes remain in a fixed positive interval.
- Algorithm and preliminary properties: The objective values do not increase, while bounded subsequences have vanishing increments and asymptotically vanishing subgradient distance.These properties support the identification of limit points as critical points.
- Convergence to a critical value: For bounded iterates, the limit set is nonempty, compact, connected, contained in crit L, and has a common finite objective value.That value equals the infimum of the objective values along the generated sequence.
- Convergence to a critical point: If L satisfies the Kurdyka–Łojasiewicz property at each relevant point, either the iterates diverge to infinity or have finite length and converge to a critical point.The finite-length alternative is the main global convergence conclusion for bounded sequences.
- Projection specialization: For quadratic coupling and indicator functions, the method becomes a proximal alternating projection scheme with convergence results for Kurdyka–Łojasiewicz feasibility problems.For sufficiently large proximal parameters, it is close to the von Neumann alternating projection method.
- Rates and local convergence: The convergence rate depends on the Kurdyka–Łojasiewicz exponent: θ = 0 gives finite-step convergence, while θ ∈ (0, 1) yields rate estimates.The local theorem interprets convergence as driven by a decreasing Lyapunov function near a critical point.
4 Examples and applications
The paper illustrates the Kurdyka-Łojasiewicz framework through smooth, convex, tame, metrically regular, semialgebraic, compressive-sensing, rank-reduction, and projection applications.
- Smooth and convex examples: Generic Morse smooth functions satisfy the Łojasiewicz inequality locally with a desingularizing function of the form ϕ(s) = c√s.Morse functions are generic in the Baire sense among C2 functions.
- Smooth and convex examples: Convex functions satisfying a local growth condition or uniform convexity satisfy the Kurdyka-Łojasiewicz inequality with explicit desingularizing functions.The paper also notes that tame convex functions provide a practical class where the inequality applies without requiring separate convexity-based arguments.
- Metrically regular problems: Metric regularity of F at x̄ implies the Kurdyka-Łojasiewicz inequality for the associated constraint function.The coefficient controlling metric regularity measures stability under perturbations of equations, and the result applies to systems F(x) ∈ C with C convex, closed, and nonempty.
- Applications: For rank reduction, the algorithm applied to the semialgebraic formulation generates a sequence converging to a critical point with the matrix variable in the constraint set.The example concerns finding a low-rank correlation matrix close to a given symmetric matrix.
- Tame functions: Semialgebraic and definable functions have the Kurdyka-Łojasiewicz property, with semialgebraic functions admitting ϕ(s) = cs^(1−θ) for θ ∈ [0,1) ∩ Q.The paper emphasizes that identifying the minimal definable structure can affect convergence-rate analysis.
- Applications: For compressive sensing, proximal alternating minimization yields a convergent reweighted ℓ1 scheme whose limit satisfies the corresponding reweighted minimization problem.The original reweighted ℓ1 method is represented as alternating minimization of an auxiliary function, while the proximal version is governed by the paper’s convergence theorem.
- Projection applications: For projection problems, the squared-distance objective is globally subanalytic, and the Kurdyka-Łojasiewicz property holds for transverse manifolds and broader regular intersections.These properties place the associated alternating projection sequences within the paper’s convergence framework.