Linear and proximal programming · Definition

Proximal operator

continuous optimizationlinear and proximal programming

Before you start you need to know

When a function is not differentiable everywhere, classical gradient descent cannot be applied directly. The proximal operator overcomes this by combining the function with a quadratic term that keeps the solution close to the starting point.

Definition

The proximal operator of a convex function \( f \) maps each point \( x \) to the unique minimizer of \( f(u)+\frac{1}{2}\|u-x\|^2 \).

\[\operatorname{prox}_{f}(x)=\arg\min_{u}\left\{f(u)+\tfrac{1}{2}\|u-x\|^2\right\}\]

For \( f \) convex, closed and proper, the minimization problem has a unique solution because the term \( \frac{1}{2}\|u-x\|^2 \) is strictly convex. Moreover, \( \operatorname{prox}_{f}(x) \) is characterized by \( x-\operatorname{prox}_{f}(x)\in\partial f(\operatorname{prox}_{f}(x)) \), where \( \partial f \) is the subdifferential.

If \( f(u)=\lambda|u| \) on \( \mathbb{R} \), the proximal operator is the soft-thresholding function: \( \operatorname{prox}_{f}(x)=\operatorname{sign}(x)\max(|x|-\lambda,0) \). For \( x=3 \) and \( \lambda=1 \) the result is \( 2 \), the point where the penalty and the distance to \( x \) balance.

A typical mistake is forgetting the factor \( \frac{1}{2} \) in the quadratic term, which changes the operator and gives wrong results. Another common error is confusing the proximal operator with projection: projection is the special case where \( f \) is the indicator function of a convex set.

Think about it

If \( f \) were not convex, why could \( \operatorname{prox}_{f} \) fail to be a function?

Because the problem may have several minimizers, so the result would be a set of points rather than a single one.

Exercises 10

  1. What is the value of \( \operatorname{prox}_{f}(x) \) for \( f(u)=0 \)?
  2. For \( f(u)=\frac{1}{2}u^2 \), what is the proximal operator at \( x \)?
  3. What is the proximal operator at \( x=0.5 \) when \( f(u)=|u| \)?
  4. Which condition characterizes \( p=\operatorname{prox}_{f}(x) \)?
  5. What is \( \operatorname{prox}_{f}(x) \) if \( f(u)=2u \) and \( x=1 \)?
  6. For \( f(u)=\lambda|u| \) with \( \lambda=2 \), what is \( \operatorname{prox}_{f}(-5) \)?
  7. If \( f(u)=\frac{1}{2}u^2 \) and \( x=4 \), what is \( \operatorname{prox}_{f}(x) \)?
  8. For \( f(u)=|u| \) and \( x=-0.5 \), what is \( \operatorname{prox}_{f}(x) \)?
  9. What is \( \operatorname{prox}_{f}(x) \) for \( f(u)=\lambda|u| \) with \( \lambda=1 \) and \( x=0.8 \)?
  10. Let \( f(u)=\lambda|u| \) with \( \lambda=1 \). Compute \( \operatorname{prox}_{f}(x) \) for \( x=-2.5 \) and decide which statement is true when checking \( x-p\in\partial f(p) \).

References

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