最优化方法课件01.4.ppt

§1.7 凸集与凸函数 凸 集 定义1.7.1 设集合D Rn,若对于任意点x,y∈ D, 及实数a,0≤a≤1,都有 ax+(1-a)y ∈ D, 则称集合D为凸集. 凸集的例 例1.7.1 超球||x||≤r为凸集 证明 设x,y为超球中任意两点, 0≤a≤1,则有 ||ax+(1-a)y||≤a||x||+(1-a)||y|| ≤a r+(1-a) r = r, 即点ax+(1-a)y属于超球,所以超球为凸集. 凸集的性质 (i)有限个(可以改成无限)凸集的交集为凸集. 即:若Dj(j ∈ J)是凸集,则它们的交集 D={x|x ∈ Dj,j ∈ J } 是凸集. (ii)设D是凸集,b是一实数,则下面集合是凸集 b D={y | y =b x, x ∈ D}. 凸集的性质 (iii)设D1,D2是凸集,则D1与D2的和集 D1+D2={y|y=x+z,x ∈ D1,z ∈ D2}是凸集. 注:和集与并集有很大的区别,凸集的并集未必是凸集, 而凸集的和集是凸集. 例:D1={(x,0)T|x ∈ R}表示 x 轴上的点, D2={(0,y)T|y ∈R},表示 y 轴上的点. 则D1∪D2表示两个轴的所有点,它不是凸集; D1+D2=R2是凸集 推论 凸集的线性组合是凸集. 极 点 定义1.7.3 设D为凸集, x∈D.若D中不存在两个相异的点y,z及某一实数a∈(0,1)使得x=ay+(1-a)z则称x为D的极点. 极 点 凸 函 数 定义1.7.4 设函数f (x)定义在凸集D Rn上,若对任意的x,y ∈ D,及任意的a ∈ [0,1]都有f (a x+(1-a)y) ≤ a f(x)+(1-a) f (y)则称函数f (x)为凸集D上的凸函数. 凸 函 数 凸函数的例 例1.7.3 设f (x)=(x–1)2,试证明f(x)在(–∞,+∞)上是严格凸函数. 凸函数的几何性质 对一元函数f (x),在几何上a f (x1)+(1-a)f (x2)(0≤a≤1)表示连接(x1,f(x1)),(x2,f (x2))的线段, f(ax1+(1-a)x2)表示在点ax1+(1-a)x2处的函数值,所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方. 对于一元凸函数f(x),可以发现,位于函数曲线上方的图形是凸集.事实上这一结论对于多元函数也是成立的,而且是充要条件,即有下面的定理. 凸函数的性质 (i)设f(x)是凸集D Rn上的凸函数,实数k≥0,则kf(x)也是D上的凸函数. 凸函数的性质 凸函数的判断 定理1.7.1 设f(x)定义在凸集D Rn上,x,y∈D.令F (t)=f (tx+(1-t)y), t ∈ [0,1],则 凸函数的判断 一阶条件 定理1.7.2 (一阶条件) 设在凸集D Rn上f(x)可微,则f(x)在D上为凸函数的充要条件是对任意的x,y ∈ D,都有 f(y)≥f(x)+ f(x)T(y-x) 二阶条件 定理1.7.4 (二阶条件)设在开凸集D Rn上f(x)可微,则 (i) f(x)是D内的凸函数的充要条件为,在D内任一点x处, f(x)的Hesse矩阵G(x)半正定,其中 凸规划 定义1.7.6 设D Rn为凸集,则f(x)为D上的凸函数,则称规划问题min f(x)s.t. x ∈ D为凸规划问题. 定理1.7.5证明(思路) (i)x*为局部极小点,若存在x0使得f(x0)f(x*),则f (t x0 +(1-t) x*)≤t f (x0)+(1-t) f (x*)令 t 取一个足够小的正数,可导出矛盾. 最优化问题的一般形式为: 整体最优解 定义1.2.3 若x*∈D,对于一切x∈D恒有f(x*)≤f(x),则称x*为最优化问题(P)的整体最优解. 若x*∈D,x≠x*, 恒有f(x*) f(x),则称x*为最优化问题(P)的严格整体最优解. 定义1.2.4 (局部最优解) 若x*∈D,存在x*的某邻域Ne(x*),使得对于一切x∈D∩Ne(x*),恒有f(x*)≤f(x),则称x*为最优化问题(P)的局部最优解. 当x≠x*时,若上面的不等式为严格不等式则称x*为问题(P)的严格局部最优解. 显然,整体最优解一定是局部最优解,而局部最优解不一定是整体最优解. x*对应的目标函数值f(x*)称为最优值，记为f *. (1.1)(目标函数) (1.3)(不等式约束) (1.2)(等式约束) 其中x是n维向量. 在实际应用中,可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式. 我们总是讨论 P: 函数 在局部极小点满足什么条件？反之满足什么条件的是