无约束优化的数学基础

无约束优化的数学基础第一页，共五十七页，编辑于2023年，星期六第一节多元函数的方向导数

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

则又因为：故Hessian阵为：第三十一页，共五十七页，编辑于2023年，星期六例:

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

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

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

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