Davidson K.R., Donsig A.P. Real Analysis with Real Applications

Подождите немного. Документ загружается.

16.6 Convex Functions in Higher Dimensions 583

O. Suppose that A ⊂ R

is a convex set.

(a) Show that if f is convex on A and g is convex and increasing on R, then g ◦ f is

convex on A.

(b) Give an example of convex functions f, g on R so that g ◦ f is not convex.

16.6. Convex Functions in Higher Dimensions

In this section, we will show that convex functions are continuous on the rela-

tive interior of their domain. Then we will investigate certain sets that are deﬁned

in terms of convex functions.

This ﬁrst lemma would be trivial if f were known to be continuous.

16.6.1. LEMMA. Let f be a convex function deﬁned on a convex set A ⊂ R

If C is a compact convex subset of ri(A), then f is bounded on C.

PROOF. Since we are only working in A, there is no loss of generality in assuming

that aff(A) = R

and so ri(A) = int(A).

Fix a point a ∈ int(A), and choose ε > 0 so that

(a) ⊂ A. We ﬁrst

show that there is an r > 0 so that f is bounded on B

(a). Let e

, . . . , e

be an

orthonormal basis for R

, and deﬁne S = {a ± εe

: 1 ≤ i ≤ n}. Then let

M = max{f(s) : s ∈ S}. By Theorem 16.1.7, every point b in conv(S) has the

form b =

i=1

(a − εe

) + µ

(a + εe

), where λ

, µ

≥ 0 and

i=1

+ µ

= 1. By

Jensen’s inequality, f(b) ≤ M.

On the other hand, 2a −b = a −(b −a) lies in conv(S). Since f (2a−b) ≤ M,

f(a) ≤

f(b) + f(2a − b)

≤

f(b) + M

Thus f(b) ≥ 2f(a) − M. Therefore, f is bounded on S and

sup

b∈S

|f(b)| ≤ max

|M|, |2f(a) − M|

Now conv(S) contains the ball B

(a) where r = ε/

√

To complete the argument, we proceed via proof by contradiction. Suppose

that there is a sequence a

in C such that |f(a

)| tends to ∞. Since C is compact,

this sequence has a convergent subsequence, say a = lim

i→∞

. Let r > 0 and M

be chosen as before so that |f| is bounded by M on B

(a). There is an integer N

so that ka

− ak < r for all i ≥ N . Hence |f(a

)| ≤ M for i ≥ N , contrary to

our hypothesis. Thus f must be bounded on C. ¥

16.6.2. THEOREM. Let f be a convex function deﬁned on a convex set A ⊂ R

If C is a compact convex subset of ri(A), then f is Lipschitz on C. In particular, f

is continuous on ri(A).

584 Convexity and Optimization

PROOF. The set X = aff(A) \ ri(A) is closed. Deﬁne a function on A by

d(a) = dist(a, X) = inf{ka − xk : x ∈ X}.

Evidently, this is a continuous function, and d(a) = 0 only if a ∈ X. Now C

is a compact subset of ri(A), and thus d(a) > 0 for all a ∈ C. By the Extreme

Value Theorem (Theorem 5.4.4), the minimum value of d on C is attained. So

r =

inf{d(a) : a ∈ C} > 0.

Let C

= {a ∈ aff(A) : dist(a, C) ≤ r}. By construction, this is a closed

bounded set that is contained in ri(A). Thus it is compact by the Heine–Borel

Theorem (Theorem 4.4.6). The reader should verify that C

is convex.

By the preceding lemma, |f| is bounded on C

by some number M. Now

ﬁx points x, y ∈ C. Let ky − xk = R and e = (y − x)/R. Then the interval

[x − re, y + re] is contained in C

. The function g(t) = f(x + te) is a convex

function on [−r, R + r]. Thus the Secant Lemma (Lemma 16.5.8) applies:

g(0) − g(−r)

≤

g(R) − g(0)

≤

g(R + r) − g(R)

Rewriting and using the bound M yields

−2M

≤

f(y) − f(x)

ky − xk

≤

whence |f(y) − f(x)| ≤ Lky − xk for L = 2M/r.

This shows that f is Lipschitz and therefore continuous on each compact subset

of ri(A). In particular, for each a ∈ ri(A), there is a ball B

(a) ∩ aff(A) contained

in ri(A), and thus f is continuous on this ball about a. ¥

A basic question in many applications of analysis is how to minimize a func-

tion, often subject to various constraints. It is frequently the case in problems from

business, economics, and related ﬁelds that the functions and the constraints are

convex. These functions may be differentiable, in which case the usual multivari-

able calculus plays a role. However, even in this case, convexity theory provides a

useful perspective. When the functions are not all differentiable, this more sophis-

ticated machinery is necessary.

16.6.3. DEFINITION. Consider a convex function f on a convex set A ⊂ R

A point a

∈ A is a global minimizer for f on A if

f(a

) ≤ f (a) for all a ∈ A.

We call a

∈ A a local minimizer for f on A if there is an r > 0 so that

f(a

) ≤ f (a) for all a ∈ B

) ∩ A.

Clearly, a global minimizer is always a local minimizer. The converse is not

true for arbitrary functions. For convex functions they are the same, as we prove in

the next theorem. Henceforth, we drop the modiﬁer and refer only to minimizers.

16.6 Convex Functions in Higher Dimensions 585

16.6.4. THEOREM. Suppose that A ⊂ R

is a convex set, and consider a

convex function f on A. If a

∈ A is a local minimizer for f on A, then it is a

global minimizer for f on A. The set of all global minimizers of f on A is a convex

set.

PROOF. Suppose that a

minimizes f on B

) ∩ A. Let a ∈ A. As A is convex,

the line [a

, a] is contained in A. Therefore, there is some λ ∈ (0, 1) such that

λa

+ (1 − λ)a ∈ B

) ∩ A. By the convexity of f, we have

f(a

) ≤ f (λa

+ (1 − λ)a) ≤ λf(a

) + (1 −λ)f(a).

Solving this yields f(a

) ≤ f (a). Hence a

is a global minimizer.

The last statement follows from Exercise 16.6.A. ¥

A sublevel set of a convex function f on A has the form {a ∈ A : f(a) ≤ α}

for some α ∈ R. For convenience, we may assume α = 0 by the simple device of

replacing f by f −α. The constraints on the minimization problems which we will

consider have this form.

16.6.5. LEMMA. Let f be a convex function on R

. Suppose that there is a

point a

∈ R

with f (a

) < 0. Then int({x : f (x) ≤ 0}) = {x : f(x) < 0} and

{x : f (x) < 0} = {x : f(x) ≤ 0}.

PROOF. By Theorem 16.6.2, f is continuous. Thus A := {x : f(x) ≤ 0} is closed

and {x : f (x) < 0} is an open subset and so is contained in intA.

Let a ∈ int(A). Then the line segment [a

, a] extends beyond a in A to some

point, say b = (1 + ε)a − εa

. Thus a = λa

+ (1 − λ)b for λ = ε/(1 + ε). By

the convexity of f,

f(a) ≤ λf(a

) + (1 −λ)f(b) < 0.

Finally, Theorem 16.2.8 shows that intA = A. ¥

Exercises for Section 16.6

A. Suppose that A ⊂ R

is convex and f is a convex function on A. Show that the

sublevel set {a ∈ A : f(a) ≤ α} is convex for each α ∈ R.

B. Suppose that A ⊂ R

is convex. A real-valued function f on A is called a strictly

convex function if for all distinct points a, b ∈ A and 0 < λ < 1,

f(λa + (1 −λ)b) < λf (a) + (1 − λ)f(b).

If f is strictly convex, show that its set of minimizers is either empty or a singleton.

C. Show that if a convex function f on a convex set A ⊂ R

attains its maximum value

at a ∈ ri(A), then f is constant.

D. Show that the set C

= {a ∈ aff(A) : dist(a, C) ≤ r} used in the proof of Theo-

rem 16.6.2 is convex.

586 Convexity and Optimization

E. A real-valued function f deﬁned on a cone C is called a positively homogeneous

function if f(λx) = λf (x) for all λ > 0 and x ∈ C. Show that a positively homoge-

neous function f is convex if and only if f(x + y) ≤ f(x) + f (y) for all x, y ∈ C.

F. A function f on R

is a sublinear function if f (λx + µy) ≤ λf(x) + µf(y) for all

x, y ∈ R

and λ, µ ∈ [0, ∞).

(a) Prove that sublinear functions are positively homogeneous and convex.

(b) Prove that f is sublinear if and only if epi(f) is a cone.

G. Let f be a sublinear function on R

(a) Prove that f(x) + f(−x) ≥ 0.

(b) Show that if f(x) + f(−x) = 0, then f is linear on the line Rx spanned by x.

) + f(−x

) = 0 for 1 ≤ j ≤ k, prove that f is linear on span{x

, . . . , x

HINT: Consider f (±(x

+ x

)). Use induction.

H. Let f be a bounded convex function on a convex subset A × B of R

× R

. Deﬁne

g(x) = inf{f(x, y) : y ∈ B}. Show that g is convex on A.

I. Suppose that a function f(x, y) deﬁned on R

is a convex function of x for each ﬁxed

y and is a continuous function of y for each ﬁxed x. Prove that f is continuous.

HINT: Given a point (a, b), ﬁnd r, s > 0 so that f(x, y) is close to f(a, b) on

X =

(x, b) : x ∈ [a − r, a + r]

∪

(a ± r, y) : y ∈ [b − s, b + s]

J. Let f

, . . . , f

be convex functions on a convex set A ⊂ R

. Suppose that there is no

point a ∈ A satisfying f

(a) < 0 for 1 ≤ i ≤ k. Prove that there exist λ

≥ 0 so that

= 1 and

≥ 0 on A.

HINT: Separate 0 from Y = {y ∈ R

: for some a ∈ A, y

> f

(a) for 1 ≤ i ≤ r}.

K. Suppose that f and g are convex functions on R

. The inﬁmal convolution of f and

g is the function h(x) := f ¯ g(x) = inf{f(y) + g(z) : y + z = x}. The value −∞

is allowed.

(a) Suppose that there is an afﬁne function k(x) = hm, xi+b for some vector m ∈ R

and b ∈ R so that f (x) ≥ k(x) and g(x) ≥ k(x) for all x ∈ R

. Prove that

h(x) > −∞ for all x.

(b) Assuming h(x) > −∞ for all x, show that h is convex.

L. Let h = f ¯ g denote the inﬁmal convolution of two convex functions f and g on R

Prove that ri(epi(h)) = ri(epi(f) + epi(g)) = ri(epi(f)) + ri(epi(g)).

M. Prove that if f is C

on a convex set A ⊂ R

, then f is convex if and only if the

Hessian matrix ∇

f(x) =

∂

∂x

∂

∂x

f(x)

is positive semideﬁnite.

HINT: Let x, y ∈ A and set g(t) = f (x

), where x

= (1 − t)x + ty. Show that

(t) = h∇f (x

), y − xi and g

(t) =

¡

∇

f(x

)

(y − x), y − x

, where ∇f(a) is

the gradient

∂

∂x

f(a), . . . ,

∂

∂x

f(a)

N. Prove that f(x) = −

√

. . . x

is convex on R

HINT: Use the previous exercise.

O. Fix a convex set A ⊂ R

. Suppose that f

are convex functions on A that converge

pointwise to a function f.

(a) Prove that f is convex.

16.7 Subdifferentials and Directional Derivatives 587

(b) If S ⊂ ri(A) is compact, show that f

converges to f uniformly on S.

HINT: Show that g = sup

is bounded above on each ball B

(a) and use the

Lipschitz condition from Theorem 16.6.2.

P. A function f deﬁned on a convex subset A of R

is called a quasi-convex function if

the sublevel set {a ∈ A : f(a) ≤ α} is a convex set for each α ∈ R.

(a) Show that f is quasi-convex if and only if

f(λa + (1 −λ)b) ≤ max{f (a), f(b)} for all a, b ∈ A.

(b) By part (a), a convex function is always quasi-convex. Give an example of a func-

tion f on R that is quasi-convex but not convex.

f(y) ≥ f(x) + f

(x)(y − x) for all x, y ∈ R.

16.7. Subdifferentials and Directional Derivatives

We now turn to the notions of derivatives and subdifferentials. For a convex

function of one variable, we had two different notions that were useful, the left and

right derivatives and the subdifferential set of supporting hyperplanes to epi(f).

Both have natural generalizations to higher dimensions.

16.7.1. DEFINITION. Suppose that A is a convex subset of R

, a ∈ A, and f

is a convex function on A. A subgradient of f at a is a vector s ∈ R

such that

f(x) ≥ f(a) + hx − a, si for all x ∈ A.

The set of all subgradients of f at a is the subdifferential and is denoted by ∂f(a).

These terms are motivated by the corresponding terms for differentiable func-

tions f : R

→ R, so we recall them. The gradient of f at a, denoted ∇f (a),

is the n-tuple of partial derivatives:

∂

∂x

f(a), . . . ,

∂

∂x

f(a)

. The differential of

f at a is the hyperplane in R

n+1

given by those points (x, t) ∈ R

× R so that

t = f (a) + hx − a, ∇f(a)i.

If f is a convex function on A and a ∈ A, then a vector s determines a hyper-

plane of R

× R by

H = {(x, t) ∈ R

× R : t = f(a) + hx − a, si}

= {(x, t) ∈ R

× R :



(x, t), (−s, 1)

= f (a) − ha, si}

The condition that s be a subgradient is precisely that the graph of f is contained

in the half-space H

= {(x, t) ∈ R

× R : t ≥ f(a) + hx − a, si}. Clearly,

this is equivalent to saying that epi(f ) is contained in H

. Since H contains the

point (a, f(a)), we conclude that the subgradients of f at a correspond to the sup-

porting hyperplanes of epi(f) at (a, f(a)). It is important that the vector (−s, 1)

determining H has a 1 in the (n+1)st coordinate. This ensures that the hyperplane

is nonvertical, meaning that it is not of the form H

×R for some hyperplane H

. In the case n = 1, this rules out vertical tangents.

588 Convexity and Optimization

An immediate and important fact is that the subdifferential characterizes mini-

mizers for convex functions. This is the analogue of the calculus fact that minima

are critical points. But with the hypothesis of convexity, it becomes a sufﬁcient

condition as well.

16.7.2. PROPOSITION. Suppose that f is a convex function on a convex set A.

Then a ∈ A is a minimizer for f if and only if 0 ∈ ∂f(a).

PROOF. By deﬁnition, 0 ∈ ∂f (a) if and only if f (x) ≥ f (a) + hx − a, 0i = f(a)

for all x ∈ A. ¥

16.7.3. THEOREM. Suppose that A is a convex subset of R

, a ∈ A, and f is

a convex function on A. Then ∂f(a) is convex and closed. Moreover, if a ∈ ri(A),

then ∂f(a) is nonempty. If a ∈ int(A), then ∂f(a) is compact.

PROOF. Suppose that s

, s

∈ ∂f(a) and λ ∈ [0, 1]. Then

f(x) ≥ f(a) + hx − a, s

i for i = 1, 2.

Hence

f(x) ≥ λ

f(a) + hx − a, s

+ (1 − λ)

f(a) + hx − a, s

= f (a) + hx − a, λs

+ (1 − λ)s

Thus λs

+ (1 − λ)s

is a subdifferential of f at a, and so ∂f(a) is convex.

Since the inner product is continuous, it is easy to check that ∂f(a) is closed.

For if (s

) is a sequence of vectors in ∂f(a) converging to s ∈ R

, then

f(x) ≥ lim

i→∞

f(a) + hx − a, s

i = f (a) + hx − a, si.

Now suppose that a ∈ ri(A). The point (a, f(a)) lies on the relative boundary

of epi(f) since if y < f(a), the line segment [(a, f(a)), (a, y)] meets epi(f) in

a single point. By the Support Theorem (Theorem 16.3.7), there is a nontrivial

supporting hyperplane H for epi(f) at (a, f(a)), say

H = {(x, t) ∈ R

× R :



(x, t), (h, r)

= α},

where (h, r) is nonzero and ha, hi + rf(a) = α.

We require a nonvertical hyperplane. Suppose that r = 0; so ha, hi = α. As H

is nontrivial, epi(f ) contains a point (b, t) so that

α <



(b, t), (h, 0)

= hb, hi.

Because a is in the relative interior, there is an ε > 0 so that c = a + ε(a − b)

belongs to A. But then

α ≤



(c, f(c)), (h, 0)

= ha, hi + εha − b, hi = α + ε(α − hb, hi).

Thus hb, hi ≤ α < hb, hi, which is absurd. Hence r 6= 0.

Let s = −h/r. Then H is nonvertical and consists of vectors (x, t) such that

rt − hx, rsi = α = rf (a) − ha, rsi or, equivalently, t = hx − a, si + f(a). Since

16.7 Subdifferentials and Directional Derivatives 589

epi(f) is contained in H

, f(x) ≥ t = f (a) + hx −a, si for all x ∈ A. Therefore,

s ∈ ∂f (a), and so the subdifferential is nonempty.

Finally, suppose that a ∈ int(A) and choose r > 0 so that B

(a) ⊂ int(A).

By Theorem 16.6.2, f is Lipschitz on the compact set B

(A), say with Lipschitz

constant L. If s ∈ ∂f(a) with s 6= 0, then b = a + rs/ksk ∈ B

(A). Moreover,

f(b) ≥ f(a) + hb − a, si = f (a) + rksk.

Hence

ksk ≤

f(b) − f(a)

≤

Lkb − ak

= L.

So ∂f(a) is closed and bounded and thus is compact. ¥

16.7.4. EXAMPLE. Let g be a convex function on R and set G(x, y) = g(x)−y.

Consider ∂G(a, b). This consists of all vectors (s, t) such that

G(x, y) ≥ G(a, b) +



(x − a, y − b), (s, t)

for all (x, y) ∈ R

Rewrite this as g(x) ≥ g(a) + (x − a)s + (y − b)(t + 1) for all x, y ∈ R. If

t 6= −1, then ﬁxing x and letting y vary, the right-hand side will take all real values

and hence will violate the inequality for certain values of y. Thus t = −1. The

desired inequality then becomes g(x) ≥ g(a) + (x − a)s for all x ∈ R, which is

the condition that s ∈ ∂g(a). Hence ∂G(a, b) = {(s, −1) : s ∈ ∂g(a)}.

Subdifferentials are closely related to directional derivatives. For simplicity,

we assume the function is deﬁned on R

instead of just a convex subset.

16.7.5. DEFINITION. Suppose that f is a convex function on R

. For a and

d ∈ R

, we deﬁne the directional derivative of f at a in the direction d to be

(a;d) = inf

h→0+

f(a + hd) − f (a)

It is routine to verify that this function is positively homogeneous in the second

variable, meaning that f

(a;td) = tf

(a;d) for all t > 0.

16.7.6. PROPOSITION. Suppose that f is a convex function on R

and ﬁx

a point a in R

. Then f

(a;d) = lim

h→0+

f(a + hd) − f (a)

for all d ∈ R

, and

(a;·) is a convex function in the second variable.

590 Convexity and Optimization

PROOF. Fix d in R

. Then g(t) = f (a + td) is a convex function on R. Hence by

Theorem 16.5.9, D

g(0) exists. However,

g(0) = lim

h→0+

g(h) − g(a)

= inf

h→0+

g(h) − g(a)

= lim

h→0+

f(a + hd) − f (a)

= inf

h→0+

f(a + hd) − f (a)

= f

(a;d).

Fix directions d, e ∈ R

and λ ∈ [0, 1]. Let c = λd + (1 − λ)e. A short

calculation using the convexity of f gives

f(a + hc) − f (a)

λ(a + hd) + (1 −λ)(a + he)

− f(a)

≤ λ

f(a + hd) − f (a)

+ (1 − λ)

f(a + he) − f (a)

Taking the limit as h decreases to 0, we obtain

(a;c) ≤ λf

(a;d) + (1 −λ)f

(a;e).

So f

(a;·) is a convex function. ¥

We are now able to obtain a characterization of the subgradient in terms of the

directional derivatives, generalizing Proposition 16.5.12.

16.7.7. THEOREM. Suppose that f is a convex function on R

, and a, s ∈ R

Then s ∈ ∂f (a) if and only if hd, si ≤ f

(a;d) for all d ∈ R

PROOF. Suppose that s ∈ ∂f(a). Then for any direction d ∈ R

and h > 0, we

have f(a + hd) ≥ f (a) + hhd, si. Rearranging, we have

(a;d) = lim

h→0

f(a + hd) − f (a)

≥ hd, si.

Conversely, suppose that s ∈ R

satisﬁes

hd, si ≤ f

(x;d) = inf

h→0+

f(a + hd) − f (a)

for all d ∈ R

. Then rearranging yields f(a) + hhd, si ≤ f (a + hd). Therefore, s

belongs to ∂f(a). ¥

Conversely, we may express the directional derivatives in terms of the subdif-

ferential. This requires a separation theorem. If C is a nonempty compact convex

set, the support function of C is deﬁned as

(x) = sup{hx, ci : c ∈ C}.

Note that σ

is a convex function on R

that is positively homogeneous.

It is a consequence of the Separation Theorem (Theorem 16.3.3) that different

compact convex sets have different support functions. For if D is another convex

set that contains a point d /∈ C, then there is a vector x so that

(x) = sup{hx, ci : c ∈ C} ≤ α < hx, di ≤ σ

(x).

16.7 Subdifferentials and Directional Derivatives 591

The next lemma shows conversely how to recover the convex set from a support

function.

16.7.8. SUPPORT FUNCTION LEMMA.

Suppose that g is a convex, positively homogeneous function on R

. Let

C(g) = {c ∈ R

: hx, ci ≤ g(x) for all x ∈ R

Then C(g) is compact and convex, and σ

C(g)

= g. Thus if A is a compact convex

set, then C(σ

) = A.

PROOF. Let M = sup{g(x) : kxk = 1}, which is ﬁnite since g is continuous and

the unit sphere is compact. If c ∈ C(g), then

kck = hc/kck, ci ≤ g(c/kck) ≤ M.

So C(g) is bounded. Since the inner product is continuous, {c : hx, ci ≤ g(x)} is

closed for each x ∈ R

. The intersection of closed sets is closed, and hence C is

closed. Thus, C(g) is compact by the Heine–Borel Theorem. If c, d ∈ C(g) and

x ∈ R

, then

hx, λc + (1 −λ)di ≤ λg(x) + (1 − λ)g(x) = g(x).

So C(g) is convex.

The inequality σ

C(g)

≤ g is immediate from the deﬁnition.

Fix a vector a in R

. By Theorem 16.7.3, there is a vector s in ∂g(a). Thus

g(x) ≥ g(a) + hx − a, si for x ∈ R

. Rewriting this yields

g(x) − hx, si ≥ g(a) − ha, si =: α.

Take x = ha for h > 0 and use the homogeneity of g to compute

α ≤ g(ha) − hha, si = h(g(a) − ha, si) = hα.

Hence α = 0, g(a) = ha, si and s belongs to C(g). So σ

C(g)

(a) ≥ ha, si = g(a).

Therefore, σ

C(g)

= g.

If A is compact and convex, setting g = σ

yields σ

= σ

C(σ

)

. By the

remarks preceding the proof, this implies that C(σ

) = A. ¥

16.7.9. COROLLARY. Suppose that f is a convex function on R

. Fix a ∈ R

Then f

(a;·) is the support function of ∂f (a), namely

(a;d) = sup{hd, si : s ∈ ∂f(a)} for d ∈ R

PROOF. Theorem 16.7.7 shows that ∂f (a) = C(g), where g(x) = f

(a;x). Thus

by the Support Function Lemma (Lemma 16.7.8),

(a;d) = σ

∂f (a)

(d) = sup{hd, si : s ∈ ∂f(a)}.

592 Convexity and Optimization

16.7.10. EXAMPLE. Consider f(x) = kxk, the Euclidean norm, on R

. First

look at a = 0. A vector s is in ∂f(0) if and only if hx, si ≤ kxk for all x ∈ R

Thus ∂f(0) = B

(0). Indeed, if ksk ≤ 1, then the Schwarz inequality shows that

hx, si ≤ kxkksk ≤ kxk.

If ksk > 1, take x = s and notice that hx, si = kxk

> kxk.

Now we compute the directional derivatives at 0,

(0;d) = lim

h→0

khdk

= kdk = f(d).

In this case, since f

(0;·) = f, Theorem 16.7.7 is redundant and provides no new

information. Let us verify Corollary 16.7.9 directly:

sup

hd, si : s ∈ B

(0)

= kdk = f

(0;d)

because hd, si ≤ kdkksk = kdk, while the choice s = d/kdk attains this bound.

Now look at a 6= 0. We ﬁrst compute the directional derivatives.

(a;d) = lim

h→0

ka + hdk − kak

= lim

h→0

ka + hdk

− kak

ka + hdk + kak

= lim

h→0

2hhd, ai + h

kdk

ka + hdk + kak

2hd, ai

2kak



kak

This time Theorem 16.7.7 is very useful. It says that s ∈ ∂f(a) if and only if

hd, si ≤



kak

for all d ∈ R

. Equivalently,



d, s −

kak

≤ 0 for all d in

. But the left-hand side takes all real values except when s =

kak

. Therefore,

∂f(a) =

kak

Observe that f

(a;d) is a linear function of d when a 6= 0. Thus f has contin-

uous partial derivatives at a and ∇f(a) =

kak

. So ∂f (a) = {∇f(a)}.

Let’s look more generally at the situation that occurs when a convex function f

is differentiable at a. Unlike the case of arbitrary functions, the existence of partial

derivatives together with convexity implies differentiability.

16.7.11. THEOREM. Suppose that f is a convex function on an open convex

set A ⊂ R

. Then the following are equivalent for a ∈ A :

(1)

∂f

∂x

(a) are deﬁned for 1 ≤ i ≤ n.

(2) f is differentiable at a.

(3) ∂f(a) is a singleton.

In this case, ∂f(a) = {∇f(a)}.

PROOF. Suppose that (1) holds and consider the convex function

g(x) = f(a + x) − f (a) − hx, ∇f(a)i.