Linear and proximal programming · Definition

Proximal gradient method

continuous optimizationlinear and proximal programming

Before you start you need to know

When part of the objective is smooth and part is not, it is useful to treat each separately. This method combines both ideas in a single iteration.

Definition

Proximal gradient minimizes \( f(x)+g(x) \), with \( f \) convex and smooth and \( g \) convex but possibly nondifferentiable, alternating a gradient step on \( f \) and a proximal step on \( g \).

\[x_{k+1}=\operatorname{prox}_{t_k g}\left(x_k-t_k\nabla f(x_k)\right)\]

If \( f \) has an \( L \)-Lipschitz gradient and \( g \) is convex and closed, with step \( t \in (0, 1/L] \) the generated sequence satisfies \( F(x_k)-F^* \le \frac{\|x_0-x^*\|^2}{2tk} \), where \( F=f+g \). When \( g=0 \) the method reduces to classical gradient descent, and when \( f=0 \) it reduces to the proximal point algorithm.

Consider minimizing \( \tfrac12\|Ax-b\|^2+\lambda\|x\|_1 \). Here \( f(x)=\tfrac12\|Ax-b\|^2 \) has gradient \( A^\top(Ax-b) \), and \( g(x)=\lambda\|x\|_1 \) has a prox given componentwise by soft thresholding. Each iteration takes a gradient step on \( f \) and then applies thresholding, producing sparse solutions.

A typical mistake is applying the gradient step also to \( g \), that is, differentiating \( \|x\|_1 \) where it does not exist. This prevents using the method when \( g \) has corners. The correct rule is to evaluate the gradient only on \( f \) and leave \( g \) to the proximal operator.

Think about it

Why can't the gradient of \( g \) be taken at \( x=0 \) when \( g(x)=|x| \)?

Because \( |x| \) is not differentiable at \( 0 \), so no gradient exists and \( g \) is handled by the proximal operator instead.

Exercises 10

  1. Which function \( g \) appears in the proximal gradient method for minimizing \( f(x)+g(x) \) when \( f \) is smooth?
  2. Which operation is applied to \( g \) in each iteration of the method?
  3. If \( g=0 \), which method does proximal gradient reduce to?
  4. What condition must the gradient of \( f \) satisfy for standard convergence guarantees?
  5. For \( g(x)=\lambda\|x\|_1 \), what does the proximal operator produce componentwise?
  6. If \( f(x)=\tfrac12\|x-a\|^2 \) and \( g=0 \), what is the result of one step with \( t=1 \) from \( x_k \)?
  7. If \( g(x)=\lambda|x| \) in one dimension and the point \( z=0.3 \) with \( t\lambda=0.5 \), what is \( \operatorname{prox}_{tg}(z) \)?
  8. With \( f(x)=\tfrac12 x^2 \) and \( g(x)=|x| \) in one dimension, what is the iterate after one step with \( t=1 \) from \( x_0=4 \)?
  9. Which of the following statements about the bound \( F(x_k)-F^*\le \frac{\|x_0-x^*\|^2}{2tk} \) is correct?
  10. Minimize \( \tfrac12(x-6)^2+|x| \) over \( \mathbb{R} \) with one proximal gradient step using \( t=1 \) from \( x_0=0 \). What is \( x_1 \)?

References

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.