工程最优化第三章.ppt

《工程最优化第三章.ppt》由会员分享，可在线阅读，更多相关《工程最优化第三章.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 非线性规划的几个基本概念非线性规划的几个基本概念 多元函数的多元函数的Taylor展开展开无约束问题的最优性条件无约束问题的最优性条件约束问题的最优性条件约束问题的最优性条件最优化的数值计算方法最优化的数值计算方法要点：要点：方向导数、下降方向、无约束函数极值的必要条件、方向导数、下降方向、无约束函数极值的必要条件、平稳点、平稳点、可行方向、几何最优性条件、起作用约束、可行方向、几何最优性条件、起作用约束、KT定理、定理、KT点、下降迭代算法、算法的收敛性点、下降迭代算法、算法的收敛性3.1 3.1 多元函数泰勒多元函数泰勒(Taylor)(Taylor)的展开公式的展开公式 n

2、元函数元函数f(x1,x2,xn)在点在点x(0)=x1,x2,xnT附近展附近展开到开到二次项二次项的的Taylor公式为公式为余余项项其中其中 xxx(0)=x1x1(0),xnxn(0)T=x1,xnT(1)梯度梯度是向量是向量 f(x(0)梯度的重要性质：梯度的重要性质：几个常用函数的梯度几个常用函数的梯度f(x)=b1x1+bnxn=BTx f(x)=b1,b2,bnT=Bf(x)=x12+xn2=xTx f(x)=2x1,2x2,2xnT=2xf(x)=xTAx(aij=aji)f(x)=2Axf(x)=c+BTx+1/2xTAx f(x)=B+Axx(0)f(x(1)x(1)点点

3、x(0)处的梯度方向与过该点的等值面垂直。处的梯度方向与过该点的等值面垂直。(2)二阶导数矩阵二阶导数矩阵Hesse矩阵矩阵记为记为H(x)n元函数元函数f(x1,x2,xn)的的Taylor展开公式的矩阵形式展开公式的矩阵形式梯梯度度H(x)3.2 3.2 方向导数与最速下降方向方向导数与最速下降方向 （一）方向导数（一）方向导数定义：定义：设设p为从为从x(0)出发的某单位向量，称函数出发的某单位向量，称函数f(x)在点在点x(0)处处沿方向沿方向p的变化率为的变化率为f(x)在点在点x(0)处沿方向处沿方向p的方向导数的方向导数f(x)x(0)Pf(x(0)（二）最速下降（上升）方向（二

4、）最速下降（上升）方向称方向导数小于零的方向为下降方向称方向导数小于零的方向为下降方向,方向导数大于零的方向方向导数大于零的方向为上升方向。为上升方向。最速上升方向为梯度方向最速上升方向为梯度方向 f(x(0)，最速下降方向为负梯度方最速下降方向为负梯度方向向 f(x(0)由于由于上升方向上升方向下降方向下降方向变化率为变化率为0 f(x(0)最速上升方向最速上升方向 f(x(0)最速下降方向最速下降方向x(0)称称为点为点x(0)处的下降方向集合处的下降方向集合3.3 3.3 局部局部最优与全局最优最优与全局最优（一）局部最优一）局部最优定义：定义：设设f(x)是定义在可行域是定义在可行域S

5、上的一个函数，若存在上的一个函数，若存在S中的点中的点x*及其一个及其一个 邻域邻域N(x*)，使得对任意使得对任意x N(x*)，都有都有 f(x*)=f(x)f(x*)0称称x*为为f(x)的局部最小点或极小点；称的局部最小点或极小点；称f*f(x*)为局部最小值为局部最小值（二）全局最优（二）全局最优定义：定义：若存在若存在S中的点中的点x*，使得对所有使得对所有x S，都有都有 f(x*)=f(x)f(x*)0称称x*为为f(x)的全局部最小点或整体最小点；称的全局部最小点或整体最小点；称f*f(x*)为为全局最小值全局最小值xf(x)x1 x2 x3 x4 x5 x6ab3.4 3.

6、4 无约束问题的最优性条件无约束问题的最优性条件研究最优性条件的目的：研究最优性条件的目的：约定：约定：实际问题目标函数可能不连续或导数不存在，甚至是实际问题目标函数可能不连续或导数不存在，甚至是离散函数，最优点可能在不连续点或导数不存在的点。离散函数，最优点可能在不连续点或导数不存在的点。以下讨论时以下讨论时假定假定f(x)处处连续可导处处连续可导.（1）用以求最优点；用以求最优点；（2）用以判定给定点是否为最优点；用以判定给定点是否为最优点；（3）优化方法的基础。优化方法的基础。（一）无约束函数极值的必要条件（一）无约束函数极值的必要条件若若x*是是f(x)的局部最小的局部最小（大）（大）

7、点，则在点，则在x*处必有处必有以及以及Hesse矩阵矩阵是半正定是半正定（半负定）（半负定）的。的。此条件仅是必要的，即对导数存在的点，若不满足上述条件，此条件仅是必要的，即对导数存在的点，若不满足上述条件，肯定不是极值点。但满足此条件，不一定是极值点肯定不是极值点。但满足此条件，不一定是极值点.定义定义：对可微函数：对可微函数f(x),使使的点为的点为平稳点平稳点（或驻点、（或驻点、定点）定点）对一元函数，两个条件变为对一元函数，两个条件变为f(x)0及及f”(x)0.极值点的候选点极值点的候选点平稳点平稳点导数不存在的点导数不存在的点由必要条件可得由必要条件可得“有资格有资格”成为最优成

8、为最优的点的点,如果有充分如果有充分条件该有多好条件该有多好!如如f(x)=x3,当当x=0时，满足上述两个条件，但不是极值点。时，满足上述两个条件，但不是极值点。（二）无约束函数极值的充分条件（二）无约束函数极值的充分条件若点若点x*满足满足 以及以及 是正定是正定（负定）（负定）的，的，则则 x*是是 f(x)的一个严格的局部最小的一个严格的局部最小（大）（大）点。点。例例3.4.1求求f(x1,x2)=2x128x1+2x224x2+20的极值点及极值。的极值点及极值。解：解：先求平稳点先求平稳点平稳点为平稳点为x*2,1THesse矩阵为矩阵为x*2,1T是是f(x)的严格极小点，的严

9、格极小点，f(x*)=10其前主子式其前主子式40，=160Hesse矩阵是正定的。矩阵是正定的。!上上述述最最优优性性条条件件都都是是对对局局部部最最优优点点而而言言的的，工工程程问问题题都都需需要要找找全全局局最最优优点点，这这方方面面已已进进行行大大量量研研究究，但但仍仍没没有有一一个统一的判别方法。个统一的判别方法。如果在可行域中只有一个局部最优点，即为全局最优点，有如果在可行域中只有一个局部最优点，即为全局最优点，有多个局部最优点，则想法全找出来，再比较确定全局最优点。多个局部最优点，则想法全找出来，再比较确定全局最优点。3.5 3.5 约束问题的最优性条件约束问题的最优性条件min

10、f(x)s.t.最优点同时与目标函数及约束函数的性质有关。存在两种情况：最优点同时与目标函数及约束函数的性质有关。存在两种情况：(a)无约束极值点无约束极值点x(0)Sx2x1x2x1SSx(0)=x*x(0)x*(b)无约束极值点无约束极值点x(0)S!目标函数的梯度等于零并不是约束问题的最优性必要条件！目标函数的梯度等于零并不是约束问题的最优性必要条件！带有不等式带有不等式约束约束的优化的优化问题的最优性条件通常是一组不等式与问题的最优性条件通常是一组不等式与方程方程，比较复杂的，很难求解，所以在一般情况下，不是直接，比较复杂的，很难求解，所以在一般情况下，不是直接求解这些条件来获得极值点

11、，而是使用各种迭代法求出近似的求解这些条件来获得极值点，而是使用各种迭代法求出近似的极值点。但极值点。但它它在理论上很重要，在理论上很重要，是各种迭代方法的基础和依据是各种迭代方法的基础和依据。（一）可行方向与起作用约束（一）可行方向与起作用约束 定义：定义：设点设点x x S，p是一个方向，如果存在实数是一个方向，如果存在实数a10,使对所使对所有有 a 0,a1，有，有x x+ap S，则称则称p为点为点x x 的一个的一个可行方向可行方向,或容或容许许方向、允许方向。方向、允许方向。几何上，若从几何上，若从x处沿方处沿方向向p引一射线，若该射引一射线，若该射线起始端有一段在可线起始端有一

12、段在可行域内，则这个方向行域内，则这个方向p就叫可行方向。就叫可行方向。SxpSg1(x)=0g2(x)=0g3(x)=0!是否为可行方向与起始点的位置有关是否为可行方向与起始点的位置有关！(1)(1)若若x x是是S的内点，的内点，则任何方向均为可行方向则任何方向均为可行方向 g1(x)g2(x)g3(x)(2)(2)若若x x是是S的边界点，的边界点，则有的方向不是可行方向则有的方向不是可行方向若若x位于第位于第i个约束上，即个约束上，即 ，若若p为边界点为边界点x的可行方向，的可行方向，则必有则必有 几何最优性条件几何最优性条件:在判定边界点处的方向是否可行方向时，有必要对约束条件进行分

13、类在判定边界点处的方向是否可行方向时，有必要对约束条件进行分类定义：定义：对可行域对可行域S中某个点中某个点x,称成立称成立gi(x)=0的那些不等式约束的那些不等式约束gi(x)0为为 点点x处的起作用约束。称集合处的起作用约束。称集合为在点为在点x处起作用约束的下标集处起作用约束的下标集最优点最优点x*处一定不存在既可行又下降的方向处一定不存在既可行又下降的方向（1.3.4）（1.3.5）（1.3.6）minf(x)s.t.（二）（二）Kuhn-Tucker最优性必要条件最优性必要条件定理：定理：设设x*为非线性规划为非线性规划(1.3.4)-(1.3.6)的最优解，的最优解，f,gi,h

14、j为可微为可微 函数，函数，其中其中=1,2,lT,=1,2,mT称为称为Lagrange乘子向量。乘子向量。以上三式称为以上三式称为KT最优性条件最优性条件，满足此条件的点称为满足此条件的点称为KT点点。如果在如果在x*处各个起作用约束的梯度向量处各个起作用约束的梯度向量 线性无关，线性无关，则存在向量则存在向量,使下述条件成立：使下述条件成立：!在无约束情形下，上述条件等同于梯度等于在无约束情形下，上述条件等同于梯度等于0！互补松驰条件互补松驰条件:在在gi(x)不是起作不是起作用约束时用约束时,i*=0KT条件可写成条件可写成引入广义引入广义Lagrange函数函数和向量函数和向量函数g

15、(x)=g1(x),g2(x),gl(x)T，?如何理解如何理解K-T定理定理?它有什么几何意义它有什么几何意义?下面以最简单的两种情况加以说明：假定不存在等式约束下面以最简单的两种情况加以说明：假定不存在等式约束(m=0)且且n=2（二维），只有一个或两个起作用的不等式约束。（二维），只有一个或两个起作用的不等式约束。先考虑只有一个起作用不等式约束先考虑只有一个起作用不等式约束g(x)0的情况：的情况：此时，此时，K-T条件为条件为（其中其中0）g(x)=0 x1x2Sf(x)的的等等值值线线x(1)x(2)=x*x(1)不是最不是最优点，优点，K-T条件不成立条件不成立x(2)是最是最优点

16、，优点，K-T条件条件成立成立Sg1(x)=0 x1x2g2(x)=0对有两个起作用不等式约束对有两个起作用不等式约束g1(x)0及及g2(x)0的情况：的情况：此时，此时，K-T条件为条件为f(x)的等值线的等值线x(1)x(1)不是不是最优点，最优点，K-T条件条件不成立不成立Sg1(x)=0 x1x2g2(x)=0f(x)的等值线的等值线x*x*是最优是最优点，点，K-T条条件成立件成立K-T条件为条件为!若最优点若最优点x*位于几个起作用不等式约束的交点上，则位于几个起作用不等式约束的交点上，则 位于这些起作用约束的梯度所构成的锥角内位于这些起作用约束的梯度所构成的锥角内 关于关于KT

17、定理的几点说明定理的几点说明（1）定理中向量组定理中向量组 线性无关线性无关 称为约束规范。称为约束规范。但要但要验证是否满足约束规范是很困难的，因为需要事先知道验证是否满足约束规范是很困难的，因为需要事先知道x*。对对一些特定的非线性规划，约束规范总是成立的。（见一些特定的非线性规划，约束规范总是成立的。（见p75)（2）约束规范不满足，定理不一定成立，最优点可以不是约束规范不满足，定理不一定成立，最优点可以不是KT点。点。例例3.5.1验证下面的非线性规划在最优点验证下面的非线性规划在最优点x*处不满足约束规范处不满足约束规范,最优点不是最优点不是K-T点：点：显然最优点显然最优点x*=x

18、1*,x2*T=1,0T,f=f(x*)=4.下面验证在下面验证在x*=1,0T处不满足约束规范。处不满足约束规范。因为因为g1(x*)=0,g2(x*)00，令迭代次数记数变量令迭代次数记数变量k=0；(2)假定已得到假定已得到第第k次近似点次近似点x(k),(但它还不是极小点但它还不是极小点)，这时，这时选择一选择一个个 下降方向下降方向p(k)，即即(3)由由x(k)出发，以出发，以p(k)为方向作射线为方向作射线 x(k)+p(k)（00），），在此射线上选取在此射线上选取 步长因子步长因子k，使使得到的第得到的第k+1k+1次次近似点近似点 x(k+1)=x(k)+kp(k)满足满足

19、 f(x(k+1)f(x(k)；x(k)p(k)x(k+1)(4)检验所得的新点检验所得的新点x(k+1)是否满足精度是否满足精度要求，若满足，就以要求，若满足，就以x(k+1)为为近似的近似的 极小点，终止迭代计算；否则令极小点，终止迭代计算；否则令k=k+1k=k+1，返回返回(2)(2)继续作下一次搜索。继续作下一次搜索。下降迭代算法中，搜索方向下降迭代算法中，搜索方向p(k)和步长因子和步长因子k的选的选择是关键，择是关键，不同的不同的p(k)和和k就就构成不同的算法构成不同的算法2、下降迭代算法的说明、下降迭代算法的说明(1)搜索方向搜索方向p(k)一般一般不可能直接指向极小点，需多

20、次迭代不可能直接指向极小点，需多次迭代(2)搜索步长的选择搜索步长的选择 x(k+1)=x(k)+kp(k)a.固定步长法固定步长法,如如k=1b.一一维精确搜索法维精确搜索法f(x(k)+kp(k)=minf(x(k)+p(k)c.不精确一维搜索法不精确一维搜索法p(k)不一定指向极小点，一维搜索没必要不一定指向极小点，一维搜索没必要非常精确，因为对加速收敛的作用不大，非常精确，因为对加速收敛的作用不大，只要每次迭代函数值有所下降即可。只要每次迭代函数值有所下降即可。(3)算法的算法的收敛性与收敛速度收敛性与收敛速度收敛性：收敛性：算法迭代得到的点序列算法迭代得到的点序列x(k)，能够在有限

21、步内达到问能够在有限步内达到问题的最优解题的最优解x*，或者序列，或者序列x(k)有一个极限点有一个极限点x*，则算法是收敛的则算法是收敛的！收敛的算法不一定是好算法，还要看收敛速度收敛的算法不一定是好算法，还要看收敛速度！x(k)p(k)x(k+1)定义：定义：对于收敛于最优解对于收敛于最优解x*的序列的序列x(k)，若，若存在与存在与k无关的常数无关的常数0和和 1 1，使得当，使得当k k从某个从某个k0开始，即开始，即kk0时，恒成立时，恒成立 则称序列则称序列x(k)具有具有 阶阶收敛速度收敛速度，为收敛系数或收敛比为收敛系数或收敛比 越大，收敛速度越快越大，收敛速度越快 1，01，

22、线性收敛线性收敛1 2，或，或 1，=0超线性收敛超线性收敛 2 2，二阶收敛二阶收敛二次收敛性：二次收敛性：当一个算法用于具有对称正定矩阵的二次函当一个算法用于具有对称正定矩阵的二次函数时，可在有限步迭代内获得极小点。数时，可在有限步迭代内获得极小点。两者不是一回事两者不是一回事f(x)=c+BTx+1/2xTAx(4)迭代终止准则迭代终止准则 由于不知道真正的极小点在哪里由于不知道真正的极小点在哪里,所以不可能计算迭所以不可能计算迭代点接近极小点的精确程度。只能根据计算过程中的一些代点接近极小点的精确程度。只能根据计算过程中的一些信息判断是否终止计算。常用的终止准则有三种：信息判断是否终止计算。常用的终止准则有三种：c.对无约束问题可用对无约束问题可用a.b.其中其中1，2，3称为允许误差。称为允许误差。3、算法的评价准则、算法的评价准则作业：作业：P4499；10P45012；13(1)通用性；通用性；(2)达到一定精度所需计算函数值和导数的次数；达到一定精度所需计算函数值和导数的次数；(3)终止时所用终止时所用CPU时间；时间；(4)收敛性；收敛性；(5)上机准备工作的难易程度。上机准备工作的难易程度。