工程优化方法与应用-第二章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,Page,*,基本概念和理论基础,主要内容：,1,代数基础：范数、正定性,2,多元函数分析基础：,Hesse,矩阵、方向导数、中值公式,3,多元函数的极值,4,等高线,5,凸分析基础：凸集、凸函数、凸规划,6,最优化算法的结构,向量范数定义,l,2,范数,l,1,范数,l,p,范数,l,范数,1,代数基础,列向量,范数常见不等式,l,1,-,范数,l,2,-,范数,l,范数,相互等价,l,2,范数也称谱范数,(,A,T,A,最大特征值开平方,),特别地，方阵有如下范数,l,1,范数,(,列和的最大者,),l,范数,(,行和的最大者,),矩阵,范数,定义：设,Q,为,nn,阶,对称矩阵,若,，,均有,，,则称,Q,正,定,若,，均有,，则称,Q,半正定若 ，均有 ，则称,Q,负定若,均有 ，则称,Q,半负定矩阵正定性,正定判定定理,矩阵,Q,半,正定,Q,的所有特征根大于,等于,零,;,Q,的各阶主子式都大于,等于,零,；,存在,矩阵,G,，使得,Q,=,GG,T,矩阵,Q,正定,Q,的所有特征根大于零,;,Q,的各阶,顺序,主子式都大于零,；,Q,的各阶主子式都大于零,；,存在,非奇异矩阵,G,，使得,Q,=,GG,T,负定判定定理,矩阵,Q,半负,定,Q,的所有特征根,小,于,等于,零,;,Q,的,所有奇数,阶主子式都,小,于,等于,零,，且偶数阶主子式都大于等于零；,存在,矩阵,G,，使得,-,Q,=,GG,T,。

矩阵,Q,负,定,Q,的所有特征根,小,于零,;,Q,的,所有奇数,阶,顺序,主子式都,小,于零,，且偶数阶顺序主子式都大于零；,Q,的,所有奇数,阶主子式都,小,于零,且偶数阶主子式都大于零；,存在,非奇异矩阵,G,，使得,-,Q,=,GG,T,解：,对称矩阵,Q,的三个顺序主子式依次为,例,1,判定矩阵是否正定:,矩阵,Q,是正定的2,多元函数分析基础,n,元函数：,n,元线性函数：,n,元二次函数：,n,元向量值线性函数：,多元函数,序列收敛,定义,若 满足 ，则称 为,Cauchy,序列i.e.,注：,收敛 是,Cauchy,序列,.,Cauchy,序列的任一子列都收敛定义,设 为一向量序列，如果,则称序列 依范数收敛到,记为,给定区域,D,上的,n,元实值函数,梯度、,Hesse,矩阵,列向量,的梯度,的梯度,的,Hesse,矩阵,常用的梯度和,Hesse,阵公式：,其中,Q,为实对称矩阵,方向导数,定义,(,方向导数,),设 在点,x,处可微,d,为固定单位向量，则称,f(x,),在,x,处沿方向,d,的方向导数为,最速上升方向,最速下降方向,解：,由于 则函数在 处的最速下降方向,例,1,试求目标函数 在点 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。

此方向上的单位向量,新点是,中值公式,设,二阶可导，则在,x*,的邻域内有：,一阶,Taylor,展开式,二阶,Taylor,展开式,第二章 基本概念和理论基础,本章主要内容：,1,代数基础：范数、正定性,2,多元函数分析基础：,Hesse,矩阵、方向导数、中值公式,3,多元函数的极值,4,等高线,5,凸分析基础：凸集、凸函数、凸规划,6,最优化算法的结构,3,多元函数的极值,对于一个极小化问题，我们的目的是求出全局极小点，而全局极小点不好求，因此我们一般的做法是先求出所有局部极小值点，再从中找出全局极小点为了求出函数的局部极小值点，我们需要考察函数,f,在局部极小点处满足什么条件？反过来，满足什么条件的点是局部极小点？首先回顾二元函数的极值条件（高等数学），然后推广到多元函数二元函数极值的判别条件,定理,(,必要条件,),设,(1),为,D,的一个内点,;,可微,;,(2),在,处,（驻点）,则在,的极值点,;,(3),为,且,注：可微的极值点一定是驻点，反之不一定成立例,在 处梯度为 ，,但 只是双曲抛物面的鞍点，而不是极小点f,(2),当 时，不是 的极值点，称为函数的,鞍点,；,(3),当 时，不能确定，需另行讨论。

定理,(,充分条件,),设,(1),为,D,的一个内点,;,二次连续可微,;,(2),在,的驻点，即,(3),为,且,令,则,(1),当 时，具有极值,取严格极大值,取严格极小值,Hesse,阵负定,Hesse,阵正定,多元函数的极值判别条件,定理,(,必要 条件,),设,(1),x*,为,D,的一个内点,;,可微,;,(2),在,则,的极值点,;,(3),为,且,证明,:,借助一元函数极值的必要条件，见下页设 是 的局部极小点，为任意单位向量由定义知：当,即 时，总有：,令 则 而 是,D,的内点，从而与之对应的,t=,0 是 的局部极小点由一元函数极小点必要性条件知 ,而由前述性质知 则 ,由单位向量任意性，即知 证明,:,（若 ，取 ，则,矛盾定理,(,充分条件,),设,(1),x*,为,D,的一个内点,;,(2),二次连续可微,;,在,(3),则,的,严格局部极小点（严格局部极大点）,为,(4),正定（负定）；,证明：,借助多元函数的泰勒公式：,（,x,充分接近 时）课后作业,P38 2.1 2.3 2.9-2.14,第二章 基本概念和理论基础,本章主要内容：,1,代数基础：范数、正定性,2,多元函数分析基础：,Hesse,矩阵、方向导数、中值公式,3,多元函数的极值,4,等高线,5,凸分析基础：凸集、凸函数、凸规划,6,最优化算法的结构,Z=,f(x,y,),的图形是一条曲面。

f(x,y,)=c,的图形称为等高线或等值线令,c=c,1,c,2,等一系列的值，得到一族等高线从等高线族的图形上大致可以看出函数值的变化情况利用二维观察三维）,4,等高线,二元函数的等值线,性质：,极值点附近，二元函数的等高线近似于一族同心椭圆,.,理由,:,注：极值点附近，,二次函数,的等高线就是一族准确的同心椭圆,.,极值点正好就是椭圆族的共同中心因此，求二次函数的极值点问题，从几何上讲，也就是求等值线族的共同中心 解：,展开,例,把二次函数,化为矩阵向量形式并检验,Q,是否正定，如正定，试用公式,求这个函数的极小点与题中函数比较各项系数为：,由前例知 正定,极小点为,性质：,若函数在某点的梯度不为零，则该梯度必与过该点的等值线垂直,.,（梯度方向也称法向量）,理由,:,注：梯度所指的方向总是等值线的法方向，并且在极大值点处梯度方向指向近似椭圆的中心，而,在极小值点处梯度方向背离近似椭圆的中心定义,（等值面）,在三维以上的空间中，使目标函数,z=,f(x,),取同一常数值的,面,x|f(x)=r,r,是常数 称为目标函数,z=,f(x,),的等值面定理,若多元函数在其极小点处的,Hesse,阵正定，则它在这个极小点附近的等值面近似地呈现为同心超椭球面族。

多元函数的等值面,等值面的性质小结,不同值的等值面之间不相交，,因为目标函数是单值函数,；,除了极值点所在的等值面外，不会在区域内部中断，,因为目标函数是连续的,；,一般地，在极值点附近，等值面（线）近似地呈现为同心椭球面族（椭圆族），,因为泰勒公式,；,二次函数的等值面是同心椭球面族，极值点是这个椭圆球面的共同中心二元函数，梯度所指的方向总是等值线的法方向，并且在极大值点处梯度方向指向近似椭圆的中心，而在极小值点处梯度方向背离近似椭圆的中心例,用图解法求解,解：,先画出目标函数等值线，再画出约束曲线对应的最优值为,由图易见约束直线与等值线的切点是最优点，利用解析几何的方法得,该切点为,本处约束曲线是一条直线，这条直线就是可行域；而最优点就是可行域上使等值线具有最小值的点,.,第二章 基本概念和理论基础,本章主要内容：,1,代数基础：范数、正定性,2,多元函数分析基础：,Hesse,矩阵、方向导数、中值公式,3,多元函数的极值,4,等高线,5,凸分析基础：凸集、凸函数、凸规划,6,最优化算法概述,一元函数有结论：,若,f,(,x,),在区间,a,b,上是凸的，则,x*,是,f,(,x,),的极小值点等价于,x*,是,f,(,x,),的最小值。

且由微分学知：若 ，则,f,(,x,),是凸的5,凸分析基础,问题（极小值点和最小值点之间的关系）：,设,f,(,x,),定义在,D,内，若,x*,为,f,(,x,),的最小值点，则,x*,为,f,(,x,),的极小值点反过来不一定成立为研究多元函数的极值与最值的关系，下面介绍多元函数凸性规定：,空集和单元素集是凸集根据定义：三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸集等价定义（凸集）：,设,5.1,凸集,定义（凸集）：,若集合 中任意两点的连线都属于 ，则称 为凸集因为两点,连线上任一点可以表示为,凸集的几何特征,凸集的代数特征,称集合 为凸集恒有,凸集：在点集中任取两点，则其连线仍在其中即没有凹入的部分；没有空洞A,B,C,D,证明,:,即,所以,即,H,是凸集例,2:,集合,是凸集,称为超平面，,c,为,n,维向量例,3,：,邻域,是凸集例,1:,集合,是凸集,.,定义：,设 那么称,是,的凸组合性质,2,：,S,是凸集,S,中任意有限个点的凸组合属于,S,证明：见书中定理,2.9(P23),充分性显然必要性：归纳法性质,1,：,设 是凸集，则 也是凸集注：,不一定是凸集。

性质,1,：,设 是凸集，则 也是凸集定义（凸包）：,包含集合,D,的所有凸集的交集,称为,D,的凸包,.,记作,Co(D,),或者,H(D).,注：,由性质,1,可知，,Co(D,),是包含,D,的最小凸集0,定义（凸锥）：,设 ，如果对任意的 及所有的 ，,都有 ，则称 是一个锥一个同时是凸集的锥，称为,凸锥定义（多胞形）：,有限个点的凸包,凸集分离定理,H,S,2,S,1,定义（集合分离）：,设 是非空集合，如果存在向量 及 ，使得,则称超平面 分离 和,定理（投影定理）,：,设 是非空凸集，则,（,1,）存在唯一的 使得它与,y,的距离最小，即,（,2,）是点,y,到,S,的距离最小的充要条件为,证明：参考袁亚湘,P39,令,根据下确界的定义，存在序列 使得 下面证它是柯西列即可y,S,x,定理（点与凸集,的分离定理）：,设 是非空凸集，,则如果存在唯一的 及 ，使得,即存在超平面 分离,y,和,S,y,l,S,证明：参考袁亚湘,P41,定理（,Farkas,）,设,则下列关系式有且仅有一组有解：,证明：参考袁亚湘,P42,几何解释,:,(1),有解，,(2),无解,a,2,a,1,a,m,c,a,1,a,2,a,m,c,(1),无解，,(2),有解,(1),式有解当且仅当凸锥,x|Ax0,与半空间,x|c,T,x,0,的交非空,.,(2),式有解当且仅当,c,在由,A,的行向量,a,1,a,2,a,m,所生成的凸锥内,.,定义（凸函数）,:,设集合,D,R,n,为凸集，函数,f,:,D,R,若,x,y,D,(0,1),，均有,f,(,x,+(1-,),y,),f,(,x,)+(1-,),f,(,y,),，,则称,f,(,x,),为凸集,D,上的凸函数。

凸函数：任意两个点的凸组合的函数值小于等于这两个点的函数值的凸组合严格凸函数：,进一步，若有上面不等式以严格不等式成立，则称,f,(,x,),为凸集 上的严格凸函数凹函数：,当,-,f,(,x,),为凸函数,(,严格凸,),时，则称,f,(,x,),为凹函数,(,严格凹,),5.2,凸函数,f(X),X,f(X,1,),f(X,2,),X,1,X,2,凸函数几何意义：任意两点的函数值的连线上的点都在曲线的上方，即,弦位于曲线的上方,x,1,+(1-,)x,2,f,(,x,1。