WIXLIB

xiPrefaceSome geometric properties of convex sets and, to a lesser extent, of convex functions hadbeen studied before the 1960s by many outstanding mathematicians, first of all by HermannMinkowski and Werner Fenchel. At the beginning of the 1960s convex analysis was greatly developed in the works of R. Tyrrell Rockafellar and Jean-Jacques Moreau who initiated a systematicstudy of this new field. As a fundamental part of variational analysis, convex analysis contains ageneralized differentiation theory that can be used to study a large class of mathematical models with no differentiability assumptions imposed on their initial data. e importance of convexanalysis for many applications in which convex optimization is the first to name has been wellrecognized. e presence of convexity makes it possible not only to comprehensively investigatequalitative properties of optimal solutions and derive necessary and sufficient conditions for optimality but also to develop effective numerical algorithms to solve convex optimization problems,even with nondifferentiable data. Convex analysis and optimization have an increasing impacton many areas of mathematics and applications including control systems, estimation and signalprocessing, communications and networks, electronic circuit design, data analysis and modeling,statistics, economics and finance, etc. ere are several fundamental books devoted to different aspects of convex analysis andoptimization. Among them we mention “Convex Analysis” by Rockafellar [26], “Convex Analysisand Minimization Algorithms” (in two volumes) by Hiriart-Urruty and Lemaréchal [8] and itsabridge version [9], “Convex Analysis and Nonlinear Optimization” by Borwein and Lewis [4],“Introductory Lectures on Convex Optimization” by Nesterov [21], and “Convex Optimization”by Boyd and Vandenberghe [3] as well as other books listed in the bibliography below.In this big picture of convex analysis and optimization, our book serves as a bridge forstudents and researchers who have just started using convex analysis to reach deeper topics in thefield. We give detailed proofs for most of the results presented in the book and also include manyfigures and exercises for better understanding the material. e powerful geometric approachdeveloped in modern variational analysis is adopted and simplified in the convex case in orderto provide the reader with an easy path to access generalized differentiation of convex objects infinite dimensions. In this way, the book also serves as a starting point for the interested reader tocontinue the study of nonconvex variational analysis and applications. It can be of interest fromthis viewpoint to experts in convex and variational analysis. Finally, the application part of thisbook not only concerns the classical topics of convex optimization related to optimality conditionsand subgradient algorithms but also presents some recent while easily understandable qualitativeand numerical results for important location problems.

xiiPREFACE e book consists of four chapters and is organized as follows. In Chapter 1 we studyfundamental properties of convex sets and functions while paying particular attention to classesof convex functions important in optimization. Chapter 2 is mainly devoted to developing basiccalculus rules for normals to convex sets and subgradients of convex functions that are in themainstream of convex theory. Chapter 3 concerns some additional topics of convex analysis thatare largely used in applications. Chapter 4 is fully devoted to applications of basic results of convexanalysis to problems of convex optimization and selected location problems considered from bothqualitative and numerical viewpoints. Finally, we present at the end of the book Solutions andHints to selected exercises.Exercises are given at the end of each chapter while figures and examples are providedthroughout the whole text. e list of references contains books and selected papers, which areclosely related to the topics considered in the book and may be helpful to the reader for advancedstudies of convex analysis, its applications, and further extensions.Since only elementary knowledge in linear algebra and basic calculus is required, this bookcan be used as a textbook for both undergraduate and graduate level courses in convex analysis andits applications. In fact, the authors have used these lecture notes for teaching such classes in theiruniversities as well as while visiting some other schools. We hope that the book will make convexanalysis more accessible to large groups of undergraduate and graduate students, researchers indifferent disciplines, and practitioners.Boris S. Mordukhovich and Nguyen Mau NamDecember 2013

xiiiAcknowledgments e first author acknowledges continued support by grants from the National Science Foundationand the second author acknowledges support by the Simons Foundation.Boris S. Mordukhovich and Nguyen Mau NamDecember 2013

xvList of SymbolsRR D . 1; 1 RCR Nco aff int ri span cone K dim bd IBIB.xIN r/dom fepi fgph FLŒa; b d.xI / .xI /hx; yiA N.xIN /ker AD F .x;N y/NT .xIN /F1T FL.x; / Fthe real numbersthe extended real linethe nonnegative real numbersthe positive real numbersthe positive integersconvex hull of affine hull of interior of relative interior of linear subspace generated by cone generated by convex cone generated by dimension of closure of boundary of closed unit ballclosed ball with center xN and radius rdomain of fepigraph of fgraph of mapping Fline connecting a and bdistance from x to projection of x to inner product of x and yadjoint/transpose of linear mapping/matrix Anormal cone to at xNkernel of linear mapping Acoderivative to F at .x;N y/Ntangent cone to at xNhorizon/asymptotic cone of Fminimal time function defined by constant dynamic F and target set LagrangianMinkowski gauge of F

xviLIST OF SYMBOLS F . I /GF .x;N t/generalized projection defined by the minimal time functiongeneralized ball defined by dynamic F with center xN and radius t

1CHAPTER1Convex Sets and Functions is chapter presents definitions, examples, and basic properties of convex sets and functions inthe Euclidean space Rn and also contains some related material.1.1PRELIMINARIESWe start with reviewing classical notions and properties of the Euclidean space Rn . e proofsof the results presented in this section can be found in standard books on advanced calculus andlinear algebra.Let us denote by Rn the set of all n tuples of real numbers x D .x1 ; : : : ; xn /. en Rn isa linear space with the following operations:.x1 ; : : : ; xn / C .y1 ; : : : ; yn / D .x1 C y1 ; : : : ; xn C yn /; .x1 ; : : : ; xn / D . x1 ; : : : ; xn /;where .x1 ; : : : ; xn /; .y1 ; : : : ; yn / 2 Rn and 2 R. e zero element of Rn and the number zeroof R are often denoted by the same notation 0 if no confusion arises.For any x D .x1 ; : : : ; xn / 2 Rn , we identify it with the column vector x D Œx1 ; : : : ; xn T ,where the symbol “T ” stands for vector transposition. Given x D .x1 ; : : : ; xn / 2 Rn and y D.y1 ; : : : ; yn / 2 Rn , the inner product of x and y is defined byhx; yi WDnXx i yi :iD1 e following proposition lists some important properties of the inner product in Rn .Proposition 1.1For x; y; z 2 Rn and 2 R, we have:(i) hx; xi 0, and hx; xi D 0 if and only if x D 0.(ii) hx; yi D hy; xi.(iii) h x; yi D hx; yi.(iv) hx; y C zi D hx; yi C hx; zi. e Euclidean norm of x D .x1 ; : : : ; xn / 2 Rn is defined byqkxk WD x12 C : : : C xn2 :

21. CONVEX SETS AND FUNCTIONSIt follows directly from the definition that kxk DProposition 1.2phx; xi.For any x; y 2 Rn and 2 R, we have:(i) kxk 0, and kxk D 0 if and only if x D 0.(ii) k xk D j j kxk.(iii) kx C yk kxk C kyk .the triangle inequality/.(iv) jhx; yij kxk kyk .the Cauchy-Schwarz inequality/.Using the Euclidean norm allows us to introduce the balls in Rn , which can be used todefine other topological notions in Rn . e centered at xN with radius r 0 and the of Rnare defined, respectively, byˇˇ IB.xIN r/ WD x 2 Rn ˇ kx xkN r and IB WD x 2 Rn ˇ kxk 1 :Definition 1.3It is easy to see that IB D IB.0I 1/ and IB.xIN r/ D xN C rIB .Definition 1.4Let Rn . en xN is an of if there is ı 0 such thatIB.xIN ı/ : e set of all interior points of is denoted by int . Moreover, is said to be if every point of is its interior point.We get that is open if and only if for every xN 2 there is ı 0 such that IB.xIN ı/ .nIt is obvious that the empty set ; and the whole space R are open. Furthermore, any open ballB.xIN r/ WD fx 2 Rn j kx xkN rg centered at xN with radius r is open.Definition 1.5A set Rn is if its complement c D Rn n is open in Rn .It follows that the empty set, the whole space, and any ball IB.xIN r/ are closed in Rn .Proposition 1.6(i) e union of any collection of open sets in Rn is open.(ii) e intersection of any finite collection of open sets in Rn is open.(iii) e intersection of any collection of closed sets in Rn is closed.(iv) e union of any finite collection of closed sets in Rn is closed.Definition 1.7 Let fxk g be a sequence in Rn . We say that fxk g to xN ifkxk xkN ! 0 as k ! 1. In this case we writelim xk D x:Nk!1

1.1. PRELIMINARIES is notion allows us to define the following important topological concepts for sets.Definition 1.8Let be a nonempty subset of Rn . en:(i) e of , denoted by or cl , is the collection of limits of all convergent sequences belonging to .(ii) e of , denoted by bd , is the set n int .We can see that the closure of is the intersection of all closed sets containing and thatthe interior of is the union of all open sets contained in . It follows from the definition thatxN 2 if and only if for any ı 0 we have IB.xIN ı/ \ ;. Furthermore, xN 2 bd if and onlyif for any ı 0 the closed ball IB.xIN / intersects both sets and its complement c .Let fxk g be a sequence in Rn and let fk g be a strictly increasing sequence of positiveintegers. en the new sequence fxk g is called a of fxk g.Definition 1.9We say that a set is bounded if it is contained in a ball centered at the origin with someradius r 0, i.e., IB.0I r/. us a sequence fxk g is bounded if there is r 0 withkxk k r for all k 2 N : e following important result is known as the Bolzano-Weierstrass theorem. eorem 1.10Any bounded sequence in Rn contains a convergent subsequence. e next concept plays a very significant role in analysis and optimization.We say that a set is in Rn if every sequence in contains a subsequenceconverging to some point in .Definition 1.11 e following result is a consequence of the Bolzano-Weierstrass theorem. eorem 1.12A subset of Rn is compact if and only if it is closed and bounded.For subsets , 1 , and 2 of Rn and for 2 R, we define the operations:ˇ ˇ 1 C 2 WD x C y ˇ x 2 1 ; y 2 2 ; WD x ˇ x 2 : e next proposition can be proved easily.Proposition 1.13Let 1 and 2 be two subsets of Rn .(i) If 1 is open or 2 is open, then 1 C 2 is open.(ii) If 1 is closed and 2 is compact, then 2 C 2 is closed.3

41. CONVEX SETS AND FUNCTIONSRecall now the notions of bounds for subsets of the real line.Definition 1.14haveLet D be a subset of the real line. A number m 2 R is a of D if wex m for all x 2 D:If the set D has a lower bound, then it is . Similarly, a number M 2 R is an of D ifx M for all x 2 D;and D is if it has an upper bound. Furthermore, we say that the set D is if it is simultaneously bounded below and above.Now we are ready to define the concepts of infimum and supremum of sets.Let D R be nonempty and bounded below. e infimum of D , denoted by inf D ,is the greatest lower bound of D . When D is nonempty and bounded above, its supremum, denoted bysup D , is the least upper bound of D . If D is not bounded below .resp. above/, then we set inf D WD 1.resp. sup D WD 1/. We also use the convention that inf ; WD 1 and sup ; WD 1.Definition 1.15 e following fundamental axiom ensures that these notions are well-defined.Completeness Axiom. For every nonempty subset D of R that is bounded above, the least upper boundof D exists as a real number.Using the Completeness Axiom, it is easy to see that if a nonempty set is bounded below,then its greatest lower bound exists as a real number. roughout the book we consider for convenience extended-real-valued functions, whichtake values in R WD . 1; 1 . e usual conventions of extended arithmetics are that a C 1 D1 for any a 2 R, 1 C 1 D 1, and t 1 D 1 for t 0.Definition 1.16 Let f W ! R be an extended-real-valued function and let xN 2 with f .x/N 1. en f is at xN if for any 0 there is ı 0 such thatjf .x/f .x/jN whenever kxxkN ı; x 2 :We say that f is continuous on if it is continuous at every point of .It is obvious from the definition that if f W ! R is continuous at xN (with f .x/N 1),then it is finite on the intersection of and a ball centered at xN with some radius r 0. FurtherN 1) if and only if for every sequence fxk g in more, f W ! R is continuous at xN (with f .x/converging to xN the sequence ff .xk /g converges to f .x/N .

1.2. CONVEX SETSDefinition 1.17 Let f W ! R and let xN 2 with f .x/N 1. We say that f has a at xN relative to if there is ı 0 such thatf .x/ f .x/N for all x 2 IB.xIN ı/ \ :We also say that f has a / at xN relative to iff .x/ f .x/N for all x 2 : e notions of local and global maxima can be defined similarly.Finally in this section, we formulate a fundamental result of mathematical analysis andoptimization known as the Weierstrass existence theorem. eorem 1.18 Let f W ! R be a continuous function, where is a nonempty, compact subsetof Rn . en there exist xN 2 and uN 2 such thatˇ f .x/N D inf f .x/ ˇ x 2 ˇ and f .u/N D sup f .x/ ˇ x 2 :In Section 4.1 we present some “unilateral” versions of eorem 1.18.1.2CONVEX SETSWe start the study of convexity with sets and then proceed to functions. Geometric ideas playan underlying role in convex analysis, its extensions, and applications. us we implement thegeometric approach in this book.Given two elements a and b in Rn , define the interval/line segmentˇ Œa; b WD a C .1 /b ˇ 2 Œ0; 1 :Note that if a D b , then this interval reduces to a singleton Œa; b D fag.Definition 1.19 A subset of Rn is if Œa; b whenever a; b 2 . Equivalently, isconvex if a C .1 /b 2 for all a; b 2 and 2 Œ0; 1 .PPmGiven !1 ; : : : ; !m 2 Rn , the element x D miD1 i !i , whereiD1 i D 1 and i 0 forsome m 2 N , is called a convex combination of !1 ; : : : ; !m .Proposition 1.20elements.A subset of Rn is convex if and only if it contains all convex combinations of its5

61. CONVEX SETS AND FUNCTIONSFigure 1.1: Convex set and nonconvex set.Proof. e sufficient condition is trivial. To justify the necessity, we show by induction that anyPconvex combination x D miD1 i !i of elements in is an element of . is conclusion followsdirectly from the definition for m D 1; 2. Fix now a positive integer m 2 and suppose that everyconvex combination of k 2 N elements from , where k m, belongs to . Form the convexcombinationmC1mC1XXy WD i !i ; i D 1; i 0iD1iD1and observe that if mC1 D 1, then 1 D 2 D : : : D m D 0, so y D !mC1 2 . In the casewhere mC1 1 we get the representationsmXiD1 i D 1 mC1 andmXiD11 iD 1; mC1which imply in turn the inclusionz WDmXiD11 i!i 2 : mC1It yields therefore the relationshipsy D .1 mC1 /mXiD11 i!i C mC1 !mC1 D .1 mC1and thus completes the proof of the proposition. mC1 /z C mC1 !mC1 2 Let 1 be a convex subset of Rn and let 2 be a convex subset of Rp . en theCartesian product 1 2 is a convex subset of Rn Rp .Proposition 1.21

1.2. CONVEX SETSProof. Fix a D .a1 ; a2 /; b D .b1 ; b2 / 2 1 2 , and 2 .0; 1/. en we have a1 ; b1 2 1 anda2 ; b2 2 2 . e convexity of 1 and 2 gives us ai C .1 /bi 2 i for i D 1; 2;which implies therefore that a C .1 /b D a1 C .1 /b1 ; a2 C .1 /b2 2 1 2 : us the Cartesian product 1 2 is convex. Let us continue with the definition of affine mappings.Definition 1.22 A mapping B W Rn ! Rp is if there exist a linear mapping A W Rn ! Rpand an element b 2 Rp such that B.x/ D A.x/ C b for all x 2 Rn .Every linear mapping is affine. Moreover, B W Rn ! Rp is affine if and only ifB. x C .1 /y/ D B.x/ C .1 /B.y/ for all x; y 2 Rn and 2 R :Now we show that set convexity is preserved under affine operations.Proposition 1.23 Let B W Rn ! Rp be an affine mapping. Suppose that is a convex subset of Rnand is a convex subset of Rp . en B. / is a convex subset of Rp and B 1 . / is a convex subsetof Rn .Proof. Fix any a; b 2 B. / and 2 .0; 1/. en a D B.x/ and b D B.y/ for x; y 2 . Since is convex, we have x C .1 /y 2 . en a C .1 /b D B.x/ C .1 /B.y/ D B. x C .1 /y/ 2 B. /;which justifies the convexity of the image B. /.Taking now any x; y 2 B 1 . / and 2 .0; 1/, we get B.x/; B.y/ 2 . is gives us B.x/ C .1 /B.y/ D B x C .1 /y 2 by the convexity of . us we have x C .1the inverse image B 1 . /. /y 2 B1. /, which verifies the convexity of Let 1 ; 2 Rn be convex and let 2 R. en both sets 1 C 2 and 1are also convex in Rn .Proposition 1.24Proof. It follows directly from the definitions. 7

81. CONVEX SETS AND FUNCTIONSNext we proceed with intersections of convex sets.Proposition 1.25subset of Rn .Let f g 2I be a collection of convex subsets of Rn . enT 2I is also a convexTProof. Taking any a; b 2 2I , we get that a; b 2 for all 2 I . e convexity of eachT ensures that a C .1 /b 2 for any 2 .0; 1/. us a C .1 /b 2 2I andTthe intersection 2I is convex. Definition 1.26Let be a subset of Rn . e of is defined byo\ n ˇˇC ˇ C is convex and C :co WD e next proposition follows directly from the definition and Proposition 1.25.Figure 1.2: Nonconvex set and its convex hull.Proposition 1.27 e convex hull co is the smallest convex set containing .Proof. e convexity of the set co follows from Proposition 1.25. On the other hand, forany convex set C that contains we clearly have co C , which veri

An Easy Path to Convex Analysis and Applications Boris S. Mordukhovich, Wayne State University Nguyen Mau Nam, Portland State University Convex optimization has an increasing impact on many areas of mathematics, applied sciences, and practical applications. It is now being taught at many universities and being used by researchers of different .