lxt第2章优化设计数学基础.ppt

第二章优化设计的数学基础,1）多元函数的Taylor展开式,2）二次型函数,3）关于优化方法中搜索方向的理论基础,4）凸集与凸函数,5）最优化问题的极值存在条件,2-1函数的Taylor展开式,*在实际计算中,常取前三项(二次函数)来近似原函数:,式中,一.一元函数的Taylor展开式,二.多元函数的Taylor展开式,(1),(2),(3),梯度,海赛(Hessian)矩阵,对称矩阵,故,解：,例：将函数写成在点处泰勒展开式的矩阵形式。,2-2二次齐次函数,例：,*矩阵A为正定的充要条件-A的各阶主子式均大于零。,如为正定，则必有：,2-3关于优化方法中搜索方向的理论基础,1.方向导数,一.函数的最速下降方向,2.梯度,二.共轭方向,1.正定二次函数,2.共轭方向的基本概念,3.构成共轭方向的方法,1.定义-函数沿指定方向的平均变化率的极限。,一)方向导数,2.3.1函数的最速下降方向,2.方向余弦,3.方向导数的计算,二）梯度,令,于是,单位矢量,从上式可得出如下结论：,*最速下降只是局部性质.,4）在与梯度垂直的方向（等值线的切线方向）上，函数的变化率为零。,2）梯度的模是最大的方向导数,负梯度方向是函数的最速下降方向；,1）方向导数是梯度在指定方向上的投影；,3）最速下降方向为等值线（面）的法线方向；,2.3.2共轭方向,*当n=2时，,1）矩阵表示,一）正定二次函数,也适于多元函数,2)正定二元二次函数的特点,)F=f时有极小.此时椭圆缩为一点,即椭圆中心.,)F只影响椭圆的大小,不影响其中心位置-同心;,椭圆方程经坐标轴平移和转动后可去掉一次项和交叉项,故写成下述形式不失一般性:,因函数为正定，故A为正定，即：由于判别式0，无论F(X)取何值,所得方程均为椭圆方程.,证：,（1）正定二元二次函数的等值线是一族同心椭圆，其中心坐标就是该函数的极小点。,（2）过同心椭圆族的中心作任意直线与椭圆族中任意两椭圆相交，再过两交点所作相应椭圆的切线必相互平行。,为常量,说明该直线上各椭圆的斜率均相等.,逆命题:设两平行线与同心椭圆族中两椭圆分别相切于点,则过的直线必通过椭圆族的中心.,设过中心的直线为,代入上式得:,就上式对求导:,证:,二）共轭方向的基本概念,*几何意义:经过线性变换A后成了与正交的向量.,例：,设A为n*n阶正定对称矩阵，是两个n维向量，若存在则称对A共轭。,1)定义,2)共轭方向的性质,*这种性质称为有限步收敛性（亦称二次收敛性）,（2）从任意选定的初始点出发，只要依次沿n个共轭方向进行一维搜索，一轮后便可达到n元正定二次函数的极小点。,(证明见席少霖:最优化方法，P97）,（1）若矢量系彼此对正定对称矩阵A共轭，则它们组成线性无关的矢量系；,三）构成共轭方向的方法,设为平行于的两条直线，则过这两直线上正定n元二次目标函数的极小点的向量和对Hessian矩阵A共轭。,证明：,二次函数,其梯度为,因分别为两直线上的极小点，故有,将上述两式相减,再从出发，沿搜索得,2）取初始点，沿方向搜索,解：,1）,例：对于目标函数，给定，试求出与共轭的方向，并求出目标函数的极小点。,2-4凸集与凸函数,凸集,非凸集,凹集,*若X是X1和X2连线上的点，则有,241凸集-若任意两点，对于，恒有，则D为凸集。,整理后即得,设f(X)为定义在Rn内一个凸集D上的函数，若对于及D上的任意两点X1,X2,恒有则f(X)为定义在D上的一个凸函数。,242凸函数,1.定义,2.凸函数的基本性质,证:由定义两式相加,整理后可得证.,（2）设、均为定义在凸集D上的凸函数，则+也是定义在D上的凸函数。,证:由定义两边乘上:,（1）设为定义在凸集D上的凸函数，为任意正实数,则也是定义在D上的凸函数。,（3）设、均为定义在凸集D上的凸函数，为任意正实数，则也是定义在D上的凸函数。,3.凸函数的判定,若D为凸集，F(x)为定义在D上的凸函数，则此规划为凸规划。,对于数学规划问题：,4.凸规划,凸规划的最优点是唯一的.,2-5最优化问题的极值存在条件,二）多元函数具有极小值的充要条件,一）一元函数具有极小值的充要条件,251无约束问题的极值存在条件,简易证明：,由矩阵理论可知,因,故,2.5.2约束问题有最优解的必要条件,（2）对于整个可行域，恒有，则X*为全局极小点；,（1）对于X*在可行域中的一个邻域，恒有，则X*为局部极小点；,一.局部极小点与全局极小点,二.有约束最优解的一阶必要条件,（Lagrange函数）,*Lagrange乘子,*可正可负，但必须有解,（1）EP型,分EP型、IP型、GP型逐步深入讨论。,（2）IP型,（Lagrange函数）,U是由起作用约束的下标组成的集合，Lagrange乘子,这就是著名的KuhnTucker(K-T）条件.,如要在条件中考虑所有的不等式约束，