1 Convex Sets, And Convex Functions
1Convex Sets, and Convex FunctionsIn this section, we introduce one of the most important ideas in the theory of optimization,that of a convex set. We discuss other ideas which stem from the basic definition, andin particular, the notion of a convex function which will be important, for example, indescribing appropriate constraint sets.1.1Convex SetsIntuitively, if we think of R2 or R3 , a convex set of vectors is a set that contains all thepoints of any line segment joining two points of the set (see the next figure).PQPQFigure 2: A Non-convexSetFigure 1: A Convex SetTo be more precise, we introduce some definitions. Here, and in the following, V willalways stand for a real vector space.Definition 1.1 Let u, v V . Then the set of all convex combinations of u and v isthe set of points{wλ V : wλ (1 λ)u λv, 0 λ 1}.1(1.1)
In, say, R2 , this set is exactly the line segment joining the two points u and v. (See theexamples below.)Next, is the notion of a convex set.Definition 1.2 Let K V . Then the set K is said to be convex provided that giventwo points u, v K the set (1.1) is a subset of K.We give some simple examples:Examples 1.3(a) An interval of [a, b] R is a convex set. To see this, let c, d [a, b] and assume,without loss of generality, that c d. Let λ (0, 1). Then,a c (1 λ)c λc (1 λ)c λd (1 λ)d λd d b.(b) A disk with center (0, 0) and radius c is a convex subset of R2 . Thisp may be easilychecked by using the usual distance formula in R2 namely kx yk : (x1 y1 )2 (x2 y2 )2and the triangle inequality ku vk kuk kvk. (Exercise!)(c) In Rn the set H : {x Rn : a1 x1 . . . an xn c} is a convex set. For anyparticular choice of constants ai it is a hyperplane in Rn . Its defining equationis a generalization of the usual equation of a plane in R3 , namely the equationax by cz d 0.To see that H is a convex set, let x(1) , x(2) H and define z R3 by z : (1 λ)x(1) λx(2) . Thenz nXai [(1 (1)λ)xi (2)λxi ]nX i 1 (1 λ) c.(1)i 1nX(1)a i xi λi 1nXi 1Hence z H.2(2)a i xi(2)(1 λ)ai xi λai xi (1 λ)c λc
(d) As a generalization of the preceeding example, let A be an m n matrix, b Rm ,and let S : {(x Rn : Ax b}. (The set S is just the set of all solutions ofthe linear equation Ax b.) Then the set S is a convex subset of Rn . Indeed, letx(1) , x(2) S. Then A (1 λ)x(1) λx(2) (1 λ)A x(1) λA x(2) (1 λ)b λb b.Note: In (c) above, we can take A (a1 , a2 , . . . , an ) so that with this choice, thepresent example is certainly a generalization.We start by checking some simple properties of convex sets.A first remark is that Rn is, itself, obviously convex. Moreover, the unit ball in Rn ,namely B1 : {x Rn kxk 1} is likewise convex. This fact follows immediately fromthe triangle inequality for the norm. Specifically, we have, for arbitrary x, y B1 andλ [0, 1]k(1 λ) x λ yk (1 λ) kxk λ kyk (1 λ) λ 1 .The ball B1 is a closed set. It is easy to see that, if we take its interior nB : {x R kxk 1} ,then this set is also convex. This gives us a hint regarding our next result.Proposition 1.4 If C Rn is convex, the c (C), the closure of C, is also convex. Proof: Suppose x, y c (C). Then there exist sequences {xn } n 1 and {yn }n 1 in C suchthat xn x and yn y as n . For some λ, 0 λ 1, define zn : (1 λ) xn λ yn.Then, by convexity of C , zn C. Moreover zn (1 λ) x λ y as n . Hence thislatter point lies in c (C).2The simple example of the two intervals [0, 1] and [2, 3] on the real line shows that theunion of two sets is not necessarily convex. On the other hand, we have the result:Proposition 1.5 The intersection of any number of convex sets is convex.3
Proof: Let {Kα }α A be a family of convex sets, and let K : α A Kα . Then, for anyx, y K by definition of the intersection of a family of sets, x, y Kα for all α A andeach of these sets is convex. Hence for any α A, and λ [0, 1], (1 λ)x λy Kα .Hence (1 λ)x λy K.2Relative to the vector space operations, we have the following result:Proposition 1.6 Let C, C1 , and C2 be convex sets in Rn and let β R then(a) β C : {z Rn z βx, x C} is convex.(b) C1 C2 : {z Rn z x1 x2 , x1 C1 , x2 C2 } is convex.Proof: We leave part (a) to the reader. To check that part (b) is true, let z1 , z2 C1 C2and take 0 λ 1. We take z1 x1 x2 with x1 C1 , x2 C2 and likewise decomposez2 y1 y2 . Then(1 λ) z1 λ z2 (1 λ) [x1 x2 ] λ [y1 y2 ] [(1 λ) x1 λ y1 ] [(1 λ) x2 λ y2 ] C1 C2 ,since the sets C1 and C2 are convex.2We recall that, if A and B are two non-empty sets, then the Cartesian product of thesetwo sets A B is defined as the set of ordered pairs {(a, b) : a A, b B}. Notice thatorder does matter here and that A B 6 B A! Simple examples are1. Let A [ 1, 1], B [ 1, 1] so that A B {(x, y) : 1 x 1, 1 y 1}which is just the square centered at the origin, of side two.2. R2 itself can be identified (and we usually do!) with the Cartesian product R R.3. let C R2 be convex and let S : R C. Then S is called a right cylinder and isjust {(z, x) R3 : z 0, x C}. If, in particular C {(u, v) R2 : u2 v 2 1},then S is the usual right circulinder lying above the x, y-plane (without the bottom!).This last example shows us a situation where A B is convex. In fact it it a generalresult that if A and B are two non-empty convex sets in a vector space V , then A B islikewise a convex set in V V .Exercise 1.7 Prove this last statement.4
While, by definition, a set is convex provided all convex combinations of two points in theset is again in the set, it is a simple matter to check that we can extend this statement toinclude convex combinations of more than two points. Notice the way in which the proofis constructed; it is often very useful in computations!Proposition 1.8 Let K be a convex set and let λ1 , λ2 , . . . , λp 0 andpXλi 1. Ifi 1x1 , x2 , . . . xp K thenpXλi xi K.(1.2)i 1Proof: We prove the result by induction. Since K is convex, the result is true, trivially,for p 1 and by definition for p 2. Suppose that the proposition is true for p r(induction hypothesis!) and consider the convex combination λ1 x1 λ2 x2 . . . λr 1 xr 1 .rr 1rXXXDefine Λ : λi . Then since 1 Λ λi λi λr 1 , we havei 1i 1i 1!!rrXXλiλi xi λr 1 xr 1 Λxi (1 Λ) xr 1 .Λi 1i 1 PrPrλiλi 1 and so, by the induction hypothesis, i 1xi K. SinceNote that i 1ΛΛxr 1 K it follows that the right hand side is a convex combination of two points of Kand hence lies in K2Remark: We will also refer to combinations of the form (1.2) as convex combinationsof the p points x1 , x2 , . . . , xp .For any given set which is not convex, we often want to find a set which is convex andwhich contains the set. Since the entire vector space V is obviously a convex set, there isalways at least one such convex set containing the given one. In fact, there are infinitelymany such sets. We can make a more economical choice if we recall that the intersectionof any number of convex sets is convex.Intuitively, given a set C V , the intersection of all convex sets containing C is the“smallest” subset containing C. We make this into a definition.Definition 1.9 The convex hull of a set C is the intersection of all convex sets whichcontain the set C. We denote the convex hull by co (C).5
432101234Figure 3: The Formation of a Convex HullWe illustrate this definition in the next figure where the dotted line together with theoriginal boundaries of the set for the boundary of the convex hull.Examples 1.10(a) Suppose that [a, b] and [c, d] are two intervals of the real line with b c so that theintervals are disjoint. Then the convex hull of the set [a, b] [c, d] is just the interval[a, d].(b) In R2 consider the elliptical annular region E consisting of the disk {(x, y) R2 :x2 y 2 R for a given positive number R without the interior points of an ellipticalregion as indicated in the next figure.Clearly the set E is not convex for the line segment joining the indicated points Pand Q has points lying in the “hole” of region and hence not in E. Indeed, this is thecase for any line segment joining two points of the region which are, say, symmetricwith respect to the origin. The entire disk of radius R, however, is convex andindeed is the convex hull, co (E).These examples are typical. In each case, we see that the convex hull is obtained byadjoining all convex combinations of points in the original set. This is indeed a generalresult.6
PQFigure 4: The Elliptically Annular RegionTheorem 1.11 Let S V . Then the set of all convex combinations of points of the setS is exactly co (S).Proof: Let us denote the set of all convex combinations of p points of S by Cp (S). Thenthe set of all possible convex combinations of points of S is C(S) : p 1 Cp (S). Ifx C(S) then it is a convex combination of points of S. Since S co(S) which isconvex, it is clear from Proposition 1.8 that x co(S) and, hence C(S) co (S). To seethat the opposite inclusion holds, it is sufficient to show that C(S) is a convex set. Then,since co(S) is, by definition, the smallest convex set containing the points of S it followsthat co(S) C(S).Now to see that C(S) is indeed convex, let x, y C(S). Then for some positive integersPPp and q, and p and q-tuples {µi }pi 1 , {νj }qj 1 with p1 µi 1 and q1 νj 1, and points{x1 , x2 , . . . , xp } S and {y1 , y2 , . . . , yq } S, we havex pXµi xi , and y i 1qXνj yj .j 1Now, let λ be such that 0 λ 1 and look at the convex combination (1 λ)x λy.From the representations we have7
(1 λ) x λ ypX (1 λ)µ i xii 1 pX(1 λ) µi xi i 1! λqXj 1qXνj yj!λ νj yjj 1But we have now, a combination of p q points of S whose coefficients are all non-negativeand, moreover, for whichpX(1 λ) µi i 1qXλ νj (1 λ)j 1pXµi λi 1qXνj (1 λ) · 1 λ · 1 1 ,j 1which shows that the convex combination (1 λ)x λy C(S). Hence this latter set isconvex.2Convex sets in Rn have a very nice characterization discovered by Carathèodory.Theorem 1.12 Let S be a subset of Rn . Then every element of co (S) can be representedas a convex combination of no more than (n 1) elements of S.Proof: Let x co (S). Then we can represent x asand scalars αi 0 withmXmXαi x(i) for some vectors x(i) Si 1αi 1. Let us suppose that m is the minimal numberi 1of vectors for which such a representation of x is possible. In particular, this meansthat for all i 1, . . . , m, αi 0. If we were to have m n 1, then the vectorsx(i) x, i 1, 2, . . . , m must be linearly dependent since there are more vectors in thisset than the dimension of the space. It follows that there exist scalars λ2 , . . . , λm , at leastone of which is positive (why?) such thatmXλi (x(i) x) 0 .i 2Let µ1 : Pmi 2λi , and µi : λi , i 2, 3, . . . , m. ThenmXµi xi 0 , andi 1mXi 18µi 0 ,
while at least one of the scalars µ2 , µ3 , . . . , µm is positive.The strategy for completing the proof is to produce a convex combination of vectors thatrepresents x and which has fewer than m summands which would then contradict ourchoice of m as the minimal number of non-zero elements in the representation. To thisend, α̂i : αi γ̂µi , i 1, . . . , m, where γ̂ 0 is the largest γ such that αi γ µi 0 forPall i. Then, since mi 1 µi xi 0 we havemXα̂i xi i 1mX(αi γ̂ µi ) xii 1 mXαi xi γ̂i 1mXµ i xi i 1mXα i xi x ,i 1the last equality coming from our original representation of x. Now, the α̂i 0, at leastone is zero, andmXi 1α̂i mXi 1αi γ̂mXi 1µi mXαi 1 ,i 1the last equality coming from the choice of αi . Since at least one of the α̂i is zero, thisgives a convex representation of x in terms of fewer than m points in S which contradictsthe assumption of minimality of m.2Carathéodory’s Theorem has the nature of a representation theorem somewhat analogous to the theorem which says that any vector in a vector space can be represented asa linear combination of the elements of a basis. One thing both theorems do, is to givea finite and minimal representation of all elements of an infinite set. The drawback ofCarathéodory’s Theorem, unlike the latter representation, is that the choice of elementsused to represent the point is neither uniquely determined for that point, nor does thetheorem guarantee that the same set of vectors in C can be used to represent all vectors in C; the representing vectors will usually change with the point being represented.Nevertheless, the theorem is useful in a number of ways a we will see presently. First, acouple of examples.Examples 1.13 (a) In R, consider the interval [0, 1] and the subinterval 1 31. If we take the point x , then we have both,4 429 1 31 3,,. Then co 4 44 4
1x 2 1 53 71 113 and x .82 84 164 161So that certainly there is no uniqueness in the representation of x .2(b) In R2 we consider the two triangular regions, T1 , T2 , joining the points (0, 0), (1, 4), (2, 0), (3, 4)and (4, 0) as pictured in the next figures. The second of the figures indicates thatjoining the apexes of the triangles forms a trapezoid which is a convex set. It is theconvex hull of the set T1 T2 .44332211012304Figure 5: The Triangles T1 andT21234Figure 6: The Convex Hull ofT1 T 2Again, it is clear that two points which both lie in one of the original triangles havemore than one representation. Similarly, if we choose two points, one from T1 andone from T2 , say the points (1, 2) and (3, 2), the point 21 1 3 2222does not lie in the original set T1 T2 , but does lie in the convex hull. Moreover,this point can also be represented by10
as can easily be checked.1 2322 2 2522 The next results depend on the notion of norm in Rn and on the convergence of a sequenceof points in Rn . In particular, it relies on the fact that, in Rn , or for that matter in anycomplete metric space, Cauchy sequences converge.Recall that a set of points in Rn is called compact provided it is closed and bounded. Oneway to characterize such a set in Rn is that if C Rn is compact, then, given any sequence{x(1) , x(2) , . . . , x(n) , . . .} C there is a subsequence which converges, lim x(nk ) xo C.k As a corollary to Carathèodory’s Theorem, we have the next result about compact sets:Corollary 1.14 The convex hull of a compact set in Rn is compact.Proof: Let C Rn be compact. Notice that the simplex()nXσ : (λ1 , λ2 , . . . , λn ) Rn :λi 1i 1is also closed and bounded and is therefore compact. (Check!) Now suppose that(j){v (j) } can be written in the formj 1 co (C). By Carathèodory’s Theorem, each vv (k) n 1Xλk,i x(k,i) , where λk,i 0,i 1n 1Xλk,i 1, and x(k,i) C.i 1Then, since C and σ are compact, there exists a sequence k1 , k2 , . . . such that the limitsn 1Plim λkj ,i λi and lim x(kj ,i) x(i) exist for i 1, 2, . . . , n 1. Clearly λi 0,λi 1j j i 1and xi C.(kj ) Thus, the sequence {v (k) } }j 1 which converges to a point ofk 1 has a subsequence, {vco (C) which shows that this latter set is compact.2The next result shows that if C is closed and convex (but perhaps not bounded) is hasa smallest element in a certain sense. It is a simple result from analysis that involvesthe fact that the function x kxk is a continuous map from Rn R and the fact thatCauchy sequences in Rn converge.11
Before proving the result, however, we recall that the norm in Rn satisfies what is knownas the parallelogram law, namely that for any x, y Rn we havekx yk2 kx yk2 2 kxk2 2 kyk2 .This identity is easily proven by expanding the terms on the left in terms of the innerproduct rules. It is left as an exercise.Theorem 1.15 Every closed convex subset of Rn has a unique element of minimumnorm.Proof:Let K be such a set and note that ι : inf kxk 0 so that the function x kxkx Kis bounded below on K. Let x(1) , x(2) , . . . be a sequence of points of K such thatlim kx(i) k ι. 1 Then, by the parallelogram law, kx(i) x(j) k2 2 kx(i) k2 2 kx(j) k2 i 11 (i)14 k x(i) x(j) k2 . Since K is convex,x x(j) K so that k x(i) x(j) k ι.222Hencekx(i) x(j) k2 2 kx(i) k2 2 kx(j) k2 4 ι2 .As i, j , we have 2 kx(i) k2 2 kx(j) k2 4 ι 0. Thus, {x(j) } j 1 is a Cauchy sequenceand has a limit point x. Since K is closed, x K. Moreover, since the function x kxkis a continuous function from Rn R,ι lim kx(j) k kxk.j In order to show uniqueness of the point with minimal norm, suppose that there were twopoints, x, y K, x 6 y such that kxk kyk ι. Then by the parallelogram law,0 1kx yk2 2 kxk2 2 kyk2 4 k (x y) k2212 ι2 2 ι2 4 k (x y) k2211so that 4 ι2 4 k (x y) k2 or k (x y) k ι which would give a vector in K of norm22less than the infimum ι.21Here, and throughout this course, we shall call such a sequence a minimizing sequence.12
Example 1.16 It is easy to illustrate the statement of this last theorem in a concretecase. Suppose that we define three sets in R2 by H1 : {(x, y) R2 : 5x y 1}, H2 : {(x, y) R2 : 2x 4y 7} and H3 : {(x, y) R2 : 2x 2y 6} whose intersection(the intersection of half-spaces) forms a convex set illustrated below. The point of minimalnorm is the closest point in this set to the origin. From the projection theorem in R 2 ,that point is determined by the intersection of the boundary line 2x 4y 7 with a lineperpendicular to it and which passes through the origin as illustrated 2 0.4 0.6 0.81 1.2 1.4 1.6 1.8x202.2 2.4Figure 7: The Convex Set1.20.2 0.4 0.6 0.81 1.2 1.4 1.6 1.8x22.2 2.4Figure 8: The Point of MinimalNormSeparation PropertiesThere are a number of results which are of crucial importance in the theory of convexsets, and in the theory of mathematical optimization, particularly with regard to thedevelopment of necessary conditions, as for example in the theory of Lagrange multipliers.These results are usually lumped together under the rubric of separation theorems. Wediscuss two of these results which will be useful to us. We will confine our attention tothe finite dimensional case.22In a general inner product space or in Hilbert space the basic theorem is called the Hahn-Banachtheorem and is one of the central results of functional analysis.13
The idea goes back to the idea of describing a circle in the plane by the set of all tangentlines to points on the boundary of the circle.Figure 9: The Circle with Supporting HyperplanesOur proof of the Separation Theorem (and its corollaries) depends on the idea of theprojection of a point onto a convex set. We begin by proving that result.The statement of the Projection Theorem is as follows:Theorem 1.17 Let C Rn be a closed, convex set. Then(a) For every x Rn there exists a unique vector z ? C that minimizes kz xk overall z C. We call z ? the projection of x onto C.(b) z ? is the projection of x onto C if and only ifhy z ? , x z ? i 0, for all y C .Proof: Fix x Rn and let w C. Then minimizing kx zk over all z C is equivalentto minimizing the same function over the set {z C : kx zk kx wk}. This latterset is both closed and bounded and therefore the continuous function g(z) : kz xk,according to the theorem of Weierstrass, takes on its minimum at some point of the set.We use the paralellogram identity to prove uniqueness as follows. Suppose that there aretwo distinct points, z1 and z2, which both minimize kz xk and denote this minimum byι. Then we have14
10 k(z1 x) (z2 x)k 2 kz1 xk 2 kz2 xk 4 [(z1 x) (z2 x)]22 2z1 z 22 kz1 xk 2 kz2 xk 4 x222222 2 ι2 2 ι2 4 kẑ xk2 ,where ẑ (z1 z2 )/2 C since C
Proof:Let us denote the set of all convex combinations of ppoints of Sby Cp(S). Then the set of all possible convex combinations of points of S is C(S) : [1 p 1Cp(S). If x2 C(S) then it is a convex com
Convex obj non-convex domain. Introduction Generic Problem: min Q(x); s:t: x 2F; Q(x) convex, especially: convex quadratic F nonconvex Examples: F is a mixed-integer set F is constrained in a nasty way, e.g. x 1 3 sin(x 2) 2cos(x 3) 4 Bienstock, Michalka Columbia Convex obj non-convex domain.
Solution. We prove the rst part. The intersection of two convex sets is convex. There-fore if Sis a convex set, the intersection of Swith a line is convex. Conversely, suppose the intersection of Swith any line is convex. Take any two distinct points x1 and x2 2 S. The intersection of Swith the line through x1 and x2 is convex.
What is convex projective geometry? Motivation from hyperbolic geometry Nice Properties of Hyperbolic Space Convex: Intersection with projective lines is connected. Properly Convex: Convex and closure is contained in an affine patch ()Disjoint from some projective hyperplane. Strictly Convex: Properly convex and boundary contains
3 convex-convex n [DK85] convex-convex (n;lognp lognq) [DK90] INTERSECTION DETECTION OF CONVEX POLYGONS Perhaps the most easily understood example of how the structure of geometric objects can be exploited to yield an e cient intersection test is that of detecting the intersection of two convex polygons. There are a number of solutions to this .
Has feasible directions at any point A polyhedral convex set is characterized in terms of a finite set of extreme points and extreme directions A real-valued convex function is continuous and has nice differentiability properties Closed convex cones are self-dual with respect to polarity Convex, lower semicontinuous .
3.4.0.0.4), make convex optimization tractable. Similarly, the problem maximize X g(X) subject to X D (686) is called convex were g a real concave function and feasible set D convex. As conversion to convex form is not always possible, there is much ongoing research to determine which problem class
Convex optimization – Boyd & Vandenberghe Nonlinear programming – Bertsekas Convex Analysis – Rockafellar Fundamentals of convex analysis – Urruty, Lemarechal Lectures on modern convex optimization – Nemirovski Optimization for Machine Learning – Sra, Nowozin, Wright Theory of Convex Optimization for Machine Learning – Bubeck .
Abrasive Water Jet Machining (AWJM) is the non-traditional material removal process. It is an effective machining process for processing a variety of Hard and Brittle Material. And has various unique advantages over the other non-traditional cutting process like high machining versatility, minimum stresses on the work piece, high flexibility no thermal distortion, and small cutting forces .
