最优化方法课件：第二章 优化方法的数学基础

第二章优化方法的数学基础§2-1方向导数与梯度§2-2

凸集、凸函数与凸规划§2-3

二次函数及正定矩阵§2-4无约束优化问题的极值条件

§2-5有约束优化问题的极值条件2022/10/221引例：一块长方形的金属板，中心在坐标原点处。在原点处有一个火焰，它使金属板受热．在(3,2)处有一个蚂蚁，问这只蚂蚁应沿什么方向爬行才能最快到达较凉快的地点？问题的实质：应沿由热变冷变化最骤烈的方向爬行．§2-1方向导数与梯度2022/10/222

讨论函数在一点P沿某一方向的变化率问题．．引射线内有定义，自点的某一邻域在点设函数lPPUyxP)(),(),(,).(pUP'lyyxxPlxD+D+上的另一点且为并设为的转角轴正向到射线设j一、方向导数的定义2022/10/223当沿着趋于时，且考虑板书三维图2022/10/224}0,1{1=er依定义，函数),(yxf在点P沿着x轴正向、y轴正向}1,0{2=er的方向导数分别为yxff,沿着x轴负向、y轴负向的方向导数是

yxff--,.的方向导数．沿方向则称这极限为函数在点在，时，如果此比的极限存趋于沿着当之比值，两点间的距离与函数的增量定义lPPlP'yxP'PD+D=22)()(r记为2022/10/225故有方向导数二、方向导数的计算2022/10/226例1

求函数yxez2=在点)0,1(P处沿从点

)0,1(P到点)1,2(-Q的方向的方向导数.解故x轴到方向lr的转角4p-=j.所求方向导数这里方向lr即为}1,1{-=PQ2022/10/227解由方向导数的计算公式知例2

求函数在点沿与x轴方向夹角为a的方向射线lr的方向导数.问在怎样的方向上此方向导数有

（1）最大值；

（2）最小值；

（3）等于零？2022/10/228故（1）当4p=a时，方向导数达到最大值2;（3）当43p=a和47p=a时，方向导数等于0.（2）当45p=a时，方向导数达到最小值-22022/10/2292022/10/2210对于三元函数),,(zyxfu=，它在空间一点),,(zyxP沿着方向L的方向导数

，可定义为推广可得三元函数方向导数的定义其中2022/10/2211n元函数在点x0处沿s方向的方向导数：

2022/10/2212三、

函数的梯度为函数F(x1，x2)在X0点处的梯度。梯度-向量?:最快沿哪一方向增加的速度函数在点问题X02022/10/2213梯度的模：设s=2022/10/2214

梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值。设：则有为单位向量。梯度方向和s方向重合时，方向导数值最大。变化率为零?变化率最大?2022/10/2215在几何上表示一个曲面曲面被平面所截得所得曲线在xoy面上投影如图等高线梯度为等高线上的法向量2022/10/2216梯度两个重要性质：

性质一函数在某点的梯度不为零，则必与过该点的等值面垂直；性质二梯度方向是函数具有最大变化率的方向。图

梯度方向与等值面的关系2022/10/2217多元函数的梯度：2022/10/2218函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的切线相垂直。

由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。梯度模：2022/10/2219例3:求函数在点[3,2]T的梯度。在点x(1)=[3,2]T处的梯度为：解：2022/10/2220例4求函数在点x1=

[3,2]T和

x2=[1,2]T的梯度,并作图表示。解：2022/10/2221则函数在X0处的最速下降方向是例5：试求目标函数在点处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。解：由于这个方向上的单位向量是：2022/10/2222例5：试求目标函数在点处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。新点是这个方向上的单位向量是：0.722022/10/2223练习：

求函数

yxzyxu2332222-+++=在点

)2,1,1(处的梯度，并问在

哪些点处梯度为零？解由梯度计算公式得在)0,21,23(0-P处梯度为0.2022/10/2224几个常用的梯度公式：2022/10/2225在整个可行域中对任一X都有f（X）≥f（X*）时，则X*就是最优点，且称为全域最优点或整体最优点。若f（X*）为局部可行域中的极小值而不是整个可行域中的最小值时，则称X*为局部最优点或相对最优点。最优化设计的目标是全域最优点。函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。为了研究函数的凸性，现引入凸集的概念：§2-2凸集、凸函数与凸规划2022/10/2226一、凸集集合D为n维欧氏空间的一个凸集。图

二维空间的凸集与非凸集X（1）、X（2）两点之间的联接直线，可用数学式表达为:式中为由0到1（0≤≤1）间的任意实数。2022/10/2227二、凸函数

具有凸性（表现为单峰性）或只有唯一的局部最小值亦即全域最优值的函数，称为凸函数或单峰函数。其数学定义是：设f（X）为定义在凸集D上的函数，如果对任何实数α（0≤α≤1）以及对D中任意两点X(1)、X(2)恒有:则f（X）为D上的凸函数，若不等式反向，则为凹函数。2022/10/2228凸函数的几何意义如图所示：在凸函数函数值曲线上取任意两点联成一直线线段，则该线段上任一点的值必大于或等于两点间的函数值。

图2-4一元凸函数的几何意义2022/10/2229凸函数的一些性质：

1）若

f（X）为定义在凸集D上的一个凸函数，且

a是一个正数（a>0），则

af（X）也必是定义在凸集D上的凸函数；

3）若f1(X），f2(X)为定义在凸集D上的两个凸函数，α和β为两个任意正数，则函数afl（X）＋βf2(X)仍为D上的凸函数。

2）定义在凸集D上的两个凸函数f1(X），f2(X)，其和f（X）=f1（X）十f2（X）亦必为该凸集上的一个凸函数。

4）若f（X）为定义在凸集D上且具有连续一阶导数的函数，则f（X）为凸函数的充分必要条件为：对任意两点X（1），X（2），不等式恒成立：2022/10/22302022/10/2231三、凸规划对于约束优化问题式中若F（X）、均为凸函数，则称此问题为凸规划。2022/10/2232凸规划的一些性质：

2）凸规划问题中的任何局部最优解都是全局最优解；

3）若F（X）可微，则X*为凸规划问题的最优解的充分必要条件为：对任意，对满足

1）可行域为凸集；2022/10/2233不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。注意：2022/10/2234外，最简单最重要的一类就是二次函数。在n元函数中，除了线性函数：或f(X)=aX+c§2-3

二次函数及正定矩阵2022/10/2235其中均为常数：其向量矩阵表示形式是：二次函数的一般形式为：其中Q=b=Q为对称矩阵2022/10/2236若，X≠0，均有＞0，则称矩阵Q是正定的。

若，且X≠0，均有＜0，则称Q是负定的。定义：设Q为n×n对称矩阵在代数学中将特殊的二次函数称为二次型。对于二次函数，我们更关心的是Q为正定矩阵的情形。2022/10/2237解：对称矩阵Q的三个主子式依次为：例：判定矩阵Q=是否正定一个n×n对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶主子式都是正的。一个n×n对称矩阵Q是负定矩阵的充要条件是矩阵Q的各阶主子式的值负、正相间。因此知矩阵Q是正定的。2022/10/2238定理：若二次函数中Q正定，则它的等值面是同心椭球面族，且中心为前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。特别地若算法对于Q为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。这族椭球面的中心是二次目标函数的唯一极小点。2022/10/22392022/10/2240求函数极值问题中，对复杂的问题，常用简单函数来逼近，最简单最重要的一类就是二次函数。§2-4

无约束优化问题的极值条件一元函数的泰勒展开2022/10/2241一、多元函数的泰勒展开二元函数：二元函数：在点Xk处2022/10/2242多元函数泰勒展开:海色矩阵（Hessian）2022/10/2243对二次函数：为二次函数的海色（Hessian）矩阵，常量矩阵。2022/10/2244例：求目标函数的梯度和Hesse矩阵。解：因为

则又因为：故Hesse阵为：2022/10/2245例题:

用泰勒展开将函数在点简化成线性函数与二次函数。解：函数在点的函数值、梯度和二阶导数矩阵：2022/10/2246简化的线性函数:简化的二次函数:2022/10/2247二、无约束优化问题的极值条件

1.F(x)在处取得极值，其必要条件是:即在极值点处函数的梯度为n维零向量。2022/10/2248函数的梯度为零的条件仅为必要的，而不是充分的。则称为f的驻点。定义：设是D的内点，若:例：在处梯度为但只是双曲抛物面的鞍点，而不是极小点。2022/10/2249根据函数在点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。为了判断从上述必要条件求得的是否是极值点，需建立极值的充分条件。2022/10/22502.处取得极值充分条件海色（Hessian）矩阵正定，即各阶主子式均大于零，则X*为极小点。海色（Hessian）矩阵负定，即各阶主子式负、正相间，则X*为极大点。正定或负定2022/10/2251§2-5约束优化问题的极值条件

不等式约束的多元函数极值的必要条件是著名的库恩--塔克（Kuhn-Tucker）条件具有等式和不等式约束的优化问题:2022/10/2252图约束问题的极值2022/10/2253图约束问题的极值2022/10/2254图约束问题的极值2022/10/2255对于等式约束优化问题：可以建立如下拉格朗日函数：令▽L(X,λ)=0：2022/10/2256对于一般约束优化问题：引入松弛变量2022/10/2257库恩—塔克条件表明：如点是函数的极值点，要么要么目标函数的负梯度等于起作用约束梯度的非负线性组合。对于一般约束优化问题，K-T条件：2022/10/2258x1x2Og2(x)=0g1(x)=0F(x)=Cg2(xk)g1(xk)－F(xk)xk可行域点xk处的切平面x1x2Og2(x)=0g1(x)=0F(x)=Cg2(xk)g1(xk)－F(xk)xk可行域