最优化方法第2章课件

第第 二二 章章基本概念基本概念 和基本理论和基本理论 n n n0 s s Ln在在 平面上任给一点平面上任给一点 ，就对应有一个目标函数值，就对应有一个目标函数值n这个值就是过这个值就是过 点作点作 平面的垂线与平面的垂线与S曲面交点的纵坐标。曲面交点的纵坐标。n 反之，任给一个值反之，任给一个值 ,使目标函数使目标函数 取值为取值为 的点的点z的的 个数就不相同了。可能没有，可能只有一个，可能有多个。个数就不相同了。可能没有，可能只有一个，可能有多个。n 这一事实的几何意义是：过这一事实的几何意义是：过 f 轴上坐标为轴上坐标为 的点作的点作 坐标坐标 平面的平行平面平面的平行平面L，可能与曲面，可能与曲面S无交点（无交点（时），可能与时），可能与S 有一个交点（有一个交点（时），可能与时），可能与S交成一条曲线（交成一条曲线（）。）。凸集凸集非凸集非凸集非凸集非凸集n多胞形多胞形 H(x1,x2,xm)：由由 x1,x2,xm的所有凸组合构成。的所有凸组合构成。n单纯形：若单纯形：若多胞形多胞形 H(x1,x2,xm)满足，满足，x2-x1,x3-x1,xm-x1线性无关。线性无关。多胞形多胞形单纯形单纯形单纯形单纯形性质性质3：分离与支撑：分离与支撑：凸集边界上任意点存在支撑超平面凸集边界上任意点存在支撑超平面 两个互相不交的凸集之间存在分离超平面两个互相不交的凸集之间存在分离超平面支撑支撑强分离强分离分离分离非正常非正常分离分离nDef：C Rn,若若 x C,0 有有 x C,则称则称 C 是以是以 0 为顶点的锥。如果为顶点的锥。如果 C 还是凸集，则还是凸集，则称为凸锥。称为凸锥。n集合集合 0、Rn 是凸锥。是凸锥。n命题：命题：C是凸锥是凸锥C中任意有限点的半正组合属于中任意有限点的半正组合属于S0n定理：定理：f(x)为凸集为凸集 S 上的凸函数上的凸函数 S 上上任意有限点的凸组合的函数值不大于各点任意有限点的凸组合的函数值不大于各点函数值的凸组合。函数值的凸组合。n思考：设思考：设f1,f2是凸函数，是凸函数，1)设设 1,2 0,1f1+2f2,1f1-2f2是否凸是否凸函数？函数？2)f(x)=max f1(x),f2(x),3)g(x)=min f1(x),f2(x)是否凸函数？是否凸函数？n定义：定义：设集合设集合 S Rn，函数，函数 f:SR，R，称，称 S =x S f(x)为为 f(x)在在 S 上上 的的 水平集水平集。n定理：定理：设集合设集合 S Rn 是凸集，函数是凸集，函数 f:SR是是凸函数，则对凸函数，则对 R，S 是凸集是凸集。n注：注：1)水平集的概念相当于在地形图中，海拔高度不高于某一水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。数值的区域。2)上述定理的逆不真。上述定理的逆不真。考虑分段函数考虑分段函数f(x)=1(x0)或或0(x 0 充分小时有充分小时有 x*+d S,如果如果 lim f(x*+d)-f(x*)/存在（包括存在（包括 ）则称则称 f(x)为在点沿方向的方向导数存在，记为在点沿方向的方向导数存在，记 f(x*;d)=lim f(x*+d)-f(x*)/若若 f(x)在在 x*可导，则可导，则 f(x*;d)=f(x*)Td .二、凸函数二、凸函数 2、凸函数的性质：、凸函数的性质：以下设以下设 S Rn 为非空凸集，函数为非空凸集，函数 f:SR2）若）若f 凸，则凸，则 f 在在 S 的内点集上连续；的内点集上连续；注：注：f 在在 S 上不一定连续。上不一定连续。例例:f(x)2(当当 x=1)；f(x)x2(当当 x 0,总有总有 x+d S.d(1)=d(2)(0)时，称时，称 d(1)和和d(2)同方向。同方向。4)极方向：方向极方向：方向 d 不能表示为两个不同方向的不能表示为两个不同方向的组合组合(d=d(1)+d(2).2.3 2.3 多面体、极点、极方向多面体、极点、极方向多面体多面体 S=x Rn Ax=b,x0 的极点和极方向的极点和极方向定理定理1（极点特征）设（极点特征）设 A 满秩，满秩，x 是是 S 极极点的充分必要条件是点的充分必要条件是:存在分解存在分解 A=B,N，其中，其中B为为m阶非奇异矩阵，使阶非奇异矩阵，使 xT=xBT,xNT,这里这里 xB=B-1b0,xN=0.nS中必存在有限多个极点。中必存在有限多个极点。(Cnm)2.3 2.3 多面体、极点、极方向多面体、极点、极方向多面体多面体 S=x Rn Ax=b,x0 的极点和极方向的极点和极方向定理定理2（极方向特征）（极方向特征）设设 A=p1,p2,pn满秩，满秩，d 是是 S 极方极方向的充分必要条件是向的充分必要条件是:存在分解存在分解 A=B,N，其中，其中B为为m阶非奇异矩阵，阶非奇异矩阵，对于对于N中的列向量中的列向量 pj 使使 B-1pj0,dT=dBT,dNT,这里这里 j dB=-B-1pj,dN=(0,.,1,0)TnS中必存在有限多个极方向。中必存在有限多个极方向。(n-m)Cnm)考虑多面体考虑多面体 S=x Rn Ax=b,x0，其中，其中 3 2 1 0 0 65 A=2 1 0 1 0 b=40 0 3 0 0 1 75 即即 3 x1+2 x2+x3 =65 2 x1+x2 +x4 =40 3 x2 +x5 =75 x1,x2,x3,x4,x5 0 例题例题 3 2 1 0 0A=P1,P2,P3,P4,P5 =2 1 0 1 0 0 3 0 0 1 A A矩阵包含以下10个33的子矩阵：B B1 1=p p1 1，p p2 2，p p3 3 B B2 2=p p1 1，p p2 2，p p4 4 B B3 3=p p1 1，p p2 2，p p5 5 B B4 4=p p1 1，p p3 3，p p4 4 B B5 5=p p1 1，p p3 3，p p5 5 B B6 6=p p1 1，p p4 4，p p5 5 B B7 7=p p2 2，p p3 3，p p4 4 B B8 8=p p2 2，p p3 3，p p5 5 B B9 9=p p2 2，p p4 4，p p5 5 B B1010=p p3 3，p p4 4，p p5 5 例题例题 其其中中 B B4 4=0 0，因因而而B B4 4不不能能构构成成极极点点和和极极方方向向。其其余余均均为为非非奇奇异异方方阵阵，因因此此该该问问题题共共有有9 9个个可可构构成成极极点点、极方向的子矩阵，我们称之为基。极方向的子矩阵，我们称之为基。对对于于基基B B3 3=p p1 1，p p2 2，p p5 5，令令x x3 3 =0 0，x x4 4=0 0，在在等等式约束中令式约束中令x x3 3=0=0，x x4 4 =0=0，解线性方程组：，解线性方程组：3 3 x x1 1 +2+2 x x2 2 +0+0 x x5 5 =65=65 2 2 x x1 1 +x x2 2 +0+0 x x5 5 =40=40 0 0 x x1 1 +3+3 x x2 2 +x x5 5 =75=75 得到得到x x1 1 =15=15，x x2 2 =10=10，x x5 5=45=45，对应的极点：，对应的极点：x x=(=(x x1 1，x x2 2，x x3 3，x x4 4，x x5 5)T T =(15 =(15，1010，0 0，0 0，45)45)T T例题例题 类似可得到极点类似可得到极点 x(2)=(5,25,0,5,0)T （对应（对应B2）x(7)=(20,0,5,0,75)T （对应（对应B5）x(8)=(0,25,15,15,0)T（对应（对应B7）x(9)=(0,0,65,40,75)T（对应（对应B10）而而 x(3)=(0,32.5,0,7.5,-22.5)T（对应（对应B9）x(4)=(65/3,0,0,-10/3,75)T（对应（对应B6）x(5)=(7.5,25,-7.5,0,0)T （对应（对应B1）x(6)=(0,40,-15,0,-45)T （对应（对应B8）不是极点不是极点例题例题 写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits55谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal