# Convex sets and their Applications

###### convex sets and their properties and their applications pdf, how to prove convex sets, what are convex sets, what convex sets are contained in the set of hyperbolic polynomials
Prof.WilliamsHibbs,United States,Teacher
Published Date:27-07-2017
Your Website URL(Optional)
Comment
Chapter 2 Convex sets 2.1 Aﬃne and convex sets 2.1.1 Lines and line segments n Suppose x = 6 x are two points in R . Points of the form 1 2 y =θx +(1−θ)x , 1 2 whereθ∈R, form the line passing throughx andx . The parameter valueθ = 0 1 2 corresponds to y = x , and the parameter value θ = 1 corresponds to y = x . 2 1 Values of the parameterθ between 0 and 1 correspond to the (closed) line segment between x and x . 1 2 Expressing y in the form y =x +θ(x −x ) 2 1 2 gives another interpretation: y is the sum of the base point x (corresponding 2 to θ = 0) and the direction x −x (which points from x to x ) scaled by the 1 2 2 1 parameter θ. Thus, θ gives the fraction of the way from x to x where y lies. As 2 1 θ increases from 0 to 1, the pointy moves fromx tox ; forθ 1, the pointy lies 2 1 on the line beyond x . This is illustrated in ﬁgure 2.1. 1 2.1.2 Aﬃne sets n A set C ⊆ R is aﬃne if the line through any two distinct points in C lies in C, i.e., if for anyx , x ∈C andθ∈R, we haveθx +(1−θ)x ∈C. In other words, 1 2 1 2 C contains the linear combination of any two points inC, provided the coeﬃcients in the linear combination sum to one. This idea can be generalized to more than two points. We refer to a point of the form θ x +···+θ x , where θ +···+θ = 1, as an aﬃne combination 1 1 k k 1 k of the points x , ..., x . Using induction from the deﬁnition of aﬃne set (i.e., 1 k that it contains every aﬃne combination of two points in it), it can be shown that22 2 Convex sets θ = 1.2 x 1 θ = 1 θ = 0.6 x 2 θ = 0 θ =−0.2 Figure 2.1 The line passing through x and x is described parametrically 1 2 byθx +(1−θ)x , whereθ varies overR. The line segment betweenx and 1 2 1 x , which corresponds to θ between 0 and 1, is shown darker. 2 an aﬃne set contains every aﬃne combination of its points: If C is an aﬃne set, x ,...,x ∈C, andθ +···+θ = 1, then the pointθ x +···+θ x also belongs 1 k 1 k 1 1 k k to C. If C is an aﬃne set and x ∈C, then the set 0 V =C−x =x−x x∈C 0 0 isasubspace,i.e.,closedundersumsandscalarmultiplication. Toseethis,suppose v , v ∈V and α, β∈R. Then we have v +x ∈C and v +x ∈C, and so 1 2 1 0 2 0 αv +βv +x =α(v +x )+β(v +x )+(1−α−β)x ∈C, 1 2 0 1 0 2 0 0 since C is aﬃne, and α+β +(1−α−β) = 1. We conclude that αv +βv ∈V, 1 2 since αv +βv +x ∈C. 1 2 0 Thus, the aﬃne set C can be expressed as C =V +x =v+x v∈V, 0 0 i.e., as a subspace plus an oﬀset. The subspace V associated with the aﬃne set C does not depend on the choice of x , so x can be chosen as any point in C. We 0 0 deﬁnethedimension ofanaﬃnesetC asthedimensionofthesubspaceV =C−x , 0 where x is any element of C. 0 Example 2.1 Solution set of linear equations. The solution set of a system of linear m×n m equations, C = x Ax = b, where A ∈ R and b ∈ R , is an aﬃne set. To show this, suppose x , x ∈C, i.e., Ax =b, Ax =b. Then for any θ, we have 1 2 1 2 A(θx +(1−θ)x ) = θAx +(1−θ)Ax 1 2 1 2 = θb+(1−θ)b = b, which shows that the aﬃne combination θx +(1−θ)x is also in C. The subspace 1 2 associated with the aﬃne set C is the nullspace of A. We also have a converse: every aﬃne set can be expressed as the solution set of a system of linear equations.2.1 Aﬃne and convex sets 23 n The set of all aﬃne combinations of points in some set C ⊆ R is called the aﬃne hull of C, and denoted aﬀC: aﬀC =θ x +···+θ x x ,...,x ∈C, θ +···+θ = 1. 1 1 k k 1 k 1 k The aﬃne hull is the smallest aﬃne set that contains C, in the following sense: if S is any aﬃne set with C ⊆S, then aﬀC ⊆S. 2.1.3 Aﬃne dimension and relative interior We deﬁne the aﬃne dimension of a setC as the dimension of its aﬃne hull. Aﬃne dimension is useful in the context of convex analysis and optimization, but is not always consistent with other deﬁnitions of dimension. As an example consider the 2 2 2 2 2 unit circle in R , i.e., x ∈ R x +x = 1. Its aﬃne hull is all of R , so its 1 2 aﬃne dimension is two. By most deﬁnitions of dimension, however, the unit circle 2 in R has dimension one. n If the aﬃne dimension of a set C ⊆ R is less than n, then the set lies in n the aﬃne set aﬀC 6= R . We deﬁne the relative interior of the set C, denoted relintC, as its interior relative to aﬀC: relintC =x∈C B(x,r)∩aﬀC ⊆C for some r 0, where B(x,r) =y ky−xk≤ r, the ball of radius r and center x in the norm k·k. (Here k·k is any norm; all norms deﬁne the same relative interior.) We can then deﬁne the relative boundary of a set C as clC\relintC, where clC is the closure of C. 3 Example 2.2 Consider a square in the (x ,x )-plane in R , deﬁned as 1 2 3 C =x∈R −1≤x ≤1, −1≤x ≤1, x =0. 1 2 3 3 Its aﬃne hull is the (x ,x )-plane, i.e., aﬀC =x∈R x =0. The interior of C 1 2 3 is empty, but the relative interior is 3 relintC =x∈R −1x 1, −1x 1, x =0. 1 2 3 3 Its boundary (in R ) is itself; its relative boundary is the wire-frame outline, 3 x∈R maxx ,x =1, x =0. 1 2 3 2.1.4 Convex sets A set C is convex if the line segment between any two points in C lies in C, i.e., if for any x , x ∈C and any θ with 0≤θ≤ 1, we have 1 2 θx +(1−θ)x ∈C. 1 224 2 Convex sets Figure 2.2 Some simple convex and nonconvex sets. Left. The hexagon, which includes its boundary (shown darker), is convex. Middle. The kidney shaped set is not convex, since the line segment between the two points in thesetshownasdotsisnotcontainedintheset. Right. Thesquarecontains some boundary points but not others, and is not convex. 2 Figure 2.3 The convex hulls of two sets in R . Left. The convex hull of a set of ﬁfteen points (shown as dots) is the pentagon (shown shaded). Right. The convex hull of the kidney shaped set in ﬁgure 2.2 is the shaded set. Roughlyspeaking,asetisconvexifeverypointinthesetcanbeseenbyeveryother point, along an unobstructed straight path between them, where unobstructed means lying in the set. Every aﬃne set is also convex, since it contains the entire line between any two distinct points in it, and therefore also the line segment between the points. Figure 2.2 illustrates some simple convex and nonconvex sets 2 in R . We call a point of the form θ x +··· +θ x , where θ +··· +θ = 1 and 1 1 k k 1 k θ ≥ 0, i = 1,...,k, a convex combination of the points x , ..., x . As with aﬃne i 1 k sets, it can be shown that a set is convex if and only if it contains every convex combination of its points. A convex combination of points can be thought of as a mixture or weighted average of the points, withθ the fraction ofx in the mixture. i i Theconvexhull ofasetC,denotedconvC,isthesetofallconvexcombinations of points in C: convC =θ x +···+θ x x ∈C, θ ≥ 0, i= 1,...,k, θ +···+θ = 1. 1 1 k k i i 1 k As the name suggests, the convex hull convC is always convex. It is the smallest convex set that containsC: IfB is any convex set that containsC, thenconvC ⊆ B. Figure 2.3 illustrates the deﬁnition of convex hull. Theideaofaconvexcombinationcanbegeneralizedtoincludeinﬁnitesums,in- tegrals, and, in the most general form, probability distributions. Supposeθ ,θ ,... 1 22.1 Aﬃne and convex sets 25 satisfy ∞ X θ ≥ 0, i = 1,2,..., θ = 1, i i i=1 n and x ,x ,...∈C, where C ⊆R is convex. Then 1 2 ∞ X θ x ∈C, i i i=1 n if the series converges. More generally, suppose p : R → R satisﬁes p(x)≥ 0 for R n all x∈C and p(x)dx = 1, where C ⊆R is convex. Then C Z p(x)xdx∈C, C if the integral exists. n In the most general form, suppose C ⊆R is convex and x is a random vector with x ∈ C with probability one. Then Ex ∈ C. Indeed, this form includes all the others as special cases. For example, suppose the random variablex only takes on the two values x and x , with prob(x =x ) =θ and prob(x =x ) = 1−θ, 1 2 1 2 where 0≤θ≤ 1. Then Ex =θx +(1−θ)x , and we are back to a simple convex 1 2 combination of two points. 2.1.5 Cones A setC is called a cone, or nonnegative homogeneous, if for everyx∈C andθ≥ 0 we have θx∈C. A set C is a convex cone if it is convex and a cone, which means that for any x , x ∈C and θ , θ ≥ 0, we have 1 2 1 2 θ x +θ x ∈C. 1 1 2 2 Points of this form can be described geometrically as forming the two-dimensional pie slice with apex 0 and edges passing through x and x . (See ﬁgure 2.4.) 1 2 A point of the form θ x +··· +θ x with θ ,...,θ ≥ 0 is called a conic 1 1 k k 1 k combination (or a nonnegative linear combination) of x ,...,x . If x are in a 1 k i convex cone C, then every conic combination of x is in C. Conversely, a set C is i a convex cone if and only if it contains all conic combinations of its elements. Like convex (or aﬃne) combinations, the idea of conic combination can be generalized to inﬁnite sums and integrals. The conic hull of a setC is the set of all conic combinations of points inC, i.e., θ x +···+θ x x ∈C, θ ≥ 0, i = 1,...,k, 1 1 k k i i which is also the smallest convex cone that contains C (see ﬁgure 2.5).26 2 Convex sets x 1 x 2 0 Figure 2.4 The pie slice shows all points of the form θ x +θ x , where 1 1 2 2 θ , θ ≥ 0. The apex of the slice (which corresponds to θ = θ = 0) is at 1 2 1 2 0; its edges (which correspond to θ = 0 or θ = 0) pass through the points 1 2 x and x . 1 2 0 0 Figure 2.5 The conic hulls (shown shaded) of the two sets of ﬁgure 2.3.2.2 Some important examples 27 2.2 Some important examples In this section we describe some important examples of convex sets which we will encounter throughout the rest of the book. We start with some simple examples. • The empty set∅, any single point (i.e., singleton)x , and the whole space 0 n n R are aﬃne (hence, convex) subsets of R . • Any line is aﬃne. If it passes through zero, it is a subspace, hence also a convex cone. • A line segment is convex, but not aﬃne (unless it reduces to a point). • A ray, which has the formx +θvθ≥ 0, wherev = 6 0, is convex, but not 0 aﬃne. It is a convex cone if its base x is 0. 0 • Any subspace is aﬃne, and a convex cone (hence convex). 2.2.1 Hyperplanes and halfspaces A hyperplane is a set of the form T xa x =b, n where a∈R , a6= 0, and b∈R. Analytically it is the solution set of a nontrivial linear equation among the components of x (and hence an aﬃne set). Geometri- T cally, the hyperplane xa x =b can be interpreted as the set of points with a constant inner product to a given vector a, or as a hyperplane with normal vector a; the constantb∈R determines the oﬀset of the hyperplane from the origin. This geometric interpretation can be understood by expressing the hyperplane in the form T xa (x−x ) = 0, 0 T where x is any point in the hyperplane (i.e., any point that satisﬁes a x = b). 0 0 This representation can in turn be expressed as T ⊥ xa (x−x ) = 0=x +a , 0 0 ⊥ where a denotes the orthogonal complement of a, i.e., the set of all vectors or- thogonal to it: ⊥ T a =va v = 0. This shows that the hyperplane consists of an oﬀset x , plus all vectors orthog- 0 onal to the (normal) vector a. These geometric interpretations are illustrated in ﬁgure 2.6. n A hyperplane divides R into two halfspaces. A (closed) halfspace is a set of the form T xa x≤b, (2.1) where a = 6 0, i.e., the solution set of one (nontrivial) linear inequality. Halfspaces are convex, but not aﬃne. This is illustrated in ﬁgure 2.7.28 2 Convex sets a x 0 x T a x =b 2 Figure 2.6 Hyperplane in R , with normal vector a and a point x in the 0 hyperplane. For any pointx in the hyperplane,x−x (shown as the darker 0 arrow) is orthogonal to a. a T a x≥b x 0 T a x≤b T 2 Figure2.7Ahyperplanedeﬁnedbya x=binR determinestwohalfspaces. T Thehalfspacedeterminedbya x≥b(notshaded)isthehalfspaceextending T in the direction a. The halfspace determined by a x ≤ b (which is shown shaded) extends in the direction−a. The vectora is the outward normal of this halfspace.2.2 Some important examples 29 x 1 a x 0 x 2 T Figure 2.8 The shaded set is the halfspace determined by a (x−x )≤ 0. 0 Thevectorx −x makesanacuteanglewitha, sox isnotinthehalfspace. 1 0 1 The vectorx −x makes an obtuse angle witha, and so is in the halfspace. 2 0 The halfspace (2.1) can also be expressed as T xa (x−x )≤ 0, (2.2) 0 T where x is any point on the associated hyperplane, i.e., satisﬁes a x = b. The 0 0 representation (2.2) suggests a simple geometric interpretation: the halfspace con- sists ofx plus any vector that makes an obtuse (or right) angle with the (outward 0 normal) vector a. This is illustrated in ﬁgure 2.8. T The boundary of the halfspace (2.1) is the hyperplane xa x =b. The set T T x a x b, which is the interior of the halfspace x a x ≤ b, is called an open halfspace. 2.2.2 Euclidean balls and ellipsoids n A (Euclidean) ball (or just ball) in R has the form T 2 B(x ,r) =xkx−x k ≤r=x (x−x ) (x−x )≤r , c c 2 c c T 1/2 where r 0, and k·k denotes the Euclidean norm, i.e., kuk = (u u) . The 2 2 vector x is the center of the ball and the scalar r is its radius; B(x ,r) consists c c of all points within a distance r of the center x . Another common representation c for the Euclidean ball is B(x ,r) =x +rukuk ≤ 1. c c 230 2 Convex sets x c 2 Figure 2.9 An ellipsoid in R , shown shaded. The center x is shown as a c dot, and the two semi-axes are shown as line segments. A Euclidean ball is a convex set: if kx −x k ≤ r, kx −x k ≤ r, and 1 c 2 2 c 2 0≤θ≤ 1, then kθx +(1−θ)x −x k = kθ(x −x )+(1−θ)(x −x )k 1 2 c 2 1 c 2 c 2 ≤ θkx −x k +(1−θ)kx −x k 1 c 2 2 c 2 ≤ r. (Hereweusethehomogeneitypropertyandtriangleinequalityfork·k ;see§A.1.2.) 2 A related family of convex sets is the ellipsoids, which have the form T −1 E =x (x−x ) P (x−x )≤ 1, (2.3) c c n T whereP =P ≻ 0, i.e.,P is symmetric and positive deﬁnite. The vectorx ∈R c isthecenter oftheellipsoid. ThematrixP determineshowfartheellipsoidextends √ ineverydirectionfromx ; thelengthsofthesemi-axesofE aregivenby λ ,where c i 2 λ are the eigenvalues of P. A ball is an ellipsoid with P =r I. Figure 2.9 shows i 2 an ellipsoid in R . Another common representation of an ellipsoid is E =x +Aukuk ≤ 1, (2.4) c 2 where A is square and nonsingular. In this representation we can assume without 1/2 loss of generality that A is symmetric and positive deﬁnite. By taking A =P , this representation gives the ellipsoid deﬁned in (2.3). When the matrixA in (2.4) issymmetricpositivesemideﬁnitebutsingular,thesetin(2.4)iscalledadegenerate ellipsoid; its aﬃne dimension is equal to the rank of A. Degenerate ellipsoids are also convex. 2.2.3 Norm balls and norm cones n Supposek·kisanynormonR (see§A.1.2). Fromthegeneralpropertiesofnormsit canbeshownthatanormball ofradiusrandcenterx ,givenbyxkx−x k≤r, c c is convex. The norm cone associated with the normk·k is the set n+1 C =(x,t)kxk≤t⊆R .2.2 Some important examples 31 1 0.5 0 1 1 0 0 −1 x −1 2 x 1 3 2 2 1/2 Figure2.10Boundaryofsecond-orderconeinR ,(x ,x ,t)(x +x ) ≤ 1 2 1 2 t. It is (as the name suggests) a convex cone. Example 2.3 The second-order cone is the norm cone for the Euclidean norm, i.e., n+1 C = (x,t)∈R kxk ≤t 2 ( )        T x x I 0 x = ≤0, t≥0 . t t 0 −1 t Thesecond-orderconeisalsoknownbyseveralothernames. Itiscalledthequadratic cone, since it is deﬁned by a quadratic inequality. It is also called the Lorentz cone 3 or ice-cream cone. Figure 2.10 shows the second-order cone in R . 2.2.4 Polyhedra A polyhedron is deﬁned as the solution set of a ﬁnite number of linear equalities and inequalities: T T P =xa x≤b , j = 1,...,m, c x =d , j = 1,...,p. (2.5) j j j j A polyhedron is thus the intersection of a ﬁnite number of halfspaces and hyper- planes. Aﬃne sets (e.g., subspaces, hyperplanes, lines), rays, line segments, and halfspaces are all polyhedra. It is easily shown that polyhedra are convex sets. A bounded polyhedron is sometimes called a polytope, but some authors use the opposite convention (i.e., polytope for any set of the form (2.5), and polyhedron t32 2 Convex sets a 1 a 2 P a 5 a 3 a 4 Figure 2.11 The polyhedron P (shown shaded) is the intersection of ﬁve halfspaces, with outward normal vectors a ,....,a . 1 5 when it is bounded). Figure 2.11 shows an example of a polyhedron deﬁned as the intersection of ﬁve halfspaces. It will be convenient to use the compact notation P =xAxb, Cx =d (2.6) for (2.5), where     T T a c 1 1  .   .  . . A = , C = ,     . . T T a c m p m and the symbol  denotes vector inequality or componentwise inequality in R : uv means u ≤v for i = 1,...,m. i i Example 2.4 The nonnegative orthant is the set of points with nonnegative compo- nents, i.e., n n n R =x∈R x ≥0, i=1,...,n=x∈R x0. i + (Here R denotes the set of nonnegative numbers: R = x ∈ R x ≥ 0.) The + + nonnegative orthant is a polyhedron and a cone (and therefore called a polyhedral cone). Simplexes Simplexes are another important family of polyhedra. Suppose the k +1 points n v ,...,v ∈ R are aﬃnely independent, which means v −v ,...,v −v are 0 k 1 0 k 0 linearly independent. The simplex determined by them is given by T C =convv ,...,v =θ v +···+θ v θ 0, 1 θ = 1, (2.7) 0 k 0 0 k k2.2 Some important examples 33 where1denotesthevectorwithallentriesone. Theaﬃnedimensionofthissimplex n is k, so it is sometimes referred to as a k-dimensional simplex in R . Example 2.5 Some common simplexes. A 1-dimensional simplex is a line segment; a 2-dimensional simplex is a triangle (including its interior); and a 3-dimensional simplex is a tetrahedron. The unit simplex is then-dimensional simplex determined by the zero vector and the n unit vectors, i.e., 0, e ,...,e ∈ R . It can be expressed as the set of vectors that 1 n satisfy T x0, 1 x≤1. The probability simplex is the (n−1)-dimensional simplex determined by the unit n vectors e ,...,e ∈R . It is the set of vectors that satisfy 1 n T x0, 1 x=1. Vectors in the probability simplex correspond to probability distributions on a set with n elements, with x interpreted as the probability of the ith element. i Todescribethesimplex(2.7)asapolyhedron,i.e.,intheform(2.6),weproceed as follows. By deﬁnition,x∈C if and only ifx =θ v +θ v +···+θ v for some 0 0 1 1 k k T θ 0 with 1 θ = 1. Equivalently, if we deﬁne y = (θ ,...,θ ) and 1 k   n×k B = v −v ··· v −v ∈R , 1 0 k 0 we can say that x∈C if and only if x =v +By (2.8) 0 T for some y  0 with 1 y ≤ 1. Now we note that aﬃne independence of the points v ,...,v implies that the matrix B has rank k. Therefore there exists a 0 k n×n nonsingular matrix A= (A ,A )∈R such that 1 2     A I 1 AB = B = . A 0 2 Multiplying (2.8) on the left with A, we obtain A x =A v +y, A x =A v . 1 1 0 2 2 0 From this we see that x ∈ C if and only if A x = A v , and the vector y = 2 2 0 T A x−A v satisﬁesy 0 and 1 y≤ 1. In other words we havex∈C if and only 1 1 0 if T T A x =A v , A xA v , 1 A x≤ 1+1 A v , 2 2 0 1 1 0 1 1 0 which is a set of linear equalities and inequalities in x, and so describes a polyhe- dron.34 2 Convex sets Convex hull description of polyhedra The convex hull of the ﬁnite setv ,...,v is 1 k T convv ,...,v =θ v +···+θ v θ 0, 1 θ = 1. 1 k 1 1 k k Thissetisapolyhedron, andbounded, but(exceptinspecialcases,e.g., asimplex) it is not simple to express it in the form (2.5), i.e., by a set of linear equalities and inequalities. A generalization of this convex hull description is θ v +···+θ v θ +···+θ = 1, θ ≥ 0, i = 1,...,k, (2.9) 1 1 k k 1 m i where m ≤ k. Here we consider nonnegative linear combinations of v , but only i the ﬁrst m coeﬃcients are required to sum to one. Alternatively, we can inter- pret (2.9) as the convex hull of the points v ,...,v , plus the conic hull of the 1 m points v ,...,v . The set (2.9) deﬁnes a polyhedron, and conversely, every m+1 k polyhedron can be represented in this form (although we will not show this). The question of how a polyhedron is represented is subtle, and has very im- portant practical consequences. As a simple example consider the unit ball in the n ℓ -norm in R , ∞ C =xx≤ 1, i = 1,...,n. i T The setC can be described in the form (2.5) with 2n linear inequalities±e x≤ 1, i wheree is theith unit vector. To describe it in the convex hull form (2.9) requires i n at least 2 points: n C =convv ,...,v , 1 2 n n where v ,...,v are the 2 vectors all of whose components are 1 or −1. Thus 1 2 the size of the two descriptions diﬀers greatly, for large n. 2.2.5 The positive semideﬁnite cone n We use the notation S to denote the set of symmetric n×n matrices, n n×n T S =X ∈R X =X , n which is a vector space with dimension n(n + 1)/2. We use the notation S to + denote the set of symmetric positive semideﬁnite matrices: n n S =X ∈S X  0, + n and the notation S to denote the set of symmetric positive deﬁnite matrices: ++ n n S =X ∈S X ≻ 0. ++ (This notation is meant to be analogous to R , which denotes the nonnegative + reals, and R , which denotes the positive reals.) ++2.3 Operations that preserve convexity 35 1 0.5 0 1 1 0 0.5 y −1 0 x 2 Figure 2.12 Boundary of positive semideﬁnite cone in S . n n n ThesetS isaconvexcone: ifθ ,θ ≥ 0andA, B∈S ,thenθ A+θ B∈S . 1 2 1 2 + + + This can be seen directly from the deﬁnition of positive semideﬁniteness: for any n x∈R , we have T T T x (θ A+θ B)x =θ x Ax+θ x Bx≥ 0, 1 2 1 2 if A 0, B 0 and θ , θ ≥ 0. 1 2 2 Example 2.6 Positive semideﬁnite cone in S . We have   x y 2 2 X = ∈S ⇐⇒ x≥0, z≥0, xz≥y . + y z 3 The boundary of this cone is shown in ﬁgure 2.12, plotted in R as (x,y,z). 2.3 Operations that preserve convexity In this section we describe some operations that preserve convexity of sets, or allow us to construct convex sets from others. These operations, together with the simple examples described in§2.2, form a calculus of convex sets that is useful for determining or establishing convexity of sets. z36 2 Convex sets 2.3.1 Intersection Convexity is preserved under intersection: ifS andS are convex, thenS ∩S is 1 2 1 2 convex. This property extends to the intersection of an inﬁnite number of sets: if T S is convex for everyα∈A, then S is convex. (Subspaces, aﬃne sets, and α α α∈A convex cones are also closed under arbitrary intersections.) As a simple example, a polyhedron is the intersection of halfspaces and hyperplanes (which are convex), and therefore is convex. n Example 2.7 The positive semideﬁnite cone S can be expressed as + \ n T X ∈S z Xz≥0. z6=0 T For each z6=0, z Xz is a (not identically zero) linear function of X, so the sets n T X ∈S z Xz≥0 n are, in fact, halfspaces in S . Thus the positive semideﬁnite cone is the intersection of an inﬁnite number of halfspaces, and so is convex. Example 2.8 We consider the set m S =x∈R p(t)≤1 fort≤π/3, (2.10) P m where p(t) = x coskt. The set S can be expressed as the intersection of an k k=1 T inﬁnite number of slabs: S = S , where t t≤π/3 T S =x −1≤(cost,...,cosmt) x≤1, t and so is convex. The deﬁnition and the set are illustrated in ﬁgures 2.13 and 2.14, for m=2. In the examples above we establish convexity of a set by expressing it as a (possibly inﬁnite) intersection of halfspaces. We will see in §2.5.1 that a converse holds: every closed convex set S is a (usually inﬁnite) intersection of halfspaces. In fact, a closed convex set S is the intersection of all halfspaces that contain it: \ S = HH halfspace, S⊆H. 2.3.2 Aﬃne functions n m Recall that a functionf :R →R is aﬃne if it is a sum of a linear function and m×n m a constant, i.e., if it has the form f(x) =Ax+b, where A∈ R and b∈ R . n n m SupposeS⊆R isconvexandf :R →R isanaﬃnefunction. Thentheimage of S under f, f(S) =f(x)x∈S,2.3 Operations that preserve convexity 37 1 0 −1 0 π/3 2π/3 π t Figure 2.13 Three trigonometric polynomials associated with points in the set S deﬁned in (2.10), for m = 2. The trigonometric polynomial plotted with dashed line type is the average of the other two. 2 1 S 0 −1 −2 −2 −1 0 1 2 x 1 Figure 2.14 The set S deﬁned in (2.10), for m = 2, is shown as the white area in the middle of the plot. The set is the intersection of an inﬁnite number of slabs (20 of which are shown), hence convex. p(t) x 238 2 Convex sets k n is convex. Similarly, if f : R → R is an aﬃne function, the inverse image of S under f, −1 f (S) =xf(x)∈S, is convex. n Two simple examples are scaling and translation. If S⊆R is convex, α∈R, n and a∈R , then the sets αS and S +a are convex, where αS =αxx∈S, S +a =x+ax∈S. The projection of a convex set onto some of its coordinates is convex: if S ⊆ m n R ×R is convex, then m n T =x ∈R (x ,x )∈S for some x ∈R 1 1 2 2 is convex. The sum of two sets is deﬁned as S +S =x+yx∈S , y∈S . 1 2 1 2 If S and S are convex, then S +S is convex. To see this, if S and S are 1 2 1 2 1 2 convex, then so is the direct or Cartesian product S ×S =(x ,x )x ∈S , x ∈S . 1 2 1 2 1 1 2 2 The image of this set under the linear function f(x ,x ) = x +x is the sum 1 2 1 2 S +S . 1 2 n m We can also consider the partial sum of S , S ∈R ×R , deﬁned as 1 2 S =(x,y +y ) (x,y )∈S , (x,y )∈S , 1 2 1 1 2 2 n m where x∈ R and y ∈ R . For m = 0, the partial sum gives the intersection of i S andS ; forn = 0, it is set addition. Partial sums of convex sets are convex (see 1 2 exercise 2.16). Example 2.9 Polyhedron. The polyhedronxAxb, Cx=d can be expressed as the inverse image of the Cartesian product of the nonnegative orthant and the origin under the aﬃne function f(x) =(b−Ax,d−Cx): m xAxb, Cx=d=xf(x)∈R ×0. + Example 2.10 Solution set of linear matrix inequality. The condition A(x)=x A +···+x A B, (2.11) 1 1 n n m whereB, A ∈S ,iscalledalinearmatrixinequality (LMI)inx. (Notethesimilarity i to an ordinary linear inequality, T a x=x a +···+x a ≤b, 1 1 n n with b, a ∈R.) i The solution set of a linear matrix inequality, x A(x)  B, is convex. Indeed, it is the inverse image of the positive semideﬁnite cone under the aﬃne function n m f :R →S given by f(x)=B−A(x).2.3 Operations that preserve convexity 39 Example 2.11 Hyperbolic cone. The set T T 2 T xx Px≤(c x) , c x≥0 n n whereP ∈S andc∈R , is convex, since it is the inverse image of the second-order + cone, T 2 (z,t)z z≤t , t≥0, 1/2 T under the aﬃne function f(x)=(P x,c x). Example 2.12 Ellipsoid. The ellipsoid T −1 E =x(x−x ) P (x−x )≤1, c c n where P ∈ S , is the image of the unit Euclidean ball u kuk ≤ 1 under the ++ 2 1/2 aﬃne mappingf(u)=P u+x . (It is also the inverse image of the unit ball under c −1/2 the aﬃne mapping g(x)=P (x−x ).) c 2.3.3 Linear-fractional and perspective functions In this section we explore a class of functions, called linear-fractional, that is more general than aﬃne but still preserves convexity. The perspective function n+1 n n We deﬁne the perspective function P :R →R , with domain domP =R × R , as P(z,t) = z/t. (Here R denotes the set of positive numbers: R = ++ ++ ++ x∈Rx 0.) The perspective function scales or normalizes vectors so the last component is one, and then drops the last component. Remark 2.1 We can interpret the perspective function as the action of a pin-hole 3 camera. A pin-hole camera (in R ) consists of an opaque horizontal plane x = 0, 3 with a single pin-hole at the origin, through which light can pass, and a horizontal image plane x =−1. An object at x, above the camera (i.e., with x 0), forms 3 3 an image at the point −(x /x ,x /x ,1) on the image plane. Dropping the last 1 3 2 3 component of the image point (since it is always −1), the image of a point at x appears at y =−(x /x ,x /x ) =−P(x) on the image plane. This is illustrated in 1 3 2 3 ﬁgure 2.15. If C ⊆domP is convex, then its image P(C) =P(x)x∈C is convex. This result is certainly intuitive: a convex object, viewed through a pin-hole camera, yields a convex image. To establish this fact we show that line segments are mapped to line segments under the perspective function. (This too40 2 Convex sets x = 0 3 x =−1 3 Figure 2.15 Pin-hole camera interpretation of perspective function. The 3 dark horizontal line represents the plane x = 0 in R , which is opaque, 3 except for a pin-hole at the origin. Objects or light sources above the plane appear on the image planex =−1, which is shown as the lighter horizontal 3 line. The mapping of the position of a source to the position of its image is related to the perspective function. makes sense: a line segment, viewed through a pin-hole camera, yields a line seg- n+1 ment image.) Suppose that x = (x˜,x ), y = (y˜,y )∈ R with x 0, n+1 n+1 n+1 y 0. Then for 0≤θ≤ 1, n+1 θx˜+(1−θ)y˜ P(θx+(1−θ)y) = =µP (x)+(1−µ )P(y), θx +(1−θ)y n+1 n+1 where θx n+1 µ = ∈ 0,1. θx +(1−θ)y n+1 n+1 This correspondence between θ and µ is monotonic: as θ varies between 0 and 1 (which sweeps out the line segment x,y),µ varies between 0 and 1 (which sweeps out the line segment P(x),P(y)). This shows that P(x,y) = P(x),P(y). Now suppose C is convex with C ⊆domP (i.e., x 0 for all x∈C), and n+1 x, y ∈ C. To establish convexity of P(C) we need to show that the line segment P(x),P(y) is in P(C). But this line segment is the image of the line segment x,y under P, and so lies in P(C). The inverse image of a convex set under the perspective function is also convex: n if C ⊆R is convex, then −1 n+1 P (C) =(x,t)∈R x/t∈C, t 0 −1 −1 is convex. To show this, suppose (x,t)∈P (C), (y,s)∈P (C), and 0≤θ≤ 1. We need to show that −1 θ(x,t)+(1−θ)(y,s)∈P (C), i.e., that θx+(1−θ)y ∈C θt+(1−θ)s

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.

Study Notes
Free

### Recommend

© Copyright @ Thesis Scientist Pvt. Ltd. Terms & Conditions | Refund Policy | Tips & Tricks