UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Duality in convex programming Muir, David Charles William 1966

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1966_A8 M8.pdf [ 2.4MB ]
Metadata
JSON: 831-1.0080576.json
JSON-LD: 831-1.0080576-ld.json
RDF/XML (Pretty): 831-1.0080576-rdf.xml
RDF/JSON: 831-1.0080576-rdf.json
Turtle: 831-1.0080576-turtle.txt
N-Triples: 831-1.0080576-rdf-ntriples.txt
Original Record: 831-1.0080576-source.json
Full Text
831-1.0080576-fulltext.txt
Citation
831-1.0080576.ris

Full Text

DUALITY IN CONVEX PROGRAMMING by DAVID CHARLES WILLIAM MUIR B.Sc, University of B r i t i s h Columbia, 1962 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF -SC-I-ENCE- fl^TS m the Department of MATHEMATICS We accept th i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA A p r i l , I966 In p resen t i ng t h i s t h e s i s in p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r re ference and study I f u r t h e r agree that permiss ion f o r ex-tens i ve copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the Head of my Department or by h i s r e p r e s e n t a t i v e s . It is understood that copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n -c i a l ga in s h a l l not be a l lowed wi thout my w r i t t e n permiss ion Department of Mat.hemat.i r>g The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada Date May 12. 1Q66. i i ABSTRACT Problems o f m i n i m i z i n g a convex f u n c t i o n o r m a x i m i z i n g a concave f u n c t i o n o v er a convex s e t a r e c a l l e d convex programming problems. D u a l i t y p r i n c i p l e s r e l a t e two pro b l e m s , one a m i n i m i z a t i o n problem, the o t h e r a m a x i m i z a t i o n problem, i n such a way t h a t a s o l u t i o n t o one i m p l i e s a s o l u t i o n t o the o t h e r and t h a t the minimum v a l u e o f one i s e q u a l t o the maximum v a l u e o f the o t h e r . When t h e f u n c t i o n s a r e l i n e a r and the c o n s t r a i n t s e t s a r e p o l y h e d r a l , the problems a r e c a l l e d l i n e a r programming problems. T h e i r d u a l i t y i s well-known. C e r t a i n d u a l i t y r e s u l t s o f l i n e a r programming can be extended t o convex programming by means o f vhe t h e o r y o f c o n j u g a t e convex f u n c t i o n s i n t r o d u c e d by F e n c h e l ( [ l ] , [ 2 ] ) . I n t h i s t h e s i s the t h e o r y o f c o n j u g a t e f u n c t i o n s i s g e n e r a l i z e d and a p p l i e d t o convex programming problems. I n p a r t i c u l a r a d u a l i t y theorem i s g i v e n f o r a c l a s s o f convex programming problems. T h i s theorem i s compared w i t h a d u a l i t y theorem f o r convex programming problems g i v e n by Dorn [3J. i i i TABLE OP CONTENTS P a g e I n t r o d u c t i o n S e c t i o n 1: R e v i e w o f D u a l i t y T h e o r y f o r C o n j u g a t e C o n v e x F u n c t i o n s 3 S e c t i o n 2. G e n e r a l i z e d C o n j u g a t e S e t s a n d F u n c t i o n s 11 S e c t i o n 3 : C o n c a v e F u n c t i o n s a n d t h e i r D u a l s 20 S e c t i o n ^ : D u a l i t y t o r C o n v e x a n a C o n c a v e F u n c t i o n s 22 S e c t i o n bs L a g r a n g i a n s a n a D u a l C o n v e x P r o g r a m m i n g P r o b l e m s 2b S e c t i o n 6: C o m p a r i s o n o f D u a l i t y T h e o r e m s . . . 35 B i b l i o g r a p h y K2 A p p e n d i x 4-3 ERRATA Page Line C o r r e c t i o n b 12, 19 The assumption of r e l a t i v e i n t e r i o r i s not required . 11 9, 12 Only J> has been proved. The e q u a l i t y requires the d e f i n i t i o n of f* and f** . 13 9 For t read C A . 17 6 "then y Q i s on the boundary of C A " . Should be dele ted . INTRODUCTION Problems which seek to maximize or minimize a f u n c t i o n of s e v e r a l v a r i a b l e s which are s u b j e c t t o c e r t a i n c o n s t r a i n t s , are c a l l e d programming problems. Those f o r which the f u n c t i o n s are convex or concave, and the c o n s t r a i n t s e t s are convex, are c a l l e d convex programming problems. D u a l i t y p r i n c i p l e s r e l a t e two programming problems, one of which, the p r i m a l , i s a maximization problem and the other the d u a l , i s a m i n i m i z a t i o n problem. Ihey are r e l a t e d i n such a way t h a t the e x i s t e n c e of a s o l u t i o n t o one i n s u r e s a s o l u -t i o n t o the other. Furthermore the r e s p e c t i v e extreme values are equal. Problems i n which the c o n s t r a i n t s e t s are p o l y h e d r a l and the f u n c t i o n s l i n e a r are c a l l e d l i n e a r programming problems. T h e i r d u a l i t y i s well-known. Pr i m a l L i n e a r Programming Problem Uiven tne mXn mat r i x A and constant v e c t o r s c i n E n and b i n E m , maximize (c,x) s u b j e c t t o the c o n s t r a i n t s Ax<b, x > 0 . Dual L i n e a r Programming Problem To minimize (?,b) s u b j e c t t o the c o n s t r a i n t s §A>c, ? > 0 . A s s o c i a t e d w i t h these problems i s the Lagrangian f u n c t i o n L(x,?) = (c,x) + ( § , b ) - §Ax d e f i n e d l o r xM), § _ > 0 . The components of the v e c t o r § i n the dual problem are the "Lagrange M u l t i p l i e r s " f o r the p r i m a l problem, hence the name Lagrangian f u n c t i o n f o r L(x,§). 2. A saddle-point of the Lagrangian f u n c t i o n L(x,§) Is a p a i r of vectors {x*,?*} f o r which L(x*,?) > L(x*,?*) > L(x,§*), f o r a l l {x,§} i n the domain of L(x,§). The connection between the two l i n e a r programming problems and t h e i r a s s o c i a t e d Lagrangian f u n c t i o n i s given by the f o l l o w i n g " d u a l i t y " theorem. Theorem: (1) i r there e x i s t s a vector x* which maximizes (c,x) i n the p r i m a l problem then there a l s o e x i s t s a vector §* which minimizes (§,b) i n the dual problem, and v i c e versa. (2) i f there e x i s t s a saddle-point lx*,§*} of the Lagrangian H.x,§) = i;c,x) + (?,b) - ?Ax then x* maximizes (c,x) i n the p r i m a l problem and minimizes (§,b) i n the dual problem, and v i c e versa. Furthermore (c,x*) = L(x*,?*) = (§*,b). Some r e s u l t s f o r l i n e a r programming problems can be extended to convex programming problems by means of the The purpose of t h i s t h e s i s i s t o o b t a i n d u a l i t y r e s u l t s f o r a l a r g e r c l a s s of convex programming problems. This i s achieved by g e n e r a l i z i n g the concept of conjugate convex f u n c t i o n s and a p p l y i n g the r e s u l t i n g theory. In p a r t i c u l a r a d u a l i t y theorem f o r a c l a s s of convex programming problems i s given, which includes the well-known d u a l i t y theorem f o r l i n e a r programming s t a t e d above. This theorem can a l s o be s p e c i a l i z e d to a d u a l i t y theorem f o r convex programming due to Dorn [ 3 j . theory of conjugate f u n c t i o n s introduced by F e n c h e l ( [ l ] , Notation: I n t h i s t h e s i s the f o l l o w i n g n o t a t i o n w i l l be -used. A = i s an mxn matrix over the r e a l numbers, x i s a column vector i n E n , y i s a column vector i n E m , ft i s a row vector i n E n , § i s a row vector i n E m. Por any r e a l numbers t and c, [ t , x j w i l l denote a column vector i n En+^~ and [c,? j w i l l denote a row vector i n E m + 1 . The u s u a l inner product i n E n or E m w i l l be denoted by ( , ). i t w i l l be defined only between a row vector and a column vector. Thus n i ( h ,x) = L h x° j = l J A l s o ?>0. means §^ 0 f o r a l l i ; i = i , - • • ,m. Sets w i l l be denoted oy c a p i t a l l e t t e r s . S e c t i o n 1: Review or D u a l i t y Theory f o r Conjugate Convex  Functions. The theory of conjugate f u n c t i o n s introduced by Fenchel [ 1 ] , can be used to extend c e r t a i n r e s u l t s of the d u a l i t y theory of l i n e a r programming to convex programming problems. Tms s e c t i o n reviews the mam r e s u l t s of the theory of conjugate convex f u n c t i o n s , most of which can be found i n Fenchel ( f l ] , [ 2 ] ) or i n the book by K a r l i n [4] (p.218-229). 4. In the f o l l o w i n g s e c t i o n s t h e s e r e s u l t s w i l l be g e n e r a l i z e d and used t o prove a d u a l i t y theorem f o r a c l a s s o f convex programming problems. D e f i n i t i o n 1.1: Convex Set A s e t 0 o f v e c t o r s m E n i s c a l l e d a convex s e t i f f o r any two v e c t o r s x^ and x 2 m C, and f o r any r e a l number \, ®Q<}-> v e c t o r Xx^ + ( l - X ) X g i s m t h e s e t C. D e f i n i t i o n 1.2: Convex F u n c t i o n A f u n c t i o n f d e f i n e d on a convex s e t C i s c a l l e d convex i f f o r any two p o i n t s x^ ana x 2 i n C ana f o r a l l \, V<\<1, f [X X l+(l-X3x 2] < \ f ( x 1 ) + ( l - \ ) f ( x 2 ) . D e f i n i t i o n l.J: Concave F u n c t i o n A f u n c t i o n g d e f i r t e d on a convex s e t D i s c a l l e d concave i f the f u n c t i o n -g i s a convex f u n c t i o n on the convex s e t D. Lemma 1.1: L e t f be a convex f u n c t i o n d e f i n e d on a convex s e t C. Then (1) f i s c o n t i n u o u s m the r e l a t i v e i n t e r i o r o f C, (2) f o r a boundary p o i n t X q o f c, l i m m f f ( x ) < f ( x ) 5. Proof: The r e s u l t i s well-known, i t can be found i n Courant [ 5 ] 5 p.326 . D e f i n i t i o n 1.4: A convex function f with domain the convex set C, i s said to be closed i f X q i n the boundary of C and l i m i n f f(x) < » implies x i s i n C and x-*x 0 o f ( x ) = lim i n f f ( x ) . ° x-»x o D e f i n i t i o n 1 . 5 : If f i s a convex function with domain C, then the set [f,C] i s defined by [f,C] = C[t,x]eE n + 1:xeC,t>f(x)} . Lemma 1 .2 : I f f i s a closed convex function then [f,Cj i s a closed convex set. Proof: The r e s u l t follows immediately from the d e f i n i t i o n . Lemma 1 . 3 : I f f i s a closed convex function defined on the convex set C, then f o r every point [ S O , X q ] [f,C] there exists a non-vertical hyperplane that s t r i c t l y separates [ s Q , x o ] from [f,C]. Proof: f closed implies [f,C] i s a closed convex set. Hence [ S O , X Q ] 0 [f,C] implies there exists a sphere S of radius e about [s ,x ] such that SD[f,C] = 0 . b. Then S and [f,Cj can be separated by a hyperplane P, say P : ( l>,hj, [t,x]) = k so that (1.1) Tt + (h,x) _< k, f o r a l l [t,x] € [f,Uj (1.2) T S + (n,x) > k, f o r a l l [s,xj e S. Since [s .x ] i s i n the i n t e r i o r ot S, o' o 3 (1.3) T S o + (h,x Q) > k. Since [t,x] i s s t i l l i n [f,C] f o r t large, T<0. Case 1: X q i s an i n t e r i o r point of C. Then T^0, f o r i f T=0, from ( l . l ) , (h,x Q)<k and from (1.3), (h,x )>k. This i s a contradiction; therefore T<0 and P i s a non-vertical hyperplane. Case 2: X q i s on the boundary of C. Suppose T=0, then (h,x Q)>k from (1.3). Since X q i s on the boundary of C there exists a sequence (x ], x -*x , with x eC and ^ n n o n r(x) defined. Therefore [ f ( x ) ,x ] e [f,C] f o r a l l n, and hence by ( l . l ) T f ( x n ) + (h,x n) <_ k for a l l n or since T=0, ( n* x n) <. Therefore ( n> x 0) = Hni(h,x n) <_ k, which i s n-*°° a contradiction. Therefore T ^ O and P i s a non-vertical hyperplane. Case 3: X q i s not i n the closure of C. Then there exists a hyperplane ? 1 i n E n , p : ( n i ax) = that s t r i c t l y separates X q from C. Thus (1.4) {H19x) < k x f o r a l l x i n C (1.5) (V x 0) > k l • n+1 This hyperplane can be extended v e r t i c a l l y to E obtaining the v e r t i c a l hyperplane P x i n E n + 1 , P 1 : ( [ 0 , n 1 ] , [ t , x ] ) •= k. Next take any non-vertical hyperplane Pg, Pg:([T,Ug], [ t , x ] ) that keeps [f,C] on one side, say (1.6) T t + (h 2,x) < k 2 f o r a l l [t,x] i n [f, C ] . The existence of the plane i s guaranteed by case 1 or 2. Form the hyperplane P = (l-a)P.j + aP 2, where l>a>0, P: ( [a r^ l -cOn^+dig] , [t,x]) = (l-cOk-j+akg . It w i l l be shown that f o r a small enough P separates [ s o , x Q ] from [f,C]. For [t,x] i n [ f , C ] , art + ( l - a ) ( h 1 , x ) + a(h g,x) < ( l - a ) ^ + a k 2 . I f [ s o , x Q ] i s on the opposite side of Pg from [ f , C ] , there i s nothing to prove, any a, 0<a<l, would be accept-able. Hence suppose [ S O , X q ] i s on the same side of Pg as [ f , C ] ; then from (1.6), T S q + (hg,x Q) _< kg, say T s o + ^ n 2 , x o ^ = k2~ e2' e2 - ° * P r o m (ni>x0) > k i * s a y 8. (h ,x ) = k-j^ +e-j^ , € 1>0. Then a T s o + a ( n 2 , x o ) + ( l - a ) ( n i 3 x o ) = a ( k 2 - e 2 ) + ( i - a ) ( k 1 + * 1 ) . Choose a>0 small enough so chat ( l - a ) e ^ > as^ , then ars o+a(n 2,x o)+(l-a)(n i,x o) > a k 2 + ( l - a ) k x . Therefore P s t r i c t l y separates [ s Q , x ] from [ f , u j , and. P i s n o n - v e r t i c a i because aiyo. Remark: I t can e a s i l y be v e r i f i e d t h a t the statement "There e x i s t s a n o n - v e r t i c a l hyperplane below the set [f,C] w i t h normal [ - l , h ] " i s e q u i v a l e n t t o the statement "sup [ ( M , x ) - f ( x ) ] < »" , xeC as long as the r e l a t i v e i n t e r i o r of C i s non-empty. D e f i n i t i o n l . b t Given the set [ f , C ] , the set C* and the f u n c t i o n f * are defined by 0* = { h e E n : s u p [ ( h , x ) - f ( x ) ] < »} xeC f*(h) = s u p [ ( h , x ) - r ( x ) ] , f o r heC*. xeC The f u n c t i o n f * i s r e f e r r e d t o as the conjugate f u n c t i o n of f. Prom the previous remarks i f C contains an i n t e r i o r p o i n t then the set C* i s non-empty. 9. Lemma 1.4: C* i s a convex set; and f* i s a convex f u n c t i o n on C * . Proof: I f l i 1 and n 2 are i n C* and 0<X<1, then sup[ (Xh,+( l -X)h 0 , x ) - f ( x ) ] xeC 1 t L = s u p [ X ( n i 5 x ) + ( l-X)(h 0,x) - X f ( x ) - ( l - X ) f ( x ) ] xeC 1 tL < sup \[(h,,x) - f ( x ) ] + sup ( l - X ) [ ( n p , x ) - f ( x ) ] X G C xeC = X f * ( n 1 ) + ( i - x ) f * ( n 2 ) < » . Hence X n i + ( l - X ) n 2 6 C * and f * [ x n x + ( i - x ) n 2 ] < x f * ( n 1 ) + ( i - x ) f * ( h 2 ) completing the proof of the lemma. Lemma 1.5: f* i s a closed convex f u n c t i o n of C * . Proof: Suppose U Q i s on the boundary of C* and there ex is t s a sequence {h^}, with i n C * , h^-* h Q and l i m i n f f * ( n ± ) < » ; then f * ( n . ) B s u p [ ( n , , x ) - f ( x ) ] > ( h . , x ) - f ( x ) f o r a l l X GC. 1 - X G C 1 - i Now « > l i m i n f f * ( n t ) > l i m i n f [ ( n i , x ) - f ( x ) ] = ( h o , x ) - f ( x ) f o r a l l X G C . Therefore sup[(h , x ) - f ( x ) ] < l i m i n f f * ( n . ) < 0 0 x e C ° ~ , 1 which implies h i s i n C* and f*(h ) < l i m i n f f*(n.) . * o s o — x 1 Since f* i s convex^the opposite i n e q u a l i t y h o l d s , therefore f* (h ) - l i m i n f f * ( h . ) and f* i s a closed convex f u n c t i o n . v o v 1 D e f i n i t i o n 1.7: The conjugate set of the set [ f , 0 ] , denoted oy [ f , C ] * , i s defined by [ f , C ] * = { [ c , h ] e E n + 1 : c > ( h , x ) - t , f o r a l l [ t , x ] e [ f , C ] j . Remark: From d e f i n i t i o n 1.6 and the remark preceding i t , [ f , C ] * = [ f * , C * ] . Theorem 1.1: I f Tf^C] i s a closed convex se t , then [ [ f , C ] * ] * = [ f , C ] . Remarks: (1) This theorem expresses the d u a l i t y p r i n c i p l e f o r con-jugate convex funct ions and sets . I t i s a well-known theorem, Fenchel ( [ l ] , [ 2 ] ) . A general ized v e r s i o n of t h i s theorem, developed i n the next s e c t i o n , w i l l be used to obtain c e r t a i n r e s u l t s on d u a l i t y f o r a c lass of convex programming problems. (2) Since [ f , C ] * = [ f * , C * ] , t h i s theorem implies that C = 0**, f = f** and m p a r t i c u l a r that f (x) = f * * ( x ) = sup [(n ,x)-f*(n)J. h€0* (3) The bas ic r e l a t i o n between [f,Cj and [ f * , C * ] Is that f * ( n ) + f (x ) > ( n , x ) , f o r a l l xeC, heC*. 11. For c o n s i d e r (1.7) f * ( h ) = s u p [ ( h , x ) - f ( x ) ] > ( h , x ) - f ( x ) i o r a i l xeU„ xeC ( l . o ) f ( x ) = sup!(ri,x)-f*(h) ] >_ ( h , x ) - f * ( h ) f o r a l l hee*. n s G * Then (1.7) and (1.8) imply ( l . y ) f * ( h ) + f ( x ) > (h,x) f o r a l l heo*, xeC. Co n v e r s e l y (1.9) i m p l i e s (1.7) and(1.8) s i n c e , (a) f * ( h j J> ( h , x ) - f ( x ) f o r a l l x i n C, i m p l i e s r * ( h j > s u p [ ( h , x ) - f ( x ) ] . T h e r e f o r e h i s i n C* ana xeC f*(n) * s u p [ ( h , x ) - f ( x ) ] . X€C (b) f ( x ) .>~(h,x)-f*(h) f o r a l l h i n C*, i m p l i e s f ( x ) _> s u p [ ( h , x ) - f * ( h ) j ; so t h a t xeC** = C and nee* f ( x ) = sup [ ( n,x)-r * ( h ) ] . K;sC* S e c t i o n 2: G e n e r a l i z e d Conjugate Sets and F u n c t i o n s . In t h i s s e c t i o n the concept of conjugate convex s e t s and f u n c t i o n s , as developed i n the p r e v i o u s s e c t i o n , i s g e n e r a l i z e d . R e s u l t s c o r r e s p o n d i n g t o those i n the p r e v i o u s s e c t i o n are o b t a i n e d , i n c l u d i n g a g e n e r a l i z e d v e r s i o n of the main theorem of the l a s t s e c t i o n . 12. D e f i n i t i o n 2 . 1 : Let A be an mxn matrix over the r e a l s , l e t f be a convex f u n c t i o n defined on a convex set C i n E n. Then the seb C A and the f u n c t i o n f A are Cfl = lyeE m:y=Ax f o r some x€CJ, defined Dy f A ( y ) = i n i { f ( x ) : y = A x , x e C ) , ycC^ . Lemma 2 . 1 : C A i s a convex set and f A Is a convex f u n c t i o n on C A . Proof: Let 0<X<1, ^ I ' ^ ^ A ' then there e x i s t s x ^,x 2 i n C such that y^ = Ax^, y^ = Ax^ . Tnen y = \ y 1 + ( i - \ ) y 2 = XAx x+(1-X)Ax g = A(\ x i + ( 1 - X ) x 2 ) = AX where x = X X l+( 1-X)x 2eC, since C i s convex . Hence yeC A and C A i s convex. For a l l €>0 and f o r a l l ^^'^2 l n CA t n e r e e x i s t s x ^,x 2 i n C such that y^ = A x ^ y 2 = A x 2 and i A ( y x ) + € > t ( x 1 ) , f A ( y 2 ) + 6 > f ( x 2 ) . Therefore f A [ X y 1 + ( i - ^ ) y 2 J < f [ X x J L + ( l - X ) x 2 J < ^ f ( x i ) + ( l - X ) i ( x 2 ) < X [ f A ( y 1 ) + e J + (i-X)[±A(y2)+eJ . Since - € i s a r b i t r a r y t h i s argument shows th a t f A i s a convex f u n c t i o n . 13 D e f i n i t i o n 2 . 2 : Let A be an mxn matrix and l e t 1 be a convex f u n c t i o n denned on the convex set C i n E n. The set € ana the f u n c t i o n f are defined by U = Ix € E n:Ax = Ax f o r some xeC] f ( x ) = i n f {f(x):Ax = Ax, xeC), xeC . Remarks: (1) As l o r and i ' A i t i s e a s i l y v e r i f i e d t h a t C i s a convex set and f i s a convex f u n c t i o n oh 6. Furthermore G A = G and = (2) I f y i s i n C^, x i s i n U ana y = Ax, then ±*A(y) = i n f {f(x):y=Ax=Ax, xeC} = £(x) . D e f i n i t i o n 2.3: Given a mxn matrix A ana the set [ f , C ] , the set P and the f u n c t i o n cp are definea by P = l§eEm:sup[§Ax-f(x)] < •} xeC cp(§) = s u p [ ? A x - r ( x ) ] , §€ T . xeC Remark: cp i s c a l l e a the conjugate f u n c t i o n of f w i t h respect to the m a t r i x A. Lemma 2.3: P Is a convex set ana cp i s a closed convex f u n c t i o n on P . Proof: S i m i l a r to the proofs of lemmas (1.4) and ( 1 . 5 ) -A Remark: I t i s c lear that the set F , f = {feE m :^A =§A, f o r some § e T ) i s jus t the set .T , and that cp(§) = cp(§ ). Furthermore cp(§) = s u p [ § A x - f ( x ) ] = s u p [ § A x - f ( x ) j f o r ?e F . xeC A xeC D e f i n i t i o n 2.4: ihe conjugate set with respect to the matrix A or the set [ r ,CJ i s denoted by [ f , C j J and i s defined by [ f , C ] | = £ [ c , S ] e E m + 1 : c > § A x - t , f o r a l l [ t , x ] e [ f , u]J Remark: When m = n and A = I } the i d e n t i t y matrix , then [ r , C ] » = [ f , u ] * . Lemma 2.4: [ f , u ] * = [cp,T ] Proof: Let [ c , § ] e [ f , c j * j then c >_ § A x - f ^ x ) for a l l x i n C Hence c >^  sup [§ A x - f (x) ] , so that ?e T and c >_ cp(§) . xeC Hence [ c , § J e [cp,!" 1]. Conversely, l e t [ c , § ] € [cp,!""], then c > cp(§) = s u p ( § A x - f (x) ] > § A x - f ( x ) , f o r a l l xeC xeC > ?Ax - t , f o r a l l [ t , x ] e [ f , C ] , Hence [ c , § ] e [ f , C ] * . Therefore [ f , C ] * = [ c p,T]. Lemma 2.5: t?A>CAl* = [f,CJ* . Proof Let [c,?] e [ f ^ C ^ ] * then c > ( 5 , y ) - f A ( y ) f o r a l l y i n C A; t n e i e f o r e c _> ? A x - f ( x ) 3 l o r a l l x i n C > § A x - t , l o r a l l [ t , x ] e [f,C] > Hence [c,§] e [ f , C j * . Conversely l e t [c,?] e [ f , C ] ^ , then c > §Ax-i(x f o r a i l X GC. Therefore f ( x ) >_ §Ax-c f o r a l l xeC. Let yeC A, then f A ( y ) = infCf ( x):y= A x , x € C } > inf{§Ax-c:y=Ax,x€C] = (§>y)-c • Since t h i s holds f o r any y i n C A, c > ( ? , y ) - f A ( y ) , f o r a l l yeC A > (§,y)-t , f o r a l l [ t , y ] e [ f A , C A J , Hence [c,?] e [ f A , C A ] * . Therefore [ f A , C A ] * = [ f , C ] * Remarks: (1) Since & A = C A and i A = l ' A , the previous two lemmas show th a t = [ r A , c A ] * = [ f , c ] * = [<P , T ] . (2) Let A' denote the transpose of the matrix A. Then the set PA, and the conjugate f u n c t i o n to cp w i t h respect to A 1, "P^,* a r e given by ' P A , = (heE n : h = ?A : f o r some §e p } cpA,(h) = mf{cp(§) : n = 5A,§e D , ae T A , • (;?) ihe conjugate set to | ' A, J i s given by [*A. I~A,]* = { [ t , x J e E n + 1 : t>(h,x)-c, V [c,h j e [cp A , T A r ]} . ( 4 ) The ge n e r a l i z e d conj'ugate set to [ c p , P ] w i t h l e s p e c t to A' i s given by [ < P , P ] * = { [ t , x j 6 E n + 1 : t>§Ax-c5\/[c,§ je [ cp , p j } . A' i (5) The previous lemmas can be a p p l i e d to the set [ c p , P J to o b t a i n [ c p , P j * , = [ ? A , } r A , J * • Lemma 2.0: [f ,CJc[f,ftjcfcp, P J*, . Proof: The d e f i n i t i o n of [f, f t ] i m p l i e s immediately t h a t [f,C]c[£,ft]. Suppose [ t , x ] i s i n [T,ftb then t>f(x ), x Is i n ft and — v o o *(?) = sup[?Ax-f(x)] = sup[?Ax-f(x)] > §Ax - T ( x J . § 6 T, xeC xefr - 0 0 ? Hence t>$(xo)>§AxQ-cp(?)>§Axo-c,\/[c,§] i n [<p,p]. Therefore [ t ,x ]e[cp, T ]£, and hence [f\ft]c [ c p , p ]*, # Lemma 2.7: t' Is a closed convex f u n c t i o n on C i f and only i f f ^ i s a closed convex f u n c t i o n on C^. Proof: Suppose f A i s closed. Let X Q be on the boundary of 0 and l e t Ix^J be a sequence of vectors i n O such that x -»x ana l i m i n f f ( x . )<<*>. Let 1 o x 1 y. = Ax.eC., y = Ax ; then y i s on the boundary n I A* J o o o of C.. Furthermore y.-*y and A J I J o •>lim i n f r ( x 1 ) = l i m i n f f A ( y x ) -Since i " A i s c l o s e d , y o G U A ' hence X q 6 U and r ( x ) = f . ( y ) = l i m m i f * ( y . ) < " . Therefore r i s O xv O xv X a closed convex f u n c t i o n . Conversely suppose f i s closed. Let y Q be on the boundary of and l e t l y } De a bounded sequence of vectors i n u A such that y ^ - ^ a n d l i m i r n° f A ( y i ) < c o > Then by Theorem A, appendix, there e x i s t s a set of vectors I x ^ j which i s boundea and such that y^ = Ax^ i'or a l l I furthermore since tx^} i s bounded there e x i s t s a con-vergent subsequence, which we assume to be the whole sequence, say x - , X q . Now »> l i m m l f A ( y 1 ) = l i m i n f and since f i s c l o s e d , x e& and hence y = Ax eC A. ' o ° o o A Furthermore °°>iim i n f i " A ( y )=lim i n f f ( x ^ ) ^ ( x Q ) = f A ( y o ) so that f A i s closed. lb. Lemma 2.8: [ t .x ]e[f,&] i f and only i f [ t ,Ax 1e[f f l,C.] 1 "• • • O O O O xi xi Proof: U o , x o ] e [ f , C ] i i and only i f t o > i ( x Q ) = f A ( A x Q ) , i f and only i f [ t ,Ax ]e[f.,C.] . 0 0 A xV Theorem 2.1: I f t^A^A^ 1 & a c^- o s e ( i convex set then rep, r i i , = Proof: Since "^A^ A^  1 S A C-'-OSEA convex s e t , by lemmas (1.2) and. (2.7), [f,C] i s a l s o a closed convex set. Assume [ t Q , x J i s not i n [ i , ^ J ; then by lemma (2.8), i f y = Ax , tnen [ t ,y j i s not i n \ i > J 0 o o o [ f A , C A J . Since f^A'^A^ i f a a c l ° s e ^ convex s e t , by lemma (1.3), there e x i s t s a n o n - v e r t i c a l hyperplane that s t r i c t l y separates [ t ,y Q] from the set [F^fGpJl ' Let the hyperplane P be P : ^ ( [ T , § q ] , [ t , y ] ) = k . Since T ^ O we can take T = - I , then (2.1) -t+(§Q,y) < k l o r a l l [ t , y ] e [ f A , C A ] , (2.2) -t + (? ,y ) > K . \ i o v o o 7 Therefore k > (§ o > y) . f A ( y ) t \/ y £ C A , and k > sup [(§„,y)-f A(y)] = SUD[§ A x - f ( x ) ] = sup[? A x - f ( x ) ] xeo f 19. hence § Q IS i n P and k>cp(? )• Therefore \ X & Q \ i s In [cp,PJ. From (2.2) t < (? *y )-k, and since t < (? ,y )-cp(§ ) = § Ax -q>(§ ) o v o ^ o 7 K oJ o o ^K^oJ > hence [ t ^ , x o ] i s not i n [ c p , P j ^ ( . Therefore [cp3 P ] A l c L r ^ , f t j . By lemma (2.6) the opposite i n c l u s i o n h o l d s , hence there i s e q u a l i t y , [cp,P]^, = [f^ft] • Kemarks: I f f ^ i s a closed convex f u n c t i o n then (1) The above theorem and the remarks f o l l o w i n g lemma (2.5), show that i$M = [<P,rji, = [«PA,A rA, J* . (2) Since [cp, P J = [ f , ^ ] * , the above remark shows that [ C ^ J A J A < = • (3) Since [r",&J = [cp, p J * ( , f i s conjugate co cp with respect to A', hence r ( x ) = sup[§Ax-cp(§) j , (t ) The basic r e l a t i o n oeuween a clo s e d convex i u n c t i o n and i t s g e n e r a l i z e d auai i u n c t i o n i s f (x)+cp(§ )>§Ax f o r a l l xeC ana f o r a l l §e P . 20. Sect ion 3: Concave Functions and t h e i r Duals A theory of conjugate concave functions can be constructed analogous to the theory given i n sec t ion 1 f o r convex f u n c t i o n s . The fac ts and d e f i n i t i o n s which w i l l be needed are obtained from those i n s e c t i o n 1 by interchanging < with +00 with -<=, and inilmum with supremum, wherever these occur. The r e s u l t s f o r general ized convex functions obtained i n s e c t i o n 2 a lso carry over to concave functions with the above mentioned interchanges. A l i s t of d e f i n i t i o n s and r e s u l t s i s g iven , f o r completeness. This w i l l serve to introduce the notat ion used i n the f o l l o w i n g sec t ions . D e f i n i t i o n 3 . 1 : Let g be a concave f u n c t i o n del ined on the convex set D i n E n . The set [g J3 ] i n E n + 1 i s defined by [g>D] = { [ s , x ] e E n + i : xeD, s<g(x)3 . Remark: [g,D] i s a closed convex set i f g i s a closed concave f u n c t i o n , that i s , - g i s a closed convex f u n c t i o n . D e f i n i t i o n 3-2\ Let A be an mxn matrix over the r e a l numbers. Let [g,D] be defined as above, then D A = ty£^m : y = A x f o r some xeDj g A (y) = sup {g(x) : xeD, y=Ax}, yeD A {xeE n : Ax=Ax f o r some xeD} sup ig(x) : Ax*=kx, xeD}, xeD { § € E m : inf [*Ax-g(x) ]>-• } X€D 1 i n f [?Ax-g(x)] , § € A . xeD Remarks: Using the arguments of the previous sections i t i s easy to v e r i f y that ( 1 ) D^ i s a convex set . ( 2 ) g^ i s a concave f u n c t i o n on D^. (3) 1> A-D A (*) g A = g A (5) A i s a convex set . ( 6 ) i|i i s a closed concave f u n c t i o n on A . D e f i n i t i o n 3.~j>: Given the matrix A and the set [g ,D] , the conjugate set to [g,D] with respect to the matrix A i s given hy [g ,D]* = { [ c , § ] e E m + 1 : c < § A x - t , V [ t ,x ]e[g ,D]) . Remarks: ( 1 ) As f o r convex f u n c t i o n s , the f o l l o w i n g r e l a t i o n holds [g,DJ* = [t|r,AJ = L g A . D A J * . ( 2 ) The main theorem of the previous sec t ion becomes under s i m i l a r r e s t r i c t i o n s [g,DJ = l ^ A ^ A l * = 0 , A J j and hence g(x) = i n f [§Ax-i|f (§ ) J. ?GA D = g(x) = A = 22. (3) For closed concave f u n c t i o n s the b a s i c r e l a t i o n between the f u n c t i o n and i t s g e n e r a l i z e d dual f u n c t i o n i s g(x)+i|; (? )< §Ax f o r a l l xeB , and f o r a l l §eA, provided g^ Is closed. S e c t i o n 4: D u a l i t y f o r Convex and Concave Functions The b a s i c r e l a t i o n s becween convex and concave f u n c t i o n s , given i n the previous s e c t i o n s , imply that i f E ^ A ^ A ^ A N D [ g A , D A J are closed then t(x)-Kp(§)>5Ax>^(x)+^(§) f o r a l l xcCOD and f o r a l l ?e P H A . Therefore (4.1) i n f [q>(5)-t(5)3 > sup A[g(x)-f(x)] . §er r iA xeCnD The main purpose of t h i s s e c t i o n i s to answer the question or e q u a l i t y i n (4.1). The f o l l o w i n g theorem due to Fenchel [ l j , answers t h i s question f o r the s p e c i a l case of ordinary dual f u n c t i o n s f * and g* . Theorem 4.1: Let f be a closed convex f u n c t i o n on the convex set C, l e t g be a closed concave f u n c t i o n on the convex set D. Let C and D have r e l a t i v e i n t e r i o r p o i n t s i n common, s i m i l a r l y f o r C* and D*. Then sun [g(x)-f(x)]= i n f [f * ( h ) - g * ( h ) J. . xeCDD heC*riD* and the supremum and infimum are a t t a i n e d . 23. The general v e r s i o n of t h i s theorem w i l l f o l l o w from the existence of a n o n - v e r t i c a l hyperplane separating two s p e c i a l convex s e t s , as w i l l he shown "by the next lemma. The existence of the n o n - v e r t i c a l hyperplane i s then assured by lemma (4.2). The general theorem i s then s t a t e d ana s e v e r a l r e s u l t s obtained. Lemma 4.1: Suppose th a t u = SUP A [ g ( x ) - f ( x ) j < ®. L e u xeOID f A ( y ) = f A ( y ) - H i , f o r a l l yeC A- I f the sets [ f A 5 C A J and and tsA>-DAJ c a n 1 3 6 s e P a r a t e d by a n o n - v e r t i c a l hyperplane, then there e x i s t s a § ef DA such that o i n f [*(?)-* ( ? ) J = * ( ? ) - • ( ? ) = s u p j g ( x ) - f ( x ) ] . §emA ° ° xeGTiD Proof: Let xeCflD N and y = Ax, then y€CAODA and i A ( y ) = Hx) > S A ( y ) = g( x ) . Therefore u = sup [ g ( x ) - f ( x ) J = sup [ g A ( y ) - f A ( y ) ] . xeCnS yecAnDA A A Let the n o n - v e r t i c a l s e p a r a t i n g hyperplane P be given by P : ( [ T , § q ] , [ t , y ] ) = c , normalized so that T=-1 , Then (4.2) -t+(5 0,y)<c o f o r a l l [ t , y ] e L f A , C A J (4.3) -t+(§ 0,y)>c Q f o r a l l [ t , y j e [ g A , D A ] . Prom ( f . 3 ) , (§ 0;y)-g A(y)>c o, f o r a l l yeD A, hence 5 q€A and • ( ? 0 ) > C q . From (4.2), ( § Q , y ) - T A ( y ) < c o \/ yeC A , 24. hence (5 Q , y ) - f A ( y ) < C Q + U SO that § Qe f 1 and co+u > cp(?Q). Therefore § e f 1 DA and s u p j | ( x ) - f ( x ) ] = n > <P(S0)-c > V(§0)-*(5_) xeCHD ~ o o - o o > i n f [cp(? )-•(§)] . ? e r n A Since the opposite i n e q u a l i t y (4.1) always holds , there must be equal i ty , This completes the proof of the lemma. Lemma 4.2: Suppose f f A > c A ] a n d t g A , D A ] a r e c l o s e d convex sets such that C/pD^ have r e l a t i v e i n t e r i o r points i n common. Suppose u = sup [ g A ( y ) - f A ( y ) ] < 0 0 . Let f"A(y) = fA(y)+M . yec AnD A for a l l y e C A . Then there ex is ts a n o n - v e r t i c a l hyperplane which separates [ g A , D A ] and ^ A * ^ ] . Proof: By the choice of \i the sets f f A * c A 3 a n d f s A ^ D A l come a r b i t r a r y close to each other but do not overlap at any i n t e r i o r points . Hence there i s a separating hyperplane P which Is a supporting hyperplane to both sets , We need to show i t i s n o n - v e r t i c a l . I f P i s a v e r t i c a l hyperplane, project ^ A , C A ^ ' [g A D A ] and P v e r t i c a l l y onto E m . The two convex sets project onto C A and D A , and the p r o j e c t i o n of P i s a hyperplane P of E m which must separate C. and D». This c o n t r a d i c t s the hypothesis that C A and D A have r e l a t i v e i n t e r i o r p o i n t s i n common. Hence P cannot be a v e r t i c a l hyperplane. j j u a l i t y theorem f o r convex and concave f u n c t i o n s . Theorem 4 . 2 : Let f be a closed convex i u n c t i o n on the convex set C, l e t g be a closed concave i u n c t i o n on the convex set D. Suppose L^A '^A^ A N D ^ A ^ A ^ a r e c l ° s e c * convex s e t s . Suppose ^A '^A h a v e r e l a t i v e i n t e r i o r p o i n t s m common and r A , j A A , have r e l a t i v e i n t e r i o r p o i n t s m common. Then the f o l l o w i n g statements are equi v a l e n t ( 1 ) sun [ g ( x ) - r ( x ) J i s f i n i t e . xeSnfi ( 2 ) i n f [ q p ( § ) - • ( § ) J i s f i n i t e . §ernA In e i t h e r case sup A [ g ( x ) - ^ ( x ) J = i n f [*(?)-•(§)] xeCTID § e r n A and the mfimum and supremum are a t t a i n e d . P r o o l : I f ( l ) holds then by lemmas ( 4 . 1 ) and ( 4 . 2 ) , there e x i s t s §Q€rnA such th a t sup A [ | ( x ) - f ( x ) j = < p ( ? J - * ( § ) = i n f [ q p(5) r*(S)J xeCDD ° 5emA and hence ( 2 ) holds. Conversely suppose ( 2 ) holds. Since [$,P] = [<p,~P] i s c l o s e d , by lemmas (1.2) and (2.7), [ c p A , J P a , ] i s closed. S i m i l a r l y [ \ | / A , ,A A , ] i s closed. Since P A , and A A, have r e l a t i v e i n t e r i o r p o i n t s i n common, lemmas (4.1) and (4.2) can be a p p l i e d to the f u n c t i o n s cp and i|> . Since [t\&] = [ c p , P ] * , and [g,DJ = [cp,A]£, by theorem (2.1), lemma (4.1) shows there e x i s t s x_e such th a t v o sup [ c p ( § ) - c p ( § ) ] = f ( x j - g ( x ) = i n f [ f ( x ) 4 ( x ) ] . Hence ( l ) holds and furthermore £(x Q)-f(x ) = s u P r g ( x ) - f ( x ) J = Inf [*>(§)-•(*)] = «p(§0)-y(s0) • Remarks: From theorem (2.1) and the remarks f o l l o w i n g , d e f i n i t i o n (3-3) (1) g(x) = i n f [§Ax-t (? ) ] ?eA (2) c p ( § ) = sup [§Ax-f(x)J xeC (3) f ( x ) = sup L§Ax-cp(§)j (4) • ( ? ) = i n j L 5 A x - | ( x ) J . xeD ihese r e l a t i o n s and the previous theorem give the f o l l o w i n g r e s u l t s . 27. (4.4) sup i n f [?Ax-* (§ )-f(x) J = mi sup[?Ax-ilr (§ ) - f (x) j xeCDD ?€A §efnD xeC (4.b) sup. i n f [g(x)-Kp(§)-?AxJ = i n f sup[g(x)-Kp(§ )-?AxJ. xecrfD §ep ?€|TlA xeD Theorem 4.3: under the hypothesis of theorem (4.2), the infimum and supremum i n equations ( 4 . 4 ) and ( 4 . 5 ) can be ( 1 taken over the smaller sets P OA and font) r e s p e c t i v e l y . Proof: To show that the infimum and supremum can be taken over the smaller sets PflA and cnft, f i r s t note that (4.6) qp(§) - * ( ? ) = sup [?Ax-*(§)-r(x)] X€C > sup T?Ax-cp(f)-f(x)] xecnD (4.7) g(x) - f ( x ) = i n f [§Ax-*(?)-r(x)] ?eA < i n f [§Ax-i|r (§)-f(x)] . ~ §€pnA Hence (4.o) sup A i n f [§Ax-1|f(?)-f(x)] xeUflD SelTlA > sup [ g ( x ) - f ( x ) ] x€cnD = i n f [qp(§ )-•(§)] SerriA > i n f sup [ ? A x - * ( ? ) - ^ ( x ) ] . §ernA XGC71D Since the opposite i n e q u a l i t y always ho l d s , there i s e q u a l i t y . 28 Therefore (4.y) sup i n f [SAxHlr(S)-f(x ) 3 xecnf) ?ernA = i n f supA[§Ax-* (§)-£(x)] Tn the same way i t can be shown tha t (4.10) su.pA i n f [g(x)+cp(§ )-§Ax] xeCDD § ePHA = i n f s \ j p A [ g ( x ) - K p ( ? ) - ? A x ] . §emA xeCHD Remarks: Under the hypothesis of theorem (4.2), i t i s e a s i l y v e r i f i e d t h a t ( l ) The supremum and infimum i n equation (4.4) can be taken over the l a r g e r sets 0 and A r e s p e c t i v e l y . (z) The supremum and infimum i n equation (4.5) can be taKen over the l a r g e r sets D and P r e s p e c t i v e l y . S e c t i o n 5: Lagrangians and Dual Convex Programming Problems A convex programming problem w i l l mean e i t h e r minimize a convex f u n c t i o n over a convex s e t , or maximize a concave f u n c t i o n over a convex set. In t h i s s e c t i o n the close connection between a saddle-p o i n t of an appropriate Lagrangian f u n c t i o n and the s o l u t i o n s to a p a i r of dual convex programming problems w i l l be studied. 29-These problems and t h e i r a s s o c i a t e d Lagrangian f u n c t i o n s w i l l extend the d u a l i t y theory of the previous s e c t i o n s . In p a r t i c u l a r a d u a l i t y theorem f o r a p a i r of convex programming proolems i s given. D e f i n i t i o n 5.1: Let f be a closed convex f u n c t i o n on the convex set C and l e t g be a closed concave i u n c t i o n on the convex set D. Let [ i , C ] J = [cp^TJ, [ g ,D j * = [cp,AJ. Then the Lagrangian f u n c t i o n s F , G , F , U " are defined by (5-1) F(x,§) = §Ax-f(x)-(jr(§ ), {x,§} € UXA (5-2) G(x,§) = g(x)-Kp(§ )-§Ax3 Cx,§} e Dxr (5-3) F(x,§) = §Ax-f(x)-t(§), {x , §3 e-OxA (5 .4) &(x,§) = g(x)-Kp(5)-§Ax, [ x a ? } e f i x r . D e f i n i t i o n 5.2: The p a i r of vectors [x* i s c a l l e d a saddle-point of a Lagrangian i u n c t i o n L(x,§) i f (5-5) L(x*?) > L(x*,§*) > L(x,§*)?\/{x,§3 i n the domain or L. Lemma 5.1: Let g^ be a closed concave f u n c t i o n . Suppose {x o,§ o3 i s a saddle-point of F(x,§) such that F ( X Q , § O ) Is f i n i t e ; then (1) x e CflD and § e PflA s ' o o (2) <P(S 0M(S 0) = F(x o,§ o) = g ( x o ) - f ( x o ) (3) cp(§ )-f(§ ) = inf [<*>(?)-•(§)] 0 0 § ernA (*0 g(x ) - f ( x ) = sup [ g ( x ) - f ( x ) ] . 0 0 xccnfi Th i s s£rp t o JWJLC : a l l No fix MP „ T i t l e filta j u t ; Vo ls _ Years Dono r No of bd vol s T i e - u p : Note f o r Cat <2_ CO/ot&<=> F r OP i t Crest Date No of vo1s Rebind Bind eve ry th inq "As i s " Bind a l l but back cove 1-5 & s t i f f advts V o l s , s p l i t in to boot Put TPC in book Put Index in book: No main TP Use f ron t cover no No main Contents No ma i n Index Ind i v i dua l contents Tog. at f ron t Where they appear Inelude al1 tex t 1n Front advts Back adv t s . V o l s , sep by ,<raft f ron t cr Pocket Folded ma te r i a l No Trim Co lo r / V / ? / / , A ,-rangement 30 Proof; Since l x o , S Q } i s a saddle-point of F ( x , % ) , S A x Q - f ( x o ) - t ( 5 ) > F ( x Q , 5 0 ) > 5 0 A x - f ( x ) - t ( ? o ) f o r a l l § I n A and f o r a l i x m CV ihe i l r s t i n e q u a l i t y i m p l i e s i n f [§Ax -•(§)-f(x ) ] > F ( x ,? ) > -» §eA ° ° 0 t h e r e f o r e x e D and o F ( x ,5 ) < g(x )-f(x ) , x e UflD . v o o y — toV o v o o ihe second i n e q u a l i t y i m p l i e s - > F ( x ,? ) > sup [LAx-f(x)-t(§ )] ° ° xeC 0 ° t h e r e i o r e § q e p and F ( X Q , § o ) > cp(§q)-<r ( § Q ) , § q e PDA . Since i n f [<p(§ )-<|r (§ ) J >. sup [ g ( x ) - f ( x ) ] always h o l d s , §€|TIA xeCM3 the infimum and supremum are a t t a i n e d at the p o i n t s § Q and X q r e s p e c t i v e l y . Lemma 5.2: Let f ^ be a closed convex f u n c t i o n . Suppose IXJ^SJ^} i s a saddle-point of G(x,§ ) such th a t G(x i s u n i t e , then (1) x ± e oTlD and § e THA (2) cp(§ i)-t(§ i) = G ( x i , 5 i ) = g ( x i ) - f ( x 1 ) 31. (3) ?(§•,)-* (Si) = i n f [cp(S )-•(?)] 1 1 § e|TiA ( 4 ) g(x )-?(x ) = sup [ g ( x ) - f ( x ) ] x 1 xeUHD Proof: S i m i l a r to lemma 5-1 • Kemarks: i n terms of Lagrangian J u n c t i o n s , che remarks f o l l o w -i n g theorem (4.3) show that i f there e x i s t vectors x* € Cni) and §* e [TlA such t h a t g ( x * ) - f ( x * ) = <p(5*M(5*) , then {x*,§*} i s a saddle-point f o r both F(x,§) ana a(x,? ) • The converse statement i s a l s o t r u e , as i s shown by the f o l l o w i n g theorem. Theorem 5.1: Let f ^ and g^ be closed. Then the statement ( i ) {x*,§*} i s a saddle-point of F(x,§) and F(x*,§*) i s f i n i t e . i s e q u i v a l e n t t o the statement ( i i ) {x*,§*} , i s a, saddle-point of 6(x ,5) ana 6(x*,§*) i s f m i t e . Furthermore (1) ( 2 ) ( 3 ) x* e CODY\§* e PfiA g ( x * ) - f \ x * ) = ¥(§*)-•(§*) (4) g ( x * ) - i ( x * j = sup [ g ( x ) - t \ x ) J xeuDD ¥ ( § * ) - * ( § * ) = inf [<P(S)-M§)] SelTtA J>2. (5) F(x*>5*) = G(x*,?*) = < * ( § * ) - • ( § * ) . Proof: I f { x * , § * 3 i s a saddle-point of F f o r which F ( x * § * ) i s f i n i t e , then using the proof of lemma (5«l) with f replaced by £ , C with C, i t i s easy to v e r i f y that ( l ) , (2), (3) and (4) h o l d . But the remarks preceding t h i s theorem show that i f ( l ) and (2) h o l d , then { x * , § * } i s a saddle-point of dr(x,g) , and then (5) holds . Conversely a saddle-point { x * , § * } of G i s a lso a saddle-rs point of F by a s i m i l a r argument. Lemma 5-3: Let f a , g , be c losed. Let {x ,§ } be a saddle-i\ I\. o o point of F. ,lx*>,?*3 be a saddle-point of F , and Cx^,?^ he a saddle-point of G, such that F ( x Q g Q ) , F(x*S*) and G ( x _ L , § 1 ) are a l l f i n i t e . Then (1) p ( x 0 J ? o ) = F(x*,?*) = G ( x 1 , ? 1 ) (2) f ( x o ) = f ( x o ) , 6 ( X ] L ) = g ( X l ) (3) ^ x o ^ o ^ 1 8 A S A D D L E ~ P O I N ' T o f P ( x ^ § ) ( 4 ) ^ x i ^ ] ^ i s a saddle-point of F ( x , § ) , Proof: By the preceding theorem and lemmas (5-1) and (5.2), F(x ,§ ) = <p(§ M(? ) = i n f [qp(§ )-•(?)] 0 0 o o ? g r n A F ( x * , § * ) = * ( ? * ) - • ( § * ) = i n f [ < ? ( § ) - • ( ? ) ] 5crnA G(x ,§ ) = cp(§ )-*(§-.) = i n f [cp(?)-•(?)] 1 1 1 1 §ernA 33. t h e r e f o r e F ( x o , § o ) = F ( x * , § * ) = G(x ,§ ) . Since ^ x 0'5 0^ 1 S a saddle-point of F ( x , § ) and { x * , § * } i s a saddle-point of F ( x , § ) , by lemma (5 .1 ) and theorem ( 5 . 1 ) , § § e rnA. Hence o F(x ,§ ) = § Ax - f (x )-4 (? ) v o a o' o o v o' y v o y < 5 * A x 0-f ( x 0 ) - * ( 5 » ) < 5 * A x 0 - ? ( x 0 ) - t ( ? » ) < ?*Ax*-f (x*)-*(?*) = F(x*>§*) = F(x o,§ Q) . Therefore there i s e q u a l i t y throughout; thus f ( x Q ) = ^ ( X Q ) and F ( x O , S Q ) = F ( X q J § o ) = F ( x » , ? * ) . r i A Now ixoJJ§oi i s a saddle-point of F since F(x Q ,g ) = F(x Q ,5) > F(x o,§ o) = F(x o,§ o), \/§ e A and F(x o,§ o) = F ( x o , 5 0 ) = «P (5 0 ) -f(g 0 ) •: > F ( x , § o ) ) Vx e C . S i m i l a r l y i t i s easy to v e r i f y t h a t ( i ) g(x 1) = g(x x) . ( i i ) G ( x l J § 1 ) = G ( x 1 , ? 1 ) = G(x*,§*) = F(x*,§*) . ( i i i ) lx l 5§ 1J i s saddle-point of G and hence or F . (iv) G(x1,§1) = F(x 1,§ 1) = F ( x * , S * ) . 34. Remarks: The Lagrangian f u n c t i o n s of t h i s s e c t i o n , the d u a l i t y uheorem (4.2) and the r e s u l t s of the previous s e c t i o n i are a l l r e l a t e d t o the f o l l o w i n g convex programming problems. Problem I: Find s u p [ g ( x ) - f ( x ) j f o r x e ODD. Problem I I : Find i n f [qp (?)-•(§ )J f o r ? e [TlA . A Problem I: Find sup[g(x)-£(x) ] f o r x e 6nf>. The Lagrangian f u n c t i o n s F and G are as s o c i a t e d w i t h problems I and I i , and the Lagrangian f u n c t i o n s F A A and G are a s s o c i a t e d w i t h problems I ana I I . The d u a l i t y theorem (4.2) and the r e s u l t s of t h i s s e c t i o n can now be summarized i n the f o l l o w i n g d u a l i t y theorem f o r convex programming problems. Theorem 5-2: Let f be a closed convex f u n c t i o n on the convex set C and l e t g be a closed concave f u n c t i o n on the convex set D. Suppose t h a t f ^ and g^ are c l o s e d , ^ A / ^ A h a v e r e l a t i v e i n t e r i o r p o i n t s i n common, and F ^ J A ^ , have r e l a t i v e i n t e r i o r p o i n t s i n common. Then the f o l l o w i n g statements are equiv a l e n t : ( l ) Ix*/?*] i s a saddle-point of t- and F(x*,§*) i s f i n i t e . 35-(2) l x * , § * } i s a saddle-point of G and G ( x * , § * ) i s f i n i t e . (3) • x* maximizes g(x) - f (x ) i n Problem I, and ?* minimizes <p(§)-i|f(§) m Problem II . (4) g (x* ) - l (x* ) = < ? ( § * ) - • ( § * ) , x*e6nD, ?*rnA . Sect ion 6: Comparison of D u a l i t y Theorems In t h i s sec t ion the well-known d u a l i t y theorem f o r l i n e a r programming w i l l be obtained from the d u a l i t y theorem (5 .2) . Theorems (4 .2 ) and ( 5 ° 2 ) are then compared with a d u a l i t y theorem due to Dorn [3 j . Dorn's theorem w i l l be derived from theorem (4 .2 ) under the assumption that the functions involved have continuous f i r s t p a r t i a l d e r i v a t i v e s . Lemma 6.1: Let b be a constant vector i n E m , c a constant vector i n E n and A a mxn matrix of rank m <_ n. Let C = £ x e E n : Ax <_ b ] , D =' {xeE n : x > 0} . I f f (x) = 0 f o r a l l x e 0, g(x) = (c,x) t o r x e D , then the convex programming problems I and II become the f o l l o w i n g l i n e a r programming problems. Problem I ' : Maximize (c ,x) subject to Ax _< b , x _> 0. Problem I I ' : Minimize (? ,b) subject to §A _> c, % > 0. Proof: C l e a r l y under the condit ions stated the convex program-ming problem I becomes problem I ' . Now 36. C = {xeE n : Ax < b} i = f x e E ^ ?Ax < (§ , b ) , ? > 0} hence by d e f i n i t i o n P = {?eEm: sup ?Ax < » } xeC = { ? e E m : § > 0} and f o r ? e f , cp(§ ) = sup §Ax = (§ ,b) xeC since rank (A)= m. Now D = {xeE n : x > 0 } hence by d e f i n i t i o n A = ( § e E m : i n f l f i A x - ( £ , * ) 3 > -00} XSD = { § e E m : i n f (?A-c ,x) . > -•} x_>0 = { § e E m : § A - c > 0} and f o r § e A> • (? ) = i n f (?A-c,x) = 0 . x>0 Hence problem II becomes problem I I ' . Remarks: The associated Lagrangian functions P and G f o r problems I and II reduce to the f u n c t i o n s : G(x,§) = (c ,x) + (? , D ) - §Ax defined on Dx P , and F(x,?) = ?Ax defined on CXA . 36. C = {xeE n : Ax < b} = {xeE n : §Ax < (5 § > 0] hence by d e f i n i t i o n p = { § € E m : sup §Ax < oo} xeC = { ? e E m : § > 0} and f o r § e p , cp(? ) = sup §Ax = (§ ,b) xeC since rank (A)= m. Now D = {xeE n : x > 0} . hence by d e f i n i t i o n A = [?eE m : i n f g A x - ( E , x ) 3 > -»} X5D = { § e E m : m f (?A-e,x) , > - » } x>_0 = { § e E m : ?A-c >_ 0} and f o r § e A ; • (? ) = i n f (?A-c ,x) = 0 . x>0 Hence problem II becomes problem I I ' . Remarks: The associated Lagrangian functions F and G f o r problems I and II reduce to the f u n c t i o n s : G ( x , § ) = (c , x ) + (? ,b) - §Ax defined on DxP , and F ( x a ? ) = ?Ax defined on CXA . 37. D e f i n i t i o n 6.1: Let A be an mxn matrix with rank m <_ n and let b be a constant vector i n E m . Let C = {xeE n :Ax <_ b j , D = (xeE n : x _> O] and suppose f(x) = 0 on C. Let g be a closed concave f u n c t i o n defined on the set D and suppose that g has continuous f i r s t p a r t i a l d e r i v a t i v e s on D. Then the f o l l o w i n g convex programming problems are def ined: Problem 1: Maximize g(x) subject to Ax _< b , x _> 0 Problem 2: Minimize H(x ,§ ) = ( § , b ) + g(x) - ( V g ( x ) , x ) subj'ect to ?A > \7g(x), § > 0. Note that these problems reauce to the l i n e a r programming problems I ' and i l ' when g(x) = ( e , x ) , c a constant vector i n E n . The f o l l o w i n g d u a l i t y theorem f o r the programming problems 1 and 2 i s due to Dorn [3]-Theorem 6.1: (Dorn) Let the programming problems 1 and 2 be given as i n d e f i n i t i o n ( 6 . i ) . Let K = l x e E n : §A >.\7g(x), ? _> 0} , S = C y e E n : ?A >^  y, § > 0 ] , The transformation y = y g ( x ) maps R onto S, and there e x i s t s a f u n c t i o n which maps S onto R. I f t h i s f u n c t i o n i s once d i f f e r e n t i a b l e and one-to-one i n a neighborhood of the maximum, then the•fol lowing statements h o l d . 38. (1) I f there ex is t s a vector x* which maximizes g(x) i n problem 1, then chere a l s o e x i s t vectors x = x*, § = § * which minimize, H ( x , § ) m problem 2. (2) Conversely i f x*, § * are vectors which minimize H ( X > ? ) i n problem 2, then x = x* maximizes g(x) i n problem 1. Furthermore maximum g(x) = minimum H ( x , § ) . In order to compare Dorn's r e s u l t s with our d u a l i t y theorems, the f o l l o w i n g lemmas w i l l be needed. Lemma 6.2: Let g(x) be a concave f u n c t i o n defined over the convex set D, with continuous f i r s t p a r t i a l d e r i v a t i v e s on D. Then f o r a l l points x, x* i n D, (VsU), x*-x) > g(x*) - g(x) . Proof: The r e s u l t i s well-known. A proof can be found i n Dorn's paper I 3 j . Lemma 6.3: Let g(x) be a closed concave f u n c t i o n defined on the convex set D = l x e E n : x _> 0} , with continuous f i r s t p a r t i a l d e r i v a t i v e s on D. Let Y = [ § e E m : min r§Ax-g(x)] = § A x * - g ( x * ) > x*> 0] x>0 Then f o r any ? e Y there ex is t s x* _> 0 such that (1) §A > \7g(x*) (2) 5Ax* = (\7s(x*)> X * K 3 9 -Proof: Let ? e Y "be f i x e d . (1) by d e f i n i t i o n of Y there e x i s t s x* _> 0 such that SAx* - g(x*) < §Ax - g ( x ) , \/x _> 0. Hence by lemma (6.1), (\7g(x),x*-x) > g(x*) - g(x) > (?A,x*-x), \/x > 0 t h e r e f o r e ( ? A - \ 7 g ( x ) , x-x*) > 0, \/x > 0 . Let x = x* + Xe i, X > 0, e = (0,...,0,1,0,...,0) e E n ; then (?A - \/g(x*+ke±), Xe.^) _> 0 f o r each 1 . Therefore ( ? A ) x J> ^ ^ f ^ f i , ) ) f o r each i . Hence by the c o n t i n u i t y i of the p a r t i a l d e r i v a t i v e s of g, t a k i n g the l i m i t as X -• 0 gives (6.1) §A > \ 7 s ( x * ) . (2) I f x* jt 0 and x* = 0 f o r I e I , 1 a subset of { l , 2 , . . . n } , then f o r i e" I and f o r X > 0 small enougn, x* - Xe, > 0. Tnen I — (?A - \ 7 g ( x * - X e i L -Xe ) > 0 i m p l i e s (§A) t - ^(x^-Xe^^) >, < Q f Q r x ^ j . Hence by c o n t i n u i t y of the d e r i v a t i v e s , (SA) < f o r i i I . I Now by the equation (6 l ) the opposite i n e q u a l i t y holds, hence (§A). = |§( x*) - f o r i f[ I ..Therefore 1 OX. 1 40. (6.2) §Ax* = (Vg(x*), x*) . Lemma 6.4: Leu g be a closed concave i u n c t i o n d e n n e a on the set, D = { x £ E n : x _> 0}, with continuous f i r s t p a r t i a l d e r i v a t i v e s on D . Let Y be the set defined i n lemma (6.3) and l e t § e Y be f i x e d . Let W = [ x : § A >Vg ( x ) , x _> 0} . Let x* > 0 be such that h(§) = mln[?Ax-g(x)] = ?Ax* - g(x*) x>0 Then -h(§) = min[g(x) - (Vg (x) ,x ) ] . x e ¥ Proof: By lemma (6 .3) , x* e ¥ and §Ax* = (\7g(x*)>x*)\ hence min[g(x) - (Vg(x) ,x)} < g(x*) - (\7g(x*),x*) x e ¥ = g(x*) - ?Ax* = -h(?) . A l s o f o r x e • g(x) - (\/g(x) ,x) _> g(x) - §Ax; hence min[g(x) - (Vg ( x ) , x ) ] > min[g(x)-?Ax] > min[g(x)-?Ax] xeW x e ¥ x>0 = g ( x » ) - §Ax* = -h(?) . Since both i n e q u a l i t i e s h o l d , there i s e q u a l i t y and -h(?) = min[g(x) - (\/g(x),x)] . x e ¥ The comparison with Dorn's r e s u l t s i s contained i n the f o l l o w i n g lemma. 41. Lemma 6.5: The convex programming problems I and II reduce to the programming problems 1 and 2 i f the sets C and D and the functions f and g are as i n d e f i n i t i o n (6 .1) , and i f i n f [?Ax-g(x)j i s a t ta ined f o r a l l ? e A . x>0 Proof: (1) The convex programming problem I c l e a r l y reduces to problem 1 under the condit ions s tated. (2) As i n the proof of lemma ( 6 . l ) i t i s c lear that r = t§ e E n : § > 0} cp(5) = sup [§Ax:Ax <_ b] x = (5 ,b) f o r § e P , since the rank of A i s m . (3) A = { § e E m : i n f [?Ax-g(x) ] > - » } = { § e E m : m i n [ § A x - g ( x ) ] > - » } . x>0 xfO Since by assumption the infimum i s a t ta ined at some x >_ 0, A = Y given i n lemma (6.3) and (6 .4) , f o r § e A , -•(5) = " m i n [SAx-g(x)] = min (g(x) - (Vg(x) ,x) : § A >Vg(x)3 . x> 0 x>_0 ' ~ Therefore the convex programming problem II ; minimize ( § , b ) - (? ) f o r ? eT^1 A becomes problem 2; minimize H (x ,?) = ( ? , b ) + g(x) - (Vg (x ) ,x ) subject to ? >_ 0, §A ^  Vg ( x ) , x >. 0 • 42. BIBLIOGRAPHY 1. W. Fenchel , On Conjugate Convex Functions , Canad. J . Math. 1 (1949), 73 - 77 . 2. ¥ . Fenchel , Convex Cones, Sets and Functions , Lecture Notes (mimeographed), Princeton U n i v e r s i t y , 1953-3. ¥ . S . Dorn, A D u a l i t y Theorem f o r Convex Programs, IBM J . Res. Develop . , 4, (19b0), 407 - 413. 4. S. K a r l i n , Mathematical Methods and Theory i n Games, Programming''and- Economics, V o l . I , Addison Wesley, Reading Mass . , 1959« 5. R. Courant, D i f f e r e n t i a l and Integral C a l c u l u s , V o l . I I , Intersc ience , New York, 193b. APPENDIX 43. Theorem A: Let A hy any matrix over the r e a l numbers. L o t t y ^ j ^ i be* a bounded set of vectors i n the range of A. Then there ex is t s a set of vectors {x±}, 1 e I , which i s bounded and f o r which Ax = y f o r a l l i e I . Proofs Let A be m*n , l e t r = rank A < min (m,n). Then A can be reduced by elementary row and column operat ions , to a matrix A , i s a rx r i d e n t i t y matrix , ° 1 i s a rx (n-r ) zero matrix , °2 i s a (m-r)xr zero matrix , °3 i s a (m-r)x(n-r) zero matrix . That i s , there e x i s t non-s ingular matrices P and Q, P i s (mxm) , Q i s (nxh), such that PAQ = A* . The system of equations (1) Ax± = y± , i € I i s equivalent to the system (2) PAQQ" 1 x i = P y , i e I or (3) I z . = u). x 1 1 where u>. = P y . , z. = Q x. , i e I. 1 ' i ' i I ' Now the set {UJ^} = {Py^J i s bounded since P i s non-s i n g u l a r and fy^} i s bounded. Furthermore (3) obviously has a bounded s o l u t i o n z^ f o r a l l i e I. Hence taking X i = ^ Z i ' 1 e I ' o n e h a s a s e t ^ x i ^ i G I , which i s bounded since Q i s non-s ingular , and' f o r which Ax^ = y i f o r a l l i e I . 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080576/manifest

Comment

Related Items