33.3.1 General Results
Definition 33.3.1 Let X be a real locally convex topological vector space. For x ∈ X ,
δϕ
⊆ X ^{′} , possibly ∅ . This subset of X ^{′} is defined by y ^{∗} ∈ δϕ means for all
z ∈ X ,
y∗ (z − x) ≤ ϕ(z)− ϕ (x ).
Also x ∈ δϕ ^{∗}
means that for all z ^{∗} ∈ X ^{′} ,
(z∗ − y∗)(x) ≤ ϕ ∗(z∗) − ϕ ∗(y∗).
We define dom
≡ .
The subgradient is an attempt to generalize the derivative. For example, a function may
have a subgradient but fail to be differentiable at some point. A good example is
f
=
. At
x = 0, this function fails to have a derivative but it does have a
subgradient. In fact,
δf =
.
To begin with consider the question of existence of the subgradient of a convex
function. There is a very simple criterion for existence. It is essentially that the
subgradient is nonempty at every point of the interior of the domain of ϕ . First recall
Lemma 16.2.15 which says the interior of a convex set is convex and if nonempty, then
every point of the convex set can be obtained as the limit of a sequence of points of the
interior.
Theorem 33.3.2 Let ϕ : X → (−∞ , ∞ ] be convex and suppose for some u ∈ dom
,
ϕ is continuous. Then δϕ ≠ ∅ for all x ∈ int . Thus
dom (δϕ) ⊇ int(dom (ϕ)) .
Proof: Let x _{0} ∈ int
and let
A ≡ {(x0,ϕ(x0))} ,B ≡ epi(ϕ)∩ X × ℝ.
Then A and B are both nonempty and convex. Recall epi
can contain a point like
. Since
ϕ is continuous at
u ∈ dom ,
(u,ϕ(u)+ 1) ∈ int(epiϕ∩ X × ℝ) .
Thus int
≠ ∅ and also
int ∩ A =
∅ . By Lemma
16.2.15 int is convex and so by
Theorem
16.2.14 there exists
x ^{∗} ∈ X ^{′} and
β ∈ ℝ such that
(x∗,β ) ⁄= (0,0) (33.3.17)
(33.3.17)
and for all
∈ int B ,
∗ ∗
x (x)+ βa > x (x0)+ βϕ(x0). (33.3.18)
(33.3.18)
From Lemma 16.2.15 , whenever x ∈ dom
,
x∗ (x) +β ϕ(x) ≥ x∗(x )+ βϕ (x ).
0 0
If β = 0, this would mean x ^{∗}
≥ 0 for all
x ∈ dom . Since
x _{0} ∈ int ,
this implies
x ^{∗} = 0, contradicting
33.3.17 . If
β < 0, apply
33.3.18 to the case
when
a =
ϕ + 1 and
x =
x _{0} to obtain a contradiction. It follows
β > 0 and
so
x∗
ϕ(x)− ϕ(x0) ≥ −-- (x − x0)
β
which says − x ^{∗} ∕β ∈ δϕ
. This proves the theorem.
Definition 33.3.3 Let ϕ : X → (−∞ , ∞ ] be some function, not necessarily
convex but satisfying ϕ
< ∞ for some y ∈ X . Define ϕ ^{∗} :
X ^{′} → (
−∞ , ∞ ]
by
ϕ∗ (x∗) ≡ sup {x∗(y)− ϕ(y) : y ∈ X} .
This function, ϕ ^{∗} , defined above, is called the conjugate function of ϕ or the polar of
ϕ . Note ϕ ^{∗}
≠ −∞ because
ϕ < ∞ for some
y .
Theorem 33.3.4 Let X be a real Banach space. Then ϕ ^{∗} is convex and l.s.c .
Proof: Let λ ∈
. Then
ϕ∗(λx∗ + (1− λ)y∗) = sup {(λx∗ + (1 − λ)y∗)(y)− ϕ(y) : y ∈ X }
∗ ∗
sup{λ (x (y) − ϕ (y)) +(1 − λ)(y (y) − ϕ (y)) : y ∈ X }
≤ λϕ∗ (x∗) +(1 − λ )ϕ∗(y∗).
It remains to show the function is l.s.c . Consider f _{y}
≡ x ^{∗} − ϕ . Then
f _{y} is
obviously convex. Also to say that
∈ epi is to say that
α ≥ x ^{∗} − ϕ for
all
y. Thus
Therefore, if epi
is closed, this will prove the theorem. If
epi , then
a < x ^{∗} − ϕ and, by continuity, for
b close enough to
a and
y ^{∗} close enough to
x ^{∗}
then
b < y∗(y)− ϕ(y), (y∗,b) ∕∈ epi(f )
y
Thus epi
is closed.
■
Note this theorem holds with no change in the proof if X is only a locally convex
topological vector space and X ^{′} is given the weak ∗ topology.
Definition 33.3.5 We define ϕ ^{∗∗} on X by
ϕ∗∗(x) ≡ sup{x∗(x)− ϕ ∗(x ∗),x∗ ∈ X′}.
The following lemma comes from separation theorems. First is a simple
observation.
Observation 33.3.6 f ∈
^{′} if and only if there exists x ^{∗} ∈ X ^{′} and α ∈ ℝ
such that f =
x ^{∗} +
λα . To get x ^{∗} , you can simply define x ^{∗} ≡ f
and to get α you just let αλ ≡ f . Why does such an α exist? You know that
f =
af +
bf and so in fact λ → f satisfies the Cauchy
functional equation g =
g +
g and is continuous so there is only one
thing it can be and that is f =
αλ for some α .
This picture illustrates the conclusion of the following lemma.
Lemma 33.3.7 Let ϕ : X → (−∞ , ∞ ] be convex and lower semicontinuous and
ϕ
< ∞ for some x . (proper). Then if β < ϕ so that is not in epi , it
follows that there exists δ > 0
and z ^{∗} ∈ X ^{′} such that for all y,
z∗ (y − x0)+ β + δ < ϕ(y), all y ∈ X
Proof: Let C = epi
∩ . Then
C is a closed convex nonempty set and it
does not contain the point
. Let
> β be slightly larger so that also
C . Thus there exists
y ^{∗} ∈ X ^{′} and
α ∈ ℝ such that for some
ĉ , and all
y ∈ X,
y∗(x0)+ αˆβ > ˆc > y∗(y)+ αϕ (y)
for all y ∈ X . Now you can’t have α ≥ 0 because
( ) ∗
α ˆβ − ϕ(y) > y (y − x0)
and you can let y = x _{0} to have
( )
◜--<◞0◟---◝
α|( ˆβ − ϕ(x0)|) > 0
Hence α < 0 and so, dividing by it yields that for all y ∈ X,
x∗(x0)+ ˆβ < c < x∗(y)+ ϕ (y)
where x ^{∗} = y ^{∗} ∕α, ĉ ∕α ≡ c . Then
∗ ( ) ∗
(− x )(y− x0)+ β + ˆβ − β < c− x (y) < ϕ (y)
∗ ˆ
(− x )(y− x0)+ β + δ < ϕ(y), δ ≡ β − β
Let
z ^{∗} =
− x ^{∗} .
■
Theorem 33.3.8 ϕ ^{∗∗}
≤ ϕ for all x and if ϕ is convex and l.s.c. , ϕ ^{∗∗} =
ϕ for all x ∈ X .
Proof:
( ∗ ∗ )
|{ ◜--------ϕ-(◞x◟)--------◝ |}
ϕ∗∗(x) ≡ sup x∗(x)− sup{x∗ (y) − ϕ (y) : y ∈ X } : x∗ ∈ X ′
|( |)
≤ sup{x∗(x)− (x∗(x)− ϕ (x ))} = ϕ(x).
Next suppose ϕ is convex and l.s.c . If ϕ ^{∗∗}
< ϕ , then using Lemma
33.3.7 ,
there exists
x _{0} ^{∗} ,δ > 0 such that for all
y ∈ X ,
(x∗0)(y− x0)+ ϕ∗∗(x0)+ δ < ϕ(y)
x∗ (y) − ϕ (y)+ δ < x∗(x )− ϕ∗∗(x )
0 0 0 0
Thus, since this holds for all y,
ϕ∗(x∗0)+ δ ≤ x∗0 (x0)− ϕ∗∗(x0)
ϕ∗∗(x )+ δ ≤ x∗ (x )− ϕ∗ (x∗)
0 0 0 0
Then
ϕ∗∗(x ) ≡ sup {x∗(x )− ϕ∗(x∗),x∗ ∈ X ′}
0 ∗ 0∗ ∗ ∗∗
≥ x0(x0)− ϕ (x0) ≥ ϕ (x0)+ δ
a contradiction.
■
The following corollary is descriptive of the situation just discussed. It says that to
find epi
it suffices to take the intersection of all closed convex sets which contain
epi .
Corollary 33.3.9 epi
is the smallest closed convex set containing epi .
Proof: epi
⊇ epi from Theorem
33.3.8 . Also
epi is closed by the proof
of Theorem
33.3.4 . Suppose
epi ⊆ K ⊆ epi and
K is convex and closed.
Let
ψ (x) ≡ min{a : (x,a) ∈ K} .
(
is a closed subset of (
−∞ , ∞ ] so the minimum exists.)
ψ is also a
convex function with
epi =
K . To see
ψ is convex, let
λ ∈ . Then, by the
convexity of
K ,
λ(x,ψ(x))+ (1− λ)(y,ψ(y))
= (λx+ (1− λ)y,λψ (x)+ (1− λ)ψ (y)) ∈ K.
It follows from the definition of ψ that
ψ (λx + (1− λ)y) ≤ λ ψ(x)+ (1− λ)ψ (y).
Then
and so from the definitions,
which implies from the definitions and Theorem 33.3.8 that
ϕ∗∗ = ϕ∗∗∗∗ ≤ ψ∗∗ = ψ ≤ ϕ∗∗.
Therefore, ψ = ϕ ^{∗∗} and epi
is the smallest closed convex set containing
epi as
claimed.
■
There is an interesting symmetry which relates δϕ,δϕ ^{∗} ,ϕ , and ϕ ^{∗} .
Theorem 33.3.10 Suppose ϕ is convex, l.s.c. (lower semicontinuous or in other words
having a closed epigraph), and proper. Then
∗ ∗ ∗
y ∈ δϕ (x) if and only if x ∈ δϕ (y )
where this last expression means
∗ ∗ ∗ ∗ ∗ ∗
(z − y )(x) ≤ ϕ (z )− ϕ (y )
for all z ^{∗} and in this case,
Proof: If y ^{∗} ∈ δϕ
then
y ^{∗} ≤ ϕ − ϕ and so
y∗(z)− ϕ(z) ≤ y∗(x)− ϕ (x )
for all z ∈ X . Therefore,
ϕ∗(y∗) ≤ y∗(x)− ϕ (x ) ≤ ϕ∗(y∗).
Hence
y∗(x) = ϕ ∗(y∗) +ϕ (x). (33.3.19)
(33.3.19)
Now if z ^{∗} ∈ X ^{′} is arbitrary, 33.3.19 shows
∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
(z − y )(x) = z (x)− y (x) = z (x)− ϕ (x) − ϕ (y) ≤ ϕ (z )− ϕ (y )