Convex Optimization Boyd Vandenberghe 2 Convex sets a ne and convex sets some important examples operations that preserve convexity generalized inequalities separating and supporting hyperplanes dual cones and generalized inequalities 2 1 A ne set line through x1 x2 all points x x1 1 x2 R x1 1 2 1 0 6 x2 0 0 2 a ne set contains the line through any two distinct points in the set example solution set of linear equations x Ax b conversely every a ne set can be expressed as solution set of system of linear equations Convex sets 2 2 Convex set line segment between x1 and x2 all points x x1 1 x2 with 0 1 convex set contains line segment between any two points in the set x1 x2 C 0 1 x1 1 x2 C examples one convex two nonconvex sets Convex sets 2 3 Convex combination and convex hull convex combination of x1 xk any point x of the form x 1x1 2x2 k xk with 1 k 1 i 0 convex hull conv S set of all convex combinations of points in S Convex sets 2 4 Convex cone conic nonnegative combination of x1 and x2 any point of the form x 1x1 2x2 with 1 0 2 0 x1 x2 0 convex cone set that contains all conic combinations of points in the set Convex sets 2 5 Hyperplanes and halfspaces hyperplane set of the form x aT x b a 0 a x0 x aT x b halfspace set of the form x aT x b a 0 a x0 aT x b aT x b a is the normal vector hyperplanes are a ne and convex halfspaces are convex Convex sets 2 6 Euclidean balls and ellipsoids Euclidean ball with center xc and radius r B xc r x x xc 2 r xc ru u 2 1 ellipsoid set of the form x x xc T P 1 x xc 1 with P Sn i e P symmetric positive de nite xc other representation xc Au u 2 1 with A square and nonsingular Convex sets 2 7 Norm balls and norm cones norm a function that satis es x 0 x 0 if and only if x 0 tx t x for t R x y x y notation is general unspeci ed norm symb is particular norm norm ball with center xc and radius r x x xc r 1 0 5 t norm cone x t x t Euclidean norm cone is called secondorder cone 0 1 1 0 x2 1 1 0 x1 norm balls and cones are convex Convex sets 2 8 Polyhedra solution set of nitely many linear inequalities and equalities Ax b Cx d A Rm n C Rp n is componentwise inequality a1 a2 P a5 a3 a4 polyhedron is intersection of nite number of halfspaces and hyperplanes Convex sets 2 9 Positive semide nite cone notation Sn is set of symmetric n n matrices Sn X Sn X 0 positive semide nite n n matrices X Sn z T Xz 0 for all z Sn is a convex cone Sn X Sn X 0 positive de nite n n matrices 1 x y y z S2 0 5 z example 0 1 1 0 y Convex sets 0 5 1 0 x 2 10 Operations that preserve convexity practical methods for establishing convexity of a set C 1 apply de nition x1 x2 C 0 1 x1 1 x2 C 2 show that C is obtained from simple convex sets hyperplanes halfspaces norm balls by operations that preserve convexity intersection a ne functions perspective function linear fractional functions Convex sets 2 11 Intersection the intersection of any number of convex sets is convex example S x Rm p t 1 for t 3 where p t x1 cos t x2 cos 2t xm cos mt for m 2 2 1 0 x2 p t 1 1 S 0 1 0 Convex sets 3 t 2 3 2 2 1 x01 1 2 2 12 A ne function suppose f Rn Rm is a ne f x Ax b with A Rm n b Rm the image of a convex set under f is convex S Rn convex f S f x x S convex the inverse image f 1 C of a convex set under f is convex C Rm convex f 1 C x Rn f x C convex examples scaling translation projection solution set of linear matrix inequality x x1A1 xmAm B with Ai B Sp hyperbolic cone x xT P x cT x 2 cT x 0 with P Sn Convex sets 2 13 Perspective and linear fractional function perspective function P Rn 1 Rn P x t x t dom P x t t 0 images and inverse images of convex sets under perspective are convex linear fractional function f Rn Rm Ax b f x T c x d dom f x cT x d 0 images and inverse images of convex sets under linear fractional functions are convex Convex sets 2 14 example of a linear fractional function f x 1 x x1 x2 1 0 1 1 Convex sets 1 x2 x2 1 C 0 x1 1 0 1 1 f C 0 x1 1 2 15 Generalized inequalities a convex cone K Rn is a proper cone if K is closed contains its boundary K is solid has nonempty interior K is pointed contains no line examples nonnegative orthant K Rn x Rn xi 0 i 1 n positive semide nite cone K Sn nonnegative polynomials on 0 1 K x Rn x1 x2t x3t2 xntn 1 0 for t 0 1 Convex sets 2 16 generalized inequality de ned by a proper cone K x K y y x K x K y y x int K examples componentwise inequality K Rn x Rn y xi yi i 1 n matrix inequality K Sn X Sn Y Y X positive semide nite these two types are so common that we drop the subscript in K properties many properties of K are similar to on R e g x K y Convex sets u K v x u K y v 2 17 Minimum and minimal elements K is not in general a linear ordering we can have x K y and y K x x S is the minimum element of S with respect to K if y S x K y x S is a minimal element of S with respect to K if y S y K x example K R2 x1 is the minimum element of S1 x2 is a minimal element of S2 x1 Convex sets S1 y x S2 x2 2 18 Separating hyperplane theorem if C and D are disjoint convex sets then there exists a 0 b such that aT x b for x C aT x b for x D aT x b aT x b D C a the hyperplane x aT x b separates C and D strict separation requires additional assumptions e g C is closed D is a singleton Convex sets 2 …