2.4 Subgradients and subdifferentials

Subgradients and subdifferentials are key concepts in convex analysis, extending the idea of gradients to non-differentiable functions. They're crucial for understanding optimality conditions and developing optimization algorithms for non-smooth problems.

These tools allow us to analyze and solve a wider range of optimization problems. By generalizing gradients, we can tackle complex real-world issues where traditional calculus falls short, opening up new possibilities in optimization theory and practice.

Subgradients and Subdifferentials

Definition and Properties

Top images from around the web for Definition and Properties

• 

  (m,r)-Convex Functions View original

  Is this image relevant?

• 

  Convex function - Simple English Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Derivatives and the Shape of a Graph · Calculus View original

  Is this image relevant?

• 

  (m,r)-Convex Functions View original

  Is this image relevant?

• 

  Convex function - Simple English Wikipedia, the free encyclopedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Properties

• 

  (m,r)-Convex Functions View original

  Is this image relevant?

• 

  Convex function - Simple English Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Derivatives and the Shape of a Graph · Calculus View original

  Is this image relevant?

• 

  (m,r)-Convex Functions View original

  Is this image relevant?

• 

  Convex function - Simple English Wikipedia, the free encyclopedia View original

  Is this image relevant?

1 of 3

• Define a subgradient of a convex function $f$ at a point $x$ as a vector $v$ satisfying the subgradient inequality $f(y) \geq f(x) + \langle v, y - x \rangle$ for all $y$ in the domain of $f$
• Introduce the subdifferential of a convex function $f$ at a point $x$, denoted $\partial f(x)$, as the set of all subgradients of $f$ at $x$
• Establish that if $f$ is differentiable at $x$, then the subdifferential $\partial f(x)$ consists of a single element, the gradient $\nabla f(x)$
• Explain that the subdifferential generalizes the concept of the gradient for non-differentiable convex functions
• Show that the subdifferential is always a non-empty, convex, and compact set for convex functions

Examples and Applications

• Provide an example of a non-differentiable convex function (absolute value function) and illustrate its subgradients and subdifferential at various points
• Demonstrate how subgradients can be used to construct supporting hyperplanes for convex functions
• Discuss the role of subgradients in convex optimization, such as defining optimality conditions and designing optimization algorithms (subgradient methods)

Characterization of Subdifferentials

Subgradient Inequality and Monotonicity

• Characterize the subdifferential $\partial f(x)$ of a convex function $f$ at a point $x$ as the set of all vectors $v$ satisfying the subgradient inequality $f(y) \geq f(x) + \langle v, y - x \rangle$ for all $y$ in the domain of $f$
• Prove that the subdifferential of a convex function is a monotone operator, meaning that for any $x$, $y$ in the domain of $f$ and any subgradients $v \in \partial f(x)$ and $w \in \partial f(y)$, the inequality $\langle v - w, x - y \rangle \geq 0$ holds
• Illustrate the monotonicity property geometrically and discuss its implications for the behavior of subgradients

Calculus Rules for Subdifferentials

• Derive the subdifferential calculus rule for the sum of convex functions: $\partial(f + g)(x) = \partial f(x) + \partial g(x)$
• Establish the subdifferential calculus rule for a positive multiple of a convex function: $\partial(\alpha f)(x) = \alpha \partial f(x)$ for $\alpha > 0$
• Present the subdifferential calculus rule for the maximum of convex functions: $\partial(\max\{f_1, \ldots, f_n\})(x) = \mathrm{co}\{\bigcup_{i:f_i(x)=f(x)} \partial f_i(x)\}$, where $f(x) = \max\{f_1(x), \ldots, f_n(x)\}$
• Provide examples demonstrating the application of these calculus rules to compute subdifferentials of composite convex functions

Subgradients in Optimization

Subgradient Methods

• Introduce subgradient methods as iterative optimization algorithms that use subgradients to minimize non-differentiable convex functions
• Describe the subgradient method update rule: $x_{k+1} = x_k - \alpha_k v_k$, where $v_k \in \partial f(x_k)$ and $\alpha_k > 0$ is the step size
• Explain that the subgradient method is not a descent method, as the objective function value may increase from one iteration to the next
• Discuss the convergence properties of the subgradient method and the conditions on the step sizes required for convergence (square summable but not summable: $\sum_k \alpha_k^2 < \infty$ and $\sum_k \alpha_k = \infty$)

Optimality Conditions

• Use subgradients to define optimality conditions for convex optimization problems, such as the zero subgradient condition: $0 \in \partial f(x^*)$ if and only if $x^*$ is a global minimizer of $f$
• Compare and contrast the zero subgradient condition with the first-order necessary optimality condition for differentiable functions ($\nabla f(x^*) = 0$)
• Provide examples illustrating the application of the zero subgradient condition to verify the optimality of solutions to convex optimization problems

Subgradients vs Directional Derivatives

Directional Derivatives and Convexity

• Define the directional derivative of a function $f$ at a point $x$ in the direction $d$ as $f'(x; d) = \lim_{t \to 0^+} \frac{f(x + td) - f(x)}{t}$, when the limit exists
• Prove that for a convex function $f$, the directional derivative $f'(x; d)$ exists for all $x$ and $d$, and is given by $f'(x; d) = \max\{\langle v, d \rangle : v \in \partial f(x)\}$
• Show that if $f$ is differentiable at $x$, then the directional derivative $f'(x; d)$ is equal to $\langle \nabla f(x), d \rangle$ for all directions $d$

Relating Subgradients and Directional Derivatives

• Express the subgradient inequality in terms of directional derivatives: $v \in \partial f(x)$ if and only if $\langle v, d \rangle \leq f'(x; d)$ for all directions $d$
• Characterize the subdifferential using directional derivatives: $\partial f(x) = \{v : \langle v, d \rangle \leq f'(x; d) \text{ for all } d\}$
• Provide examples illustrating the relationship between subgradients and directional derivatives for specific convex functions (max function, absolute value function)