优化方法的数学基础课件.ppt

1、 二元函数二元函数(定义可微定义可微)在点在点x0处沿某一方向处沿某一方向S的方向导数的方向导数 三元函数三元函数:n元函数在点元函数在点x0处沿处沿S S方向的方向导数方向的方向导数 上式表明了方向导数与偏导数之间的数量关系上式表明了方向导数与偏导数之间的数量关系方向导数是偏导数概念的推广方向导数是偏导数概念的推广方向导数表明了函数方向导数表明了函数f(X)在点在点X(0)沿沿S方向的方向的变化率变化率，它，它是一个是一个标量标量 +函数函数f(X)在在X(0)点处沿点处沿S方向是方向是增加增加的的 -函数函数f(X)在在X(0)点处沿点处沿S方向是方向是减小减小的的0000012121co

2、scoscoscosnnniiiffffxxxfxxxxxxdl二元函数的梯度二元函数的梯度 0001212coscosfffSxxxxx01212coscosffxxx0010122()Tfxffffxxxxxx为函数为函数f(x1，x2)在在x0点处的点处的梯度梯度l梯度的模：梯度的模：11221212coscoscoscoscos,TffffSxxxxfSfSf S 2212fffxx设设12coscosS梯度方向和梯度方向和S 方向重合时，方向导数值最大。方向重合时，方向导数值最大。12coscosS 梯度方向是函数值变化最快的方向，而梯度梯度方向是函数值变化最快的方向，而梯度的模就是

3、函数变化率的最大值的模就是函数变化率的最大值。梯度方向与等值线的关系梯度方向与等值线的关系000()()cos(,)TffSff SS xxxl设：设：l则有则有 为单位方向向量。为单位方向向量。0012012()Tnnfxffffxfxxxfxxxx00001cos()()cos(,)nTiiifffSff SSx xxxxl梯度梯度 模：模：l 函数的梯度方向与函数等值面相垂直，也就函数的梯度方向与函数等值面相垂直，也就是和等值面上过是和等值面上过x0的一切曲线相垂直。的一切曲线相垂直。l 由于梯度的模因点而异，即函数在不同点处由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因

4、此，梯度是函数的的最大变化率是不同的。因此，梯度是函数的一种局部性质。一种局部性质。012201()()niiffxxx0()fxl求函数求函数 在点在点3,2T、2,0T的梯度的梯度l解解 l l在点在点x(1)=3,2T处的梯度为：处的梯度为：22121()44fxxxx112224()2fxxfxfxx在点在点x(1)=3,2T处的梯度为：处的梯度为：在点在点x(2)=2,0T处的梯度为：处的梯度为：若函数在某点取得极值，若函数在某点取得极值，则该点的所有一阶偏导数则该点的所有一阶偏导数 必定为零，即梯度为零必定为零，即梯度为零(1)1(1)2242()24xxfx x一般一般n元二次函

5、数的矩阵式为元二次函数的矩阵式为其中其中C为常数，求梯度为常数，求梯度f f(X(X)。解：解：将二元二次函数矩阵式展开将二元二次函数矩阵式展开若若推广到n元二次函数，则一般n元二次函数梯度 的矩阵表达式为l 复杂函数复杂函数的极值问题，常用的极值问题，常用泰勒展开式泰勒展开式得到得到目标函目标函数在所讨论点的近似表达式数在所讨论点的近似表达式，最常用的是，最常用的是线性近似和线性近似和二次近似二次近似 n n元函数在某点元函数在某点(至少二阶可导至少二阶可导)展开到二次项展开到二次项 写成矩阵形式写成矩阵形式 f(X(X)的二阶导数矩阵，称为的二阶导数矩阵，称为f(X(X)的海森的海森(He

6、ssian)(Hessian)矩矩 阵，海森矩阵是一个阵，海森矩阵是一个nXnnXn的对称矩阵，常用的对称矩阵，常用H(X)H(X)表示表示 332212121()339fxxxxxxl 用泰勒展开将函数用泰勒展开将函数l在点在点 简化成线性函数与二次函数。简化成线性函数与二次函数。l解：函数在点解：函数在点 的函数值、梯度和二阶导数矩阵：的函数值、梯度和二阶导数矩阵：(1)1,1Tx(1)x(1)()3f x(1)211(1)2220369()336xxfxx xx(1)12(1)266012 0()06600 xfxxx11(1)221111xxxx xxl简化的线性函数简化的线性函数(1

7、)(1)(1)22()()()33(1)36Tfffxx xxxxxl简化的二次函数简化的二次函数(1)(1)(1)(1)2(1)(1)1()()()()2TTfffxfxxxx xxxx x2212112366(1)6123xxxxx l1.在在 处取得极值，其必要条件是处取得极值，其必要条件是:l即在极值点处函数的梯度为即在极值点处函数的梯度为n维零向量。维零向量。l 为了判断从上述必要条件求得的为了判断从上述必要条件求得的 是否是是否是极值点，需建立极值的充分条件。极值点，需建立极值的充分条件。l 根据函数在根据函数在 点处的泰勒展开式，考虑上述点处的泰勒展开式，考虑上述极值必要条件，可

8、得相应的充分条件。极值必要条件，可得相应的充分条件。12()0Tnffffxxxxx*x*x*x*x大于0+大于0222211212222*2122222212*()nnnnnfffxx xx xfffx xxx xfffx xx xx 正定xG xl即要求即要求 各阶主子式均大于零。各阶主子式均大于零。()G x*xl全局最优与局部最优全局最优与局部最优?l凸规划凸规划-对非线性规划对非线性规划 凸规划凸规划 凸规划的局部极小点一定是全局极小点凸规划的局部极小点一定是全局极小点 l 不等式约束的多元函数极值的必要条件是著名不等式约束的多元函数极值的必要条件是著名的库恩的库恩-塔克（塔克（Ku

9、hn-Tucker）条件，它是非线性）条件，它是非线性优化问题的重要理论优化问题的重要理论l（1）库恩）库恩塔克条件塔克条件(K-T条件）条件）l对于多元函数不等式的约束优化问题：对于多元函数不等式的约束优化问题：l min()f x.()0(1,2,)jst gjmxl库恩库恩塔克条件表明：如点塔克条件表明：如点 是函数是函数 的极值点，的极值点，要么要么 （此时（此时 ）l要么目标函数的负剃度等于起作用约束梯度的非负要么目标函数的负剃度等于起作用约束梯度的非负线性组合（此时线性组合（此时 ）*()0fx0j*1*()()0(1,2,)()0(1,2,)0(1,2,)mjjjiijjjgfi

10、nxxgjmjmxxxx()f x0jOx1x2极值点处于等值线的中心极值点处于等值线的中心极值点处于两个约束曲线的交点上极值点处于两个约束曲线的交点上xg1(x)0g2(x)0g3(x)0Ox1x2xg1(x)0g2(x)0起作用约束：起作用约束：(*)|(*)0,1,2,jJj gjmxxl库恩库恩塔克条件的几何意义是塔克条件的几何意义是:在约束极小值点在约束极小值点 处，处，函数函数 的负梯度一定能表示成所有起使用约束在的负梯度一定能表示成所有起使用约束在该点梯度（法向量）的非负线性组合。该点梯度（法向量）的非负线性组合。x()f x()()0mjjj Jfgxxx1x2Og2(x)=0

11、g1(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()f x.()0(1,2,)jst gjmx()0(1,2,)khklx10(1,2,)()0()0()ljkjkj JkiiijjghfinxxxgjJjJxlK-T条件：条件：K-T K-T条件是多元函数取得约束极值的必要条件条件是多元函数取得约束极值的必要条件,以用来

12、作为约束极值的判断条件，又可以来直接以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。求解较简单的约束优化问题。例例1-6 1-6 库恩库恩塔克（塔克（K-TK-T）条件应用举例）条件应用举例 2212()(2)minfxxx21122231()1 0()0()0gxxgxgx xxxls.tl判断判断1 0T是否为约束最优点。是否为约束最优点。1211202(2)2()02xxxfxx1211022()11ixxxg x20()1gx(1)当前点当前点 为可行点，因满足约束条件为可行点，因满足约束条件(1)10Tx(1)1(1)2(1)3()0()0()10ggg xxx（2）在）在 起作用约束为起作用约束为g1和和g2,因因 (1)10Tx(3)各函数的梯度：各函数的梯度：(1)3()0gx1122()()()fggxxx12220011 121010（4）求拉格朗日乘子）求拉格朗日乘子l由于拉格朗日乘子均为非负，说明由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足是一个局部最优点，因为它满足K-T条件。条件。(1)10Tx2212min()(2)fxxx21122231()1 0()0()0gxxgxgx xxxls.t