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 Profile Pic
Prof.WilliamsHibbs,United States,Teacher
Published Date:27-07-2017
Your Website URL(Optional)
Comment
Chapter 2 Convex sets 2.1 Affine 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 figure 2.1. 1 2.1.2 Affine sets n A set C ⊆ R is affine 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 coefficients 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 affine combination 1 1 k k 1 k of the points x , ..., x . Using induction from the definition of affine set (i.e., 1 k that it contains every affine 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 affine set contains every affine combination of its points: If C is an affine 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 affine 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 affine, and α+β +(1−α−β) = 1. We conclude that αv +βv ∈V, 1 2 since αv +βv +x ∈C. 1 2 0 Thus, the affine set C can be expressed as C =V +x =v+x v∈V, 0 0 i.e., as a subspace plus an offset. The subspace V associated with the affine set C does not depend on the choice of x , so x can be chosen as any point in C. We 0 0 definethedimension ofanaffinesetC 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 affine 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 affine combination θx +(1−θ)x is also in C. The subspace 1 2 associated with the affine set C is the nullspace of A. We also have a converse: every affine set can be expressed as the solution set of a system of linear equations.2.1 Affine and convex sets 23 n The set of all affine combinations of points in some set C ⊆ R is called the affine hull of C, and denoted affC: affC =θ x +···+θ x x ,...,x ∈C, θ +···+θ = 1. 1 1 k k 1 k 1 k The affine hull is the smallest affine set that contains C, in the following sense: if S is any affine set with C ⊆S, then affC ⊆S. 2.1.3 Affine dimension and relative interior We define the affine dimension of a setC as the dimension of its affine hull. Affine dimension is useful in the context of convex analysis and optimization, but is not always consistent with other definitions of dimension. As an example consider the 2 2 2 2 2 unit circle in R , i.e., x ∈ R x +x = 1. Its affine hull is all of R , so its 1 2 affine dimension is two. By most definitions of dimension, however, the unit circle 2 in R has dimension one. n If the affine dimension of a set C ⊆ R is less than n, then the set lies in n the affine set affC 6= R . We define the relative interior of the set C, denoted relintC, as its interior relative to affC: relintC =x∈C B(x,r)∩affC ⊆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 define the same relative interior.) We can then define 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 , defined as 1 2 3 C =x∈R −1≤x ≤1, −1≤x ≤1, x =0. 1 2 3 3 Its affine hull is the (x ,x )-plane, i.e., affC =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 fifteen points (shown as dots) is the pentagon (shown shaded). Right. The convex hull of the kidney shaped set in figure 2.2 is the shaded set. Roughlyspeaking,asetisconvexifeverypointinthesetcanbeseenbyeveryother point, along an unobstructed straight path between them, where unobstructed means lying in the set. Every affine 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 affine 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 definition of convex hull. Theideaofaconvexcombinationcanbegeneralizedtoincludeinfinitesums,in- tegrals, and, in the most general form, probability distributions. Supposeθ ,θ ,... 1 22.1 Affine 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 satisfies 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 figure 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 affine) combinations, the idea of conic combination can be generalized to infinite 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 figure 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 figure 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 affine (hence, convex) subsets of R . • Any line is affine. If it passes through zero, it is a subspace, hence also a convex cone. • A line segment is convex, but not affine (unless it reduces to a point). • A ray, which has the formx +θvθ≥ 0, wherev = 6 0, is convex, but not 0 affine. It is a convex cone if its base x is 0. 0 • Any subspace is affine, 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 affine 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 offset 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 satisfies 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 offset x , plus all vectors orthog- 0 onal to the (normal) vector a. These geometric interpretations are illustrated in figure 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 affine. This is illustrated in figure 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.7Ahyperplanedefinedbya 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., satisfies 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 figure 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 definite. 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 definite. By taking A =P , this representation gives the ellipsoid defined in (2.3). When the matrixA in (2.4) issymmetricpositivesemidefinitebutsingular,thesetin(2.4)iscalledadegenerate ellipsoid; its affine 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 defined 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 defined as the solution set of a finite 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 finite number of halfspaces and hyper- planes. Affine 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 five halfspaces, with outward normal vectors a ,....,a . 1 5 when it is bounded). Figure 2.11 shows an example of a polyhedron defined as the intersection of five halfspaces. It will be convenient to use the compact notation P =xAxb, 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 : uv 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 x0. 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 affinely 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. Theaffinedimensionofthissimplex 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 x0, 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 x0, 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 definition,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 define 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 affine 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 satisfiesy 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 xA 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 finite 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 first m coefficients 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) defines 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 differs greatly, for large n. 2.2.5 The positive semidefinite 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 semidefinite matrices: n n S =X ∈S X  0, + n and the notation S to denote the set of symmetric positive definite 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 semidefinite 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 definition of positive semidefiniteness: 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 semidefinite 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 figure 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 infinite number of sets: if T S is convex for everyα∈A, then S is convex. (Subspaces, affine 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 semidefinite 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 semidefinite cone is the intersection of an infinite 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 infinite number of slabs: S = S , where t t≤π/3 T S =x −1≤(cost,...,cosmt) x≤1, t and so is convex. The definition and the set are illustrated in figures 2.13 and 2.14, for m=2. In the examples above we establish convexity of a set by expressing it as a (possibly infinite) intersection of halfspaces. We will see in §2.5.1 that a converse holds: every closed convex set S is a (usually infinite) 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 Affine functions n m Recall that a functionf :R →R is affine 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 isanaffinefunction. 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 defined 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 defined 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 infinite 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 affine 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 defined 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 , defined 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 polyhedronxAxb, Cx=d can be expressed as the inverse image of the Cartesian product of the nonnegative orthant and the origin under the affine function f(x) =(b−Ax,d−Cx): m xAxb, 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 semidefinite cone under the affine 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 affine 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 affine mappingf(u)=P u+x . (It is also the inverse image of the unit ball under c −1/2 the affine 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 affine but still preserves convexity. The perspective function n+1 n n We define 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 figure 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.