Linear Controller Design: Limits of Performance by Stephen Boyd and Craig Barratt - HTML preview

CHAPTER 13 ELEMENTS OF CONVEX ANALYSIS

We can think of the right-hand side of (13.2) as an a ne approximation to ( ),

z

which is exact at = . The inequality (13.2) states that the right-hand side is a

z

x

global lower bound on . This is shown in gure 13.1.

slope g1

;

;

( )

x

@

I

@

slope g

@

@

R

2

@

I

@

slope ~g2

x

x

1

2

A convex function on along with three ane global lower

Figure

13.1

R

bounds on derived from subgradients. At , is dierentiable, and the

x

1

slope of the tangent line is = ( ). At , is not dierentiable two

0

g

x

x

1

1

2

dierent tangent lines, corresponding to subgradients and ~ , are shown.

g

g

2

2

We mention two important consequences of

( ). For T(

) 0 we

g

2

@

x

g

z

;

x

>

have ( )

( ), in other words, in the half-space

T (

) 0 , the values

z

>

x

fz

j

g

z

;

x

>

g

of exceed the value of at . Thus if we are searching for an that minimizes

x

x

, and we know a subgradient of at , then we can rule out the entire half-space

g

x

T (

) 0. The hyperplane T(

) = 0 is called a cut because it cuts o

g

z

;

x

>

g

z

;

x

from consideration the half-space T(

) 0 in a search for a minimizer. This

g

z

;

x

>

is shown in gure 13.2.

An extension of this idea will also be useful. From (13.2), every that satis es

z

( )

, where

( ), must also satisfy T(

)

( ). If we are searching

z

<

x

g

z

;

x

;

x

for a that satis es ( )

, we need not consider the half-space T(

)

z

z

g

z

;

x

>

( ). The hyperplane T(

) =

( ) is called a deep-cut because it rules

;

x

g

z

;

x

;

x

out a larger set than the simple cut T(

) = 0. This is shown in gure 13.3.

g

z

;

x

13.1.1

Subgradients: Infinite-Dimensional Case

The notion of a subgradient can be generalized to apply to functionals on in nite-

dimensional spaces. The books cited in the Notes and References at the end of this

chapter contain a detailed and precise treatment of this topic in this book we will

give a simple (but correct) description.

13.1 SUBGRADIENTS

295

g

q

x

T

T

g

z

>

g

x

q

x

( )

( )

z

x

;

;

=

T

T

g

z

g

x

T

T

g

z

<

g

x

A point and a subgradient of at . In the half-space

Figure

13.2

x

g

x

, ( ) exceeds ( ) in particular, any minimizer of must lie

T

T

g

z

>

g

x

z

x

x

in the half-space

.

T

T

g

z

g

x

g

q

6

x

( )z

;

;

(

) =

( )

T

g

z

;

x

;

x

A point and a subgradient of at determine a deep-cut

Figure

13.3

x

g

x

in the search for points that satisfy ( )

(assuming does not satisfy

z

x

this inequality). The points in the shaded region need not be considered

since they all have ( )

.

z

>

296