无约束优化的数学基础

无约束优化的数学基础第1页，共57页，2023年，2月20日，星期五第一节多元函数的方向导数

与梯度偏导数：函数对于一个自变量的变化率一个二元函数在处的偏导数：第2页，共57页，2023年，2月20日，星期五一个二元函数在处的沿方向d的导数Ox2x1x10x20x0x1x2dxd12第3页，共57页，2023年，2月20日，星期五一个二元函数在处的沿方向d的导数第4页，共57页，2023年，2月20日，星期五同理，三元函数的方向导数多元函数的方向导数第5页，共57页，2023年，2月20日，星期五三维空间中的方向第6页，共57页，2023年，2月20日，星期五二元函数的梯度令：称为函数在处的梯度。令：第7页，共57页，2023年，2月20日，星期五方向导数的几种形式：第8页，共57页，2023年，2月20日，星期五梯度方向与等值线的关系第9页，共57页，2023年，2月20日，星期五当在平面内画出的等值线可以看出，在等值线的切线方向d是函数变化率为零的方向，即有第10页，共57页，2023年，2月20日，星期五多元函数的梯度第11页，共57页，2023年，2月20日，星期五d方向上的方向导数第12页，共57页，2023年，2月20日，星期五为梯度的模。为梯度方向单位向量，它与函数等值面相垂直。由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。第13页，共57页，2023年，2月20日，星期五梯度两个重要性质：性质一函数在某点的梯度不为零，则必与过该点的等值面垂直；性质二梯度方向是函数具有最大变化率的方向。梯度方向与等值面的关系第14页，共57页，2023年，2月20日，星期五梯度方向与等值面的关系第15页，共57页，2023年，2月20日，星期五求函数在点[3,2]T的梯度。在点x(1)=[3,2]T处的梯度为：解：第16页，共57页，2023年，2月20日，星期五则函数在处的最速下降方向是例：试求目标函数在点处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。解：由于新点是这个方向上的单位向量是：第17页，共57页，2023年，2月20日，星期五几个常用的梯度公式：第18页，共57页，2023年，2月20日，星期五外，最简单最重要的一类就是二次函数。在n元函数中，除了线形函数：或f(X)=aX+c第二节二次函数及正定矩阵第19页，共57页，2023年，2月20日，星期五其中均为常数。且在代数学中将特殊的二次函数称为二次型。其中Q=b=Q为对称矩阵其向量矩阵表示形式是：二次函数的一般形式为：第20页，共57页，2023年，2月20日，星期五若，且X≠0，均有＞0，则称矩阵Q是正定的。对于二次函数，我们更关心的是Q为正定矩阵的情形。若，且X≠0，均有＜0，则称Q是负定的。定义：设Q为n×n对称矩阵一个n×n对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶主子式都是正的。一个n×n对称矩阵Q是负定矩阵的充要条件是矩阵Q的各阶主子式的值负、正相间。第21页，共57页，2023年，2月20日，星期五解：对称矩阵Q的三个主子式依次为：例：判定矩阵Q=是否正定因此知矩阵Q是正定的。第22页，共57页，2023年，2月20日，星期五定理：若二次函数中Q正定，则它的等值面是同心椭球面族，且中心为证明：作变换，代入二次函数式中：根据解析几何知识，Q为正定矩阵的二次型的等值面是以坐标原点为中心的同心椭球面族。由于上式中的是常数，所以的等值面也是以=0为中心的同心椭球面族。回到原坐标系中去，原二次函数就是以为中心的同心椭球面族。而且这族椭球面的中心恰是二次目标函数的唯一极小点第23页，共57页，2023年，2月20日，星期五一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此，对于二次目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于Q为正定的二次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。若算法对于Q为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。第24页，共57页，2023年，2月20日，星期五第三节、多元函数的泰勒展开一元函数在点处的泰勒展开式为其中二元函数在点处的泰勒展开式为其中第25页，共57页，2023年，2月20日，星期五第26页，共57页，2023年，2月20日，星期五其二阶偏导数矩阵：又称海赛hession矩阵其中：第27页，共57页，2023年，2月20日，星期五将二元函数的泰勒展开式推广到多元函数，则在点处泰勒展开式的矩阵形式为其中为函数在点处的梯度第28页，共57页，2023年，2月20日，星期五若将函数的泰勒展开式只取到线性项，即取则是过点和函数所代表的超曲面相切的切平面。第29页，共57页，2023年，2月20日，星期五对二次函数：为二次函数的海赛（Hessian）矩阵，常量矩阵。二次函数的梯度为：第30页，共57页，2023年，2月20日，星期五例：求目标函数f（X）=的梯度和Hessian矩阵。解：因为

则又因为：故Hessian阵为：第31页，共57页，2023年，2月20日，星期五例:

用泰勒展开将函数在点简化成线性函数与二次函数。解：函数在点的函数值、梯度和二阶导数矩阵：第32页，共57页，2023年，2月20日，星期五简化的线性函数简化的二次函数第33页，共57页，2023年，2月20日，星期五第四节无约束优化的极值条件第34页，共57页，2023年，2月20日，星期五对于二元函数，若在点处取得极值，其必要条件是第35页，共57页，2023年，2月20日，星期五例：在处梯度为但只是双曲抛物面的鞍点，而不是极小点。函数的梯度为零的条件仅为必要的，而不是充分的。为了判断从上述必要条件求得的是否是极值点，需建立极值的充分条件。第36页，共57页，2023年，2月20日，星期五现在建立极值的充分条件。根据二元函数在点处的泰勒展开式，考虑上述极值必要条件，有设则第37页，共57页，2023年，2月20日，星期五因为：即要求:或表示为第38页，共57页，2023年，2月20日，星期五该条件反映了海赛函数在处的各阶主子式大于0第39页，共57页，2023年，2月20日，星期五推而广之，多元函数的极小值充分必要条件正定第40页，共57页，2023年，2月20日，星期五【例】试证明函数在点处具有极小值。解：将代入得H(X(0))正定，目标函数在（2,4）处具有极小值。第41页，共57页，2023年，2月20日，星期五当极值点X*能使f（X*）在整个可行域中为最小值时，即在整个可行域中对任一X都有f（X）≥f（X*）时，则X*就是最优点，且称为全域最优点或整体最优点。若f（X*）为局部可行域中的极小值而不是整个可行域中的最小值时，则称X*为局部最优点或相对最优点。

优化设计的目标是全域最优点。函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。第五节凸集、凸函数与凸规划第42页，共57页，2023年，2月20日，星期五下凸的一元函数第43页，共57页，2023年，2月20日，星期五（一）凸集设D为n维欧氏空间中的一个集合，若其中任意两点X(1)、X(2)之间的联接直线都属于D，则称这种集合D为n维欧氏空间的一个凸集。图a是二维空间的一个凸集，而图b不是凸集。二维空间的凸集与非凸集第44页，共57页，2023年，2月20日，星期五凸集的概念可以用数学的语言简练地表示为：如果对一切，及一切满足的实数，点，则称集合为凸集。凸集既可以是有界的，也可以是无界的。n维空间中的维子空间也是凸集（例如三维空间中的平面）。第45页，共57页，2023年，2月20日，星期五凸集具有以下性质：（1）若A是一个凸集，是一个实数，是凸集A中的动点，即，则集合还是凸集（2）若A和B是凸集，、分别是凸集A、B中的动点，即，，则集合还是凸集。（3）任何一组凸集的交集还是凸集。第46页，共57页，2023年，2月20日，星期五这三个性质如图所示凸集的性质+第47页，共57页，2023年，2月20日，星期五（二）凸函数函数如果在连接其凸集定义域内任意两点、的线段上，函数值总小于或等于用及作线性内插所得的值，那么称为凸函数。用数学语言表达为第48页，共57页，2023年，2月20日，星期五在凸函数曲线上取任意两点（对应于X轴上的坐标x1、x2）联成一直线线段，则该线段上任一点（对应于X轴上的x点）的纵坐标Y值必大于或等于该点（X）处的原函数值f(x)。第49页，共57页，2023年，2月20日，星期五下面给出凸函数的一些简单性质：设为定义在凸集上的一个凸函数，对任意实数，则函数也是定义在上的凸函数。设和为定义在凸集上的两个凸函数，则其和也是上的凸函数。对任意两个整数和，函数也是在上的凸函数。第50页，共57页，2023年，2月20日，星期五（三）函数的凸性条件恒成立。方法1：若函数f(x)在D上具有一阶的连续导数，对任意两点x1、x2，

f(x)为凸函数的充要条件是:方法2：若函数f(X)在D上具有二阶的连续导数，则f(X)为凸函数的充要条件是:

G(X)处处半正定第51页，共57页，2023年，2月20日，星期五第52页，共57页，2023年，2月20日，星期五第53页，共57页，2023年，2月20日，星期五（四）凸规划对于约束优化问题若都为凸函数，则称此问题为凸规划。凸规划有如下性质：1）若给定一点，则集合为凸集。此性质表明，当为二元函数时其等值线成大圈套小圈形式。2）可行域