Convexity ISYE 7682
Popular in Course
Popular in Industrial Engineering
This 0 page Class Notes was uploaded by Maryse Thiel on Monday November 2, 2015. The Class Notes belongs to ISYE 7682 at Georgia Institute of Technology - Main Campus taught by Renato Monteiro in Fall. Since its upload, it has received 12 views. For similar materials see /class/234184/isye-7682-georgia-institute-of-technology-main-campus in Industrial Engineering at Georgia Institute of Technology - Main Campus.
Reviews for Convexity
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
Lecture Notes in Convexity Instructor Renato D C Montoiro November 8 2008 def subspace finemanifold Chapter 1 Convex sets 11 Notation In this section we introduce some global notation and terminology that will be used throughout our presentation We write V Q W to indicate that the set V is a subset of the set W We write a E V resp a 52 V to indicate that a is resp is not an element of the set V We denote the sets of real numbers real n vectors and real in x72 matrices by ER ERquot and 33mm respectively For scalars a g 3 de nea tE Ralttlt a tE Rza t a tE Ra tlt and a 3 z t E 33 a lt t g Given two distinct vectors 33 E ERquot de ne any 2 1 cm 023 a E 01 331 2 1 aaa3aE 011 33 2 1 aaa3aE 11 3y 2 1 cm 023 a E 0 1 Note that if a 3 then all the above sets reduce to the singleton Otherwise they describe the four possible segments connecting a and 3 depending whether the endpoints a and 3 are included or not to the segment 12 Subspaces and Af ne Manifolds De nition 121 A nonempty subset V 9 33quot is a subspace if it is closed under addition and scalar multiplication that is 0mm alga E V for every mama E V and cm on E 33 De nition 122 A nonempty subset V Q ERquot is an af ne manifold if am 1 aa1 E V for every mama E V and a E 33 In other words a subset V of ERquot is an af ne manifold if for any two elements mama of V the line passing through 30 and 31 is in V Singletons lines and ERquot itself are examples of af ne manifolds It is easy to see that a subset of ERquot is a subspace if and only if it is an a ne manifold containing the origin Figure 11 The set V is an a ne manifold V 30 is a subspace for some 30 E V figzsubspac Exercise 123 Let V Q ERquot be an af ne manifold Prove that for every 30 E V the set V 30 is a subspace which does not depend on 30 see Figure 11 De nition 124 The dimension of an af ne manifold V Q ERquot is the dimension of the subspace V 30 where 30 is an arbitrary point in V De nition 125 A ERquot gt 33 is an af ne map if for every mama E ERquot and a E ER Acmu 1 aa1 aAau1 aAa1 Exercise 126 Prove that A 33quot gt 33 is an af ne map if and only if there exists T E 337quot and b E 33 such that Aa To b for all a E ERquot affmap affman Proposition 127 Let A ERquot gt 33 be a linear resp af ne map Then a IfV Q 33quot is a subspace resp af ne mainfold then AC Aa a E C Q 33 is a subspace resp af ne mainfold b IfD Q 33 is a subspace resp af ne mainfold then A 1D E 33quot Aa E D is a subspace resp af ne mainfold zoperaffman Proposition 128 The following statements hold a fl is a set of indexes not necessarily nite and W39th is a family of subspaces resp af ne manifolds of ERquot then We W is a subspace resp af ne manifold b If W Q ER i 1k are subspaces resp af ne manifolds then V1 gtlt gtlt Vc Q ER gtlt x 337 is a subspace resp af ne manifold c If on cuc E 33 and V1 Vk Q 3quot are subspaces resp af ne manifolds then a1V1 miach 2 a131 miawn mi E WVi1k is a subspace resp af ne manifold De nition 129 A linear combination of 31 E E ERquot is any point of the form man means where on ka E 3 Such a point is said to be an af ne combination ofm1 mk E 33quot if in addition on Q 1 zaffineComb Proposition 1210 V Q ERquot is a subspace resp af ne manifold if and only if every linear resp af ne combination of elements ofV is in V 2 Actionaffman axerczaffcart If S is a nonempty subset of ERquot we can construct the smallest with respect to inclusion subspace or af ne manifold containing S This can be accomplished in two different but equivalent ways namely by means of an outer construction or an inner construction De nition 1211 Outer Constructionz Given a set S Q ERquot its linear hull linS and af ne hull affS are de ned as lin S aff S O V Vis a subspace S Q V 11 O V Vis an a ne manifold S Q V 12 Proposition 1212 Inner Construction IfS is a nonempty subset of ERquot then a linS set of all linear combinations of elements of S b a S set of all af ne combinations of elements of S De nition 1213 The dimension of a set C Q ERquot denoted dimC is de ned as dimC z dima C Exercise 1214 Show that if Sihgr is a family of sets in ERquot then a migSi Q nieia si Also give an example to show that the reverse inclusion does not hold even when I 1 2 Exercise 1215 For an af ne map A 3quot gt 33 the following statements hold a a AS Aai39fS for any S Q 33quot b a A WT Q A Wa 39T for any T Q 3339 Exercise 1216 Give an example showing that the inclusion in Exercise 1215b can be strict Exercise 1217 For sets S Q 3339 i 1k we haveaffS1gtltgtltSca S1xxa Sk 13 Af ne independence Recall the following de nition from Linear Algebra De nition 131 The vectors x1 xk E ERquot are linearly independent if cmka 6 ER gtQ1uc0 a1x1akxk0 The following facts of linear algebra are well known A necessary and suf cient condition for 1 xk E 3quot to be linear independent is that the dimension of the subspace lin 31 xk be equal to k Also a necessary condition for k vectors in ERquot to be linearly independent is that k g 72 We will now give another notion of vector independence which is more suitable in the study of convex analysis namely that of a ne independence First we state the following technical result Lemma 132 Let V S Q ERquot Then a S 339 linS for any 339 E affS 3 Proof 9 The set lin S T 339 is an af ne manifold which obviously contains the set S It then follows from de nition 12 of a ne hull of a set that aff S Q lin S 5 or equivalently affS 339 Q lin S 2 The assumption that 339 E aff S implies that aff S 339 is a linear subspace which obviously contains the set S 5 It then follows from de nition 11 of linear hull of a set that a S 3 Q lin S I Proposition 133 Let 30 31 m E 3quot be given Then the following statements are equivalent a dimaga1 mk k b dimlin 30 5 ac k for some or any 339 E a u1 Wm c the vectors 31 30 mk 30 are linearly independent d the equations 2260 621551 2 0 and 210 on 0 imply that cm 2 a1 a 0 e the vectors mu1a11ac1 E 3quot X 33 are linearly independent Proof a f b For xed 339 E affag mk we have dimmmac dima agak a dimlin 5120Ec dimlinag a ac where the second equality follows from Lemma 132 b t Statement b with 3 30 is equivalent to dimlin 31 30 mk 30 2 k and hence to the vectors 31 30 mk 30 being linearly independent 0 f d The vectors 31 au mk au are linearly independent if and only if on one 0 0 is the only solution to the system ELI 30 2 ELI mm 2quot1 omen 0 The latter conclusion reduces to statement d upon letting a0 L2 d f e Follows immediately from the fact that the equations 221 mm 0 and ELI a 0 are equivalent to the single equation ELI aa 1 0 I De nition 134 The vectors 30a1 mk are af ner independent if any one of the equivalent statements of Proposition 133 holds Clearly a necessary condition for k 1 vectors in ERquot to be af nely independent is that k g 72 14 Topological Concepts and Results In this chapter we assume that ER denotes an p dimensional vector space endowed with a norm H H De nition 141 A sequence is said to converge to a point a if limkn0c 0 De nition 142 A function f X gt Y where X C 33quot and Y C 33 is said to be continuous at a point a E X iffor any sequence Q X converging to 3 the sequence 9 Y converges to f If f is continuous at every point of X then f is said to be a continuous map ap continuous Proposition 143 Every af ne map A 33quot gt 33 is continuous 4 erczidenclos przclosure De nition 144 The closure of a set S Q ERquot denoted by clS is the set of all limit points of sequences in S or equivalently a E clS if and only if there exists a sequence Q S converging to 3 Clearly S Q clS If these two sets agree S is said to be closed A more general de nition than the one given above is that of the closure of a set S with respect to another set containing S De nition 145 For given sets S Q X Q ERquot the closure ofS with respect to X denoted chS is the set de ned as cle clS O X or equivalently a E cle if and only if a E X and there exists a sequence Q S converging to 3 Clearly S Q chS If these two sets agree S is said to be closed with respect to X Clearly it follows from the above de nition that cl XS 2 cl S whenever X 2 ERquot More generally we have the following result Exercise 146 For given sets S Q X Q ERquot show that ifX is closed then cle clS The following facts about the above notion of closure can be established Proposition 147 Show the following statements a ifS Q T Q X Q ERquot then cle Q chT b ifS Q Xi Q 33 i 1k then chS1 gtlt xSk ch1S1 gtlt XX1gtltgtltXc gtlt leSk where c ifS Q X Q ERquot and f X gt Y Q 33 is a continuous map then fchS Q clyfS if in addition the set fchS is closed with respect to Y then these two sets are equal d ifT Q Y Q 33 and f X Q 3quot gt Y is a continuous map then f 1clyT Q le ICI in particular ifT is closed with respect to Y then f 1T is closed with respect to X e ifSiiE is collection of subsets ofX Q ERquot then merchSi Q clxmigrSi in particular if the sets Si i E I are closed with respect to X then WEIS is closed with respect to X f if Si Q X Q ERquot i 1k then Uf chSi chUf1Si in particular if the sets Si i 1 k are closed with respect to X then ULIS is closed with respect to X We observe that that each one of the above statements reduces to a statement about the pure closure simply by taking X 2 ERquot Y 33 or Xi 2 ERquot for every i 1 k The closure of a set can also be obtained by the following outer construction Proposition 148 Let S Q X Q 3quot be given Show that cle to is the smallest set closed with respect to X containing S ie cle C Q X C Q S C is closed with respect to X In particular if the set C Q X is closed with respect X and contains S then C Q chS De nition 149 For a set X Q ERquot and a point x E X N Q X is called a neighborhood of a E 33quot with respect to X if there exists 5 gt 0 such that Bx5 O X Q N 5 Clearly by de nition any set N of the form N Ba5 O X is a neighborhood of a with respect to X We note that since norms de ned over a nite dimensional vector space are all equivalent the above de nition does not depend on the norm used in the de nition of BM 5 De nition 1410 For sets S Q X Q ERquot a point a E X is said to be an interior point of S with respect to X if there exists some neighborhood N39X of a with respect to X such that Q S The set of all such points is referred to as the interior ofS with respect to X and is denoted by int XS The boundary of S with respect to X denoted by bdXS is de ned as bdXS 2 cle int XS When X 2 ERquot we denote the sets intXS and bdXS simply by int S and bd S respectively and refer to them simply as the interior and boundary of S respectively In view of the de nition of JV39X3 we easily see that a E int XS if and only if there exists 5 gt 0 such that BM 5 O X Q S Also it follows from the above de nition that int XS Q S De nition 1411 For sets S Q X Q ERquot S is said to be open with respect to X if int XS 2 S IfS is open with respect to X 2 ERquot we simply say that S is open Proposition 1412 Show the following statements a ifS Q T Q X Q ERquot then int XS Q int XT and intXS Q int TS b Q X Q 33 i 1l then intXS1 X X intXlSl X XinthSk where XX1 X XXk c ifS Q X Q ERquot then X int XS 2 chX S and bdXS bdX S moreover the sets intXS bdXS bdXX S and int X S are disjoint and their union is equal to X d ifT Q Y Q 33 and f X Q 33quot gt 33 is a continuous map then f 1int yT Q int Xf la39 in particular ifT is open with respect to Y then f 1T is open with respect to X e ifS3939E is collection of subsets ofX Q ERquot then Uieflnt XS Q intXU39ES39 in particular if the sets Si i E I are open with respect to X then U16 Si is open with respect to X f if S Q X Q ERquot i 1 k then f1intXS39 intX f1Si in particular if the sets Si i 1 k are open with respect to X then OLIS is open with respect to X The interior of a set with respect to another set can also be obtained by the following construc tion Proposition 1413 Let S Q X Q ERquot be given Then intXS to is the largest open set with respect to X contained in S ie intXS UK O Q S O is open with respect to X In particular if the set 0 Q S is open with respect X then 0 Q int XS The following de nition introduces a certain class of maps De nition 1414 f X Q ERquot gt Y Q 33 is called an open map iffor any set S Q X open with respect to X the set fX is open with respect to Y The following characterization of open maps can be established 6 Proposition 1415 For a map f X Q 3quot gt Y Q 33 the following statements are equivalent 3 aff ineopen Tiarascompact przfcompact a f is an open map b fintXS is open with respect to Y for any S Q X c fintXS Q int yfS for any S Q X Proof a gt bl Assume f is an open map Since int XS is open with respect to X it follows that fint XS is open with respect to Y b gt 1 Let S Q X be given Then b implies that fintXS is open with respect to Y which together with the fact that fintXS Q fS imply that fint XS Q int yfS in view of Proposition 1413 1 gt al Assume that S C X is open with respect to X ie S int XS Then c implies that fS fint XS Q int yfS Q fS and hence that fS is open with respect to Y I An important class of open maps is described in the following result Proposition 1416 Let A V Q 3quot gt W Q 33 be an af ne map which is onto ie AV Then A is an open map As a consequence for any set S Q V the set Aint VS is open with AV and 111th vs Q int 7143 respect to W De nition 1417 A set X Q 33quot is called compact if every sequence Q X has a convergent subsequence mkhgc whose limit is in X We have the following characterization of a compact set in ERquot Proposition 1418 A set X Q 33quot is compact if and only if X is closed and bounded Proposition 1419 IfX Q ERquot is compact and f X gt Y Q 33 is continuous then fX is compact Proposition 1420 Let V Q 33quot be an af ne manifold and A V gt 33 be an af ne map Then for every set S open with respect to V the set AS is open with respect to AV Exercise 1421 Give an example to show that the version of above result where the word open is replaced by the word closed is not true 15 Convex Sets De nition 151 A set C Q 33quot is convex if 37 Q C for every 33 E C see Figure 12 Hyperplanes and halfspaces are the simplest convex sets They are the main ingredients involved in the separation theory described in Chapter 3 which in turn has major consequences in convex analysis For s E ERquot gtlt ER 3 0 let HM E ERquot sa 3 13 3 6 itquot sa 2 3 14 H35 3 6 ERquot sa g 5 15 E ERquot sa gt 3 16 E ERquot sa lt 3 17 n l a b Figure 12 a convex set b non convex set figzconvex a b Figure 13 a convex cone b non convex cone Set 13 is called a hyperplane sets 14 and 15 are called closed halfspaces and sets 16 and 17 are called open halfspaces Exercise 152 Prove that HM x0 sJ for any x0 E Est3 where sJ z H54 2 E 3quot sx 0 De nition 153 A set K Q ERquot is a cone if cm E K for every 3 E K and a gt 0 De nition 154 A cone K which is convex is called a convex cone see Figure 13 Examples The following sets are convex cones a 2xE Rnx20and RzxE Equotxgt0 b The set E ERquot Am 2 01423 3 0 where Al E WM and Ag E ERWXquot De nition 155 A convex combination of 31 xk E 3quot is any point of the form mm waxy where the scalars a1 we are nonneyative and satisfy a1 a 1 See Figure 14 zconvexcomb Proposition 156 A set C Q ERquot is convex if and only if every convex combination of elements of C is in C Proof To show the only if7 part assume that C is a convex set We will show by induction on k that every convex combination of k elements of C is in C for every integer k 2 1 This assertion is obviously true for k 1 and for k 2 in view of the de nition of convexity Assume that the assertion is true for k in Let x0x1 x be m 1 elements of C and Ag A1 Am be nonnegative scalars whose sum is one We want to show that 2170 Mex E C This is obviously 8 affineconvex Legend af ne combination convex combination Figure 14 The linear combination of a and 3 generates the plane de ned by the lines As and 13 for A 1 E 3 true if Aquot 1 why Assume now that Aquot 1 We clearly have 2170 Akxk 1 Ama39 Amxm where Since the coef cients Akl Am k 0 m 1 are nonnegative and their sum is 1 why we conclude that 3 is a convex combination of in elements of C and hence is in C by our induction hypothesis Since 2170 Akxk is a convex combination of 339 E C and 37 E C it must lie in C Hence the induction step is complete The if part is obvious since by de nition a set C is convex if every convex combination of two elements of C is in C I 16 Convexity Preserving Operations and Convex Hull In this section we show how to construct convex sets by performing different types of operations on a given convex set or on a nite or in nite collection of convex sets The proof of the following result follows directly from the de nition of an af ne map and is left to the reader Lemma 161 If A ERquot gt 33 is an af ne map then Axgx1 xux1 E ERquot Axg Ax1 for every Proposition 162 Let A 33quot gt 33 be an af ne map Then a IfC Q 3quot is convex then AC z Ax a E C Q 33 is convex b IfD Q 33 is convex then A 1D z E 3quot Ax E D is convex Proof a Suppose C Q ERquot is convex and let 3031 E AC be given Then there exist xux1 E C such that Aim 2 3 for i 01 Since C is convex we have mama Q C Hence 30411 AxgAx1 Aagx1 Q AC where the second equality is due to Lemma 161 and the assumption that A is an af ne map This shows that AC is convex b Suppose that D Q ERquot is convex and let xux1 E A 1D be given Clearly we have AxgAx1 E D Using Lemma 161 and the assumptions that A is af ne and D is convex we conclude that Axgx1 AxgAx1l Q D and hence that mama Q A 1D This shows that A 1D is convex I figzlinaff arconvexset Proposition 163 The following statements hold a fl is a set of indexes not necessarily nite and C mr is a family of convex sets of ERquot then We 0 is a convex set 1 IfC Q 33quotquot2 set 1 k are convex sets then 01 X X C Q ER gtlt x 337 is a convex b If a1cuc E 33 and 01Cc Q ERquot are convex sets then a101cucCca1x1akxk x ECVi1k is a convex set Proof a Suppose x3 E 0pr Then x3 E C for every i E I Since C is convex am Q 0 for every i E I Thus xnl Q 0610 which shows that 060 is a convex set b Suppose x3 E 01 x ka Then a x1 xk and 31 3c for some mugi E 0 1 k Since C is convex we conclude that 33 Q C for every i 1 k or equivalently mug1 gtlt gtlt Q 01 x gtlt Ck Using the simple fact that 332 Q xhyll gtlt gtlt snugk we then conclude that 352 Q 01 x gtlt Ck and hence that the latter set is convex c Suppose that on ka E 33 and Cl C Q ERquot are convex sets Consider the map A ERquot gtlt gtlt ERquot gt ERquot de ned as Ax1 xk 2 mm akxk Since the map A is linear and thus af ne and A01 gtlt gtlt Ck c2101 cuch we conclude that the latter set is convex in view of statement b and Proposition 162a I For a subset S of ERquot we can construct the smallest with respect to inclusion convex set containing S using the same scheme employed in the de nition of its linear and af ne hulls De nition 164 Outer Constructionz Given a set S Q ERquot its convex hull coS is de ned as coS O V V is a convex set V 2 S 18 ropertiesCOC Proposition 165 The following statements hold a coS is convex and co S Q S b coS is the smallest convex set containing S i e ifC is convex and C Q S then C 2 co S Proof This result follows immediately from the de nition of coS and Proposition 163a I menstruation Proposition 166 Inner Construction IfS is a nonempty subset of ERquot then coS is equal to the set of all convex combinations of elements of S Proof Let C denote the set of all convex combinations of elements of S We will rst show that C is convex Indeed suppose that x E C and a E 01 Then i000akk y uw wu for some 0xkyuyl E S and auak u l 2 0 such that aucuc 1 and g l Then axl ayaauxuaakxk1 a uyu1 a lyl 10 lem Clo sure and aauaak1 a u1 a aauak1 a u p a1 a1 Hence as 1 003 E C showing that C is convex Since C is convex and S Q C it follows from 18 that coS Q C Now it follows from 18 and Proposition 163a that coS is a convex set Hence Proposition 156b and the inclusion S Q co S imply that C Q co S We have thus shown that C 2 co S or equivalently statement c holds I De nition 167 The closed convex hull of a set S Q ERquot denoted by cTS is the set C C is a closed convex set C Q S There is a strong relationship between coS and cTS But before establishing this connection we rst prove the following result Lemma 168 If C Q 33quot is convex then ch is convex Proof Let x3 E ch and a E 01 Then there exist sequences and lying in C and converging to a and 391 respectively Since C is convex it follows that axk 1 003c E C for every k 2 0 Also limkn0c axk 1 003c as 1 My The two latter conclusions imply that as 1 003 E ch and hence that ch is a convex set I Proposition 169 For any S Q ERquot we have 2 cl co S In other words cTS consists of all limit points of the set of all convex combinations of S Proof By Proposition 148 and Lemma 168 the set cl co S is closed and convex Since S Q coS Q cl co S it follows from De nition 167 that Q cl co S Also De nition 167 implies that c S is a convex set containing S Hence co S Q c S Taking closure of both sides of this inclusion we obtain cl co S Q cTS since is already closed in view of De nition 167 I Exercise 1610 For a set V S C ERquot show that the sets S clS coS and all have the same af ne hull and closed convex hall For a given set V S Q 33quot and nonnegeative integer k de ne lc akxkZa1xgxkESa20i0k Spit 620550 i0 ie S is the set of all convex combinations of any k elements of S Clearly S S 0 Q S 1 Q Sp Q and coS Uiu Theorem 161 Caratheodory Let V S Q ERquot Then coS 2 SM 11 Proof Clearly S 72 Q co S To prove the reverse inclusion let a E co S Let k be the smallest index such that a E S We claim that k g 72 from which the conclusion of the theorem follows Assume for contradiction that k gt 72 The de nition of k and S then implies that a 2 0mm mam for some scalars a gt 0 i 0 k satisfying 220 a 1 Since k gt 72 the vectors 30 m are not af nely independent Hence in view of Proposition 133d there exist scalars g 3 not all zero such that Zita 3 0 and 220 0 Then for every t E 33 1 1 t0Za tZ Za t 19 70 70 i0 a a t0 tZ m t a 110 70 70 70 Since the sum of the scalars s is zero and they are not all zero it follows that there exists some j E 0 k such that 1 gt 0 Let tquot z supt a t 2 0 Vi 0k mina i such that 3 gt 0 Clearly we have tquot lt 00 since the latter set is nonempty De ning 7 a 1873 for every 7 0 k it follows from relations 19 and 110 and the de nition of 11 that a 220 733 207 2 1 and 7 2 0 for every 7 0 k Moreover the de nition of 11 also implies that there exists I E 0 k such that 39n a ff 2 0 why This conclusion implies that a is indeed a convex combination of k elements of S or equivalently that a E S k 1 contradicting the minimality of k I The following result follows is a consequence of Caratheodory s theorem and Proposition 1419 Proposition 1611 Ifm S Q 33quot is compact then coS is compact As a consequence we have cTS 2 co S Proof Since coS S 72 by Caratheodory s theorem it suf ces to show that S is compact for every k 2 0 Indeed let A denote the k th simplex ie 16 A16 2 agak E Ek1ZZai1a120 i0 and consider the map Q A x SIM 1 gt ERquot de ned as Qagakgk 620550 C cc where SIM 1 denotes the cartesian product of k 1 copies of the set S Clearly Q is a continuous map and S QAc gtlt Sf Since the domain of Q is compact it then follows that its image under Q namely S k is compact The last claim of the proposition follows from Proposition 169 and the fact that co S is compact and hence closed I Remark If S is closed but unbounded the identity cTS coS does not necessarily hold Indeed consider the unbounded closed set S 0 0 U gtlt In this case we have coS 01 x ER U 00 which is not closed Hence coS cTS 01 x ER 12 1 7 Relative Interior If S Q ERquot is a set such that a S ERquot ie S is a at set then intS m in words S does not have interior points But it is possible to give a weaker de nition of interiority which properly describes the interior of at sets and which turns out to play an important role in nite dimensional convex analysis De nition 171 A point x E ERquot is said to be a relative interior point ofS ifx is interior point ofS with respect to its af ne hull a S or equivalently there exists 5 gt 0 such that 1 x 5 affS Q S The set of all such points is referred to as the relative interior ofS and is denoted by riS The relative boundary of S denoted by rbd S is de ned as rde 2 cl S riS Note that rbd S is the same as the boundary of S with respect to a S Indeed letting X z affS we have clS cle due to Exercise 146 and the fact that aff S is closed Hence rde z clSriS chSintXS bdXS It follows from the above de nition that riS Q S De nition 172 The set S Q ERquot is said to be relatively open ifS is open with respect to its af ne hull affS ie S riS Proposition 173 Let S Q V Q 33quot be given and assume that V is an af ne manifold Then if int VS V then affS V and hence riS int VS V In particular ifint S V then a S 33quot and hence riS intS V Proof Clearly the inclusion S Q V and the assumption that V is a ne manifold imply that aff S Q V To prove the reverse inclusion let 3 E V be given Fix some 37 E int VS V Then 37 E V and there exists 6 gt 0 such that B375 O V Q S H37 2 3 we conclude that 3 E S Q affS Assume then that 37 3 and consider the point 2 37 53 Since 5 373 E V and 2 E a 337 Q V we conclude that 2 E 1 375 O V Q S Now since 3 E a 372 and 339 2 E S it follows that 3 E a S We have thus established the reverse inclusion The second part of the proposition follows from the rst one by letting V 2 ERquot I Examples 1 If C then affC riC and dimC 0 2 If C 3 3 and 3 3 then a C is equal to the line passing through a and 3 riC x 3 and dimC 1 3 HO 2 Bx6 2 3 E ERquot 3 x 3 6 then a C 2 ERquot riC Ba6 and dimC 72 The following facts about a relative interior point are useful exerczrelim Exercise 174 Assume that 339 E riS where S Q ERquot Then a there exists 5 gt 0 such that Ba 5 aiTS Q riS b given any a E a S there exists 6 gt 0 such that 339 113 E ri S for every t such that M S 6 c given any u lying in the subspace parallel to affS there exists 6 gt 0 such that 339 in E riS for every t such that t 3 e The proof of the following result follows directly from the de nition of the operator ri 13 inclr1 exerczricart Proposition 175 If S1 Q S2 and a S1 a Sg then riS1 Q rng Proposition 176 Let S C ERquot be given Then a ifriS V then affriS affS a cl ri S Q clS and ri ri S riS Proof a Clearly a riS Q a S since riS Q S To show the reverse inclusion let a E a S be given Since riS V by assumption there exists 339 E riS In view of Exercise 174b 339 53 E riS for every 5 suf ciently small Hence for 5 0 suf ciently small we have a E a 3 53 Q a ri S We have shown the reverse inclusion and hence that a S affri S b The rst inclusion follows immediately from the inclusion riS Q S and Proposition 147a Note that the identity ri riS riS obviously holds if riS V Assume then that riS V The inclusion riS Q S together with a and Proposition 175 then imply that ri ri S Q riS Also statement a and Exercise 174a imply that the reverse inclusion ri riS Q riS also holds I The proof of following result is straightforward and is left to the reader Exercise 177 For sets S Q ERMA 1k we have riS1 gtlt gtlt Sk riS1 gtlt gtlt riSk De nition 178 A subsetB ofa setX Q ERquot is said to be open with respect to X ifB X D 0 where O is an open set of ERquot Recall that a function f X C ERquot gt Y Q 33 is said to be homeomorphism if it is a continuous bijection ie one to one and onto whose inverse is also continuous The proof below uses the following well known topological fact if f X gt Y is a homeomorphism then U Q X is open with respect to X if and only if f U is open with respect to Y1 It is possible to exhibit examples of sets S Q ERquot which have no relative interior points For instance the set of rational numbers in ER has no relative interior point However the next result shows that this pathology does not occur when C is a convex set Proposition 179 Let V C Q 33quot be convex Then riC V Proof Let k dim C Then there exist af nely independent vectors mama E E C such that affag mk a C Let lt1 ER gt a C be de ned as a1ak mg a1a1 au au Since 31 30 mk 30 are linearly independent we conclude that lt1 is an a ne isomorphism and hence a homeomorphism Consider the set Oa1akEka1akltlaigt0i1k and note that V O Q C Since 0 is open and lt1 is a homeomorphism we conclude that O is an open set with respect to a C Since 0 Q C we conclude that V O Q riC I The proposition uses the following simple fact whose proof is left to the reader lcmn George L Introduction to General Topology AddisonVesley 1994 534 14 iresolution risimilar Lemma 1710 The following statements hold a for any x3 E 3quot and positive scalars L5 we have Bx t3 t5 a tl 33935 b for any positive scalars 51 lt 52 if Q 33quot convertes to x then Bx51 Q Bxk52 for every k sv iciently large Moreover the above statements also hold if the closed balls are replaced are replaced by open balls Proof We will only prove Clearly the assumption implies that limkn0c 0 and hence that g 62 51 for all k suf ciently large Hence if 3 E Bx51 or equivalently Hy mu 3 6 we have My mu 3 My an Na new 3 mm a 62 equivalently 3 E B 52 for every k suf ciently large I One of the main consequences of the result below is the fact that the relative interior of a convex set is also convex Proposition 1711 Let convex set V C Q ERquot 3 E ch and 3 E riC be given Then x3l Q riC As a consequence riC is a convex set Proof Assume rst that x E C Since 3 E riC there exists 6 gt 0 such that B35 a C Q C For t E 011 let 2 z 1 tx 13 and 5 t5 We claim that 57255 affC Q C for every t E 011 from which we conclude that x 3 Q riC To prove the claim x 1 E 011 and note that 57255 1 tx Bt3 t5 1 tx tB3 5 and affC 1 tx taffC Hence Bzl6l affC 1 txtB36l 1 txtaffCl 1 txtB36 a C 1 m tC g 0 Assume now that a E ch and let 1 E 011 be given Then there exists a sequence Q C converging to x In view of the above claim it follows that the point z 1 txk t3 satis es Bzlk5l affC Q C for every k 2 0 Now by Lemma 1710b and the fact that converges to 2 as k gt 00 it follows that 325 it2 Q 32f 5 for every k suf ciently large From the above two conclusions we have Bzl5l2 aff C Q C and hence 2 E riC We have thus shown that x3l Q riC I Proposition 1712 For a convex set V C Q ERquot the sets riC C and ch have the same af ne hall the same relative interior and the same closure Proof In view of Exercise 1610 and Propositions 176 and 179 the above three sets have the same af ne hull and the following relations are already known ririC riC Q rich and cl riC Q ch 2 cl ch To prove the reverse inclusion riC Q rich let a E rich be given Since riC V by Proposition 179 there exists 3 E riC In view of Exercise 174b with S ch and the fact that x E ri cl C and 3 E riC Q affch the point 3 z x tx E rich Q 10 for every t E 33 suf ciently small Fix some t E 01 such that xi E ch Clearly a 1 t 1xl it1 1015 and hence a E phi Since 3 E ch and 339 E riC it follows from Proposition 1711 that a E riC We have thus proved that riC Q ri ch The proof of the inclusion cl riC Q ch can be similarly proved and is left to the reader I As a consequence of Proposition 1712 we have the following result which states that convex sets with the same relative interior or closure differ from each other only in their relative boundary 15 lemzprepAri przrisum Exercise 1713 Let convex sets C1Cg Q 33quot be given Then the following statements are equiv alent a riC1 rng b ch1 chg c riC1 Q Cg Q ch1 Moreover any of these three conditions imply that afIC1 afI Cg Proof la 3 bl This equivalence from the fact that ri ch riC and cl riC 2 cl C for every convex set C Q 33quot 1 gt bl Assume that riC1 Q Cg Q cl C1 Passing this relation to the closure we conclude that cl C1 2 cl ri C1 Q cng Q cl C1 and hence that cl C1 cng b gt 1 Assume that cl C1 cng and hence that riC1 ri Cg due to the equivalence of a and Then using the well known inclusions ri Cg Q Cg Q cng we conclude that riC1 ri Cg Q Cg Q cng 2 cl C1 showing that c holds I Lemma 1714 Let S Q 33quot and an af ne map A 33quot gt 33 be given statements hold a AriS Q riAS b ifriS V then afIAriS a riAS afIAS Then the following Proof To prove a let S Q ERquot be given and de ne V afIS and W AV afIAS where the latter equality is due to Exercise 1215 By reducing the domain and co domain of A to V and W repectively we can view A as an af ne map from V onto W In view of Proposition 1416 and the de nition of relative interior we conclude that Aint VS is open with respect to W and AriS Aint VS Q int WAS riAS Hence in view of Proposition 173 we conclude that W a AriSl Q a lriASl Q W and hence that b holds I Proposition 1715 Let a convex set C Q ERquot and an af ne map A ERquot gt 33 be given Then riAC AriC and a AriC a riAC a AC Proof The inclusion AriC Q riAC follows from Lemma 1714a In view of the implication b gt c of Exercise 1713 to prove the reverse inclusion riAC Q AriC it suf ces to show that cl AC 2 cl AriC Indeed using the inclusions riC Q C Q ch statements a and c of Proposition 147 and Proposition 1712 we have AC Q Ach Acl riC Q clAriC Q cl AC which together with Proposition 147a implies that cl AC Q cl AriC Q cl AC and hence that cl AC 2 cl AriC We will now show that afIAriC a riAC afIAC If riC m then these identities follow from Lemma 1714b If C V then riC V in view of Proposition 179 and hence the three af ne hulls are all empty I Proposition 1716 For scalars a1cuc E 33 and sets C1Cc Q ERquot the following state ments hold nzpreprizAinv rizAinv a ria101 aka Q alriCl akriCk b ifC 1Cc are convex then ri c2101 aka alriCl Lucrng Proof I Lemma 1717 Let T Q 33 and an af ne map A 3quot gt 33 be given statements hold Then the following a A 1riT Q riA 1T b ifA 1riT V then the sets A 1riT riA 1T A 1T A 1clT and cl A 1T all have the same af ne hull namely A 1aff T Proof Let X z A Wa T and Y affT Consider the a ne and hence continuous map f X gt Y obtained by reducing the domain and co domain of A to X and Y respectively Observe that this map is well de ned since AX Q Y Using the second inclusion of Proposition 1412a the de nition of relative interior and the fact that A 1T Q affA 1T Q X z A 1aff T where the latter inclusion is due to Exercise 1215b we conclude that int XA 1T Q riA 1T This inclusion Proposition 1412d and the de nition of relative interior then imply that A lriT f 1riT f 1int yT g int X f 1T int XA 1T g riA 1T and also that A 1riT is open with respect to X a A 1Tl Clearly the rst conclusion implies that a holds Also under the condition that A 1ri T V the latter conclusion together with Proposition 173 imply that affA 1riTl X z A 1affT In view of a Proposition 147d and the fact that riT Q T Q clT we have A 1ri T Q riA 1T Q A 1T Q A 1cl T Q cl A 1T Q A 1a T Applying the af ne hull to this sequence of inclusions and using the fact that a A 1riTl A 1a T and A 1aff T is an a ne manifold we conclude that b holds I Exercise 1718 Give an example showing that the inclusion in Lemma 1717a can be strict even when riT V Proposition 1719 Let D Q 33 be a convex set and A 3quot gt 33 be an af ne map such that A 1riD V Then riA 1D A 1riD and clA 1D A 1ch and these two sets together with the set A 1D have the same af ne hull namely A 1affD Proof In view of Lemma 1717 and Proposition 147d it suf ces to show that the inclusions riA 1D Q A 1ri D and clA 1D Q A 1cl D hold To show the rst inclusion let a E riA 1D be given Since A 1ri D V by assumption take 30 E A 1ri D lfa 30 we are done So assume that a 30 Since a E ri A 1D and the segment mmml is in a lA WD we can stretch this segment beyond a and yet stay in A 1D Select in particular a point 3 E A 1D such that a E baby Clearly we have Aag E riD A3 E D and Aa E Aau A3 due to the af nity of A By Proposition 1711 it then follows that E riD and hence that a E A 1riD To show the second inclusion let a E A 1ch be given Since Aa E ch and Amu E riD it follows from Proposition 1711 that Aaua AmgAa E riD Q D and hence that ew Q A 1D Clearly this implies that a E cl 30a Q cl A 1D I 17 Proposition 1720 If Ci Q ERquot i 1 k are convex sets such that Hill riC V then ri 10 af rm 111 1 11310 1131010 112 Proof We will proof only the rst relation The second one is proved similarly Consider the af ne map A ERquot gt ERquot gtlt gtlt ERquot de ned as Ax x Then for sets Si Q ERquot i 1k it is easy to see that 14461 x gtlt S13 2 OLISi In particular we have 14 1riCl gtlt x 0 14 1ri01 gtlt gtlt riCk f riCi where the rst equality is due to Exercise 177 In view of the assumption that f riC V we then conclude from the above identity and Proposition 1719 with D C1 gtlt x C that ri 10 ri 14401 gtlt x 0 14 1ri01 gtlt x 0 af rm I Using Theorem 1711 it can be shown that 112 can be extended in the following manner Exercise 1721 If Cihg Q ERquot is a possibly in nite collection ofconvex sets such that igriC V then Cl nieil l 01 Cl mack 716ml 01 18 Asymptotic or Recession Cone In this section we introduce the cone of asymptotic directions associated with a given closed convex set In words an asymptotic direction is one which we never leave the set by moving from an an arbitrary point in the set along its positive orientation We also prove the fundamental result that the closed convex set is bounded if and only if d 0 is the only asymptotic direction of the set De nition 181 The asymptotic or recession cone of a nonempty closed convex set C Q ERquot denoted by Coo is the set de ned as C a CoodE RquotxtdECxECVtgt0 7 lgt01 EC Proposition 182 For any nonempty closed convex set C Q ERquot C0c is a closed convex cone containing 0 Proof It is easy to see that C0c is clearly a cone containing 0 Since C t is a closed convex set for every 3 E C and t gt 0 it follows that C0c lgt0C t is a closed convex set I Note that d E C0c if and only if the semi ray along the direction d originating at any point a E C is contained in C The following result shows that if only one of these semi rays is contained in C then its corresponding direction d is in Coo prrecequiv Proposition 183 Let C Q 3quot be a nonempty closed convex Iffor some m E C and direction d E ERquot the semiray x0 td t gt 0 is contained in C then d E C06 18 arcrecequiv Lemzrecctech reccbounded przreccoper Proof To show that d E Coo let x E C and t gt 0 We will show that x td E C from which the result follows Indeed for c E 01 consider the point t x zxutd1 cx xu1 cxcxugd which is in C in view of the latter expression for and the fact that C is convex a E C x0 tcd E C by assumption and c E 0 1 Moreover using the rst expression for xi we easily see that limcng a td from which we conclude that a td E ch C I Exercise 184 A polyhedron is a set C which can be represented as C E 3quot Ax 3 b for some A E 337quot and b E ERquot Assume that the polyhedron C E 33quot Am 3 b is nonempty and bounded Show that C0c d E 33quot Ad 3 0 and that the possibly empty polyhedron x E 33quot Am 3 b is bounded for any other right hand side b E 33 Exercise 185 For a nonempty closed convex C Q ERquot show that C0c d E 33quot C d Q C Lemma 186 Let a nonempty closed convex C Q 3quot be given Ifd limkn0c akxk for sequences Q C and Q R such that limkn0c a 0 then d E Coo Proof Fix some a E C It suf ces to show that a td E C for every t gt 0 Indeed let 1 gt 0 be given Since Sam s E C C is convex and limkn0c Q 0 it follows that the point 3c z 1 touch takxk is in C for every k suf ciently large Moreover using the assumption that limkn0c Q 0 and limkn0c maxquot d we easily see that limkn0c 3quot a lid and hence that xtdEchC I Proposition 187 Let V C Q 33quot be a closed convex set Then G is bounded if and only if C0c Proof The only if7 part is obvious since a bounded set can not contain a semi line To prove the if part assume that C0c 0 and for contradiction that C is unbounded Then there exists a sequence Q C such that limkn0c 00 Consider the bounded sequence de ned as d c z xk for every k By the Bolzano VVeierstrass Theorem d c has a convergent subsequence d chgg Let d z limkem d c We claim that 0 d E Coo which yields the desired contradiction To show the claim rst note 1 and hence d 0 due to the fact that 1 for every k Moreover d is the limit of the sequence akxkhgm where Q converges to 0 as k gt 00 Hence Lemma 186 implies that d E Coo I The following result gives some tools for constructing the recession cones of closed convex sets lts trivial proof is is left to the reader Proposition 188 The following statements hold a If thg is a family of nonempty closed convex sets such that je Cj V then R Choc ltCjoc jEJ jEJ b Let C Q ERquot i 1 k be nonempty closed convex sets Then 01 x x Case C 10c gtlt gtlt 19 c Let A 33quot gt 33 be a linear map Then 1 ifC Q 33quot is a nonempty closed convex set and AC is closed then ACoc Q A C x 2 ifD Q 33 is a nonempty closed convex set andA 1D V then A 1Doc A 1Dloc amzArecc tech Lemma 189 Let A ERquot gt 33 be a linear map and C Q 33quot be a nonempty closed convex set such that A 10 C0c If for a sequence Q C and a bounded sequence Q 3344 the sequence Atcak is bounded then so is the sequence Proof Assume for contradiction that there exists a subsequence hex such that limkgg 11k 00 Since is bounded by assumption it follows that llmkeyc 00 By passing to a subse quence if needed we may assume that converges to some d E 33quot such that 1 Hence by Lemma 186 with Q 1 we conclude that d E Coo Also continuity of A implies that k M a 1 tka Add Hen l2 mum s 0 where the last equality is due to the fact that llmkeyc 00 and Atcak is bounded We have thus shown that d E A 10 0 COO Since by assumption the latter set contains only the zero vector we conclude that d 0 contradicting our earlier conclusion that 1 I Is Proposition 1810 Let A 3quot gt 33 be a linear map and C Q 3quot be a nonempty closed convex set such that A 10 C0c Then AC is closed and ACoc ACloc Proof We rst show that AC is closed Indeed let Q AC be such that limkn0c 3c 3 By the de nition of AC there exists Q C such that Amk 3c for every k Since Amie is convergent and hence bounded it follows from Lemma 189 with ii 1 for all k that is bounded and hence has a convergent subsequence Sikbcgg Since C is closed it follows that a z limkgg wk E C Continuity of A clearly implies that An 3 We have thus shown that 3 E AC and hence that AC is closed We now establish the identity ACoc ACloc The inclusion ACoc Q ACl0c is due to Proposition 188c To establish the other inclusion let u E ACl0c be given Fix some a E C Then for every positive integer h it follows that An ku E AC Hence for every integer k 2 1 there exists H E C such that Ax ku Am c or equivalently u Clearly this implies that is bounded Hence it follows from Lemma 189 with ii 1k that wkk is bounded and hence that it has an accumulation point d E ERquot Passing the expression Abidek Amk u to the limit we conclude that Ad 2 u Moreover by Lemma 186 with a 1k we conclude that d E Coo We have thus shown that u E ACgc and hence that mom 2 Wan De nition 1811 The lineality space of a nonempty closed convex set C Q ERquot denoted by lineal C is de ned as lineal C C0c Cgc Exercise 1812 For a nonempty closed convex set C Q ERquot show that the following statements hold a the lineality space of C is the smallest subspace contained in Coo b d E linealC if and only if for some 30 E C the line 30 td t E 3 is contained in C 20 defzcompl zlinealdecomp nrzACcloseext c linealCdE RquotdCC De nition 1813 Given two subspaces W Q V Q 33 a subspace W Q V is called a complement ofW with respect to V ifW W V and W O W Proposition 1814 Let a nonempty closed convex set C Q ERquot be given and set L linealC Then for any subspace LC which a complement ofL with respect to ERquot we have C L CO LC Moreover lineal C 0 LC 2 Proof The inclusion C Q L C 0 LC is straightforward To prove the reverse inclusion let 3 E C be given We can write 3 in a unique way as 3 31 32 where 31 E L and 32 E LC Clearly 32 2 3 31 E C L C We have thus proved that 3 E L C 0 LC and hence that C Q L C 0 LC Moreover we have linealC 0 LC 2 linealC 0 LC 2 L 0 LC 2 I The following result shows that the conclusions of Proposition 1810 still holds under a slightly weaker condition than that assumed in it Proposition 1815 Let A 3quot gt 33 be a linear map and C Q 3quot be a nonempty closed convex set such that A 10 Cgc Q L where L linealC Then AC is closed and ACoc ACoc Proof Consider a subspace W Q L which is a complement of V A 10 O L with respect to L Clearly AL AV W AV AW AW Now consider the map A ERquot gtlt ERquot gt 33 de ned as A3132 A31 32 for every 3132 E ERquot gtlt ERquot and let LC Q ERquot be a complement of L with respect to ERquot By Proposition 1814 we have C L C 0 LC Hence by the linearity of A the de nition of A and the fact that AL AW we have 140 AL AC 0 LC AW AC 0 LC 216 where C W x C 0 LC We will now show that AC and hence AC is closed by applying Proposition 1810 to the map A and set Indeed it suf ces to show that A 10 C0c First observe that W X C O LC0c W X C0c 0L6 Now let at d1d2 E A 10 y be given Then we have Ad1 d2 0 d1 E W and d2 E C0c 0 LC Hence the vector d z d1 d2 is in A 10 C0c since d1 E W Q L Q Coo d2 E COC and C0c is a convex cone Since by assumption A 10 C0c Q L we must have d E L This implies that d2 d d1 E L since d d1 E L and L is a subspace But since d2 is also in LC and L 0 LC 0 we must have d2 0 Hence it follows that d1 d E A 10 O L But since d1 is also in W and W is a complement of A 10 O L we must also have that d1 0 We have thus shown that at d1d2 00 and hence that A 10 C0c I The following result is a consequence of Proposition 1815 Proposition 1816 Let C1 Ck Q 33quot be nonempty closed convex sets satisfying the following property d14dk Q d1 E Ckoc i2 1k Then C1 C is closed and C1 Cage C1oc gt d E linealC i1k 113 Proof Consider the map A ERquot gtlt gtlt ERquot gt ERquot de ned as A31 3c 31 3c and observe that AC C1 Ck where C C1 gtlt gtlt Ck Using the de nition of A and Proposition 188b it can be easily veri ed that condition 113 is equivalent to the condition that A 10 C0c Q linealC Hence Proposition 188b and Proposition 1815 implies that AC C1 C is closed and C1 Case 2 ACloc ACoc C10c 21 condACclose 22 eraepigraph iefzconvfunc iefzconcfunc Chapter 2 Convex Functions 21 De nition of convex functions Let 3 or 30 00 denote the set 33 U ice For any 7 E 3 and function f 33quot gt 3 we write f 39y to indicate that 39y for every 3 E 33quot otherwise we write f 7 De nition 211 Given function f 33quot gt 3 and scalar r E 33 de ne the epigraph of f strict epigraph of f and the domain of f respectively as epif 392 3t E ERquot gtlt 3 g t 21 8915 f 39 33106 W X 31 flm lt11 domf z E 33quot lt 1 Clearly f 00 f domf V f epif V f epis f V Exercise 212 Show the following statements a for given functions f1f2 33quot gt 3 we have f1 3 f2 if and only if epifl Q epifg in particular f1 2 f2 if and only if epi f1 epifg b for given function f 3quot gt 3 and a family of functions f 33quot gt 3 E A we have f supyeA f if and only if epif OAEAepifA De nition 213 A function f ERquot gt 3 3 is said to be convew if its epigraph epi f is a convex set The set of all such functions is denoted as E Conv Rquot De nition 214 A function f ERquot gt 3 3 is said to be proper convew if f E E Cnv l3quot gt 30 for every 3 E 3quot and f 00 The set of all such functions is denoted as Conv 3quot Equivalently f 33quot gt 3 is proper convex if and only if its epigraph is a non empty convex set which contains no vertical line ie a set of the form gtlt 3 for some a E 33quot De nition 215 A function f ERquot gt 3 3 is said to be concave resp proper concave if f E E Conv R resp f E Conv l3quot The set of all concave resp proper concave functions is denoted by E Conc R resp Conc 3quot The following result gives equivalent conditions for a function to be convex 23 I Proposition 216 For a function f 3quot gt 3 the following conditions are all equivalent a epi f is a convex set ie f E E Conv Rquot b epis f is a convex set c for every xux1 E dom f and a E 01 we have fxflu 1 60551 3 afflu 1 afx1 24 relationco Proof a gt We rst observe that by De nition 211 we have 3t E epis f if and only if 3t c E epif for any or some 6 gt 0 suf ciently small Let 30tu 31t1 E epis f be given By the above observation there exists 6 gt 0 such that 7th c x1t1 c E epi Hence assumption a implies that for every a E 01 axe 1 ax1 wig 1 at1 c aagtg c 1 ax1t1 c E epif and hence that axutu 1 ax1t1 2 am 1 ax1 wig 1 at1 E epis f in view of the above observation b gt 11 Let xux1 E dom f and a E 01 be given Then for any 10 gt ow and 11 gt fa1 we have 30tu x1t1 E epis Hence assumption b implies that axe 1 ax1atu 1 at1 axutu 1 ax1t1 E epis f and hence that ame 1 ax1 lt atu 1 at1 Noting that this inequality holds for every 110 gt ow and 11 gt fa1 and letting t converge to for i 01 we obtain 24 c gt al Let 30t0a1t1 E epi f and a E 01 be given Then 3 E domf and 3 t for i 1 2 Assumption c then implies that ame 1 ax1 3 afxu 1 afx1 3 wig 1 at1 and hence that axutu 1 ax1t1 axe 1 ax1atu 1 at1 E epif This shows that epi f is a convex set I Exercise 217 Using the characterization of Proposition 215 of a convex function verify that the following functions are proper convex a If A ERquot gt 33 is an af ne function then A E Conv Rquot Conc Rquot b Any arbitrary norm in ERquot is in Conv Rquot The sublevel and strict sublevel sets of a function f ERquot gt 3 are the inverse image under f of intervals of form 00 and cor respectively for some 739 E ER ie the following sets f 1 orl E 3quot g r and f 1 oorl E 33quot lt 739 respectively The following result shows that strict sublevel sets of a convex function are convex sets lelset39convex Proposition 218 For f E E Conv Rquot the following statements hold a f 1 cor is a convex set for every 739 E ER 1 f 1 orl is a convex set for every 739 E 3 24 Jensen ineq tly convexity riot 1yconvex iv strongconv fC convexity In particular domf f 1 00 00 is a convex set Proof a Let r E it xmxl E f 1 00r and a E 01 be given Then 3 E domf and lt r for i 1 2 Hence the convexity characterization c of Proposition 216 implies that ame 1 ax1 3 afxu 1 afx1 lt or 1 ar r and hence that axe 1 ax1 E f 1 00r b The convexity of f 1 00rl follows from a the identity f 1 00rl lgtrf 1 00t and Proposition 163a I Proposition 219 Iff E E Conv Rquot then fauflu meme 3 aufflu cucfxc 25 for every 30xc E domf and agcuc E A13 In particular for every 30xc E domf and x E co 30 xk there holds 3 maxfx i 0 k Proof Let 30ac E domf and aga E A be given Let scalars r E 33 such that r gt for i 1k be given Clearly 3373 E epi f for every i 0k Since epi f is a convex set we conclude that 220 aixi Zita am 220 axr E epi f or equivalently zf 3 Egg am Letting r converge to for every i 1 k in this inequality we obtain 25 The second conclusion of the proposition is an obvious consequence of the rst one and the fact that every point in co 30 xk is of the form a 20 mm for some aucuc EA I De nition 2110 A function f ERquot gt 3 is said to be strictly convex if for every 0 an E domf and a E 01 inequality 24 holds strictly Moreover f is said to be strongly convex with modulus 3 gt 0 if for every xux1 E dom f and a E 01 ame 1 C031 S afu1 af1 ga1 6 H330 1H2 26 It follows from Proposition 216 and the above de nition that any strongly convex function is a strictly convex function and that the latter one is always convex Exercise 2111 Show that any strictly convex function f which is not in Conv Rquot is either identically equal to 00 or there exists x0 E 33quot such that fxu 00 and 00 for every I 50 Exercise 2112 Let f 3quot gt lt be given Show that f is strongly convex with modulus 3 gt 0 if and only if f f E E Conv Rquot De nition 2113 Let V C Q ERquot begiven A function f ERquot gt 3 3 is said to be convex on C if f E E Conv Rquot where f 3quot gt 33 is the function de ned as 00 ifxEC otherwise flt The function f is said to be strictly convex on C resp strongly convex on C with modulus 3 gt 0 if f is strictly convex resp strongly convex with modulus 3 gt 0 25 relationst Exercise 2114 Let V C Q 33quot and f 3quot gt 3 be given Show the following statements a f is convex resp strictly convex on C if and only if C O dom f is convex and inequality 24 holds resp strictly for every a E 01 and 30x1 E C O domf such that 30 31 1 if C Q dom f then f is convex resp strictly convex on C if and only if C is convex and inequality 24 holds resp strictly for every a E 01 and xux1 E C O domf such that 0 3315 c ifC is convex and inequality 24 holds resp strictly for every a E 01 and xux1 E C O domf such that 0 on then f is convex resp strictly convex on C d if C is a convex set and f is a convex resp strictly convex function then f is convex resp strictly convex on C arconvexfunc Proposition 2115 The following statements hold a If f1 1 E Conv R and a1k E Wi then the function f z alfl emf de ned as a1f1x cucf x for all a E ERquot satis es f E Conv Rquot if Of dom V 27 00 otherwise 1 for a possibly in nity nonempty family f ig Q E Conv Rquot then the pointwise supre mum f z supieffi de ned as supieff for all a E ERquot is in E Conv R more over if fiber 9 Conv Rquot then either f E Conv Rquot or f 00 c iff E Conv Rm and A ERquot gt 33 is an af ne map such that A Rquot domf V then the function f o A 3quot gt 33 de ned as f o A fAa for all a E 3quot is in Conv Rquot Application 2116 Let Squot denote the set of 72 x 72 symmetric matrices ie matrices X E 33mm such that X XT For a matrix A E Squot let AmaxA and AminA denote the maximum and minimum eigenvalue of A These two de nitions yield functions Am Squot gt ER and Amp Squot gt 33 which are convex and concave respectively To see that rst recall the following well known expression for Amm A and mmA respectively AmA mama Hmll 1 a e an AmmiA minaquotAa Hmll 1 a e 9r Since for xed a E 33quot the function A E Squot gt xTAx E 33 is linear and hence convex it follows from 3 Proposition 2115b that Am is a nite valued convex function Since AminA max A it follows from De nition 215 and Proposition 2115c that Ami is a nite valued concave function 22 Continuity of convex functions In this section we will see that convex functions have some nice continuity properties We start with the following preliminary result which shows that a convex function is locally bounded in the relative interior of its domain 26 allybounded Llylipschitz Lemma 221 Suppose that f E Conv Rquot Then for any 30 E ri domf there exist scalars Ill 2 JlIlau and A1 IlIuau and a neighborhood Nag of 30 such that Nag affdom f Q domf and All 3 3 1 Va E Nau a domf Proof To simplify notation let C ri dom f We may assume without loss of generality that C is an open set or equivalently that C int dom f Since 30 E C there exists 5 gt 0 such that the l norm closed ball B mu 5 E 33quot 30H1 3 5 is contained in C We let Nau 31330 5 which is clearly a neighborhood of 30 We will now show that any a lying in this neighborhood satis es f 3 A1 for some scalar 1 Indeed it is easy to verify that B mu 5 co21 22quot where 2 30 56 and 0 quot 30 56 for every i 1 71 where e is the i th unit vector Now let a E Nau 2 co 7122quot be given Proposition 219 then implies that 3 A1 maxfv i 1271 for every 3 E Nau We next show that any a E Nau satis es f 2 All for some scalar 1 Indeed let a E Nau be given and de ne 5 30 30 2 230 3 Clearly 30 2 and a E Nau 31330 5 since 30H1 30H1 3 5 Hence since f E Conv Rquot we have 1 1 1 1 fwwsi S Mt WL and hence 2 All z 2fag 1 I Proposition 222 Suppose that f E Conv Rquot Then for any 30 E ridomf there exists a constant L Mam 2 0 and a neighborhood Nau of 30 such that Nau affdom f Q domf and fa39 3 LHa 53H Vaga39 E Nau ai domf In particular the restriction of f to set ridom f is continuous Proof Let 30 E ridom f be given By Lemma 221 there exist constants 5 gt 0 Ill and 1 such that All 3 3 A1 for every 3 E Bau25 We will show that L z ll1 IlIQo and Nau Bu5 satis es the conclusion of the lemma Indeed let 35 E Bu5 be given and de ne V a a 2 z a 57 H33 33 Clearly 2 E B025 since au 3 30 5 3 25 Hence All 3 fz 3 1 Using 28 we easily see that 28 i 1 L m 16 162 where 6 z Since f E Conv R we have vltiL J m 16 7 16 2 from which it follows that 1 M M M lIlaE a lt7 ltquot7quot lt mm my a L16 5w mw n where the equality and the last inequality follow from the de nition of 6 and L respectively I We are now ready to establish the main result of this section 27 zlipsoncomp aff inemanif przepiclf Proposition 223 Suppose f E Conv Rquot Then for every compact set K Q ridom f there exists a constant L LK such that 3 for every 35 E K Proof For contradiction suppose there exist sequences and in K such that Ms mam gt kak 33k Vic 2 0 29 Since K is compact there exists a in nite set of indexes IC such that limkeycmquot a E K and limkgc 33k 5 E K why l Using the fact that the restriction of f to ri dom f 2 K is locally bounded in view of Lemma 221 we conclude that lim supkem lt co Relation 29 then implies that llmkeyc 0 and hence that a 5 Now by Proposition 222 there exists a neighborhood N of a 5 and constant L depending on a 5 such that f3 f37 3 L3 3 for every 3 37 E N Since mkheg and aikhgc both converge to a 5 it follows that for every k E K suf ciently large 16331c E N and hence 3 5k a conclusion that contradicts 29 I Corollary 224 If f E Conv Rquot is nite everywhere then f is continuous on 3quot and for every bounded set C Q ERquot there exists a positive scalar L LC such that 3 for every 35 E C Proof This result follows immediately from the fact that ri dom f 2 ERquot the last statement in Proposition 222 and Proposition 223 with K 10 I 23 Lower semicontinuity De nition 231 The lower semicontinuous hull of a function f ERquot gt it denoted by lscf is the function de ned as lscfa lirrgnffy Va E ERquot 9 139 A function f ERquot gt git is said to be lower semicontinuous at a point a E ERquot iffa lscfa Moreover f ERquot gt 33 is called lower semicontinuous iff lscf The following result relates the epigraph of f with that of cl f Proposition 232 For a function f 3quot gt l the followiy statements hold a epilscf 2 cl epif 1 iff E E Conv Rquot then lscf E E Conv Rquot Proof a The identity epilsc f 2 cl epi f follows from the equivalence between the following statements i 3739 E cl epif ii there exists a sequence Q epif converging to 3739 iii there exists sequences Q ERquot and Q ER converging to a and 739 respectively such that 3 rlc for all k iv lscfa z liminfynx y 3 r v 3739 E epilscf The only equivalence which might not be straightforward is iii 3 iv which can be proved as follows The implication iii gt iv is obvious since liminfynx f is the smallest element of the set consisting of limits of convergent sequences f such that limgch0c a quot 3 To prove the implication iv gt iii assume that liminfynl f 3 739 Then there exists a sequence Q ERquot converging to 28 a such that the limit of exists and is less than or equal to 739 Letting 7quotc z maxfak 739 for all k we easily see that limkn0c 7quotc 739 and f 3 7Jc for all k b This statement follows immediately from a Proposition 216 and Lemma 168 I The following result gives equivalent conditions for a function f 3quot gt 3 to be lower semi continuous Proposition 233 For a function f 3quot gt 3 the following conditions are all equivalent a epif is a closed set 1 f 1 o739l is a possibly empty closed set for every 739 E 33 c f is lower semicontinuous Proof a gt Let 739 E 33 be given It is easy to see that f Wwd gtlt r WW 0 lt9quot gtlt 7 210 The assumption that the set epi f is closed implies that the right hand side and hence the left hand side of 210 is a closed set This clearly implies that f 1 oo 739 is closed b gt a Assume that f 1 oo739l is closed for every 739 E 33 and let Q epif be a sequence converging to 3t Let 6 gt 0 be given Since converges to t it follows that 11k 3 te for every k suf ciently large Moreover since wk t c E epi f we have f 3 11k 3 11 6 for every k suf ciently large The set f 1 Oot 6 being closed and the fact that converges to a then imply that f 3 t 6 Since the latter inequality holds for every 6 gt 0 we conclude that f 3 739 or equivalently 3 739 E epi f We have thus shown that epi f is closed a f 11 In view of Proposition 232 we have the following equivalences f is lower semi continuous f lscf f f epi lscf epif 3 cl epif epif f epif is closed I I Proposition 234 Let f 3quot gt 3 be given Then the following statements hold a lsc f is lower semicontinuous and lsc f 3 f b lscf supg g E Q where Q is the collection of lower semicontinuous functions 9 3quot gt 33 such that g 3 f c lscf is the largest function in Q ie lscf E Q and lscf 2 g for every 9 E Q Proof a Proposition 232 implies that the epigraph of lsc f is a closed set Hence it follows from Proposition 233 that lsc f is lower semi continuous b By a we have that lscf E Q which clearly implies that lscf 3 supg g E Q Also if g E Q or equivalently g is lower continuous and g 3 f then we have that liminfynl 3 liminfynl f lsc f for every 3 E 33quot ie g 3 lsc f The latter observation clearly implies that lsc f 2 supg g E Q We have thus shown that c holds c This statement is an obvious consequence of statements b and c I From an optimization point of view lower semi continuous functions have the following desirable property 3minachieve Proposition 235 Assume that f 3quot gt 3 is a lower semicontinuous function and K 9 3quot is a compact set Then there exists of E K such that inffa a E 29 Proof Let inffa 3 E If f 00 then 00 for every x E K and hence any xi E K satis es f Assume now that f lt 00 Then there exists a sequence Q K such that limgcn0c f Since K is compact the sequence has a convergent subsequence 3 quot ex whose limit point 3 z limkgg 16 is in K The fact that xi E K and the de nition of f clearly implies that f 2 f Also since f is lower semi continuous we have mm s liggig s lig gfm c gigolo ftm c ii We have thus shown that f f I 24 Closure of a convex function redefinition De nition 241 Given f E E Conv Rquot the closure of f denoted by cl f is the function de ned as lscf iff E Conv Rquot cl f 2 00 iff 00 00 otherwise Moreover f E E Conv Rquot is said to be closed iff 2 cl The set of all closed convex func tions is denoted by E Cm Also the set of all closed proper convex functions is denoted by 0mmquot Observe that if f E Conv Rquot then f is closed if and only if f is lower semi continuous Hence the set CW 33quot is exactly the set of functions in Conv Rquot which are lower semi continuous Also if f is closed and aw 00 for some 30 E ERquot then we have f clf 2 00 These simple observations yield the following result iptionbEConv Proposition 242 The set Cm l quot of closed proper convex functions consists of the functions in Conv Rquot which are lower semicontinuous The only improper closed convex functions are f 00 and f 00 Hence E Cmm 2 0mmquot U f 30 U f 2 oo lesscriteria Exercise 243 Suppose that f E Conv Rquot Show that the following implications hold a if dom f is closed and the restriction of f to dom f is continuous then f E Cm f quot b if domf is an af ne manifold then f E Cm f quot Our goal in the remaining part of this section is to study how the function f E E Conv Rquot differs from lsc f and hence its closure cl f First we need to prove two technical results The rst result characterizes the relative interior of a function f E E Conv Rquot and is interesting in its own right Proposition 244 For a function f E E Conv Rquot we have riepi xr E 3quot gtlt ER a E ridomf r gt fx 211 a epif affdomf gtlt ER 212 30 Proof Consider the linear map 77 ERquot gtlt ER gt ERquot de ned as 77739 3 77epi dom f and hence Mri epi f 1 1 Wepi fl 1 1 WW 1 due to Proposition 1715 and the fact that epi f is a convex set This implies that for any a E ri dom f there exists 739 E 33 such that 3 739 E ri epi f or equivalently ri epi X 33 7 Hence in view of Proposition 1720 and Exercise 177 if a E ri dom then ri epi 71 n 7 gtlt 9 r1 epi 71 a rim gtlt 971 rilepi f n 7 gtlt 91 ri e x 739 E 33 739 2 x 739 E 33 739 gt Clearly we have 213 This shows that for a E ridom and 739 E ER we have 3739 E riepi f lt 739 This conclusion together with 213 implies 211 The proof of 212 is left to the reader I Proposition 245 Suppose that f E E Conv R and 30 E ridom we have Then for every 7 E ERquot lscfa fa tau 214 Proof Let 30 E ri dom f and a E ERquot be given Clearly we have lscfa z liminff3 g liminffa tau gaze at We will now show that lscfa 2 lim sllplhu fatag a and hence that 214 holds Indeed let 739 E 33 such that 739 2 lscfa be given Then 3 739 E epi lscf 2 cl epif due to Proposition 234a Moreover since 30 E ridom Q domf and hence ffEu lt 00 there exists 7390 E 33 such that ffEu lt 7390 Proposition 244 then implies that 0711 E riepif By Proposition 1711 we then conclude that for every t E 0 1 a tau 3739 t739g 3739 tau739u 3739 E epif or equivalently fa tag 3 739 t739g 739 Hence lim sup fa tag 3 lim sup 739 t739g 739 739 70 70 We have thus shown that 739 E 33 and 739 2 lsc f implies the above inequality This clearly implies that lscfa 2 lim supHu fa tau I Proposition 246 Assume that f E E Conv Rquot Then the following statements hold a lscfa for every 3 E ERquot rbddom f b domf Q dom lscf Q cl dom f c dom f and domlsc f have the same closure af ne hull and relative interior Proof a A point ERquot rbddom f is either in ri dom f or in ERquot cl dom f why Assume rst that a E ri dom f Then setting 30 2 a in Proposition 245 we conclude that lscfa liming m 713 Assume now that a E 33quot cl dom f Then there exists a 31 neighborhood such that domf 7 or equivalently y 2 30 for all 3 E This clearly implies that lsc fa liggilf y 30 fa Va g cl dom f 215 where the last equality is due to the assumption that a 52 cl dom f 2 dom f b The second inclusion follows from 215 and the rst inclusion follows from the inequality lscf g f Proposition 234b c By b we see that dom f and domlsc f have the same closure The other conclusions follow from Proposition 1712 I When f is a proper convex function we have lsc f 2 cl f and hence the following result follows as an immediate consequence of Proposition 246 Corollary 247 Suppose that f E Conv Rquot Then the following statements hold a clfa for every 3 E ERquot rbd domf b domf Q dom cl f Q cl dom f c dom f and domcl f have the same closure af ne hull and relative interior Corollary 248 ff E Conv Rquot and domf is an af ne manifold then f E Cm Proof Since dom f is an af ne manifold it follows that rbddom f 7 Hence by Corollary 247 we conclude that f clf and hence that f E Cm l quot I The following result considers now the relationship of an improper convex function that is not identically equal to 00 with its lower semi continuous hull and its closure Proposition 249 Suppose that f E E Convw and that lscfau 00 for some 30 E 3quot Then the following statements hold a dom lscf 2 cl dom f and clfa lscfa 00 for every 3 E dom lscf b clfa 00 for every 3 E ri dom f In particular iff E E Conv R is such that fag 2 30 for some 30 E ERquot then all the above statements hold Proof a Let a E dom lscf be given Then there exists 739 E 33 such that 3 739 E epi lscf Note that Proposition 234 implies that epi lsc f is a closed set The assumption that lsc f 30 2 OO implies that am t 30O t0 1 E epilscf for every t 2 0 In view of Proposition 183 this implies that 0 1 is a direction of recession of epilsc f This conclusion together with the fact that 3739 E epilscf implies that 3739 t 3739 t0 1 E epilscf or equivalently lsc g 739 t for every t 2 0 Hence we must have lsc 2 30 for every 3 E dom lscf This implies that epilscf domlscf gtlt ER Since epilscf is a closed set the set epi lscf Rn gtlt dom lsc f x 0 is also closed implying that dom lscf itself is closed This fact together with Proposition 246c show that dom lsc f 2 cl dom f b Statement b follows from a and Proposition 246a The last statement of the proposition is obvious since the assumption that f 30 2 30 and the inequality lscf g f imply that lscfag 2 00 I 32 orzlscinfty nainmanifold properconvex finitevalued Corollary 2410 For a function f E E Conv Rquot the following statements hold a if there exists 30 E ridom f such that aw E 33 then f E Conv Rquot and lscf E Cm l quot b if there exists 30 E ERquot such that lscfau E 3 then f E Conv Rquot and lscf E 0mmquot c iff is lower semicontinuous and fa0 E 33 for some 30 E ERquot then f E Cm l quot Proof a Assume that aw E 33 for some 30 E ri dom f This clearly implies that f co and lsc f 00 If either f or lsc f were not proper then it would follow from Proposition 249b that f 30 for every 3 E ri dom f which contradicts our assumption b Assume that lsc fau E 33 for some 30 E ERquot This clearly implies that f co and lsc f 00 If either f or lsc f were not proper then it would follow from Proposition 249b that lsc f 30 for every 3 E dom lsc f which contradicts our assumption c This statement follows immediately from b I Corollary 2411 Suppose that f E E Conv Rquot and domf is a manifold Then either f E Cm l quot or 00 for every 3 E domf In particular f is lower semicontinuous Proof Assume that there exists 30 E domf such that aw E 33 Since rillI 2 Al for every manifold IlI we have 30 E ri dom f since by assumption dom f is a manifold Hence it follows from Corollary 2410a that f E Conv R Hence by Corollary 248 f E Cm l quot We have thus proved the rst part of the corollary The second part of the corollary follows immediately from the rst one I Proposition 2412 Suppose that f E E Conv Rquot Then f is proper if and only if lscf is proper in which case clf lscf E Cm l quot Proof The if part follows from the fact that lsc f g f and the fact that f 00 implies that lsc f 2 30 To prove the only if part assume that f is proper and for contradiction that lsc f is not proper This assumption together with the relation lsc f g f implies the existence of 30 E 33quot such that lsc f120 00 By Proposition 249 we then conclude that f 30 for every 3 E ridom f which contradicts the assumption that f is proper We have thus shown that properness of f implies properness of lsc f Now assume that f E E Conv Rquot is proper or equivalently lsc f is proper Then the def inition of the closure of f and Proposition 232b imply that cl f lsc f E Conv Rquot This conclusion together with Propositions 234a and 242 further imply that lsc f E Cm l quot I Proposition 2413 Let f E E Conv Rquot be given Then the following three conditions are equiv alent a f is nite everywhere 6 lsc f is nite everywhere and c cl f is nite everywhere Moreover any of the above conditions implies that f lsc f 2 cl f Proof a gt b and 1 Iff is nite everywhere then De nition 241 implies that clf lscf and Exercise 243 implies that f is lower semi continuous Thus cl f lsc f f and both b and c holds b gt a If lscf is nite everywhere then rbd dom f rbd dom cl f V where the rst equality is due to Proposition 246c Hence Proposition 246a implies that f lsc f and hence that f is nite everywhere 1 gt b If cl f is nite everywhere then De nition 241 implies that cl f lsc f and hence that lsc f is nite everywhere I 33 repropert ies arc indicator amzasymptech Proposition 2414 Let f E E Conv Rquot be given Then the following statements hold a clf E E Cm Rquot and clf g f b clf supg E E Cm quot g g f c ifg E E Cm Rquot and g 3 f then 9 3 clf hence clf is the largest element in the collection offanctions g E E Cm f quot g g f Proof I The following function plays an important role in convex analysis De nition 2415 The indicator function ofa set S 9 ERquot denoted Is is the function 13 3quot gt 3 de ned as Exercise 2416 For a set S 9 ERquot show the following equivalences 07 00 imeS otherwise a S is a closed set if and only if 13 is lower semicontinuous b S is a convex set if and only if 13 E Conv R c S is a closed convex set if and only if 13 E Cm f quot 25 Asymptotic Function De nition 251 The asymptotic fanction of a fanction f E Cm f quot denoted by f c is the fanction f c 33quot gt 33 de ned as fatd fa t ow sup tgt 03 E domf 216 Lemma 252 Let f E Cm l quot be given Then the following statements hold a for any we E domf we have suplgt0fa td fa lt S I if and only if muyflmun td p E epif for every t gt 0 b for anyt gt 0 we have s11pfatd falt a E domf g I if and only if mrtdp E epif for every 3 r E epif Proof i Note that suplgt0fa td fa t g p is equivalent to fa td g fu tp for every t gt 0 which in turn is equivalent to 30 fag tdp 30 td fag 11p E epif for every t gt 0 ii For any xed 1 gt 0 we have sup a td a E domf g I if and only if fatd g rtp for every 3 E domf and r 2 fa which in turn is equivalent to 3739 td p a lid 739 11p E epif for every 3 r E epif I The following proposition gives alternative expressions for the asymptotic function and relates it to the recession cone of epi f 34 def asympf zasymptexpr Proposition 253 Let f E Cm l quot be given Then the following statements hold a epif c epifoc b for every d E 33quot and 30 E dom f we have fcd supw sup fad fa 217 lgt0 wedom f Proof For every d de ne h1d and h2d as being the rst and second supremum appearing in 217 We claim that epi fgc epihl epihg epi f0c from which a and d follows Indeed Lemma 252a the de nition of recession cone and Lemma 183 imply that dp E epihl if and only if dp E epifoc or equivalently epihl epifoc Also Lemma 252b with t 1 the de nition of recession cone and Exercise 185 imply that dp E epihg if and only if dp E epifoc or equivalently epihg epifoc Finally de nition 216 Lemma 252b and the de nition of recession cone imply that d p E epi f c if and only if d p E epi f oc or equivalently epi fgc epi fgc I recc sublevel Proposition 254 Let f E Cm l quot be given Then the following statements hold a fgc E 0mmquot 1 for any 739 E 33 such that f 1 oo739l V we have f 1 oo739l0c fgc71 oo0 Proof a Since by Proposition 253a epi fgc is a closed convex cone it follows that f c E E Cm Rquot due to De nition 214 and Proposition 233 Also 216 implies that fc0 0 Hence it follows from Corollary 2410c that f E 0mmquot b Let 739 E 33 be such that f 1 oo739l V Take 30 E f 1 oo739l Then f 1 oo7390c epif n 9quot gtlt mix epinoc n 9quot gtlt 0 epif c n 9quot gtlt 0 ltf 1lt ee 0 where the second equality follows from statements a and b of Proposition 188 and the third equality is due to Proposition 253a I af increasing Proposition 255 Let f E E Conv Rquot and 3303 E 33quot be given and assume that E 33 Then the function Af a d R gt ER de ned as f 339 td f 339 mum z 218 is nondecreasing If in addition f is strictly convex then Af a39d is strictly convex Proof Let 0 lt t1 lt 1 be given Using the fact that t t it1d 1 i5 i5t2d t2 t2 and the assumption that f E E Conv Rquot we conclude that t t m ed 3 1 5 M gm ed 219 2 2 or equivalently Aft1ad g Aftga d This shows the rst part of the proposition If f is strictly convex and both t1 112 are in the domain of A f 5 d or equivalently 3 t1d and 339 tgd are in domf then 219 holds strictly or equivalently Aft1 5 d lt Aftga d I 35 zasymplimit Proposition 256 Let f E Cm f quot and 339 E domf be given Then ow 2 limlw Afta d for every d E ERquot where Afa d is de ned by 218 Proof This result follows immediately from Proposition 255 and the rst equality in 217 I The following result provides some rules for computing the asymptotic function of convex func tions obtained by some elementary operations mic function Proposition 257 The following statements hold a if f1fc E meen satis es Of dom V then for every a1ak E ERy f z alfl Loaf E 0mmquot and fix allflyoc Whale b if fiiei Q Cm l quot with I V is such that supieff mu lt 00 for some 30 E ERquot then f z supieffi E Cm R and f c 3161 Mac 7 c iff E and A 33quot gt 33 is an af ne map such that A Rquot domf V then f o A E and f 0 A 0 AU where Au A A0 is the linear part of A I Proposition 258 Let f E Cm l quot be given Then the following statements are equivalent a for every 739 E ER the set f 1 corl is bounded b there exists 7390 E 33 such that f 1 corul is nonempty and bounded c the set of optimal solutions of inffa a E 33quot is nonempty and bounded a ow gt 0 for every 0 d E ERquot Proof a gt bl Take 30 E domf V and de ne r0 fa Clearly f 1 corgl is bounded in view of assumption a and is non empty since it contains 3 b gt 1 Since f 1 corgl is non empty the set of optimal solutions of inffa a E f 1 corgl coincides with that of inffa a E 33quot Noting that the assumption that f E CW 33quot and assumption b imply that f 1 corgl is compact it follows from Proposition 235 that the rst problem and hence the latter one has a nonempty and bounded set of optimal solutions 1 gt d Let rquot z inffa a E 33quot Then assumption c is equivalent to the set f 1 corg being non empty and bounded Hence in view of Propositions 187 and 254 we have fgcf 000 2 f 1 corloc 0 which is equivalent to d d gt a Let 739 E 33 be such that f 1 orl V Then in view of Proposition 254 and assumption d we have f 1 corloc f c 1 co0 Hence f 1 corl is bounded due to Proposition 187 I aptindicator Exercise 259 Let V C 9 3quot be a closed convex set Prove that 15 1590 36 alsolutionl The following result is a generalization of Proposition 258 to constrained optimization prob lems Proposition 2510 Let function f E Cm l quot and closed convex set C Q 33quot such that C O dom f V be given Then the following statements are equivalent a for every 739 E 33 the set E C g r is bounded b there exists r0 E 33 such that E C f 3 70 is nonempty and bounded c the set of optimal solutions of inffx a E C is nonempty and bounded d ow gt 0 for every 0 d E Coo Proof Consider the function fC de ned in De nition 2113 and note that f f IC under the condition that f gt ltgtO for all a E ERquot Moreover the assumption of the proposition implies that 15 E Cm l quot and domf dom IC V Hence by Proposition 257a and Exercise 259 we have fcyoc f c ICYOC f c ICx This expression clearly implies that statement d is equivalent to statement d of Proposition 258 with f 2 f5 Since statements a b and c are clearly equivalent to statements a b and c respectively of Proposition 258 with f 2 f the equivalence of the above statements follows from Proposition 258 with f 2 f I Exercise 2511 Assume that f E Conv Rquot is a convex quadratic function ie 12 x Qx cx r for some Q E Squot c E 3quot and 39y E 33 Show that for every d E 33quot ad ide0 f d 00 otherwise Exercise 2512 Let f E 0mmquot A E 337quot b E 33 and a closed convex set X be given Assume that the problem fquot z inffx Ax bx E X is such that f E 33 and its set of optimal solutions is nonempty and bounded Prove that for every E 33 and p gt 0 the problem inffx Al Ax pr Ax22 a E X has nite optimal value and its set of optimal solutions is nonempty and bounded 26 Directional derivative De nition 261 Let f 3quot gt 3 and a E 3quot be such that E 33 The directional derivative off at 339 along d E ERquot denoted by f a39 d is de ned as m m mt 4w f 7 d 2 lllw 220 directional whenever the above limit exists possibly equal to ice Recall that f ERquot gt 3 is said to be differentiable at 3 E ERquot if f E 33 and there exists a linear map f a ERquot gt 33 such that f M W f W o 221 It is easy to see that there is at most one linear map f a satisfying 221 and that the later equation implies that 339 E int dom f Moreover if f is differentiable at 5 then f a d is well de ned and f a d f a d for every d E ERquot lim hat 37 inearmappos Lemma 262 If A ERquot gt ER is a linear map such that Ad 2 0 for every d E ERquot then A 0 Proof For every d E ERquot we have Ad 2 0 and Ad 2 A d 2 0 and hence Ad 2 0 I The result which gives necessary condition for 3 to be a local minimizer of f over ERquot is well known ioptimalsol Proposition 263 Assume that f 33quot gt 3 and a E 3quot are such that E 33 and 339 is a local minimum of inffa a E 33quot Then f a39 d 2 0 for every d for which f a39 d is wellde ned In particular iff is di erentiable at 5 then f a39 0 Proof Let d E 3quot be such that f a d is well de ned and assume for contradiction that f a39 d lt 0 In view of de nition 220 it follows that fa39 td lt 0 or equiva lently f td lt f for every t gt 0 suf ciently small Since any neighborhood of 3 will contain a point 339 id for some t gt 0 suf ciently small and f td lt f we conclude that 3 is not a local minimum of inffa a E 33quot and thereby 339 t the l quot of the l l quot39 Hence the rst part of the proposition follows If in addition f is differentiable at 5 we have 0 g f a d f a d for every d E ERquot By Lemma 262 we conclude that f a 0 I ss derivative Proposition 264 Assume f E E Conv Rquot and 3 E ERquot are such that E 33 Then the following statements hold a for every d E ERquot f a d is wellde ned and f a d inflgtg Afta d b 2 f a39 a for every 3 E 33quot c if in addition f is strictly convex then fa39 gt f a39 m i for every 3 E domfa Proof Statement a follows immediately from the fact that Afa d R gt 3 is a non decreasing function in view of Proposition 255 To prove b note that by a we have that for every 3 E ERquot fm gAfWiwiSA himi f l Statement c follows by noting that in view of Proposition 255 the only inequality in the I expression above holds strictly when a E dom f abalmin equiv Proposition 265 Assume f E E Conv Rquot and 339 E 33quot are such that E 33 Then the following statements are equivalent a 339 is a global minimum of inffa a E 33quot b 3 is a local minimum of inffa a E 33quot c f a d 2 0 for all d E 33quot d f a m i 2 0 for alla E domf If in addition f is di erentiable at 5 then the above statements are equivalent to arma 38 imalsolution fCglobalmin Proof The implications a gt b gt gt d are either immediate or follows from Proposition 263 To show the implication d gt a let a E dom f be given It follows from the assumption and Proposition 264b that fa fa 2 f a x i 2 0 We have thus shown that 2 for every x E dom f and hence a E ERquot The equivalence f e follows from Lemma 262 and the fact that when f is differentiable at 5 we have f a d f a d for every d E ERquot I Proposition 266 Let C Q ERquot and f ERquot gt it be such that C O domf E m If f is strictly convex on C then the problem minf a E C has at most one global minimum In particular if C is convex f is strictly convex and C O dom f E V then the above problem has at most one global minimum Proof Assume that f is strictly convex on C or equivalently that the function f de ned in De nition 2113 is strictly convex Assume also that 3 is a global minimum of minf a E C This is equivalent to say that 3 is a global minimum of f5 over the whole ERquot Note that the assumption C dom f E V implies that 339 E C dom f dom f or equivalently that few lt 00 If fan 00 then Exercise 2111 implies that 3 is the only global mimimum of f5 over ERquot and hence of the problem minf a E C Assume now that few E 33 Then by Proposition 264c and Proposition 265 with f 2 f we have few few 3 gt f53 33 3 3 2 0 for every x E dome This clearly implies that 3 is the only global minimum of f5 over ERquot and hence of the problem minf a E C The second part of the proposition follows immediately from the rst one and Exercise 2114d I Proposition 267 Let f E E Conv Rquot a convex set V E C Q 33quot and a point 339 E C such that f E 33 be given Then the following statements are equivalent a 339 is a global minimum of inffx a E C b 339 is a local minimum of inffx a E C c f a d 2 Ofor alld E RC a d f a x x 20for allx E C domf If in addition f is di erentiable at 5 then the above statements are equivalent to e f a39x 2 0 for every x E C Proof Consider the function fa 3quot gt 3 de ned in De nition 2113 The assumption of the proposition implies that few E 33 and that fC E E Conv Rquot in view of Exercise 2114d We claim that f ER C I fid7idE Jr 5 fclmi d 00 otherwise Indeed ifd E 33 C a39 then 339 td E C and hence Afdt 5 d 00 for every t gt 0 Thus if d E 334 C a we have f d inflgtg Afgta d 00 Assume now that d E R C i This implies that there exists 110 gt 0 such that 339 tad E C why The assumption that C is convex then implies that 33 td E C and hence that Afdtmi d A t 5d for every t E 0t01 This clearly implies that fa d f a d 39 iivdiffconv Using the above claim and the fact that dom f0 C Odom f it is now straightforward to verify that statements a b c and d are equivalent to statements a b c and d respectively of Proposition 265 with f 2 f5 Hence the equivalence of statements a b c and d follows from Proposition 265 applied to f 2 f The equivalence of c and is straightforward why I We observe that Proposition 267 would still hold if its assumption were relaxed to simply requiring that f 33quot gt 3 be convex on a set C 9 3quot and that 339 E C be such that E 33 Note that under this assumption f i d may not be well de ned for every d E 33quot but the above proof shows that f a d is well de ned for every d E 33 C Exercise 268 Show that iff E E Conv l3quot anda39 E 3quot is such thatfa39 E 33 then dom f a 33 domf 27 Convex differentiable functions In this section we discuss several characterizations for the convexity of a differentiable function Proposition 271 Assume that f 3quot gt l3 is di erentiable at every point of a convex set V C Q 33quot Then the following statements hold a f is convex on C if and only if M 2 me rem as e c 222 1 f is strictly convex on C if and only if inequality 222 holds strictly for any two distinct points 333 E C c f is strongly convex on C with modulus 3 gt 0 if and only if 2 fng V5351 E C 223 strongcom Proof We will proof only a The proof of b and c are similar First note that the assumption implies that f E 33 for every 3 E C and hence that f is convex on C if and only if C is convex and inequality 24 holds for every a E 0 1 and x0 an E C Exercise 2114b Assume rst that f is convex on C and let 333 E C be given Consider the function fC de ned in De nition 2113 Then by the proof of Proposition 267 we have f x i f a39 x i f a a 5 where the last equality is due to the assumption that f is differentiable at points on C Moreover since f E E Conv l3quot we have by Proposition 264b and the de nition of f5 that fx fa39 2 f a Inequality 222 now follows from the last two conclusions Assume now that 222 holds and let xux1 E C and a E 01 be given De ne 3 z axe 1 ax1 Using 222 twice the de nition of 3 and the fact that a E 0 1 we obtain afu1 awn 2 0W3 f3953u 53l1 coma f3933931 53H f a axu 1 ax1 ame 1 ax1 from which the convexity of f on C follows I 40 Exercise 272 Prove that iff E E Conv R is di erentiable at 339 E ERquot then 6fa39 gum monotone Proposition 273 Assume that f 3quot gt 3 is di erentiable at every point of a convex set V C 9 ERquot Then the following statements hold a f is convex on C if and only if man f lta1lta 4 2 o e c 224 h f is strictly convex on C if and only if inequality 224 holds strictly for any two distinct points 333 E C c f is strongly convex on C with modulus 3 gt 0 if and only if Q 5 strongcom Proof We will prove only a Assume rst that f is convex on C and hence that relation 222 holds in view of Proposition 271a Let 5 a E C be given Using 222 twice we conclude that 0 W33 f 7 3llf53 fl 2 f 53 53 f l l a lf f 53l 53 Assume now that 224 holds and let 333 E C be given Consider the function q 01 gt ER de ned as q t fal where 3 339 113 for every t E 01 Clearly q t f xlx a39 for every t E 0 1 Hence Lagrange s mean value theorem implies the existence of a scalar g E 0 1 such that f x mam 5 2 ng a 2 V323 e c 2 ff53f 53 33 53 1 0 0 39 390 li39WaFf HWii lf39af39il i20 where the last inequality is due to 224 It then follows from Proposition 271a that f is convex on C I Proposition 274 Assume that f 33quot gt 3 is twice di erentiable at every point of a convex set C Q 33quot such that intC V Then the following statements hold a f is convex on C if and only if f a39 gt39 0 for every 339 E int C b if f gt 0 for every 339 E C then f is strictly convex on C c f is strongly convex on C with modulus 3 gt 0 if and only if fquota gt39 H for every 339 E int C Proof We will only proof a Assume that f is convex on C and int C V By Proposition 273a it follows that 224 holds Now let 3 E intC and a E C be given Consider the map q 01 gt ER de ned in the proof of Proposition 273 Note that for every t E 0 1 we have 4W 4W0 lf39l t f39ul 53 tlf39W f3933lt 53 2 0 where the inequality is due to 224 The latter conclusion clearly implies that f a39x a39 x a q 0 2 0 This in turn implies f a d d 2 0 for every d E R C Now using the fact that 3 E int C we can easily show that 33 C 2 ERquot why and hence that f a39 t 0 41 To prove the converse assume that f a39 gt39 0 for every 3 E int C Now x 333 E intC and consider the map q 01 gt t as above Then q t f ala a a a39 2 0 for every t E 01 in view of the assumption and the fact that an E int C This implies that q is a nondecreasing function In particular we have 0 S 4W1 W0 lf391 f39ul 53 lf39l f3953l 3393 showing that 224 holds with C int C Since f is a continuous map on C and C Q ch 2 cl int C due to Proposition 1712 a trivial limiting argument shows that 224 also holds with C C why and hence that f is convex on C in view of Proposition 273a I 28 Subgradients De nition 281 Let function f 33quot gt 3 and point 339 E 33quot such that E 33 be given A vector 3 E ERquot is called a snbgmd ent off at 3 if 2 33 5 Va E ERquot The set of all subgradients off at 5 denoted by 8fa39 is called the subdi erential off at 5 lbg39baSiC39ObS Proposition 282 Let function f 3quot gt 3 and point 339 E 33quot such that E 33 be given Then the following statements hold a 3 is a global minimizer of inffa a E 33quot if and only if 0 E 8fa b the subdi erential 6fa off at 3 is a possibly empty closed convex set Proof a 17 b 27 I The following result shows that the directional derivative f i determines the subdifferential of f at 5 Proposition 283 Assume that f E E Conv Rquot and 339 E 3quot is such that E 33 Then S E 33quot 2 303 3 f 7 d Vd E 33quot 226 subgderivl Proof The proof follows from Proposition 264 a and the following straightforward equivalences s E 6fa39 f fa39 2 s z fa td me 2 s d Vt gt 0 Vd 6 ERquot E f39idinfw Tl M t 2sd VdE R We observe that another equivalent and more compact way of writting 226 is as follows 6fa s E 33quot s 3 f39a In words the subdifferntial of f at 339 consists of the vectors 3 E ERquot whose associated linear function 3 minorizes the directional derivative functional f a of f at 5 We now state two important results regarding subgradients which will be proved later after we develop the tools needed for their proofs The rst result establishes the existence of subgradients at points lying in the relative interior of the domain of f 42 Proposition 284 Let f E Conv R and 339 E ri dom f be given Let S denote the subspace parallel to a dom f Then the set d i O S is nonempty and bounded and d a d i O S SJ where SL 2 E ERquot 33 0 Vs E S The second result establishes that the subdii39ferential of f at 3 determines the directional deriva tive functional f a whenever 3 is in the relatice interior of the domain of f This result together with Proposition 283 therefore establishes an associtation between subgradients and directional derivatives which generalizes the association between the gradient and derivative of a differentiable function f at a certain point 5 Proposition 285 Let f E Conv Rquot and 339 E domf be given Then for every d E ERquot we have m d supltsdgt e are Moreover the svprenmm in the above relation is attained whenever it is nite 43 44 Chapter 3 Separation and Duality Results 31 Projection operator jwelldefined Proposition 311 Let a point 339 E 33quot and a closed convex set V C Q 33quot be given Then the problem infx a E C has exactly one global minimim Proof First observe that the set of optimal solutions of the problems infx a E C and infq ix 5 22 a E C are identical Clearly ti is strongly convex with modulus i 1 and hence strictly convex Moreover it is easy to see that 00 for every d 0 The conclusion of the proposition now follows from these two observations together with Propositions 266 and 2510 l The unique global minimum of Proposition 311 will be called the closest point to a in C De nition 312 Given a closed convex set V C Q ERquot the projection operator onto C is the map Hg 33quot gt 33quot which maps a E 33quot into the closest point ght E C to a in C Clearly Hd l quot C and a if and only if a E C The following result characterizes the closest point to a in C Proposition 313 Let a point 339 E 33quot and a closed convex set V C Q 33quot be given Then 15 Haw J and only x a 1 OVxE C Proof Clearly 15 11533 if and only if 15 argmin z 5 22 a E C In view of Proposition 267 and the fact that ti is a convex function the later condition is equivalent to the condition that 0 3 it39d 15 15 15 5 a 15 for every x E C I The above characterization of the projection operator allows us to prove a number of results about it Proposition 314 Let a closed convex set V C Q 33quot be given Then for every x0x1 E ERquot there holds Hx1 H E0H2 3 31 130 HC1 HCb Eu 31 projcontrl As a consequence we have IL43 HCOH 3 32 projcontr2 45 Proof Using Proposition 313 twice the rst time with 3 30 and a Ha1 and the second one with 3 31 and a Ham we have HOW Ham 3 Hx S 0 HC30 HfE1fE1 H E1 3 0 Addind these two inequalities and rearranging we obtain 31 Moreover 31 and the Cauchy Schwarz inequality imply that HID 1 new S 1 330 110331 110330 gt S H331 0HHHC1 HOMO which clearly implies 32 I 32 Separation results for convex sets De nition 321 Let nonempty subsets C1 and Cg of 3quot and a hyperplane H 9 3quot be given It is said that a H separates C1 and Cg if C1 lies in one of the closed half spaces determined by H and Cg lies in the opposite closed half space b H properly separates C1 and Cg ifH separates C1 and Cg and C1 U Cg Z H c H strongly separates C1 and Cg if there exist 51 gt 0 and 6g gt 0 such that H separates the sets C1 B051 and Cg B05g Clearly the above conditions are related as c gt b gt a Moreover it is possible to give examples showing that the two reverse implications do not hold Also if C1 and Cg are strongly separated by a hyperplane H then C1 U Cg O H V so that C1 lies in an open halfspace determined by H while Cg lies in the opposite open halfspace The next result shows that the above geometric de nitions admit algebraic characterizations in terms of two optimization problems whose feasible sets are C1 and Cg respectively 1a1gcharact Proposition 322 Let nonempty subsets C1 and Cg of 3quot be given Then the following state ments hold a there exists a hyperplane H separating C1 and Cg if and only if there exists 0 s E 3quot such that sups x1 x1 E C1 3 infs mg xg E Cg 33 b there exists a hyperplane H properly separating C1 and Cg if and only if there exists 3 E 33quot such that 33 holds and infs x1 x1 E C1 lt sups 122 xg E Cg c there exists a hyperplane H strongly separating C1 and Cg if and only if there exists 3 E 33quot such that sups 511 231 E Cl lt infs mg ng E Cg 34 strongsepa 46 3strongsepa 3propersepa Proof The proofs of a and b are straightforward and are left to the reader We will prove only c We rst note that for any 5 gt 0 and s E 33quot we have MUS 1 1 Hull S 5 5HSH Sllplltugt1UHS 5 5HSH Indeed by Cauchy Schwarz inequality we have s g g 5H3 for every n E H and this inequality holds as equality if and only if u E ios when 3 0 and u E B when 3 0 Then a hyperplane H H so strongly separates C1 and Cg if and only if s 0 and there exist 5 gt 0 i 12 such that 67 H3 Sllplltulgt1ulEC1B051l S 39r S inflltu2gtIUQECQB052 lt3 Sllpllt1 gt1u351 331601 7 lt infllt2ulillu352 2602 a Supltsm1gtm1 0161Hs s 7 inn mmmgecgi agusu S S It is now immediate to see that s 0 and the fact that the latter inequality holds for some 51 gt 0 52 gt 0 and 39y E 33 is equivalent to the strict inequality 34 I The following result is a rst main consequence of the projection operator introduced earlier Proposition 323 Let a point 339 E 33quot and a convex set V C Q 33quot be given Then there exists a hyperplane strongly separating 339 and C if and only if 3 E ch Proof Assume rst that there exists a hyperplane H strongly separating 3 and C It is easy to see that this implies that C and hence cl C is in one of the closed halfspace spaces determined by H and that 3 is in the opposite open half space Hence we must have 3 E ch Assume now that 3 E ch and let C ch Take 3 z 3 HA3 and note that s 0 since 3 E C and Hay E C By the de nition of s and Proposition 313 we have sups x a H s supa HC 3 x Hd 30 13966 xEC and hence that supxec s g supxa s g s lt s Thus by Proposition 322c there exists a hyperplane strongly separating C and 5 I As an immediate consequence we have the following result Proposition 324 Let a convex set V C Q ERquot be given Then ch is equal to the intersection of all closed halfspaces containing C Proof We rst observe that a closed half space contains C if and only if it contains ch This implies that cl C is contained in the intersection of all closed half spaces containing C To prove the reverse inclusion let a E ch be given By Proposition 323 there exists a hyperplane H strongly separating a and ch Let H and H I denote the closed half spaces determined by H containing a and C respectively Strong separation implies that a E H I Moreover since C Q H I it follows that the intersection of all closed half spaces containing C is a subset of H I Hence a does not belong to this intersection I Proposition 325 Let a point 339 E 33quot and a convex set V C Q 33quot be given Then there exists a hyperplane properly separating 339 and C if and only if 3 E riC 47 Proof To show the only if7 part assume that there exists a hyperplane H properly separating 3 and C Let H I and H denote the closed half spaces determined by H and assume without loss of generality that 339 E H and C Q H4 By assumption we have U C Q H If 3 E H then 339 E int H7 3quot H Q 3quot C and hence 3 E C Q riC If on the other hand C Q H we claim that riC 0 int H I 9 Indeed if this intersection were empty the fact that riC Q C Q H I would imply that riC Q H and hence that C Q ch 2 cl riC Q H where the second inclusion is due to the fact that H is closed Since this 39 t 339 t the l quot that C Q H the claim follows Now the claim and Proposition 1720 imply that riC intH riC riH riCnH riC and hence that riC Q int H I Since 3 E H the latter conclusion implies that 3 E riC To prove the if part assume now that 3 E riC There are two possibilities either 3 E ch or 339 E rde In the rst case we know by Proposition 323 that there exists a hyperplane which strongly and hence properly separates 339 and C Assume now that 339 E rde rbd ch where the last equality is due to Proposition 1712 Then there exists a sequence Q a C ch converging to 5 By the proof of the if part of Proposition 323 the vector 3 3 z wk Hawk 0 satis es k k k V quot quot quot V mlts 3 VkEO 39 Observe also that 3 6 E affC Hawk 2 L where L denotes the subspace parallel to Dividing 3 3 by its norm we may assume that 1 for each h Since the boundary of the unit ball is a compact set the Bolzano VVeisstrass theorem implies that the sequence has a convergent subsequence skhem Letting 3 denote its limit we clearly have that 1 and s E L Moreover taking the limit of 35 as k gt 00 we obtain sumem g s In view of Proposition 322b to complete the proof of the if part it suf ces to show that infxeds lt s Indeed assume for contradiction that s s for every 3 E C This clearly implies that s u 0 for every n E linC Since 339 E rbdC Q ch Q affch a C we have linC affC 3 L The last two observations then imply that s u 0 for every n E L Since 3 itself is in L we must have 3 s s 0 which contradicts the fact that 1 Hence it follows that inf16s lt s 3 I 32 separation Proposition 326 Let nonempty convex subsets C1 and Cg of 33quot be given Then the following statements hold a there exists a hyperplane strongly separating C1 and Cg if and only if 0 E cl C1 Cg b there exists a hyperplane properly separating C1 and Cg if and only if riC1 ri Cg V Proof We rst note that sups 233601 02 sups El 132 ml EC1 ngCg supsa1 infsag MECi EC and similarly infs 232601 02 inf sa1 sup 3332 39QECQ 1391 ECl 1 These two relations together with Proposition 322 show that C1 and Cg can be properly resp strongly separated by a hyperplane if and only if 0 and C1 Cg can be properly resp strongly 48 fineenvelope separated by a hyperplane which in turn is equivalent to the condition that 0 E riC1 Cg resp 0 52 cl C1 Cg in view of Proposition 325 resp Proposition 323 Hence a follows Moreover b also follows by noting that by Proposition 1716 we have ri C1 Cg ri C1 ri Cg and hence 0 52 ri C1 Cg f riC1 ri Cg V I We now state two consequences of the results proved above Proposition 327 Let nonempty convex subsets C1 and Cg of ERquot be given and assume that Cg is bounded Then there exists a hyperplane strongly separating C1 and Cg if and only if cl Cl cl Cg V Proof We claim that the assumption that Cg bounded implies that cl C1 Cg 2 cl C1 cng Note that the conclusion of the proposition follows from this claim Proposition 326a and the fact that cl C1 0 cl Cg V f 0 g cl C1 cng To prove the claim we rst note that the inclusion cl C1 Cg 2 cl C1 cl Cg follows from Proposition 7 To prove the reverse inclusion let a E cl C1 Cg be given Then by the de nition of the operator cl and the set C1 Cg there exist sequences Q C1 and Q Cg such that limknocbx 1quot 3 Since Cg is bounded it follows from the Bolzano VVeisstrass theorem that has a convergent subquence Let xg denote its limit point Clearly we have xg E cng Moreover we have limknm limkn xf limgHyg a xg 2 31 Clearly 31 E cl C1 This shows that a x1 xg E cl C1 cl Cg I We now make a few observations which are useful for the next result It is easy to see that any closed half space in ERquot gtlt ER admits one of the following representations Hs xt E ERquot gtlt ER sx 1 3 3 36 H s 392 xt E ERquot gtlt ER sx t 3 3 37 H s z Hggx xtE RquotX Bsx 9 38 for some 3 3 E ERquot gtlt ER Among these three representations only two are epigraphs H s 3 is the epigraph of the a ne function 3 3 and H 3 3 is the epigraph of the improper convex function which assumes the values 30 on the hyperplane H 5quot3 and 00 outside of it One of the main consequences of the separation results proved above is the following important result about convex functions Proposition 328 If f E E Conv Rquot then f is equal to the pointulise supremum of all af ne functions minorizing f ie clf sup A A ERquot gt ER af ne A g f 39 As a consequence if f E Conv Rquot then there exists an af ne function minorizing f Proof The theorem clearly holds if f 30 or f x0 30 for some 30 E ERquot We may then assume from now on that f E Conv R De ne 2 s E Rquotgtlt RH s erif 20 356quotXHusy 2 pif and note that in view of Exercise 212a we have x Va E dom f 0 Va E dom f 310 311 49 supaffine Note also that any half space H s 3 can not contain the epigraph of any function which is not identically equal to 00 and hence the set epi f By Proposition 324 and the above observations it follows that 1 epi f 1135 Q Q H 3 312 supaffine s3ez 35gt 20 We claim that the second intersection can be removed from the right hand side of the above expression ie clepif H 3 3 87562 Note that this claim implies that epiclf epilscf cl epif H 3quot epi3 3 35gtEZ 23562 Hence in view of Exercise 212b and 310 we have clf s11p3 33quot 6 3quot gtlt 3 such that f 2 3 3 or equivalently holds To prove the claim assume for a contradiction that there exists 0130 6 3quot gtlt 3 satisfying a t 1113 whom H 3quot 313 supaffine smei39 8mg Then there exists 3030 6 20 such that 330130 H 3 3 or equivalently 30330 gt 30 Note also that 2 7 0 since otherwise we would have epif domf gtlt 3 due to 312 and 38 which is not possible in view of the assumption that f E Conv3quot Now x 313 E 2 5 0 Using 310 and 311 we easily see that 3 0303 043 6 2 for any on gt 0 Hence in view of the rst inclusion in 313 we have 0130 6 H 3 0303 043 or equivalently 3 30330 to g 3 043 Va gt 0 which is clearly not possible due to the fact that 3 30 gt 30 I 33 Conjugate Functions De nition 331 The conjugate of a function f 3quot gt 3 denoted by fquot is the function fquot 3quot gt 3 de ned as sup 333 V3 6 3quot 65quot Clearly equivalent expressions for f3 are sup 333 sup 333 t V3 6 3quot 314 defconjugl medomf xteepif exerc conjugl Exercise 332 Let f 3quot gt 3 be given Show that a iff 00 then fquot 00 iffa 00 for some 0 6 3quot then fquot 00 50 exerc conjugZ same conjug jensen tight 00 for some 3 6 3quot then f 00 and hence fquot 00 5 iff3 c epifsquot E3quot gtlt3zf 2 s 3 d for every 3 6 3quot we have fs inf 3 6 3 f 2 s 3 and the in mum is achieved whenever fs is nite e f0 inffa a 6 3quot f F enohel s inequality for any 333 6 3quot we have 2 at s Exercise 333 The following statement hold a for any collection f77gf of functions f7 3quot gt 3 there holds inf su 751 ii 763 f7 clf lscf Proposition 334 For any f E E Conv3quot we have fquot Proof lff so then we have f clf lscf and hence fquot clf lscf If 00 for some 30 6 3quot then fquot clf lscf 00 due to Exercise 332a Assume then that f E Conv3quot Since every af ne function is continuous and hence lower semi continuous it follows from Proposition 234 that an af ne function A minorizes f if and only if A minorizes cl f lsc f Hence it follows from Exercise 332c that fquot cl f and lsc f all have the same epigraph namely the set 33 6 3quot gtlt 3 f 2 s 3 Hence Exercise 212a implies that fquot clf lscf I Proposition 335 Let f 3quot gt 3 be such that f 5 00 and f is minorized by some af ne function Then fquot E Cm3quot In particular iff E Conv3quot then fquot E Cm3quot Proof Since f 7 so we have domf 7 0 By 314 fquot is the pointwise supremum of the nonempty collection of the a ne functions f as a varies in dom f Hence Proposition 257b implies that either fquot E Cm3quot or fquot so Also the assumption that f is minorized by some af ne function and Exercise 332c imply that epifquot g Q and hence that fquot g 00 Thus we conclude that fquot E Cm3quot l Proposition 336 Assume that f E E Conv3quot Then clf f where fM Proof By Proposition 328 we have for every 3 6 3quot cl w supsa 3 SJ 6 3quot gtlt 3 such that f 2 s 3 supsa 3 36 6 epif where the last two equalities are due to Exercise 332c and relation 314 with f fquot I Proposition 337 Let f 3quot gt 3 and ac 6 3quot be such that ac 6 3 Then 3 E B w if and only if fs g 333 or fs sa 51 Proof We have sea w ltgt fy2fatsy at VyE3quot 4 lt35gtfw2lt3531gtfy5 vye Rn 4 NS 2 8119M fly 96513quot A geometric interpretation of the above result is that s 6 if if and only if the graph of the largest af ne function with slope s minorizing f namely the a ne function 3 s fs contains the point at lying in the graph of f Example 338 Consider the function f 3 gt 3 de ned as e r for every 3 6 3 Since the largest af ne function with slope 0 minorizing f does not intersect the graph of f it follows that 0 for any a 6 3 g implies lsc Proposition 339 Let f 3quot gt 3 and a 6 3quot be such that 6 3 and and g 0 Then the following statements hold a lscfac ac ie f is lower semicontinuous at 90 b if in addition f E E Conv3quot then clfac ns ie f is closed at ac Proof a Fix 3 E 5 0 Then the af ne function 333 minorizes f and clearly f Since A is lower semi continuous it follows from Proposition 234c that A g lscf g f Hence we have g lscfa g from which a follows b If in addition f E E Conv3quot then it follows from the trivial fact that A E Cm3quot g E Cm3quot and Proposition 2414c that A S clf S f and hence that g lscfa g from which follows I Proposition 3310 Let f E E Conv3quot and ac 6 3quot be such that ac 6 3 Then the following conditions on a vector 3 6 3quot are all equivalent a 8 E aim 5 8 E 3le and 01f N c w e are and mm M Proof By Propositions 337 and 339b statement a is equivalent to emu M emu Me was In view of Propositions 336 and 334 the second condition above is equivalent to either one of the following two conditions 333 and clfs 333 Also in view of Proposition 337 applied to the functions fquot and cl f the above two conditions in turn are equivalent to the conditions a E 8fs and s E 8cl respectively I Exercise and the result below show that the value and subddifferential of fquot at 0 completely determines the optimal value and set of optimal solutions of the problem inff a 6 3quot under the assumption that f 6 CW 52 Proposition 3311 Assume that f E CW2quot Then 8f0 is equal to the set of minimizers ofinffa a 6 2quot Proof By Proposition 282a it is a minimizer of inffa a 6 2quot if and only if 0 E B i or equivalently it E 8f0 where the latter equivalence is due to the equivalence of statements a and c of Proposition 3310 I 34 Convex hull of a function De nition 341 The convex hull of a function f 2quot gt 2 denoted by co f is the function de ned as cof supg E E Conv2quot g S 315 Proposition 342 Let f 2quot gt 2 be given Then the following statements hold a cof E E Conv2quot and cof S f b cof is the largest function in the collection offunctions Cm g E E Conv2quot g S f c for g E E Conv2quot we have 9 S f if and only if g S co f Proof The proof of this result follows from de nition 315 and Proposition 21151 I De nition 343 The closed convex hull of a function f 2quot gt 2 denoted by ch is de ned as ch cl cof Proposition 344 Let f 2quot gt 2 be given Then the following statements hold a ch E E Cm2quot and ch S f b ch is the largest function in the collection offunctions g E E Cm2quot g S c for g E E Cmmquot we have g S f if and only if 9 S Proof a By Propositions 342a we know that cof E E Conv2quot and cof S f Then by Proposition 2414 we conclude that ch cl co f E E Cm2quot and ch S co f and hence that ch S f b By Proposition 2414a ch cl co f is the largest function in the collection 9 E E Cm2quot g S co f which is identical to the collection CU in view of Proposition 342c c This statement is an immediate consequence of a and I We will next provide an inner characterization of the function co f in terms of the epigraph of f First we introduce the de nition of the lower bound function of a set and establish suf cient conditions for its convexity sum function De nition 345 For a set D g 2quot gtlt 2 the lowerbound function ofD is the function l1 2quot gt 2 de ned as l1a inft 6 2 att E D Va 6 2quot 53 inner 00f inner ccof Clearly if D epif then ID f ie flw inst m e epif Proposition 346 IfD g 3quot gtlt 3 is convex then 1 E E Conv3quot Va 6 requot 316 Proof In view of Proposition 216 it suf ces to show that epislp is convex Indeed let wor0w1r1 E epislp and 010021 6 A1 be given Then due to the de nition of 1 there exist scalars t lt n such that whiz E D Since D is convex we have 105170 x1331 auto a1t1 a0w0t0 121337131 E D Hence l10 0170 021731 S auto 011131 lt more mm due to the def inition of ID and the fact that 01mm 6 A1 and t lt n for i 01 We have thus shown that a0a0r0 031277 7 1 010330 a11a07 0 mm 6 epislp and hence that epislp is convex I Proposition 347 Let f 3quot gt 3 be given Then epicof 2 co epif and cofa inft 6 3 att 6 co epif Va 6 3quot Proof Let D co epif We want to show that cof ll where ID is de ned in Propo sition 346 Indeed since D co epi f is convex it follows from Proposition 346 that l 1 E E Conv3quot Also 316 and the fact that epif g co epif imply that inft att E epif 2 inft att 6 co l1fl or equivalently l 1 S f Hence it follows from Proposition 342c that l 1 S co f On the other hand since co f E E Conv3quot and co f S f by Proposition 342 it follows that epi co f is convex and epico f 2 epi f In view of Proposition 165b this implies that epi co f 2 co epi Using this inclusion and identity 316 with f co f we conclude that co inft att E epi co S inft att 6 co 1012 Va 6 3quot or equivalently co f S l 1 We have thus shown that co f l 1 l Va 6 3quot Exercise 348 Let f 3quot gt 3 and de ne h lscco Then epi and inft 6 3 att E cTepif Va 6 3quot In particular if f is minorized by some af ne function then epif cTepi f and inft 6 3 att E cTepif Va 6 3quot Proposition 349 Let f 3quot gt 3 be given Then the following identities hold r lscf cof WW ch f Proof The third identity in 317 follows from Proposition 334 applied to the function c f Since every af ne function is convex resp lower semi continuous it follows from Proposition 342b resp Proposition 234d that an af ne function A minorizes f if and only if A mi norizes cof resp lscf Hence Exercise 332c implies that the functions fquot lscf and cof have the same epigraph namely the set 3 6 3quot gtlt 3 f 2 s 3 Hence it follows from Exercise 212a that the rst and second identities in 317 also hold Proposition 336 applied to the function co f implies that ch cl co f co f f where the last equality follows from 317 I 317 318 f lower epi same conjug racter izat ion Jroperat ions rt invariance QOI C monotone 3 5 Sublinear Functions In this section we introduce an important class of convex functions namely those whose epigraph is a cone De nition 351 A function 0 33quot gt 33 is said to he a sublinear if its epigraph is a convex cone h subadditive if 0xo 301 3 0xo 0x1 for every 300901 6 dom0 c positively homogeneous of degree one if 0tx t0x for every t gt 0 and x E 33quot Proposition 352 Let 0 33quot gt 33 be given Then the following statements are equivalent a 0 is sublinear h 0 is suhadditive and positively homogeneous c 0t0x0 t1x1 g t00x0 t10x1 for every 130131 gt 0 and xmxl E dom0 d 0 is convex and positively homogeneous Exercise 353 Let 0 33quot gt 33 he a sublinear function Prove the following statements a dom0 is a convex set h 00 6 oo0oo c if0 is a proper sublinear function then 0d 0 d 2 00 2 0 d if0 is a proper closed sublinear function then 00 0 Example 354 1 For a set C Q 33quot the support function 00 33quot gt 33 is a closed sublinear function Note that 00 is proper if and only if C g 0 in which case 000 0 Also if C 0 then 00 00 2 Any norm in 33quot is a nite Valued and hence closed sublinear function Proposition 355 For any set C L 33quot we have lscIC 2 dc coIC ICOC W10 GT6 Proposition 356 For any set C L 33quot we have 00 0610 0000 0mg 319 Proof Relation 319 follows by using 317 with f Io Proposition 355 and the fact that 171quot 01 for every set D g 33quot I Proposition 357 Suppose 0102 g 33quot are closed convex sets 0Cl S 002 As a consequence Cl Cg if and only if 0Cl 002 Then Cl g Cg if and only if 55 supp barcoc supp ontoness subl sigmo ide Proof The only if part follows immediately from the de nition of the support function To prove the if part assume that 001 S 002 In view of the identity Ic 00 the latter inequality is equivalent to ICI S 102 This conclusion together with Propositions and 336 and the fact that IC 6 E Cm quot whenever C is a closed convex set then imply that IQ ICIM 2 162M 102 and hence that 01 g Cg I Corollary 358 For any C g 33quot we have cTCacE Bquotac Soc 320 Proof In view of Propositions 356 and 357 and the fact that 00 at we have the following equivalences about a given a E 33quot chTCltgtat 0 ox omcltgtat Soc Proposition 359 Ifo is a closed sublineur function such that o 7 00 then a 00 where C 00 E W 90 S a 321 Proof The assumption implies that either a 00 or a is a proper closed sublinear function If U 00 then C Q from which we conclude that 00 00 0 Assume now that a is a proper closed sublinear function We claim that 0 160 Indeed assume rst that a E C Then by 321 we have S a and hence 027 sulphas as S 0 36 7 Moreover since 00 0 due to Exercise 353d we also have that 0 2 370 00 0 We have thus shown that 027 0 whenever a E C Assume now that 3 Ca Then due to 321 there exists 30 E 33quot such that 51780 gt 030 This inequality and the homogeneity of 0 imply that wave sup 333 03 2 supats 0t30 s11ptas 03 00 86quot tgt0 tgt0 We have thus proved that 0 I C This conclusion the assumption that a is closed and Proposition 336 then imply that o a U IC 00 I Corollary 3510 fa is a sublineur function such that o 5 00 then clo 00 where C 00 and 0a is given by 321 Proof The assumption implies that cla is a closed sublinear function such that cla g 00 Hence by Proposition 359 we conclude that cla 00 where C E 33quot at S cl 0 Moreover by Proposition 2414c and the fact that every linear function at is closed it follows that the latter set is equal to the set Ca de ned in 321 I Corollary 3511 Let C Q 33quot be a closed convex set and o be a closed sublineur function Then a 00 if and only if C 00 where Co L 33quot is de ned by 321 56 supp barcoc p boundedness onvex direct Proof This result follows as immediate consequence of Corollary 358 and Proposition 359 I Corollary 3512 The function which maps a closed convex set C L 33quot into its support function 00 is a bijection from the family of closed convex sets onto the family of closed sublinear functions a such that o 5 00 Proof This result follows as immediate consequence of Propositions 357 and 359 I Proposition 3513 Let C L 33quot be given Then C is nonempty and bounded if and only if 00 is nite everywhere Proof only if7 part If C is bounded then ch is non empty and compact and by Weierstrass Theorem we have add supd a E C E 33 for every 1 E 33quot if7 part Assume that 00 is nite everywhere Clearly this implies that C 7 Q and 00 E Conv quot From the latter conclusion and Corollary 224 it follows that 00 is continuous on 33quot Hence by VVeierstrass s theorem there exists a constant M gt 0 such that M 2 add supda a E C for every 1 E B01 In particular if a E C and d we conclude that M 2 da and hence that C Q BOM I Exercise 3514 Show that a 33quot gt 33 is a norm if and only if a 00 for some nonempty compact convex satisfying the following properties i 0 6 int C and ii a E C implies a E C 36 Subdifferential versus directional derivative In this section we further study the connection between subgradients and directional derivatives We have seen in Proposition 283 that the subdifferential of a proper convex f at a given point a E domf is characterized by the directional derivative function 1 E 33quot gt f In this section we establish results showing that the subdifferential of a proper convex function f at a point a E dom f characterizes the directional derivative function 1 E 33quot gt f 1 Proposition 361 Assume that f E E CoanBquot and i E 33quot is such that E 33 Then a domf a39c 321 domf is b f 7 is a sublinear function Proof Statement a follows from the following equivalences fitd fi t ltgt 3t gt 0 such that td lt oo ltgt 3t gt 0 such that i td E domf d E domf39 ltgt f39 d lt oo ltgt lt 00 1 ltgt 313 gt 0 such that d E domf aE ltgt d E B domf aE To prove b we rst show that E E Crnv 3quot Indeed let too1 6 domf39i and 020 01 6 A1 be given Then by a there exist positive scalars 130131 such that i hoti E domf fori 0 1 Convexity of domf then implies that itdi E domf fort 6 013 and i 0 1 Letting t mintot1 convexity of f and Proposition 216 imply that for every t 6 011 it tmodquot a1d1 ame tdquot aim c td1 g ozon tdquot al a39 td1 57 closuredire ct istence subg and hence that fli taod a1d1 fli S aofl td mic WM mi ma Letting t go to 0 in the above expression we conclude that fat modo 0211153 aof39uc 02 alf a39cd1 and hence that f E E Conv quot in view of Proposition 216 Noting that f Old ozf39 d for every 1 E 33quot and or gt 0 we then conclude from Proposition 352 that f is sublinear I Proposition 362 Assume that f E E Convmquot and a E W is such that at 6 32 Then 1 lf39l 39c l Ham Proof Since by Proposition 361 f is sublinear it follows from Corollary 3510 that cl 00 where C s E 33quot s g Bf where the last equality follows from Proposition 283 I Proposition 363 Assume that f E E Convmquot and is E W is such that at 6 32 Then 0 if and only if there exists d0 E 33quot such that f39ido oo in which case f39ligd 00 for every 1 E ri domf Proof Using Proposition 362 we have 0 if and only if clf Uaf 00 By de nition of the closure of a function the latter statement is equivalent to the existence of l0 E 33quot such that f do 00 Since f E E CoanBquot achieves the value 00 it follows from Proposition 249 that f d lf id 00 for every 1 E ridom ri 331 domf It remains to show that ri 331 domf Q ri domf Indeed it is easy to see that affm domf affdomf a Since domf a g B domf a and the two sets have the same a ne hull we conclude that ri dom f g ri 331 dom f I Proposition 364 Assume that f E E CoanBquot and i E 33quot is such that E 33 Then the following statements hold a ifi E ridomf then 7 Q and 03m b it 6 int domf if and only if is nonempty and bounded in which case f39 d maxds 3 E 322 Proof First note that by Proposition 361 domf a39 B domf and is sublinear and hence convex To prove a assume that it E ri dom f Using this assumption we can easily verify that B dom f is exactly the subspace parallel to a dom f from which we conclude that dom f is a subspace This conclusion Corollary 2411 and the fact that flit 0 0 imply that f E CWQR This together with Proposition 363 and Proposition 362 imply that 5 0 and f clf i 03f Hence a follows 58 subg f ormul Noting Proposition 361a it is easy to see that a 6 int domf if and only if dom B domf 3quot In view of Corollary 2411 and the fact that f i0 0 the latter condition is equivalent to f being nite everywhere In view of Propositions 2413 and 362 the latter condition is equivalent to the support function game being nite everywhere which in turn is equivalent to the subdifferential if being non empty and bounded due to Proposition 3513 We have thus proved the equivalence in Formula 322 follows immediately from a the de nition of the support function and the fact that if is a non empty compact set I 37 Lagrangian duality Consider the following equality constrained minimization problem ECP fquot inffa a E X 0Vi E E where E is a nite index set f and 9 i E E are functions from 3quot gt ooool and X is a subset of bequot We make the following assumptions on the data of problem ECP A1 0 5 X L domf ig d mgi A2 De nition 371 The Lagrangian of problem E39CP is the function 33quot X bequot gt 00 00 de ned as X H nv EiEEAZgAw ifa and A E 33 324 00 otherwise We observe that every 3 E bequot m Jaw A iwaXand ga0for alliEE A 00 otherwise and hence that problem ECP is equivalent to the following inf sup problem inf sup La A 325 x65quot Aggy De nition 372 The dual function 6 3 gt oooo is the function de ned as on we A fig m ZAgat VA 6 are 326 23961 The dual of problem ECP is the problem obtained by interchaging the in mum and the supremum in 325 ie the problem Sllpygg infxgg n La A or equivalently DECP 6 sup WA 327 A65 For every A E 3 denote the set of optimal solutions of 326 as XA ie XA E X 6A atA 59 primalminma dualfunct io weakdual icy Proposition 373 Everett For some A E 33 assume that ac E XA Then ac is an optimal solution of the problem inffa a E X ga W E 328 Proof Clearly at is a feasible solution of 328 Moreover for every 3 E X we have flw Z XMAS 90 A 2 CW M flu Zhigix 23961 is where the inequality is due to the assumption that at E XA In particular for a E X such that ga for everyi E E we have 2 ag from which we conclude that at is an optimal solution for 328 I De nition 374 Aquot E 33E is said to be a Lagrange multiplier of ECP if fquot E 33 and fquot 6Aquot Proposition 375 The following statements about a pair 37 Aquot E 33quot X 33E are equivalent a atquot is an optimal solution and Aquot is a Lagrange multiplier of ECP b 13 E XA and 0 for alli E E Proof a gt Assume that atquot is an optimal solution and Aquot is a Lagrange multiplier for ECP Then fquot WAquot and atquot E X 0 for all i E E and fquot This implies that 3W Aquot wquot ZAmMquot fl fquot 99 2396 and hence that atquot E XA gt al Assume that atquot E XA and 0 for all i E E These assumptions and Proposition 373 with A Aquot and at atquot imply that atquot is an optimal solution of ECP and hence that fquot fl fW ZAmil cquot C 99 i613 where the last equality is due to the assumption that atquot E XA Since E 33 the above expression also implies that fquot E 33 We have thus shown that Aquot is a Lagrange multiplier of ECP I Proposition 376 Weak duality For every feasible solution ac of ECP and every A E 331 there holds 2 WA As a consequence we have fquot 2 9 Proof If a is a feasible solution of ECP and A E 33 then a E X and 0 for all i E E and hence m m Z mm age A 2 inf and A WA is x EA This together with the de nition of fquot an 6 also imply that fquot 2 6 I Proposition 377 Aquot is a Lagrange multiplier of ECP if and only if fquot 9 E 33 and Aquot is an optimal solution of DECP 60 imal function r ima1 dua1 Proof By Proposition 376 we have fquot 2 6 2 WAquot Hence we have fquot WAquot 6 3 if and only if fquot 9 6 3 and 9 9Aquot Since this is exactly the equivalence stated by the proposition the result follows I The following result follows as an immediate consequence of the above proposition Corollary 378 Assume that fquot 6 6 3 Then the set of Lagrange multipliers of ECP is equal to the set of optimal solutions of DECP Proposition 379 The following statements hold a either 9 E Cm3 or 9 00 h the set of optimal solutions of DECP is closed and convex c the set of Lagrange multipliers of ECP is closed and convex Proof a We have supr w and we know that for every 3 E X at is an af ne and hence closed proper convex function It then follows from Proposition 7 that 9 E CW3E or 9 00 b The set of optimal solutions of DECP De nition 3710 The primal function corresponding to problem ECP is the function I 31 gt 3 de ned as pa inffa a e X We b o w e E Vb e are The primal function is directly related to the dual function as the following result shows Proposition 3711 For every A 6 3 we have 12A 6A Proof For every A 6 31 we have P SUMblPU infabllb has 5653 bigot n inffw w e X W b 0 w 6 En E E II bigrsefEinffwA b a E X gab 0 W E big inffac gxgw a e X gm 5 o w e inf at A 9A ISA Corollary 3712 For every 6 6 3 we have 6b chw Proof By Proposition 3711 we have 6 pM ch where the latter equality is due to Proposition 349 I The following result characterizes the dual optimal value 6 in terms of the primal function 61
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'