Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

1.6 Convex functions

1.6 Convex functions

In what follows let K be a non-empty open convex subset in the coordinate space of dimension n and consider a function

f : K R .

(1.33)

Definition The function f is convex if for any points p and q in K

f ( ( 1 - λ ) p + λ q ) ( 1 - λ ) f ( p ) + λ f ( q ) ,

(1.34)

where λ is in [0,1]. The function f is concave if - f is convex.

The geometric meaning of equation 1.34 is that chords joining the points on the graph are above it. This can be expressed in terms of the so-called epigraph as the following theorem shows.

Figure 6: The epigraph of a function.

Proposition 1.6.1 The function f is convex if and only if itsepigraph

e p i f = { ( p , t ) | p K   a n d   t f ( p ) } E n + 1

is a convex subset in the coordinate space of dimension n+1.

Proof Let f be a convex function and suppose that (p,t) and (q,s) are in epi f. Then

( 1 - λ ) ( p , t ) + λ ( q , s ) = ( ( 1 - λ ) p + λ q , ( 1 - λ ) t + λ s ) ,

where v:=(1 - λ)p+λq is in K because of its convexity and the scalar "coordinate" satisfies the inequalities

( 1 - λ ) t + λ s ( 1 - λ ) f ( p ) + λ f ( q ) f ( v )

because of the convexity of the function. Therefore epi f is convex (as a set). Conversely, if epi f is a convex set then the chords joining its boundary points are "above" the graph of f and inequality 1.34 follows immediately. ▮

Proposition 1.6.2 (Jensen, Johan) The function f is convex if and only if

f ( λ 1 v 1 + + λ k v k ) λ 1 f ( v 1 ) + + λ k f ( v k )

(1.35)

for any convex combination of elements from K.

Proof Inequality 1.35 gives the definition of convex functions under the special choice k=2. Conversely, if a function is convex then inequality 1.35 is satisfied in case of k=2 because of the definition of convex functions (if k=1 then there is nothing to prove). For convex combinations involving more that two terms the proof is based on a simple induction. Suppose that 1.35 is true for convex combinations containing at most k - 1 vectors and consider the convex combination

v : = λ 1 v 1 + + λ k v k

of the elements v(1), ..., v(k) in K. Because at least one of the coefficients must be different from 1 we can write, for example, that

v = ( 1 - λ k ) ( λ 1 1 - λ k v 1 + + λ k - 1 1 - λ k v k - 1 ) + λ k v k ,

where

w : = λ 1 1 - λ k v 1 + + λ k - 1 1 - λ k v k - 1

is in K because of its convexity and

v = ( 1 - λ k ) w + λ k v k .

Then

f ( v ) ( 1 - λ k ) f ( w ) + λ k f ( v k )

(1.36)

and, by the inductive hypothesis,

f ( w ) λ 1 1 - λ k f ( v 1 ) + + λ k - 1 1 - λ k f ( v k - 1 ) .

(1.37)

Relations 1.36 and 1.37 give that

f ( v ) λ 1 f ( v 1 ) + + λ k - 1 f ( v k - 1 ) + λ k f ( v k )

as was to be proved. ▮

Figure 7: Johan Jensen, 1859-1925.

Proposition 1.6.3 Let K be a non-empty open convex set. If the function

f : K R

is convex then it is continuous at any point in K.

Proof Let p in K be a given point (recall that K is a non-empty open convex subset). Without loss of generality we can suppose that p is just the origin 0. As the first step we are going to prove that f is locally bounded. Consider an open box R of dimension n centered at the origin in K. Since the elements in R can be expressed as a convex combination of the vertices

v 1 , , v m ( m = 2 n )

we have that for any v in R

f ( v ) λ 1 f ( v 1 ) + + λ m f ( v m ) M ( λ 1 + + λ m ) = M ,

where

M : = m a x { f ( v 1 ) , , f ( v m ) } .

On the other hand

0 = 1 2 v + 1 2 ( - v ) ,

where - v is in R because the origin is the center of the box. Using the upper bound M and the convexity of the function

f ( 0 ) 1 2 f ( v ) + 1 2 f ( - v ) 1 2 f ( v ) + 1 2 M

and, consequently,

m : = 2 f ( 0 ) - M f ( v )

is a lower bound. Therefore

| f ( v ) | C : = m a x { | m | , | M | } ( v R ) .

Figure 8: The proof of Proposition 1.6.3.

In the second step we claim that f is locally Lipschitzian. Consider an open ball B centered at p with radius r such that 2B is contained in the box R. Then for each q in B we have a point z not in B but in R such that

q s ( p , z )   a n d   s ( - z , z ) R .

Explicitly

q = ( 1 - λ ) p + λ z ,

where

λ = | | q - p | | | | z - p | |

is the simple ratio among the points. Using the convexity of the function we have that

f ( q ) ( 1 - λ ) f ( p ) + λ f ( z )

and, consequently,

f ( q ) - f ( p ) | | q - p | | f ( z ) - f ( p ) | | z - p | | 2 C | | z - p | | 2 C r

(1.38)

because z is not in B but z is in R. Therefore

f ( q ) - f ( p ) 2 C r | | q - p | | .

(1.39)

Using the same argumentation as above for the triplet q, p and u:= - z we have that

f ( p ) - f ( q ) | | p - q | | f ( u ) - f ( q ) | | u - q | |

(1.40)

and, consequently,

f ( q ) - f ( u ) | | u - q | | f ( q ) - f ( p ) | | p - q | | .

The last equation allows us to present a lower estimation

- 2 C r - 2 C | | u - q | | f ( q ) - f ( u ) | | u - q | | f ( q ) - f ( p ) | | p - q | | .

(1.41)

Therefore

- 2 C r | | p - q | | f ( q ) - f ( p ) .

(1.42)

Inequalities 1.39 and 1.42 say that

| f ( q ) - f ( p ) | 2 C r | | p - q | | ,

i.e. the function is locally Lipschitzian and, consequently, it is continuous at p as was to be proved. ▮

Figure 9: Rudolf Lipschitz, 1832-1903.

Inequalities 1.38 and 1.42 imply more than the continuity: the existence of the one-sided directional derivatives

D v + f ( p ) = l i m t 0 + f ( p + t v ) - f ( p ) t

at each point into each direction. Indeed, consider the function

h ( t ) : = f ( p + t v ) - f ( p ) t ( 0 < t < r )

defined on a sufficiently small open interval. Using the notation q=p+tv inequality 1.42 says that h is bounded from below. Taking t < s and z=p+sv 1.38 shows that h is monotone increasing. Therefore its infimum M*=inf h exists and

l i m t 0 + f ( p + t v ) - f ( p ) t = M * .

For further regularity properties of convex functions see Lebesgue's theorem and [8]. Figure 10 shows why it is important for the point p to be in the interior of the domain.

Figure 10: Discontinuity on the boundary of the domain.

Definition The element w is called a subgradient of the function f at the point p in K if the inequality

w , q - p f ( q ) - f ( p )

(1.43)

holds for any point q in K. The subdifferential of the function f is the set of its subgradients.

For the geometric description of a subgradient vector write inequality 1.43 into the form

( w , - 1 ) , ( q , f ( q ) ) - ( p , f ( p ) ) 0

to express that the graph of the function must be entirely above the hyperplane

( w , - 1 ) , ( x , t ) - ( p , f ( p ) ) = 0

(1.44)

passing through the point (p, f(p)) in the coordinate space of dimension n+1. The vector (w, - 1) plays the role of the normal vector to the hyperplane 1.44.

Figure 11: The subgradient vector.

The subgradient involves a global property whereas the derivative has a local character. Nevertheless the convexity of the function allows us to describe the set of subgradients locally in terms of the directional derivative.

Proposition 1.6.4 (Local characterization.) Let K be a non-empty open convex set and consider a convex function

f : K R .

The element w is a subgradient at the point p in K if and only if the inequality

w , v D v + f ( p )

holds for any element v in the coordinate space.

Proof Suppose that w is a subgradient of the function f at the point p and let us choose the point q in the special form

q : = p + t v ,

where v is a nonzero vector and t is a positive real number which is small enough for q to be in K. Then the relation

w , v f ( p + t v ) - f ( p ) t

follows immediately from the definition of the subgradient. Therefore

w , v l i m t 0 + f ( p + t v ) - f ( p ) t = D v + f ( p ) .

In order to see the converse statement let q be an arbitrary point in K and consider the line segment

c ( t ) : = ( 1 - t ) p + t q = p + t v

joining p and q. Since the function is convex, the formula

f c ( t ) ( 1 - t ) f ( p ) + t f ( q )

holds for any parameter t between 0 and 1. Therefore

D v + f ( p ) = ( f c ) ' ( 0 ) = l i m t 0 + f c ( t ) - f c ( 0 ) t

l i m t 0 + ( 1 - t ) f ( p ) + t f ( q ) - f ( p ) t = f ( q ) - f ( p ) .

This means that

w , q - p = w , v D v + f ( p )

implies that

w , q - p f ( q ) - f ( p )

as was to be proved. ▮

Corollary 1.6.5 Let K be a non-empty open convex set and consider a convex function

f : K R .

The following conditions are equivalent:

• The point p in K is a global minimizer.

• The zero vector 0 belongs to the subdifferential of f at p.

• For any element v

0 D v + f ( p ) .

Proof If p is a global minimizer then for any q in K

0 f ( q ) - f ( p )

showing that 0 is one of the subgradient at p. If 0 is one of the subgradient at p then, by definition

0 = 0 , q - p f ( q ) - f ( p )

and we have that p is a global minimizer. The equivalence of (ii) and (iii) is a direct consequence of the local characterization Proposition 1.6.4 of the subgradient vectors. ▮

Figure 12: The zero vector as a subgradient.

Definition Suppose that

f : K R

is differentiable at the point p. The gradient vector is defined in terms of the usual partial derivatives:

g r a d f p : = ( D 1 f ( p ) , , D n f ( p ) ) .

Actually it is a special notation for the Jacobian matrix at the point p.

For the sake of simplicity we restrict ourselves to the coordinate plane to present the geometric characterization of the gradient vector. We will use the standard symbols x and y for the coordinates of the points in the plane. Let U be a non-empty open subset and consider a (not necessarily convex) function

f : U R .

Suppose that f is continuously differentiable, i.e. it is differentiable everywhere and the partial derivatives are continuous. Let p be a point in U with a non-zero gradient vector. This means, for example, that the partial derivative with respect to the second coordinate at p is different from zero:

D 2 f ( p ) 0 .

Let us define the mapping

Φ : U E 2 , ( x , y ) Φ ( x , y ) = ( x , f ( x , y ) ) .

The Jacobian

d e t J = d e t 1 0 D 1 f D 2 f = D 2 f

is different from zero at p.

Figure 13: The inverse mapping theorem.

Using the inverse mapping theorem we have an inverse function defined on an open neighbourhoof Φ(V) of Φ(p). We are going to give a local parameterization for the level curve

f ( x , y ) = c 0

(1.45)

passing through the point p. Let r be a sufficiently small positive real number such that

v ( t ) Φ ( V ) ,   w h e r e   v ( t ) = ( x p + t , c 0 )

is a parametrization of the horizontal segment passing through Φ(p) and t is between r and - r. Then

w ( t ) : = Φ - 1 ( v ( t ) )

is just a local parametrization of the level curve 1.45 because

f ( w ( t ) ) =   t h e   s e c o n d   c o o r d i n a t e   o f   Φ ( w ( t ) ) =

t h e   s e c o n d   c o o r d i n a t e   o f   v ( t ) = c 0 .

Therefore

0 = ( f w ) ' = w ' 1 D 1 f ( w ) + w ' 2 D 2 f ( w )

(1.46)

which means that the gradient vector field along the level curves is orthogonal to the tangent lines represented by the derivative vector w'.

Figure 14: The gradient vector.

Remark In case of higher dimensional spaces the gradient vectors are orthogonal to the tangent hyperplanes of the level hypersurfaces.