数据库文化基础 (25).pdf
Convexity14thweek/Optimization(III)Understand basic properties of convex sets and convex/concave functionsObjectives of This SessionDiscuss the definiteness of the Hessian and the check of convexity Convex Set A set of points is a convex set if every line segment joining two points of the set is entirely in the set A set is convex if +1 for any,and for any 0,13=shaded areaSome Properties of Convex Set If is convex,+|is convex for any If is convex,|is convex for any If and are convex,is convex 4Convex Function Convex function is convex if 1+1 2 1+1 (2)for any 1,2and 0,1 Strictly Convex Function is convex if 1+1 2 0 for all Two-dimensional cases1001:=12+22 0 for all 1,2(0,0)21111:=12+22+212=1+22 0 for all 1,2 =:PD if 0,=2 015Negative(Semi-)Definiteness A square matrix is negative semi-definite(NSD)if 0for all A square matrix is negative definite(ND)if 0 for all leading principal minors is positive semi-definite if and only if 0 for all principal minors is negative definite if and only if 1 0 for all leading principal minors is negative semi-definite if and only if 1 0 for all principal minors20 Example 1.1,2=21 52 12+12+22 7Convex Function and Hessian Matrix211=21 2 22=1+22 5212=2222=2212=12=2112Since 2 0 and 2 2 12 0,is(strictly)convex1001001010010300400200010010551001030040020000Convex Function and Hessian Matrix Example 2.1,2=21+52+12 12 22+722Method 11=21+2+22=1 22+5212=2222=2212=12=2112Since 2 0,is(strictly)concaveMethod 2 x1,x2=1,2is convex is concaveConvex Function and Hessian Matrix Example 3.1,2=13+21 612+22 52 7231=312+2 622=61+22 52=616621stprincipal minor=61,22ndprincipal minor=121 36If 1 3,then the 1stand 2ndprincipal minors are all nonnegative 1,2is convex over S=1,2|1 3500-100101001010001500500010001500200055Convex function :1+1 2 1+1 (2)for any 1,2and 0,1SummaryConvex set:every line segment joining two points of the set isentirely in the setHessian,Its Definiteness and Convex functionHessian()Function()is Positive definiteStrictly convexPositive semi-definiteConvexNegative definiteStrictly concaveNegative semi-definiteconcaveIntroduction to Mathematical Programming(Operations Research:Volume One),W.L.Winston&M.Venkataramanan,Thomson,4th editionReferencesConvex Analysis,R.T.RockaFellar,Princeton University PressOR/MS(Management Science)and Probability Models,Ho Woo Lee,Sigma Press
