2-优化方法的数学基础

第2章优化方法的数学基础2.1方向导数与梯度2.2多元函数的泰勒展开及海森矩阵2.3无约束优化问题的极值条件2.4凸集、凸函数与凸规划2.5不等式约束优化问题的极值条件定义1.),(yxfz在点存在,xyxyxfz对在点),(),(00的偏导数，记为),(00yx的某邻域内;),(00yxxfxx00x则称此极限为函数极限设函数)(0xf)()(00xfxxfx0limxx;),(00yxxz0ddxxxy.),(001yxfxyxfyxxfx),(),(lim00000),(00yxfx注意:偏导数一、方向导数二元函数偏导数的几何意义:00),(dd00xxyxfxxfxxyy0),(yyyxfzxTM000),(dd00yyyxfyyfxxyy是曲线yTM0在点M0处的切线对x轴的斜率.在点M0处的切线斜率.是曲线yxz0xyToxT0y0M对y轴的l),,(zyxP一、方向导数定义:若函数),,(zyxff0lim则称lf为函数在点P处沿方向l的方向导数.),,(),,(lim0zyxfzzyyxxf在点),,(zyxP处沿方向l(方向角为,,)存在下列极限:P记作方向导数与偏导数的公式推导二元函数(定义可微)在点x0处沿某一方向s的方向导数三元函数:方向导数与偏导数的关系n元函数在点x0处沿d方向的方向导数◆上式表明了方向导数与偏导数之间的数量关系◆方向导数是偏导数概念的推广◆方向导数表明了函数f(X)在点X(0)沿S/d方向的变化率，它是一个标量+函数f(X)在X(0)点处沿S方向是增加的-函数f(X)在X(0)点处沿S方向是减小的0000012121coscoscoscosnnniiiffffxxxfxxxxxxd2、梯度二元函数的梯度（二元函数方向导数的表达式）0001212coscosfffxxxxxd01212coscosffxxx0010122()Tfxffffxxxxxx为函数f(x1，x2)在x0点处的梯度梯度的模：1212coscoscos,Tfffxxfffdddd2212fffxx设12coscosd梯度方向和d方向重合时，方向导数值最大。将两个向量梯度和d的内积写成向量之间的投影形式12coscosd梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值。梯度方向与等值线的关系000()()cos(,)Tffffxxdxdd设：则有为单位向量。多元函数的梯度0012012()Tnnfxffffxfxxxfxxxx00001cos()()cos(,)nTiiifffffxxxxdxdd梯度模：函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。012201()()niiffxxx0()fx例题2-1求函数在点[3,2]T、[2,0]T的梯度解在点x(1)=[3,2]T处的梯度为：22121()44fxxxx112224()2fxxfxfxx在点x(1)=[3,2]T处的梯度为：在点x(2)=[2,0]T处的梯度为：◆若函数在某点取得极值，则该点的所有一阶偏导数必定为零，即梯度为零(1)1(1)2242()24xxfxx2.2多元函数的泰勒展开及海森矩阵◆复杂函数的极值问题，常用泰勒展开式得到目标函数在所讨论点的近似表达式，最常用的是线性近似和二次近似n元函数在某点(至少二阶可导)展开到二次项写成矩阵形式返回f(X)的二阶导数矩阵，称为f(X)的海森(Hessian)矩阵，海森矩阵是一个nXn的对称矩阵，常用H(X)表示例题332212121()339fxxxxxx用泰勒展开将函数在点简化成线性函数与二次函数。解：函数在点的函数值、梯度和二阶导数矩阵：(1)[1,1]Tx(1)x(1)()3fx(1)211(1)2220369()336xxfxxxx(1)12(1)2660120()06600xfxxx11(1)221111xxxxxx简化的线性函数(1)(1)(1)22()()()[]33(1)36Tfffxxxxxxx简化的二次函数(1)(1)(1)(1)2(1)(1)1()()()[][]()[]2TTfffxfxxxxxxxxx2212112366(1)6123xxxxx2.3无约束优化问题的极值条件1.在处取得极值，其必要条件是:即在极值点处函数的梯度为n维零向量。为了判断从上述必要条件求得的是否是极值点，需建立极值的充分条件。根据函数在点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。12()[]0Tnffffxxxxx*x*x*x2.处取得极值充分条件222211212222*2122222212*()nnnnnfffxxxxxfffxxxxxfffxxxxx正定xGx即要求各阶主子式均大于零。()Gx*x2．4凸集、凸函数与凸规划全局最优与局部最优???1、凸集几何特征是：其任意两点连线上的一切点都位于这个集合内2、凸函数对凸集D内，任两点X(1)、X(2)及0α1f(X)为凸函数几何意义为：这两个点的连线完全处在f(X)曲线(曲面)的上方，或在f(X)曲线(曲面)上判定一个函数的凸性，可利用以下性质：f(X)为一阶连续导数，f(X)在凸集D上为凸函数的充分必要条件为f(X)为二阶连续导数，f(X)在凸集D上为凸函数的充分必要条件为H(X)0凸规划----对非线性规划f(X)与g(X)均为凸函数凸规划★凸规划的局部极小点一定是全局极小点2.5不等式约束优化问题的极值条件不等式约束的多元函数极值的必要条件是著名的库恩--塔克（Kuhn-Tucker）条件，它是非线性优化问题的重要理论（1）库恩—塔克条件(K-T条件）对于多元函数不等式的约束优化问题：min()fx..()0(1,2,,)jstgjmx库恩—塔克条件表明：如点是函数的极值点，要么（此时）要么目标函数的负剃度等于起作用约束梯度的非负线性组合（此时）K-T条件*()0fx0j**1*()()0(1,2,,)()0(1,2,,)0(1,2,,)mjjjiijjjgfinxxgjmjmxxxx()fx0jOx1x2极值点处于等值线的中心极值点处于两个约束曲线的交点上x﹡g1(x)＝0g2(x)＝0g3(x)＝0Ox1x2x﹡g1(x)＝0g2(x)＝0起作用约束：(*){|(*)0,1,2,}jJjgjmxx库恩—塔克条件的几何意义是:在约束极小值点处，函数的负梯度一定能表示成所有起使用约束在该点梯度（法向量）的非负线性组合。x()fx()()0mjjjJfgxxx1x2Og2(x)=0g1(x)=0f(x)=Cg2(xk)g1(xk)－f(xk)xk可行域点xk处的切平面x1x2Og2(x)=0g1(x)=0f(x)=Cg2(xk)g1(xk)－f(xk)xk可行域点xk处的切平面(a)(b)同时具有等式和不等式约束的优化问题:min()fx..()0(1,2,,)jstgjmx()0(1,2,,)khklx10(1,2,,)()0()0()ljkjkjJkiiijjghfinxxxgjJjJxK-T条件：K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。例1-6库恩—塔克（K-T）条件应用举例2212()(2)minfxxx21122231()10()0()0gxxgxgxxxxs.t判断[10]T是否为约束最有点。1211202(2)2()02xxxfxx1211022()11ixxxgx20()1gx(1)当前点为可行点，因满足约束条件(1)[10]Tx(1)1(1)2(1)3()0()0()10gggxxx（2）在起作用约束为g1和g2,因(1)[10]Tx(3)各函数的梯度：(1)3()0gx1122()()()fggxxx12220011121010（4）求拉格朗日乘子由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足K-T条件。(1)[10]Tx2212min()(2)fxxx21122231()10()0()0gxxgxgxxxxs.t