非线性规划课件.ppt

《非线性规划课件.ppt》由会员分享，可在线阅读，更多相关《非线性规划课件.ppt（84页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、非线性规划第1页，此课件共84页哦1 1 非线性规划基本概念非线性规划基本概念 解：设该学生买入馒头，肉丸子，青菜的数量分别为x1,x2,x3；个人的满意度函数即为效用函数为u(x1,x2,x3)=Ax1a1x2a2x3a3.于是数学模型为 例例7.7.1 1 某高校学生食堂用餐，拟购三种食品，馒头0.3元/个，肉丸子1元/个，青菜0.6/碗.该学生的一顿饭支出不能够超过5元.问如何花费达到最满意？显然，此模型即为非线性.第2页，此课件共84页哦例例7.2 一容器由圆锥面和圆柱面围成一容器由圆锥面和圆柱面围成.表面积为表面积为 ，圆锥部分高为，圆锥部分高为 ，和和圆柱部分高圆柱部分高 之比为之

2、比为 ,为圆柱底圆半径为圆柱底圆半径.求求 使面积最大使面积最大.解：解：由条件由条件 所以，数学模型为：所以，数学模型为：s.t.第3页，此课件共84页哦二、数学模型二、数学模型 称如下形式的数学模型为数学规划（Mathematical Programming 简称MP）n是维欧几里得空间Rn中的向量（点），f(x)称满足约束条件的向量x为（MP）问题的一个可行解，全体可行点组成的集合称为可行域.如果f(x),gi(x),hi(x)均为线性函数，就是前面所学的线性规划问题(LP).如果至少有一个为非线性函数称为非线性规划问题.由于等式约束hi(x)=0等价于下列两个不等式约束 所以(MP)问

3、题又可表示为 第4页，此课件共84页哦1、线性代数知识考虑二次型ZTAZ,Z为n维向量正定的二次型：若对于任意Z0,有ZTAZ0;半正定的二次型：若对于任意Z0,有ZTAZ0;负定的二次型：若对于任意Z0,有ZTAZ0,又存在Z0，有ZTAZf(xf(x)f(x*),),称点称点x x*是是f(x)f(x)的可行解集的可行解集K K上的上的严格整体极小点严格整体极小点.定义定义7.2(7.2(MP)MP)问题的一个可行点问题的一个可行点x x*被称为被称为局部极小点局部极小点，如果存在一个正数，如果存在一个正数使得对于使得对于所有满足关系式所有满足关系式x-xx-x*的可行点的可行点x x都有

4、都有 f(x)f(xf(x)f(x*)成立成立.如果对任意的可行如果对任意的可行点点xK,xxxK,xx*,存在一个正数存在一个正数使得对于所有满足关系式使得对于所有满足关系式x-xx-x*f(xf(x)f(x*)成立成立.则称则称x x*是是f(x)f(x)在在K K上的一个局部严格极小点上的一个局部严格极小点.显然整体极小点一定是局显然整体极小点一定是局部极小点，反之不然部极小点，反之不然.第7页，此课件共84页哦五、凸规划五、凸规划 定义定义7.3 集合集合 被称为被称为 中的一个中的一个凸集凸集，如果对于，如果对于 中任意两点中任意两点 和任一实数和任一实数 ,点点 .几何解释几何解释

5、：当一个集合是凸集时，连接此集合中任意两点的线段也一定包含在此集合内，：当一个集合是凸集时，连接此集合中任意两点的线段也一定包含在此集合内，规定空集规定空集 是凸集是凸集.定义定义7.4 凸函数凸函数：是凸集是凸集 上的实值函数，如果对于上的实值函数，如果对于 中任意两点中任意两点 和任意实数和任意实数 有不等式有不等式 成立成立.严格凸函数严格凸函数：是凸集是凸集 上的实值函数，如果对于上的实值函数，如果对于 中任意两点中任意两点 ，和任意实数，和任意实数 ，有不等式，有不等式 成立成立.第8页，此课件共84页哦定义定义7.5 是定义在凸集是定义在凸集 上的实值函数，如果上的实值函数，如果

6、是是 上凸函数，称上凸函数，称 是是凹函数凹函数.n定理定理7.1 设设 是凸集是凸集 上的凸函数，则上的凸函数，则 在在 中的任一局部极小点都是中的任一局部极小点都是它的整体极小点它的整体极小点.n证明：证明：设设 是一局部极小点而非整体极小点，则必存在可行点是一局部极小点而非整体极小点，则必存在可行点 (可行域可行域).对任一对任一 ，由于，由于 的凸性，有的凸性，有n n 当当 时，时，与与 充分接近，与充分接近，与 是局部极小矛盾是局部极小矛盾.证毕证毕.n定义定义7.6 设有设有(MP)问题问题 ，若可行域，若可行域 是凸集，是凸集，是是 上的上的凸函数，则称此规划问题为凸函数，则称

7、此规划问题为凸规划凸规划.n定理定理7.2 凸规划的任一局部极小解为整体极小解凸规划的任一局部极小解为整体极小解.第9页，此课件共84页哦六、非线性规划问题的求解方法六、非线性规划问题的求解方法迭代法迭代法考虑(MP)问题：一般来说，MP问题难以求得整体极小点，只能求得局部极小点.以后我们说求(MP)问题，指的是求局部极小点.n1、无约束极小化问题n （UMP）（7.6）n这里是 定义在 上的一个实值函数（7.5）第10页，此课件共84页哦定理定理7.3（一阶必要条件）如果（一阶必要条件）如果 是可微函数是可微函数.是上述无约束问题是上述无约束问题（UMP）的一个局部极小点或局部极大点的必要条

8、件是：）的一个局部极小点或局部极大点的必要条件是：.满足满足 的点称为平稳点或驻点的点称为平稳点或驻点.n定理定理7.4 设设 为定义在为定义在 上的二阶连续可微函数，如果上的二阶连续可微函数，如果 是是 的一个局部极小的一个局部极小点，必有点，必有n n 这里这里 表示表示 在在 处的处的Hesse矩阵矩阵.n证明：证明：，根据，根据 在点在点 处的展开式有处的展开式有n n 若若 ，当，当 充分小时，有充分小时，有n n 有有 .这和这和 是是 的极小矛盾的极小矛盾.第11页，此课件共84页哦定理定理7.5 设 是定义在 上的二阶连续可微函数，如果点 满足 ，而且存在 的一个邻域 ，则 是

9、 的一个局部极小点.n在高等数学中求解极值点方法先求出满足在高等数学中求解极值点方法先求出满足 的点及不可导点的点及不可导点.在这在这些点判断些点判断 是否取得极小值是否取得极小值.n2、等式约束的极小化问题、等式约束的极小化问题n考虑考虑 定义定义7.7 7.7 如果在点处线性无关，则称点 是此约束条件的一个正则点.Langrange乘子法：第12页，此课件共84页哦引进拉格朗日函数 其中 被称为拉格朗日乘子向量.n定理定理7.6 设设 是连续可微函数，是连续可微函数，是是 在可行集中的一在可行集中的一个局部极小点个局部极小点.在在 是正则点的假定下必存在一个拉格朗日乘子向量是正则点的假定下

10、必存在一个拉格朗日乘子向量 ，使，使 得满足方程组得满足方程组n对等式约束，用拉格朗日乘子法求解出平稳点，判断是否极值点对等式约束，用拉格朗日乘子法求解出平稳点，判断是否极值点.n用上述解析法求解无约束和等式约束极值问题的平稳点，再判断是否为极值点用上述解析法求解无约束和等式约束极值问题的平稳点，再判断是否为极值点.该方法有一该方法有一定的局限性：定的局限性：n （1）它们要求函数是连续的，可微的，实际问题中不一定满足这一条件；）它们要求函数是连续的，可微的，实际问题中不一定满足这一条件；n （2）上述求平稳点的方程组求解比较困难，有些解不出来；）上述求平稳点的方程组求解比较困难，有些解不出来

11、；n （3）实际问题中有大量的不等式约束）实际问题中有大量的不等式约束.n因此求解非线性规划应有更好的新方法因此求解非线性规划应有更好的新方法.实际应用中一般用迭代法来求解非线性规划问题，实际应用中一般用迭代法来求解非线性规划问题，即求近似最优解的方法即求近似最优解的方法.n 第13页，此课件共84页哦3 3、非线性规划问题的求解方法、非线性规划问题的求解方法迭代法迭代法迭代法一般过程为：在迭代法一般过程为：在(MP)(MP)问题的可行域问题的可行域 内选择初始点内选择初始点 ，确确定定某某一一方方向向 ，使使目目标标函函数数 从从 出出发发，沿沿 方方向向使使目目标标函函数数值值下下降降，即

12、即 ，有有 ，进进一一步步确确定定 ，使使 ，令令 .如如果果 已已满满足足某某终终止止条条件件，为为近近似似最最优优解解.否否则则，从从 出出发发找找一一个个方方向向 ，确确定定步步长长 ，使使 ，有有 .如如此此继继续续，将将得得到到点点列列 .显显然然有有 ,即即 点点列列 相相对对应应的的目目标标函函数数是是一一个个单单调调下下降降的的数数列列.当当 是是有有穷穷点点列列时时，希希望望最最后后一一个个点点是是(MP)(MP)问问题题的的某某种种意意义义下下的的最最优优解解.当当 为为无无穷穷点点列列时时，它它有有极极限限点点，其其极极限限点点是是(MP)(MP)的的某某种种意义下的最优

13、解（此时称该方法是收敛的）意义下的最优解（此时称该方法是收敛的）.第14页，此课件共84页哦迭代法一般步骤：迭代法一般步骤：1.1.选取初始点选取初始点x x0 0,k:=0,k:=0 2.2.构造搜索方向构造搜索方向p pk k 3.3.根据根据p pk k方向确定方向确定k k 4.4.令令x xk+1k+1 x xk kk kp pk k 5.5.若若x xk+1k+1已满足某终止条件，停止迭代，输出近似最优解已满足某终止条件，停止迭代，输出近似最优解x xk+1k+1.否则令否则令k:=k+1,k:=k+1,转向第二步转向第二步.迭代法求解迭代法求解(MP)MP)的注意点：构造的点列的

14、注意点：构造的点列 x xk k，其极限点应是近似最优解，其极限点应是近似最优解，即该算法必须是收敛的即该算法必须是收敛的.第15页，此课件共84页哦迭代法的关键：迭代法的关键：(1)如何构造每一轮的搜索方向pk;(2)确定步长k 关于k，前面是以minf(xk+pk)产生的，也有些算法k取为一个固定值，这要根据具体问题来确定.关于Pk的选择，在无约束极值问题中只要是使目标函数值下降的方向就可以了，对于约束极值问题则必需为可行下降方向.(3)在无约束最优化中，当函数梯度的模充分小时,(2)当函数值的下降量充分小时，(1)自变量的改变量充分小时，计算终止条件计算终止条件 在上述迭代中有：若在上述

15、迭代中有：若x xk+1k+1满足某终止条件则停止计算，输出近似最优解满足某终止条件则停止计算，输出近似最优解x xk+1k+1.这这里满足某终止条件即到达某精确度要求里满足某终止条件即到达某精确度要求.常用的计算终止条件有以下几个：常用的计算终止条件有以下几个：第16页，此课件共84页哦定义7.8 设，若存在使，则称向量是函数在点处的下降方向.n定义定义7.9 设，若存在使得，称向量设，若存在使得，称向量是点处关于的可行方向是点处关于的可行方向.若一个向量既是目标函数在点处的若一个向量既是目标函数在点处的下降方向，又是该点处关于可行域的可行方向，则称为函数在点处下降方向，又是该点处关于可行域

16、的可行方向，则称为函数在点处关于区域的可行下降方向关于区域的可行下降方向.n根据不同原理产生了不同的和的选择方法，就产生了各种算法根据不同原理产生了不同的和的选择方法，就产生了各种算法.n在以后的讨论中，一维极值的优化问题是讨论求解步长在以后的讨论中，一维极值的优化问题是讨论求解步长.n无约束极值中讨论的最速下降法，共轭方向法，坐标轮换法，牛顿法，变尺度法及有约无约束极值中讨论的最速下降法，共轭方向法，坐标轮换法，牛顿法，变尺度法及有约束极值中讨论的可行方向法都是根据不同的原理选择得到的迭代算法束极值中讨论的可行方向法都是根据不同的原理选择得到的迭代算法.第17页，此课件共84页哦七、迭代算法

17、的收敛性七、迭代算法的收敛性n定义定义7.10 设有一算法设有一算法A，若对任一初始点（可行点），通过，若对任一初始点（可行点），通过A进行迭代时，或在有限步后进行迭代时，或在有限步后停止得到满足要求的点；或得到一个无穷点列，它的任何一个聚点均是满足要求的停止得到满足要求的点；或得到一个无穷点列，它的任何一个聚点均是满足要求的点，则称此算法点，则称此算法A具有全局收敛性具有全局收敛性.n定义定义7.11 设（设（UMP）问题的目标函数）问题的目标函数 ，为对称半正定矩为对称半正定矩阵，若由算法阵，若由算法A进行迭代时，不论初始点进行迭代时，不论初始点 如何选择，必能在有限步后停止迭代，得到所要

18、求的如何选择，必能在有限步后停止迭代，得到所要求的点，则称此算法点，则称此算法A有二次有限终止性有二次有限终止性.n定义定义7.12 设序列设序列 收敛于收敛于 ，定义满足，定义满足 的非的非负数负数 的上确界为的上确界为 的收敛级的收敛级.n 若序列的收敛级为若序列的收敛级为 ，就称序列是，就称序列是 级收敛的级收敛的.第18页，此课件共84页哦若 且 就称序列是以收敛比 线性收敛的.若 或 且 就称序列是超线性收敛的.n如何判别算法的收敛性和收敛速度问题本书不讨论如何判别算法的收敛性和收敛速度问题本书不讨论.n本书给出的算法中，最速下降法具有全局收敛性、是线性收敛的；本书给出的算法中，最速

19、下降法具有全局收敛性、是线性收敛的；改进牛顿法具有全局收敛性、二次有限终止性、是二阶线性收敛改进牛顿法具有全局收敛性、二次有限终止性、是二阶线性收敛的；变尺度法和共轭方向法具有全局收敛性和二次有限终止性、的；变尺度法和共轭方向法具有全局收敛性和二次有限终止性、是超线性收敛的；是超线性收敛的；Zoutenddijk法不具有全局收敛性、改进的法不具有全局收敛性、改进的T-V 法具有全局收敛性；制约函数法具有全局收敛性法具有全局收敛性；制约函数法具有全局收敛性.关于这些算法的关于这些算法的收敛性的讨论和证明有兴趣的读者可参考其他文献收敛性的讨论和证明有兴趣的读者可参考其他文献.第19页，此课件共84

20、页哦2 一维极值问题的优化方法一维极值问题的优化方法n 前面讨论迭代算法时前面讨论迭代算法时,从从 出发确定沿方向出发确定沿方向 的步长的步长 是这样求解的是这样求解的 这里这里 ,已知已知.所以所以,若记若记 ,则为求解则为求解 的过程的过程.n于是我们考虑如下形式的极值问题于是我们考虑如下形式的极值问题.(7.8)为任意实数为任意实数n很显然可应用高等数学中学过的解析法很显然可应用高等数学中学过的解析法,即令即令 求出平稳点求出平稳点,但如前面所述如果但如前面所述如果该方程解不出来该方程解不出来,怎么办怎么办?可用下述迭代算法可用下述迭代算法0.618法法.第20页，此课件共84页哦定义7

21、.13 定义在 上,若存在点 当 ,有 ,当 时,称 在 中为单峰函数(单谷函数).n显然满足定义要求的点显然满足定义要求的点 是是 在在 中的极小点中的极小点.n在在 中任选两点中任选两点 ,且且 ,根据根据 的单峰性的单峰性,若若 ,则则 必然位于必然位于 内内,如果如果 ,则则 必然位于必然位于 内内.如如果果 ,则则 必然位于必然位于 ,记此区间为记此区间为 .如此继续如此继续,得得闭区间套闭区间套 .显然显然 ，又，又 .由闭区间套性质由闭区间套性质,为极小值点为极小值点.闭区间套的选择方法不同闭区间套的选择方法不同,求得的求得的 的快慢及求解过程的计算量是不的快慢及求解过程的计算量

22、是不一样的，有一个常用的方法是一样的，有一个常用的方法是0.618法法.第21页，此课件共84页哦0.618 0.618 法：法：第22页，此课件共84页哦解：解：，=-3，5 =-3+0.3828=0.056 =0.115 =-3+0.6188=1.944 =7.667由于由于 所以新的不定区间为所以新的不定区间为 ，=-3，1.944由于由于 -=4.944 0.2 :=0.056 :=0.115 =-3+0.3824.944=-1.112 =-0.987如此反复得下表如此反复得下表例例7.3 用0.618法求解：第23页，此课件共84页哦迭代换换1-350.0561.9440.1157.

23、6672-31.944-1.1120.056-0.987-0.9874-1.8320.056-1.112-0.664-0.987-0.9876-1.384-0.664-1.1120.936-0.987-0.9967-1.112-0.664-0.936-0.840-0.996-0.9748-1.112-0.840-1.016-0.936-1.000-0.9969-1.112-0.936第24页，此课件共84页哦3 无约束极值的优化方法无约束极值的优化方法n考虑无约束最优化问题（考虑无约束最优化问题（）n (7.9)n前面已经讨论过前面已经讨论过,求解此无约束优化问题求解此无约束优化问题,可以求出

24、平稳点及不可导点的方法可以求出平稳点及不可导点的方法.令令 ,求出平稳点求出平稳点.如果如果 是正定的是正定的,则则 是是 的严格局部最优解的严格局部最优解.若若 在在 上是凸函数上是凸函数,则是整体最优解则是整体最优解.n在求解在求解 这这 维方程组比较困难时，就用最优化算法维方程组比较困难时，就用最优化算法迭代法迭代法.本节将介绍本节将介绍最速下降法最速下降法,牛顿法牛顿法,共轭方向法共轭方向法,坐标轮换法坐标轮换法,变尺度法变尺度法.这些算法就是用不同的方法来选择这些算法就是用不同的方法来选择搜索方向搜索方向 而得到的而得到的.当然当然 必须是下降方向必须是下降方向.第25页，此课件共8

25、4页哦定理定理7.7 设设 ，在点，在点 处可微处可微,若存在若存在 ,使使 ,则向量则向量 是是 在在 处的处的下降方向下降方向.n证明证明:可微可微(在在 处处)，由泰勒展开式，由泰勒展开式,有有 时时,有有 是是 在点在点 的下降方向的下降方向.证毕证毕.第26页，此课件共84页哦一、最速下降法一、最速下降法 最速下降法又称梯度法最速下降法又称梯度法,选择负梯度方向作为目标函数值下降的方向选择负梯度方向作为目标函数值下降的方向,是比是比较古老的一种算法，其它的方法是它的变形或受它的启发而得到的，因此它是较古老的一种算法，其它的方法是它的变形或受它的启发而得到的，因此它是最优化方法的基础最

26、优化方法的基础.基本思想基本思想:迭代法求解无约束最优化问题的关键是求下降方向迭代法求解无约束最优化问题的关键是求下降方向P Pk k.显然最容易想到的显然最容易想到的是使目标函数值下降速度最快的方向是使目标函数值下降速度最快的方向.从当前点从当前点x xk k出发出发,什么方向是使什么方向是使f(x)f(x)下降速度下降速度最快呢最快呢?略去略去 的高阶无穷小项的高阶无穷小项,取取 时时,函数值下降最多函数值下降最多.而而 为为 在在 处的梯度，处的梯度，所以下降方向所以下降方向P Pk k取为负梯度方向时取为负梯度方向时,目标函数值下降最快目标函数值下降最快.第27页，此课件共84页哦最速

27、下降法迭代步骤:例例7.4 7.4 用最速下降法求解下列无约束优化问题用最速下降法求解下列无约束优化问题 第28页，此课件共84页哦解：很显然，该问题的整体最优解为解：很显然，该问题的整体最优解为 ，令令n易验证易验证 是正定的，是正定的，是整体最优解是整体最优解.n下面用最速下降法求解下面用最速下降法求解取取 由由得得 第29页，此课件共84页哦重复上述过程得重复上述过程得 从上图可知，从上图可知，随着迭代次数的增加，越来越接近与最优解随着迭代次数的增加，越来越接近与最优解 ，同时也看到，随着，同时也看到，随着迭代次数的增加，收敛速度越来越慢迭代次数的增加，收敛速度越来越慢.极小点附近沿着一

28、种锯齿形前进，即产生极小点附近沿着一种锯齿形前进，即产生“拉锯拉锯”现象：现象：沿相互正交的方向小步拐进，趋于最优解的过程非常缓慢沿相互正交的方向小步拐进，趋于最优解的过程非常缓慢.这种现象怎样解释？如何克服？这种现象怎样解释？如何克服？第30页，此课件共84页哦 在求在求 时，由于时，由于 ，求导得，求导得 ，是是 的极小的极小点点.故有故有 ，即，即 ，又，又n，即，即 或或 .也就是最速下降法相邻两个搜索方向是彼此正交的也就是最速下降法相邻两个搜索方向是彼此正交的.因此最速下降法因此最速下降法是局部下降最快，但不一定是整体下降最快的是局部下降最快，但不一定是整体下降最快的.在实际应用中一

29、般开始几在实际应用中一般开始几步用最速下降法，后来用下面介绍的牛顿法步用最速下降法，后来用下面介绍的牛顿法.这样两个算法结合起来，求解速这样两个算法结合起来，求解速度较快度较快.第31页，此课件共84页哦基本思想：考虑无约束优化问题基本思想：考虑无约束优化问题 由前面的讨论知，若能解出方程组由前面的讨论知，若能解出方程组 ，求出平稳点，求出平稳点 ，则可验证，则可验证 是否为极值点是否为极值点.由于由于 难以求解难以求解.如果如果 具有连续的二阶偏导数具有连续的二阶偏导数,则考虑用则考虑用 在点在点 二阶泰勒展开式条件替代二阶泰勒展开式条件替代 ，即由，即由二、牛顿法二、牛顿法 第32页，此课

30、件共84页哦令 即从即从 出发，搜索方向为出发，搜索方向为 ，步长恒为，步长恒为1，得到下一个，得到下一个迭代点迭代点.牛顿法：牛顿法：（1）选取初始点）选取初始点 ，精度，精度 （2）计算）计算 ，如果，如果 ，计算终止，计算终止.否则计算否则计算 ，求出搜索方向，求出搜索方向 .（3）令）令 ，返回（，返回（2）.第33页，此课件共84页哦例例7.5 考虑无约束问题考虑无约束问题试分别取初始点（试分别取初始点（1），（，（2），（，（3），取精度要求，取精度要求 ，用牛顿法求解，用牛顿法求解.解：解：（1）取）取 有有 重复计算结果得下表重复计算结果得下表.为近似最优解为近似最优解.实际上

31、，该问题最优解为实际上，该问题最优解为 第34页，此课件共84页哦迭代次数04.00006.082814.51568.449520.12731.338830.00030.3298400第35页，此课件共84页哦(2)取取 ,同上计算同上计算,得得 有有 ，这一迭代结果收敛到，这一迭代结果收敛到 的鞍点的鞍点 .n(3)取取 ,n ,n即即 不可逆，所以无法求得点不可逆，所以无法求得点 .n牛顿法的主要缺点牛顿法的主要缺点:n该法的某次迭代反而使目标函数值增大该法的某次迭代反而使目标函数值增大(见上例见上例).n初始点初始点 距极小点距极小点 较远时较远时,产生的点列产生的点列 可能不收敛可能不

32、收敛,还会出现还会出现 n 的奇异情况的奇异情况.n 的逆矩阵计算量大的逆矩阵计算量大.第36页，此课件共84页哦牛顿迭代法的主要优点牛顿迭代法的主要优点:n当目标函数当目标函数 满足一定条件满足一定条件,初始点初始点 充分接近极小点充分接近极小点 时时,由牛顿法由牛顿法产生的点列产生的点列 不仅能够收敛到不仅能够收敛到 ,而且收敛速度非常快而且收敛速度非常快.n 实际应用中常将最速下降法和牛顿法结合起来使用实际应用中常将最速下降法和牛顿法结合起来使用.n牛顿法的改进牛顿法的改进:n 上面介绍的牛顿法中上面介绍的牛顿法中,处的搜索方向为处的搜索方向为n,步长恒为步长恒为1.若通过一维搜索来取最

33、优步长若通过一维搜索来取最优步长 ,可防止在迭代中步长恒为可防止在迭代中步长恒为1时标目标函数值增大的可能时标目标函数值增大的可能.第37页，此课件共84页哦 改进的牛顿法改进的牛顿法:n(1)取初始点取初始点 ,允许误差允许误差 .n(2)检验是否满足检验是否满足 ,若是若是,迭代停止迭代停止,得到得到 为近似最优解为近似最优解.否否则进入则进入(3).n(3)令令 .n(4)求求 ,使使 .n(5)令令 ,令令 转转(2).第38页，此课件共84页哦三、坐标轮换法三、坐标轮换法n 既然求解非线性规划问题的迭代法是给出初始点既然求解非线性规划问题的迭代法是给出初始点 ,求出一个方向求出一个方

34、向 ,根据根据 确定步长确定步长 ,使使 ，如果，如果 满足某精度要求则停止，否则继续满足某精度要求则停止，否则继续找方向找方向 .显然构造出搜索方向有一定的困难，能否按既定的搜索方向寻显然构造出搜索方向有一定的困难，能否按既定的搜索方向寻找最优解找最优解,省去找搜索方向省去找搜索方向 呢呢?在最速下降法中我们看到相邻两个搜索方向在最速下降法中我们看到相邻两个搜索方向 和和 是正交的是正交的.n 我们知道在我们知道在 维欧氏空间中坐标轴向量维欧氏空间中坐标轴向量 是正交的，可否选坐标是正交的，可否选坐标轴向量为搜索方向轴向量为搜索方向 呢呢?回答是肯定的，这样我们得到了坐标轮换法回答是肯定的，

35、这样我们得到了坐标轮换法.第39页，此课件共84页哦坐标轮换法基本思想坐标轮换法基本思想:n 从从 出发出发,取取 ,沿沿 进行一维搜索得到进行一维搜索得到 .若满足精度要若满足精度要求求,则停止则停止.否则取否则取 ,.如此继续如此继续 ,取取 ，若，若 满足精度要求满足精度要求,则停止则停止.否则令否则令 ,如如此反复连续此反复连续,可以求出近似最优解可以求出近似最优解.n 坐标轮换法的缺点坐标轮换法的缺点是收敛速度较慢是收敛速度较慢,搜索效率较低搜索效率较低,但基本思想简单但基本思想简单,沿坐沿坐标轴的方向进行搜索标轴的方向进行搜索.,第40页，此课件共84页哦四、共轭方向法和共轭梯度法

36、四、共轭方向法和共轭梯度法n共轭方向法是一类方法的总称共轭方向法是一类方法的总称,它原来是为求解目标函数为二次函数的问题它原来是为求解目标函数为二次函数的问题而设计的而设计的.这类方法的特点是这类方法的特点是:方法中的搜索方向是与二次函数的系数矩阵有关方法中的搜索方向是与二次函数的系数矩阵有关的所谓共轭方向，用这类方法求解元二次函数的极小化问题最多进行次一维的所谓共轭方向，用这类方法求解元二次函数的极小化问题最多进行次一维搜索便可以得到极小点搜索便可以得到极小点.n由于可微的非二次函数在极小点附近的性态近似于二次函数由于可微的非二次函数在极小点附近的性态近似于二次函数,因此这类方法也用因此这类

37、方法也用于求可微的非二次函数的问题于求可微的非二次函数的问题.第41页，此课件共84页哦定义定义7.14 设设 为为 对称正定矩阵对称正定矩阵,如果如果 称称 维向量维向量 和和 关于关于 共轭共轭.n定义定义7.15 设设 为为 中一组向量中一组向量,是一个是一个 对称正定矩阵对称正定矩阵.如果如果 ,称称 为为 共轭向量组共轭向量组,也称它们为一组也称它们为一组 共轭方向共轭方向.n当当 (单位矩阵单位矩阵)时时,为正交方向为正交方向.n定理定理7.8 若若 为矩阵为矩阵 共轭向量组共轭向量组,则它们必线性无关则它们必线性无关.证明证明:若存在若存在 ,使使 ,则对任一则对任一 ,由由 又

38、又,线性无关线性无关.证毕证毕.,第42页，此课件共84页哦 由高等代数知识可知由高等代数知识可知,共轭向量组中最多包含共轭向量组中最多包含 个向量个向量,是向量的维数是向量的维数.反之反之,可以证明可以证明,由由 维空间的任一组基出发可以构维空间的任一组基出发可以构造出一组造出一组 共轭方向共轭方向 .n 前面我们已经讲述了坐标轮换法，在前面我们已经讲述了坐标轮换法，在 维欧几里德空间中维欧几里德空间中 ,是一组线性无关的正交向量是一组线性无关的正交向量.从从 出发出发,依次使用依次使用 作为下降方向进行一维精确搜索作为下降方向进行一维精确搜索来确定来确定 ,重复进行得点列重复进行得点列 ,

39、最终求得满足精度要求的最优解最终求得满足精度要求的最优解.n刚才我们引进了共轭向量组刚才我们引进了共轭向量组 ,又证明了它们的线性无关性又证明了它们的线性无关性,那么是否可以用那么是否可以用这共轭向量组像坐标轮换法一样这共轭向量组像坐标轮换法一样,从从 出发依次用出发依次用 作为下降方向来确定作为下降方向来确定 ,最终求得近似最优解最终求得近似最优解?回答是肯定的回答是肯定的.这个方法称为共轭方向法这个方法称为共轭方向法.n共轭方向法适合任何可微凸函数共轭方向法适合任何可微凸函数,且对于二次函数极值且对于二次函数极值 特别有效特别有效.下面的定理告诉我们下面的定理告诉我们用共轭方向法求解二次函

40、数的极值，经过用共轭方向法求解二次函数的极值，经过 次迭代就能次迭代就能求得最优解求得最优解.第43页，此课件共84页哦定理定理7.9 设设 为为 对称正定矩阵对称正定矩阵,函数函数 ,又设又设为一组为一组 共轭向量组共轭向量组,且每个且每个 是是(下面形成的下面形成的)点点 处的下降方向处的下降方向.则由任一点则由任一点 出发出发,按如下迭按如下迭代至多代至多 步后收敛步后收敛,这里这里 满足满足 .证明证明:欲证至欲证至 多步收敛多步收敛,即证即证 .下证下证 和和 正交正交.又又 和和 正交，正交，又又 线性无关线性无关.是问题的最优解是问题的最优解.证毕证毕.共轭方向法具有二次有限终止

41、性.第44页，此课件共84页哦 由于共轭方向组由于共轭方向组 的取法有很大的随意性的取法有很大的随意性,用不同方式产用不同方式产生一组共轭方向就得到不同的共轭方向法生一组共轭方向就得到不同的共轭方向法.如果利用迭代点处的负梯度向量如果利用迭代点处的负梯度向量为基础产生一组共轭方向为基础产生一组共轭方向,这样的方法叫共轭梯度法这样的方法叫共轭梯度法.下面对二次函数讨论形成下面对二次函数讨论形成 共轭梯度方向的一般方法共轭梯度方向的一般方法,然后引到求然后引到求解无约束化问题上解无约束化问题上.任取初始点任取初始点 ,若若 ,取取 ,从从 点沿方向点沿方向 进行一维搜索进行一维搜索,求得求得 .令

42、令 ,若若 ,则已获得最优解则已获得最优解 .否则，取否则，取 ,其中其中 的选择要使的选择要使 和和 关于关于 共轭，由共轭，由 ,得得 第45页，此课件共84页哦 一般地一般地,若已获得若已获得 共轭方向共轭方向 和依次沿它们进行一维搜和依次沿它们进行一维搜索的得到的点列索的得到的点列 ,若若 ,则最优解为则最优解为 ,否则否则 为使为使 和和 是共轭是共轭,可证可证 所以有所以有 又又 和和 是是 共轭的共轭的.有有 ，得，得 进一步可得进一步可得 综合起来得综合起来得 Fletcher-Reeves公式公式 （7.10）第46页，此课件共84页哦共轭梯度法：共轭梯度法：(1)选取初始点

43、选取初始点 ，给定终止误差，给定终止误差 .(2)计算计算 ，若，若 ,停止迭代，输出停止迭代，输出 .否则进行否则进行(3).(3)取取 ，令，令(4)求求 ，令，令(5)计算计算 ，若，若 ，停止迭代，停止迭代，为最优解为最优解.否则转否则转(6).(6)若若 ，令，令 ，转，转(已经完成一组共轭方向的迭代已经完成一组共轭方向的迭代,进入下一进入下一轮轮)否则转否则转(7)(7)取取 ,其中其中 ,令令 ,转转(4)第47页，此课件共84页哦讨论:当当 是二次函数是二次函数时上述共轭梯度法至多进行时上述共轭梯度法至多进行 步可求得最优解步可求得最优解.当当 不是二次函数不是二次函数,共轭梯

44、度法也可以构造共轭梯度法也可以构造 ,但已不具有有限步收敛的性质，于是和坐标轮换法但已不具有有限步收敛的性质，于是和坐标轮换法一样经过一轮迭代后一样经过一轮迭代后,采用重新开始的技巧采用重新开始的技巧.上述共轭上述共轭梯度法就是带有再开始技巧的梯度法就是带有再开始技巧的F-R法法.第48页，此课件共84页哦例7.6 用F-R法求下面问题 取初始点 ,终止误差为解:在例7.4中已得 最优解第49页，此课件共84页哦五、变尺度法五、变尺度法n 当初始点为当初始点为 的其极值点附近时牛顿法收敛速度很快，但缺点是需的其极值点附近时牛顿法收敛速度很快，但缺点是需计算计算 的逆矩阵，在实际问题中目标函数往

45、往相当复杂，计算二阶导的逆矩阵，在实际问题中目标函数往往相当复杂，计算二阶导数的工作量或者太大或者不可能，在数的工作量或者太大或者不可能，在 的维数很高时，计算逆矩阵也相当的维数很高时，计算逆矩阵也相当费事费事.如果能设法构造另一个矩阵如果能设法构造另一个矩阵 ，用它来逼近二阶导数矩阵的逆矩阵，用它来逼近二阶导数矩阵的逆矩阵 则可避免上述问题则可避免上述问题.n 下面就来下面就来研究如何构造研究如何构造 的近似矩阵的近似矩阵 .我们希望：每一步我们希望：每一步都能以现有的信息来确定下一个搜索方向，每做一次迭代，目标函数值都能以现有的信息来确定下一个搜索方向，每做一次迭代，目标函数值均有所下降，

46、这些近似矩阵最后应收敛于最优解处的海赛矩阵的逆矩阵均有所下降，这些近似矩阵最后应收敛于最优解处的海赛矩阵的逆矩阵 .第50页，此课件共84页哦n于是于是 当当 是非二次函是非二次函数时，令数时，令 （7.11）称为）称为拟牛顿条件拟牛顿条件.n显然，我们构造出来的近似矩阵显然，我们构造出来的近似矩阵 必须满足上述拟牛顿条件及递推性：必须满足上述拟牛顿条件及递推性：，这里，这里 称为矫正矩阵称为矫正矩阵.n记记 有有 .n变尺度法即变尺度法即DEP法是由法是由Davidon首先提出，后来又被首先提出，后来又被Fletcher和和Powell改进的算法改进的算法.记记 （7.12）n 容易验证容易

47、验证 满足拟牛顿条件，称上式为满足拟牛顿条件，称上式为DEP公式公式.第51页，此课件共84页哦变尺度方法计算步骤变尺度方法计算步骤：(1)给出初始点给出初始点 ，允许误差，允许误差 .(2)若若 ，停止，停止，为近似最优解；否则转下一步为近似最优解；否则转下一步.(3)取取 （单位矩阵），（单位矩阵），.(4)求求 ，使，使 .(5)令令 若若 ，为最优解，停止；否则当为最优解，停止；否则当 时，令时，令 转转（）（）.（即迭代一轮（即迭代一轮n次仍没求得最优解，以新的次仍没求得最优解，以新的 为起点重新开始一轮新为起点重新开始一轮新的迭代）的迭代）.计算计算 ，令令 ，转（），转（）.第5

48、2页，此课件共84页哦4 约束极值的最优化方法约束极值的最优化方法n考虑考虑(MP)问题：问题：（7.13）n其中其中 是向量函数是向量函数.n显然显然 n于是（于是（MP）问题可以写为：）问题可以写为：（7.14）第53页，此课件共84页哦一、积极约束一、积极约束n设设 是（是（MP）问题（）问题（5.14）的一个可行解）的一个可行解.对对 来说，在点有两种来说，在点有两种情况：或者情况：或者 ，或者，或者 .时，则不在时，则不在 形成的边界上，称这一约束为形成的边界上，称这一约束为 的的非积极约束非积极约束；时，时，处于由处于由 这个这个约束条件形成的可行域边界上，当约束条件形成的可行域边

49、界上，当 有变化时就不满足的有变化时就不满足的 条件，所条件，所以称为以称为积极约束积极约束，记为：，记为：.n定义定义7.16 设设 满足约束条件满足约束条件 ，如果，如果 ，线性无关，则称点线性无关，则称点 是约束是约束条件的一个条件的一个正则点正则点.第54页，此课件共84页哦二、可行方向、下降方向的代数条件二、可行方向、下降方向的代数条件n可行方向可行方向：设：设 是（是（MP）问题（）问题（5.14）的可行域，）的可行域，,若存在若存在 使得使得 时有时有 ，称，称 为为 点处的一个可行方向点处的一个可行方向.由泰勒公式：由泰勒公式：当当 为为 的积极约束时，有的积极约束时，有 .只

50、要只要 足够小，足够小，和和 同号，于是当同号，于是当 时有时有 .n 当当 为为 的非积极约束时，有的非积极约束时，有 .由由 的连续性，当的连续性，当 足够小时，由保号性知足够小时，由保号性知 .n 所以只要所以只要 ，就可保证，就可保证 ，于是，于是 为为 点点处的一个可行方向处的一个可行方向.n 称称 ，为为 在点在点 处是可行方向的代数条件处是可行方向的代数条件.第55页，此课件共84页哦下降方向下降方向：设：设 是（是（MP）问题的可行域，）问题的可行域，,.若存在若存在 使得使得 时，有时，有 ，称，称 为为 点处的一个下降方向点处的一个下降方向.由泰勒公式：由泰勒公式：当当 足