Inertial accelerated primal-dual algorithms for non-smooth convex optimization problems with linear equality constraints

This paper proposes an inertial accelerated primal-dual algorithm derived from a time-scaled second-order differential system to solve non-smooth convex optimization problems with linear equality constraints, establishing fast convergence rates for the primal-dual gap, feasibility violation, and objective residual, and validating its performance through numerical experiments.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy, and bumpy landscape (the optimization problem). However, there's a catch: you are only allowed to walk along a very specific, narrow path drawn on the ground (the linear equality constraints). If you step off the path, you fail.

This paper introduces a new, super-fast way to find that lowest point while staying strictly on the path, even when the ground is rough and uneven (the non-smooth part).

Here is the breakdown of their invention, the Inertial Accelerated Primal-Dual Algorithm (IAPDA), using some everyday analogies.

1. The Problem: The Foggy Hike

In the real world, many problems (like restoring a blurry photo or training an AI) are like hiking in a fog. You can't see the whole mountain; you can only feel the ground under your feet.

• The "Non-Smooth" part: Imagine the ground isn't just a smooth hill; it has jagged rocks and sudden cliffs. Standard hikers (algorithms) often get stuck or have to stop and feel their way carefully around these rocks, which is slow.
• The "Constraint" part: You must stay on a tightrope. If you drift even a little to the left or right, you fall.

2. The Old Way: The Careful Crawler

Previous methods were like a hiker who takes one small, cautious step at a time. They check the ground, adjust their balance, take a step, check again, and repeat.

• Primal-Dual Systems: Think of this as having two people hiking together. One person (the Primal) tries to find the low ground, while the other (the Dual) constantly yells, "Hey, you're drifting off the tightrope! Pull back!" They talk back and forth to correct each other.
• The Issue: This conversation is slow. They often overshoot, correct, overshoot again, and wobble a lot before finally settling down.

3. The New Solution: The "Momentum" Skier

The authors propose a new method called IAPDA. Instead of a cautious hiker, imagine a skier or a skateboarder.

The Secret Sauce: Inertia (Momentum)

In physics, inertia is the tendency of a moving object to keep moving.

• The Analogy: If you are skiing down a hill, you don't stop at every bump. You use your speed (momentum) to glide over the rough spots. If you start to drift off the path, your momentum carries you forward, but your "steering" (the algorithm's math) gently nudges you back on course without stopping your speed.
• The Paper's Innovation: They added a "time-scaling" feature. Imagine the skier gets a little boost of speed as they go further down the hill, allowing them to cover ground much faster than a walker ever could.

The "Second-Order" System

The paper starts with a complex mathematical model (a differential equation) that describes how this skier moves.

• Viscous Damping: This is like air resistance. It slows the skier down just enough so they don't crash into a tree, but not so much that they stop.
• Extrapolation: This is the skier looking ahead. Instead of just reacting to the ground under their feet, they predict where the ground will be in the next second and lean into that direction.

4. How It Works in Practice

The authors took this continuous "skier" model and turned it into a step-by-step computer recipe (an algorithm).

1. The Setup: They define the "Lagrangian," which is essentially a scorecard. It adds up the "badness" of being high up on the mountain and the "badness" of being off the tightrope.
2. The Move: In every step, the algorithm:
   • Looks at where it is.
   • Looks at where it was (to use momentum).
   • Calculates a "push" to get lower and stay on the rope.
   • Takes a big, confident step.
3. The Result: Because of the momentum and the "look-ahead" feature, the algorithm doesn't just wiggle toward the solution; it zooms toward it.

5. The Proof: Why It's Better

The paper proves mathematically that this new skier reaches the bottom much faster than the old hikers.

• Old Hikers: Might take $100$ steps to get close to the answer.
• The New Skier (IAPDA): Might only take $10$ steps to get the same accuracy.
• The Math: They showed that the "error" (how far you are from the perfect spot) shrinks incredibly fast—specifically, it shrinks by the square of the number of steps. This is a massive speedup.

6. The Real-World Test

To prove it works, they tested it on two problems:

1. Cleaning up a noisy signal: Like trying to hear a whisper in a loud room. The new algorithm found the clear voice much faster than the old methods.
2. Fitting data to a shape: Like trying to force a square peg into a round hole as efficiently as possible. Again, the new method was faster and more stable.

Summary

This paper is about building a super-efficient navigation system for complex problems.

• The Problem: Finding the best solution while following strict rules, on a bumpy road.
• The Solution: A "skier" that uses momentum (inertia) and foresight (extrapolation) to glide over obstacles and stay on the path.
• The Benefit: It solves difficult math problems in computers significantly faster than previous methods, saving time and energy for things like medical imaging, AI training, and financial modeling.

In short: Don't just walk; skate with momentum.

Technical Summary

Here is a detailed technical summary of the paper "Inertial accelerated primal-dual algorithms for non-smooth convex optimization problems with linear equality constraints."

1. Problem Statement

The paper addresses the optimization of non-smooth convex functions subject to linear equality constraints. The specific problem formulation is:

$$\begin{aligned} \min_{x \in H} \quad & f(x) + g(x) \\ \text{s.t.} \quad & Ax = b \end{aligned}$$

Where:

• $H$ and $G$ are real Hilbert spaces.
• $f: H \to \mathbb{R}$ is a differentiable convex function with a Lipschitz continuous gradient.
• $g: H \to \mathbb{R}$ is a proper, convex, and lower semi-continuous function (allowing for non-smoothness, e.g., $\ell_1$-norm).
• $A: H \to G$ is a continuous linear operator, and $b \in G$.

This model is fundamental in fields such as image restoration, machine learning (e.g., Support Vector Machines), and sparse portfolio optimization.

2. Methodology

The authors employ a continuous-time dynamical systems approach to design and analyze a discrete algorithm. The methodology proceeds in three main stages:

A. Continuous-Time System Design

The authors propose a new second-order differential system with time scaling, viscous damping, and extrapolation. The system is defined as:

$$\begin{cases} \ddot{x}(t) + \frac{\alpha}{t} \dot{x}(t) + \beta(t) \partial_x L_\rho \left( x(t), \lambda(t) + \frac{t}{\alpha-1} \dot{\lambda}(t) \right) \ni 0 \\ \ddot{\lambda}(t) + \frac{\alpha}{t} \dot{\lambda}(t) - \beta(t) \nabla_\lambda L_\rho \left( x(t) + \frac{t}{\alpha-1} \dot{x}(t), \lambda(t) \right) = 0 \end{cases}$$

Key components of this system include:

• Viscous Damping: The term $\frac{\alpha}{t} \dot{x}(t)$ (with $\alpha \geq 3$) provides asymptotically vanishing damping.
• Time Scaling: The function $\beta(t)$ is a non-decreasing, continuously differentiable scaling factor that accelerates convergence.
• Extrapolation: The terms involving $\frac{t}{\alpha-1}$ introduce inertial effects (momentum) similar to Nesterov's acceleration.
• Augmented Lagrangian: The system utilizes the augmented Lagrangian function $L_\rho$ to handle the constraints.

B. Continuous-Time Convergence Analysis

Using Lyapunov analysis, the authors establish fast convergence rates for the trajectories generated by the differential system. They define an energy function $E(t)$ and prove that under mild assumptions on parameters ($\alpha \geq 3$ and specific bounds on $\beta(t)$):

• The primal-dual gap converges at a rate of $O\left(\frac{1}{t^2 \beta(t)}\right)$.
• The feasibility violation ($\|Ax(t) - b\|$) and objective residual converge at a rate of $O\left(\frac{1}{t \sqrt{\beta(t)}}\right)$.

C. Discretization and Algorithm Proposal

The continuous system is discretized to derive a practical iterative algorithm, termed IAPDA (Inertial Accelerated Primal-Dual Algorithm).

• Discretization Scheme: The authors use implicit finite-difference schemes and specific variable transformations (e.g., $u_k, v_k$) to convert the differential equations into an iterative update rule.
• Algorithm Steps:
  1. Extrapolation: Compute extrapolated points $\bar{x}_k$ and $\mu_k$ using previous iterates.
  2. Primal Update: Solve a proximal minimization subproblem involving the gradient of $f$, the subgradient of $g$, and the augmented Lagrangian term. This subproblem is solved using FISTA (Fast Iterative Shrinkage-Thresholding Algorithm) in the numerical experiments.
  3. Dual Update: Update the dual variable $\lambda_{k+1}$ based on the constraint violation.

3. Key Contributions

1. Novel Differential System: Introduction of a second-order primal-dual dynamical system that uniquely combines viscous damping, extrapolation, and time scaling specifically for non-smooth composite optimization.
2. Theoretical Convergence Rates:
   • Established $O\left(\frac{1}{t^2 \beta(t)}\right)$ convergence for the primal-dual gap in the continuous setting.
   • Proved that the discrete IAPDA algorithm inherits these rates, achieving $O\left(\frac{1}{k^2 \beta_k}\right)$ for the primal-dual gap, feasibility violation, and objective residual.
   • Demonstrated that specific choices of the sequence $\{t_k\}$ (e.g., Nesterov's rule, Chambolle-Dossal rule, Attouch-Cabot rule) yield optimal rates.
3. Generalization: The results generalize existing works (e.g., Bot et al., Zeng et al.) by extending slow vanishing damping systems to include time scaling, thereby achieving faster convergence.
4. Practical Validation: Provided numerical experiments showing the algorithm's superiority over state-of-the-art methods.

4. Results

Theoretical Results

• Iterate Convergence: The sequence of iterates $\{(x_k, \lambda_k)\}$ is bounded, and the step sizes satisfy $\|x_{k+1} - x_k\| = O(1/k)$ and $\|\lambda_{k+1} - \lambda_k\| = O(1/k)$.
• Objective Convergence: The algorithm achieves a non-ergodic convergence rate of $O(1/k^2)$ (assuming constant $\beta_k$) or faster if $\beta_k$ grows, significantly outperforming standard $O(1/k)$ rates.

Numerical Experiments

The authors tested IAPDA on two problems:

1. $\ell_1 - \ell_2$ Minimization (Sparse Signal Recovery):
   • Compared against Inertial Accelerated Augmented Lagrangian Method (IAALM) and Inertial Accelerated Linearized Primal-Dual (IALPD).
   • Result: IAPDA achieved significantly faster convergence and higher accuracy across various sub-tolerance levels ($\gamma = 10^{-4}, 10^{-6}, 10^{-8}$).
2. Non-negative Least Squares:
   • Compared against FISTA and Accelerated Forward-Backward Method (AFBM).
   • Result: IAPDA demonstrated superior stability and accuracy, particularly in high-dimensional settings ($m=1500, n=2000$), and was less sensitive to the density parameter $\gamma$ compared to competitors.

5. Significance

• Bridging Theory and Practice: The paper successfully bridges the gap between continuous-time dynamical systems theory and discrete optimization algorithms, providing a rigorous framework for designing accelerated methods.
• Handling Non-Smoothness: Unlike many previous works focusing on smooth objectives, this method effectively handles composite objectives ($f+g$) where $g$ is non-smooth, a common scenario in real-world applications like compressed sensing and machine learning.
• Acceleration via Time Scaling: The introduction of the time-scaling function $\beta(t)$ offers a flexible mechanism to tune convergence speeds, potentially allowing for rates faster than the standard $O(1/k^2)$ if $\beta(t)$ is chosen appropriately.
• Future Directions: The authors identify the convergence of the trajectories (weak convergence of the iterates themselves, not just the objective values) as an open challenge for future research, suggesting extensions to separable problems and Tikhonov regularization.

In summary, this paper presents a robust, theoretically grounded, and empirically superior algorithm for solving constrained non-smooth convex optimization problems, leveraging the power of inertial dynamics and time scaling.