A primal-dual flow for affine constrained convex optimization

Hao LuoarXiv 2021 · DOI · arXiv

TL;DR

This paper introduces a novel "primal-dual flow"—a continuous-time dynamical system—designed to solve convex optimization problems with affine constraints. By modifying standard saddle-point equations with a clever extrapolation term, the author proves the system achieves exponential decay and translates this into discrete algorithms with global, nonergodic linear convergence rates.

What Problem Does This Paper Address?

Many real-world problems, from compressed sensing to image processing, involve minimizing a convex function $f(x)$ subject to linear constraints ($Ax = b$). While we have many algorithms to solve these, two issues often persist:

  1. Oscillation: Standard saddle-point methods (which try to find a balance between the primal variable $x$ and the dual multiplier $\lambda$) often suffer from high-frequency oscillations that slow down convergence.
  2. Convergence Rates: Most existing primal-dual methods offer "ergodic" convergence, meaning the average of your guesses gets closer to the solution at a rate of $O(1/k^2)$. Achieving a "nonergodic" rate—where the actual current guess converges linearly—is much harder to guarantee for general convex problems.

The author tackles these by looking at the problem through the lens of dynamical systems, treating the optimization process as a continuous flow that "drains" toward the optimal solution.

Methods

The core contribution is a modified primal-dual flow (Equation 15 in the paper). Unlike the classical system, this one introduces:

  • Time Rescaling Factors: Two scaling factors ($\gamma$ and $\beta$) that automatically adjust based on the convexity of the objective function.
  • Extrapolation Term: The dual update uses $\nabla_\lambda \mathcal{L}(x + x', \lambda)$ instead of the standard $\nabla_\lambda \mathcal{L}(x, \lambda)$. This small change ($x'$ is the derivative of $x$) acts as a stabilizer.
  • Lyapunov Analysis: The author uses a tailored "energy function" (Lyapunov function) to prove that the system's distance from the optimal solution decays exponentially ($e^{-t}$).

To turn this theory into software, the paper proposes two discretization schemes:

  1. Implicit Primal-Dual (Im-PD): A fully implicit scheme that inherits the exponential decay property.
  2. Semi-Implicit Primal-Dual (Semi-PDPG): A scheme designed for composite functions (e.g., $f(x) = h(x) + g(x)$ where $h$ is smooth and $g$ is not).

Crucially, instead of solving the primal subproblem directly, the author applies a Semi-smooth Newton (SsN) iteration to the dual multiplier subproblem, which is highly efficient when the problem has sparse or piecewise-linear structures.

Datasets

The paper evaluates the algorithms on two classic optimization benchmarks:

  • $l_1$-$l_2$ Minimization: A regularized basis pursuit model used in compressed sensing.
  • ROF Image Denoising: A Total-Variation (TV) based model. For this, the author uses four standard benchmark images: barb, boat, cameraman, and lena, all corrupted with standard normal noise.

Key Insights and Ideas

  • The Power of $x + x'$: The inclusion of the derivative $x'$ in the dual update is the "secret sauce." It cancels out cross-terms in the energy analysis that otherwise prevent proving exponential decay.
  • Continuous to Discrete Bridge: The paper shows that the popular Primal-Dual Hybrid Gradient (PDHG) algorithm can be viewed as a specific discretization of this modified flow, providing a new theoretical justification for why PDHG's "over-relaxation" works so well.
  • Stability over Speed: The equilibrium analysis demonstrates that while standard systems might spin around the solution indefinitely, this modified flow "sinks" into the solution by increasing the negativity of the system's eigenvalues.

Key Results

  • Linear Convergence: The algorithms achieve global linear convergence rates even for problems that aren't strongly convex, provided the step size is managed correctly.
  • Efficiency in Denoising: In the ROF image denoising tests, the Inexact Im-PD method reached the target KKT tolerance ($10^{-6}$) in roughly 10 total iterations. In contrast, baseline methods like PDHG and A-ADMM required thousands of iterations to reach the same accuracy.
  • Robustness: The method proved significantly more robust than the Accelerated Linearized Bregman (ALB) method as the regularization parameter $\rho$ became very small (making the problem more "degenerate").

Limitations and Future Work

  • Nonsmooth Well-posedness: While the flow works beautifully for smooth functions, the author notes that the theoretical "well-posedness" (existence and uniqueness of the solution) for the flow under general nonsmooth conditions is still an open question for future research.
  • Inexact Computation: The current convergence proofs assume subproblems are solved exactly. While the numerical tests use a "restart" technique to handle inexactness, a more rigorous theoretical analysis of convergence under inexact Newton steps is needed.
  • Linear Solver Scalability: For very large-scale problems, the efficiency of the method depends on the ability to solve the Newton system quickly. The author suggests exploring algebraic multilevel methods for even better scaling.

Summary updated

Abstract

We introduce a novel primal-dual flow for affine constrained convex optimization problems. As a modification of the standard saddle-point system, our primal-dual flow is proved to possess the exponential decay property, in terms of a tailored Lyapunov function. Then two primal-dual methods are obtained from numerical discretizations of the continuous model, and global nonergodic linear convergence rate is established via a discrete Lyapunov function. Instead of solving the subproblem of the primal variable, we apply the semi-smooth Newton iteration to the subproblem with respect to the multiplier, provided that there are some additional properties such as semi-smoothness and sparsity. Especially, numerical tests on the linearly constrained $l_1$-$l_2$ minimization and the total-variation based image denoising model have been provided.
BibTeX
@misc{luo2021primal,
  author = {Hao Luo},
  title = {{A primal-dual flow for affine constrained convex optimization}},
  year = {2021},
  eprint = {2103.06636},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2103.06636},
}
Figure