Scribd
Upload
8 views3 pages

Subgradient and Subdifferential Explained

Chapter 9 discusses subgradients and subdifferentials of proper functions, defining the subdifferential at a point and establishing the Fermat Rule for global minimizers. It provides examples of subdifferentials for specific functions and outlines properties such as convexity and monotonicity. Additionally, it presents rules for subgradient calculus involving non-negative linear combinations and affine transformations of variables.

Uploaded by

Caporal Fourrier
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views3 pages

Subgradient and Subdifferential Explained

Chapter 9 discusses subgradients and subdifferentials of proper functions, defining the subdifferential at a point and establishing the Fermat Rule for global minimizers. It provides examples of subdifferentials for specific functions and outlines properties such as convexity and monotonicity. Additionally, it presents rules for subgradient calculus involving non-negative linear combinations and affine transformations of variables.

Uploaded by

Caporal Fourrier
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1

Chapter 9: Subgradient
Definition (Subgradients and Subdifferential). Let f : X → (−∞, +∞] be proper.
Then the subdifferential of f at x ∈ X is

∂f (x) := {u ∈ X | ∀y ∈ X, f (x) + ⟨y − x, u⟩ ≤ f (y)} .

subgradient affine minorant of f


Moreover,
dom ∂f := {x ∈ X | ∂f (x) ̸= ∅} ⊆ dom f.
Lemma (Fermat Rule). Let f : X → (−∞, +∞] be proper, and let x ∈ X. Then

0 ∈ ∂f (x) ⇔ x is a global minimizer of f.

Proof.
0 ∈ ∂f (x) ⇔ f (x) + ⟨y − x, 0⟩ ≤ f (y) ∀y ∈ X
⇔ f (x) ≤ f (y) ∀y ∈ X
⇔ x is a global minimizer.
Example. Let f : R → R be defined by f (x) = |x|.
The function is not differentiable at x = 0, and its subdifferential is given by:

{−1}, x < 0

∂f (x) = [−1, 1], x = 0

{1}, x>0

2

Prop: Let f = ∥ · ∥ be any norm on X. Then

∂f (0) = {u ∈ X | ∥u∥∗ ≤ 1}

Example: Suppose X = Sn , and that f maps A ∈ X to its largest eigenvalue, i.e.


f (A) = λmax (A). Given A ∈ X, let v be the normalized eigenvector of A corresponding to
the eigenvalue f (A). Then, one can show vv ⊤ ∈ ∂f (A).
Proposition: Let f : X → [−∞, ∞] be proper and let x ∈ X. Then ∂f (x) is convex
and closed. Furthermore, ∂f is a monotone operator, i.e.

(∀u ∈ ∂f (x))(∀v ∈ ∂f (y)) ⟨x − y, u − v⟩ ≥ 0

Let f (in previous proposition) be convex. If x ∈ int dom f , then ∂f (x) is nonempty and
bounded.
Example: Let f (x) = max{f1 (x), f2 (x)}, with f1 and f2 convex and differentiable.

• If f1 (x̂) = f2 (x̂), subdifferential at x̂ is the line segment

[∇f1 (x̂), ∇f2 (x̂)]

• If f1 (x̂) > f2 (x̂), subdifferential is a singleton:

∂f (x̂) = {∇f1 (x̂)}

• If f2 (x̂) > f1 (x̂), subdifferential is a singleton:

∂f (x̂) = {∇f2 (x̂)}

Other example: f (x) = ∥x∥2 (not differentiable at x = ⃗0)


(n o
1
∥x∥2
x x ̸= ⃗0
∂f (x) =
{g | ∥g∥2 ≤ 1} x = ⃗0
3

Rules for Subgradient Calculus


1. Non-negative Linear Combination
If
f (x) = α1 f1 (x) + α2 f2 (x) with α1 , α2 ≥ 0,
then
∂f (x) = α1 ∂f1 (x) + α2 ∂f2 (x)
(where the right-hand side is a set sum).

2. Affine Transformation of Variables


If
f (x) = h(Ax + b),
then
∂f (x) = A⊤ ∂h(Ax + b).

You might also like