第三章-非线性规划无约束问题的最优化方法课件.ppt

《第三章-非线性规划无约束问题的最优化方法课件.ppt》由会员分享，可在线阅读，更多相关《第三章-非线性规划无约束问题的最优化方法课件.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、研究生课程研究生课程工程数学工程数学之之“最优化方法最优化方法”第三章第三章 无约束问题的最优化方法无约束问题的最优化方法能源与动力工程学院能源与动力工程学院College of Energy and Power Engineering 第三章第三章 无约束问题的最优化方法无约束问题的最优化方法第一节第一节 变量轮换法变量轮换法第二节第二节 最速下降法最速下降法 第三节第三节 牛顿法牛顿法第四节第四节 共轭梯度法共轭梯度法本章主要介绍构造无约束问题本章主要介绍构造无约束问题(多维多维)搜索方向的方法。这些方搜索方向的方法。这些方法大致可分为两类：法大致可分为两类：第一类：直接搜索方法。在搜索过

2、程中，只用到目标函第一类：直接搜索方法。在搜索过程中，只用到目标函数值，不需要计算其导数。例如，数值，不需要计算其导数。例如，变量轮换法变量轮换法 第二类：解析方法。在搜索过程中，要用到目标函数的第二类：解析方法。在搜索过程中，要用到目标函数的导数。例如导数。例如最速下降法、牛顿法、共轭梯度法最速下降法、牛顿法、共轭梯度法等。等。一、基本思想一、基本思想认为最有利的搜索方向是各坐标轴的方向，因此它轮流认为最有利的搜索方向是各坐标轴的方向，因此它轮流按各坐标的方向搜索最优点。按各坐标的方向搜索最优点。过程：从某一个给定点出发，按第过程：从某一个给定点出发，按第i个坐标轴个坐标轴xi的方向搜的方向

3、搜索时，假定有索时，假定有n个变量，则只有个变量，则只有xi在变化，其余在变化，其余(n-1)个变量个变量都取给定点的值保持不变。这样依次从都取给定点的值保持不变。这样依次从x1到到xn做了做了n次单变次单变量的一维搜索，完成了变量轮换法的一次迭代。量的一维搜索，完成了变量轮换法的一次迭代。第第 一一 节节 变变 量量 轮轮 换换 法法二、算法步骤二、算法步骤设问题为设问题为记记即即ei为第为第i个分量为个分量为1，其余分量为，其余分量为0的单位向量。的单位向量。第第1 1步：给定初始点步：给定初始点第第2 2步：步：从从x(1)出发，先沿第出发，先沿第1个坐标轴方向个坐标轴方向e1进行一维搜

4、索，记求得进行一维搜索，记求得的最优步长为的最优步长为l l1，则可得到新的点，则可得到新的点x(2)：第第 一一 节节 变变 量量 轮轮 换换 法法再再从从x(2)出发，先沿第出发，先沿第2个坐标轴方个坐标轴方向向e2进行一维搜索，记求得的最优进行一维搜索，记求得的最优步长为步长为l l2，则可得到新的点，则可得到新的点x(3)：完成了变量轮换完成了变量轮换法的一次迭代法的一次迭代第第 一一 节节 变变 量量 轮轮 换换 法法第第3步：令步：令x(1)=x(n+1)，返回第二步，再沿着各坐标轴方向依次进行，返回第二步，再沿着各坐标轴方向依次进行一维搜索。直到最新点一维搜索。直到最新点x(n+

5、1)满足给定的精度要求为止，输出满足给定的精度要求为止，输出x(n+1)作作为为f(x)极小点的近似值。极小点的近似值。1.坐坐标标轮轮换换法法是是每每次次搜搜索索只只允允许许一一个个变变量量变变化化，其其余余变变量量保保持持不不变变，即即沿沿坐坐标标方方向向轮轮流流进进行行搜搜索索的的寻寻优优方方法法。它它把把多多变变量量的的优优化化问题轮流地转化成单变量的优化问题；问题轮流地转化成单变量的优化问题；特点总结：特点总结：2.算法的基本思想简单，不需要进行导数运算；算法的基本思想简单，不需要进行导数运算；3.搜索效率低，收敛速度慢，只有对那些具有特殊结构的函数使用搜索效率低，收敛速度慢，只有对

6、那些具有特殊结构的函数使用起来尚好。起来尚好。第第 一一 节节 变变 量量 轮轮 换换 法法第第 一一 节节 变变 量量 轮轮 换换 法法例题例题1 1 用变量轮换法求解用变量轮换法求解给定初始点给定初始点当当时，停止迭代时，停止迭代答案：答案：第第 二二 节节 最最 速速 下下 降降 法法解：解：从初始点从初始点出发，沿出发，沿x1轴方向轴方向e1进行一维搜索：进行一维搜索：第第 二二 节节 最最 速速 下下 降降 法法再从再从x(2)点点 出发，沿出发，沿x2轴方向轴方向e2进行一维搜索：进行一维搜索：第第 二二 节节 最最 速速 下下 降降 法法再从再从x(3)点点 出发，沿出发，沿x3

7、轴方向轴方向e3进行一维搜索：进行一维搜索：故故 即为极小点。即为极小点。f(x(4)=0第第 二二 节节 最最 速速 下下 降降 法法因为因为 ，故以，故以x(4)点作为新的点作为新的x(1)，进行新一轮迭代。，进行新一轮迭代。设问题为设问题为一、基本思想一、基本思想式中式中f(x)具有一阶连续偏导数，有极小点具有一阶连续偏导数，有极小点x*。若现已求得若现已求得x*的第的第k次近似值次近似值x(k)，为了求得第，为了求得第k+1次近似值次近似值x(k+1)，需选定方向需选定方向p(k)。p(k)有什么特征呢？有什么特征呢？令令，其中，其中p(k)为某个下降方向。为某个下降方向。现将现将f(

8、x)在在p(k)处展开：处展开：第第 二二 节节 最最 速速 下下 降降 法法略去无穷小，可以得到略去无穷小，可以得到由于由于所以所以上式表明了搜索方向上式表明了搜索方向p(k)应该满足的条件：应该满足的条件：p(k)与与x(k)点的梯度点的梯度 的点积小于的点积小于0。第第 二二 节节 最最 速速 下下 降降 法法因为因为当搜索方向确定后，进行下面的一维搜索：当搜索方向确定后，进行下面的一维搜索：显然，只有显然，只有 时，目标函数值时，目标函数值f(x)在在x(k)点附近下降最快，称点附近下降最快，称之为之为负梯度方向负梯度方向。可以用已经学过的一维可以用已经学过的一维搜索方法进行搜索，求搜

9、索方法进行搜索，求得步长因子得步长因子第第 二二 节节 最最 速速 下下 降降 法法也可以用求导的方法得出最优步长因子也可以用求导的方法得出最优步长因子第第 二二 节节 最最 速速 下下 降降 法法二、最速下降法的算法步骤二、最速下降法的算法步骤第第2 2步：步：求梯度向量的范数求梯度向量的范数第第1 1步：给定初始点步：给定初始点 ，及终止误差，及终止误差 ，令，令k=0=0 若若 ，停止计算，输出，停止计算，输出x(k)作为极小点的近似值，作为极小点的近似值，否则转到下一步。否则转到下一步。第第3 3步：步：构造负梯度方向构造负梯度方向第第4 4步：步：进行一维搜索，求得最佳步长因子进行一

10、维搜索，求得最佳步长因子 后，令后，令然后再令然后再令k=k+1，转到第二步。，转到第二步。第第 二二 节节 最最 速速 下下 降降 法法例题例题2 用最速下降法求解下述函数的极小点。用最速下降法求解下述函数的极小点。给定初始点给定初始点答案：答案：第第 二二 节节 最最 速速 下下 降降 法法解：解：求最佳步长求最佳步长l l0第第 二二 节节 最最 速速 下下 降降 法法则：则：第第 二二 节节 最最 速速 下下 降降 法法三、最速下降法的锯齿现象三、最速下降法的锯齿现象第第 二二 节节 最最 速速 下下 降降 法法一、基本思想一、基本思想为了寻求收敛速度较快的求解无约束问题的优化算法，可

11、在每一轮为了寻求收敛速度较快的求解无约束问题的优化算法，可在每一轮迭代时用适当的二次函数，如迭代时用适当的二次函数，如x(k)点的点的二阶二阶Taylor多项式来近似目标多项式来近似目标函数函数，并用迭代点，并用迭代点x(k)处，处，指向近似二次函数的极小点方向指向近似二次函数的极小点方向作为搜索作为搜索方向方向p(k)。二、牛顿方向和牛顿方法二、牛顿方向和牛顿方法设问题为设问题为式中式中f(x)在在x(k)点处具有二阶连续偏导数，且在点点处具有二阶连续偏导数，且在点x(k)处的黑塞矩阵处的黑塞矩阵 正定，正定，x(k)是是f(x)的一个极小点的第的一个极小点的第k轮估计值。轮估计值。第第 三

12、三 节节 牛牛 顿顿 法法第第 三三 节节 牛牛 顿顿 法法令令则则1.求求Q(x)的平稳点：的平稳点：(数数)(向量向量)(矩阵矩阵)第第 三三 节节 牛牛 顿顿 法法令令 ，记，记x(k+1)为为Q(x)的平稳点的平稳点将将b,A的关系式代入上式，可以得到的关系式代入上式，可以得到令令 牛顿方向牛顿方向所以所以实际上，实际上，牛顿法已经规定步长因子牛顿法已经规定步长因子第第 三三 节节 牛牛 顿顿 法法2.牛顿法的算法步骤牛顿法的算法步骤第第2 2步：步：求梯度向量求梯度向量 ，并计算，并计算第第1 1步：给定初始点步：给定初始点 ，及终止误差，及终止误差 ，令，令k=0=0 若若 ，停止

13、迭代，输出，停止迭代，输出x(k)作为极小点的近似值，作为极小点的近似值，否则转到下一步。否则转到下一步。第第3 3步：步：构造牛顿方向。根据构造牛顿方向。根据 确定确定 第第4 4步：步：根据根据 计算计算x(k+1)作为下一轮迭代点，令作为下一轮迭代点，令k=k+1，转第，转第2步。步。第第 三三 节节 牛牛 顿顿 法法例题例题3 用牛顿法求解用牛顿法求解给定初始点给定初始点答案：答案：与最速下降法的对比：与最速下降法的对比：(1)牛顿法对于二次正定函数只需做牛顿法对于二次正定函数只需做1次迭代就得到最优解，特别次迭代就得到最优解，特别是在极小点附近，收敛性很好，收敛速度快；是在极小点附近

14、，收敛性很好，收敛速度快；(2)最速下降法在极小点附近收敛速度很差。最速下降法在极小点附近收敛速度很差。第第 三三 节节 牛牛 顿顿 法法解：解：构造牛顿方向：构造牛顿方向：所以选取所以选取作为极小点。作为极小点。第第 三三 节节 牛牛 顿顿 法法第第 三三 节节 牛牛 顿顿 法法与最速下降法进行对比与最速下降法进行对比求最佳步长求最佳步长l l0还需要经过还需要经过10次迭代才次迭代才能满足精度要求能满足精度要求第第 三三 节节 牛牛 顿顿 法法3.牛顿法的缺点：牛顿法的缺点：牛顿法要求初始解离最优解不远，若初始点选得离最优解牛顿法要求初始解离最优解不远，若初始点选得离最优解太太远远时，时，

15、牛顿法并不能保证其收敛，甚至也不是下降方向牛顿法并不能保证其收敛，甚至也不是下降方向。因此，。因此，常将常将牛顿法与最速下降法结合起来使用牛顿法与最速下降法结合起来使用。前期使用最速下降法，。前期使用最速下降法，当迭代到一定程度后，改用牛顿法，可得到较好的效果。当迭代到一定程度后，改用牛顿法，可得到较好的效果。4.修正牛顿法修正牛顿法基本思想：基本思想：保留了保留了从牛顿法中选取牛顿方向作为搜索方向，从牛顿法中选取牛顿方向作为搜索方向，摒弃摒弃其其步长恒步长恒为为1的做法，而用一维搜索确定最优步长来构造算法。的做法，而用一维搜索确定最优步长来构造算法。第第 三三 节节 牛牛 顿顿 法法5.修正

16、牛顿法的算法步骤修正牛顿法的算法步骤第第4步：进行一维搜索，求步：进行一维搜索，求l lk，使，使 计算计算x(k+1)作为下一轮迭代点，作为下一轮迭代点，令令k=k+1，转第，转第2步。步。第第1步：给定初始点步：给定初始点 ，及终止误差，及终止误差 ，令，令k=0=0 第第2步：步：求梯度向量求梯度向量 ，并计算，并计算若若 ，停止迭代，输出，停止迭代，输出x(k)作为极小点的近似值，作为极小点的近似值，否则转到下一步。否则转到下一步。第第3步：步：构造牛顿方向。根据构造牛顿方向。根据 确定确定 第第 三三 节节 牛牛 顿顿 法法例题例题4 用修正牛顿法求解用修正牛顿法求解给定初始点给定初

17、始点答案：答案：第第 三三 节节 牛牛 顿顿 法法解：解：第第 三三 节节 牛牛 顿顿 法法构造牛顿方向：构造牛顿方向：从从x(0)出发，沿牛顿方向做出发，沿牛顿方向做一维搜索一维搜索，令步长变量为，令步长变量为l l，最优步长为，最优步长为l l0第第 三三 节节 牛牛 顿顿 法法所以选取所以选取作为极小点。作为极小点。第第 三三 节节 牛牛 顿顿 法法6.修正牛顿法的缺点：修正牛顿法的缺点：修正牛顿法虽然比牛顿法有所改进，但也有不足之处：修正牛顿法虽然比牛顿法有所改进，但也有不足之处：(1)要计算黑塞矩阵及其逆矩阵，工作量较大；要计算黑塞矩阵及其逆矩阵，工作量较大；(2)要求迭代点要求迭代

18、点x(k)处的黑塞矩阵正定。处的黑塞矩阵正定。可是有些函数未必满足上述条件，因而牛顿方向未必是下降的，可是有些函数未必满足上述条件，因而牛顿方向未必是下降的，也有一些函数的黑塞矩阵是不可逆的，因此不能确定后继的迭代也有一些函数的黑塞矩阵是不可逆的，因此不能确定后继的迭代点，导致迭代工作无法进行。点，导致迭代工作无法进行。第第 四四 节节 共共 轭轭 梯梯 度度 法法一、基本思想：一、基本思想：共轭梯度法是基于共轭梯度法是基于共轭方向共轭方向的一种算法。针对目标函数为二次函的一种算法。针对目标函数为二次函数的问题，其搜索方向是与数的问题，其搜索方向是与二次函数系数矩阵二次函数系数矩阵相关的共轭方

19、向。相关的共轭方向。用这类方法求解用这类方法求解n元二次元二次正定函数正定函数的极小问题，最多进行的极小问题，最多进行n次一维次一维搜索。搜索。二、共轭的概念二、共轭的概念定义：设定义：设x，y是是n维欧氏空间中两个向量，即维欧氏空间中两个向量，即 ，若有，若有 ，就，就称称 x与与y是两个正交的向量。又设是两个正交的向量。又设A是一个是一个n阶阶对称正定矩阵对称正定矩阵，若有，若有 ，则称向量，则称向量x，y关于关于A共轭正交，简称关于共轭正交，简称关于A共轭。共轭。第第 四四 节节 共共 轭轭 梯梯 度度 法法例：例：向量向量x，y关于关于A共轭。共轭。向量向量x，y关于关于A共轭。共轭。

20、但是，但是，另外，向量另外，向量(1,0)T与与(0,1)T显然是正交的，但是它们不是关于显然是正交的，但是它们不是关于A共轭。共轭。而向量而向量(1,1)T与与(1,-1)T显然是正交的，而且它们还关于显然是正交的，而且它们还关于A共轭。共轭。第第 四四 节节 共共 轭轭 梯梯 度度 法法三、共轭方向三、共轭方向设一组非零向量设一组非零向量 ，A为为n阶对称正定矩阵，若有下式成阶对称正定矩阵，若有下式成立：立：。称向量组称向量组 关于关于A共轭，也称共轭，也称它们为一组它们为一组A共轭方向，或称为共轭方向，或称为A的的n个共轭方向。个共轭方向。若若A是是n阶单位矩阵时：阶单位矩阵时：则则p(

21、i)，p(j)是正交向量。是正交向量。设有二维二次函数设有二维二次函数其等值线为其等值线为 为以为以x0为中心的椭圆。为中心的椭圆。第第 四四 节节 共共 轭轭 梯梯 度度 法法根据根据可知，可知，x0是是f(x)的极小点。的极小点。设设x1是某等值线上的一点，该等值线在点是某等值线上的一点，该等值线在点x1处的法向量为处的法向量为若记若记又设又设 是该等值线在点是该等值线在点x1处的一个切向量，则有切向量处的一个切向量，则有切向量 与法向量与法向量 正交，即正交，即第第 四四 节节 共共 轭轭 梯梯 度度 法法所以，所以，等值线上一点处的切向量与由该点指向极小点的向量关等值线上一点处的切向量

22、与由该点指向极小点的向量关于于A共轭。共轭。四、正定二次函数的共轭梯度法四、正定二次函数的共轭梯度法用不同方法产生关于用不同方法产生关于A共轭的一组共轭方向组就得到不同的共轭方共轭的一组共轭方向组就得到不同的共轭方向法。用向法。用迭代点处的负梯度向量迭代点处的负梯度向量为基础产生为基础产生一组共轭方向一组共轭方向的方法叫的方法叫做共轭梯度法。做共轭梯度法。因此，对于以上定义的因此，对于以上定义的正定二维二次函数正定二维二次函数，若依次沿着方向若依次沿着方向 和和 进行一维搜索，则经过两次迭代必可到达极小点。进行一维搜索，则经过两次迭代必可到达极小点。第第 四四 节节 共共 轭轭 梯梯 度度 法

23、法考虑考虑第第1步：任意取定初始点步：任意取定初始点x(0)，并取初始搜索方向，并取初始搜索方向p(0)为为x(0)的负梯度的负梯度方向。方向。以以x(0)为出发点沿为出发点沿p(0)方向进行一维搜索：方向进行一维搜索：若若则则x(1)就是最优解，否则继续进行迭代。就是最优解，否则继续进行迭代。第第2步：步：以以x(1)点处的负梯度方向与上一个搜索方向的组合来形成下点处的负梯度方向与上一个搜索方向的组合来形成下一个搜索方向一个搜索方向p(1)，令，令 第第 四四 节节 共共 轭轭 梯梯 度度 法法第第3步：步：以以x(1)点点为出发点沿为出发点沿p(1)方向方向进行进行最佳最佳一维搜索：一维搜

24、索：，为待定常数，使得为待定常数，使得p(1)与与p(0)关于关于A共轭。共轭。第第 四四 节节 共共 轭轭 梯梯 度度 法法若若则则x(2)就是最优解，否则继续进行迭代。就是最优解，否则继续进行迭代。综上所述，对于正定综上所述，对于正定n维二次函数，共轭梯度法的公式为维二次函数，共轭梯度法的公式为第第 四四 节节 共共 轭轭 梯梯 度度 法法(k=0,1,(n-1)(k=0,1,(n-2)Fletcher和和Reeves提提出的，称之为出的，称之为F-R共共轭梯度法轭梯度法第第 四四 节节 共共 轭轭 梯梯 度度 法法例例 利用共轭梯度法求解下列二次函数的极小点利用共轭梯度法求解下列二次函数

25、的极小点解：首先将二次项化成对称正定矩阵的组成形式，即解：首先将二次项化成对称正定矩阵的组成形式，即取取第第 四四 节节 共共 轭轭 梯梯 度度 法法为最优解为最优解第第 五五 节节 最最 小小 二二 乘乘 法法一、测试数据的最小二乘拟合一、测试数据的最小二乘拟合 假设通过某实验获得以下数据假设通过某实验获得以下数据 ti24589yi2.012.983.505.025.47可以假定其近似表达式为线性函数可以假定其近似表达式为线性函数则有则有超定方程，怎么办？超定方程，怎么办？第第 五五 节节 最最 小小 二二 乘乘 法法1.选点法：选点法：2.平均法：平均法：(前三组和后两组分别平均前三组和

26、后两组分别平均)问题：问题：(1)前面两种方法本身没有给出评价解的好坏标准，即怎样的解才前面两种方法本身没有给出评价解的好坏标准，即怎样的解才是最优的？是最优的？(2)前面两种方法也未指出用何种方法求得最优解。前面两种方法也未指出用何种方法求得最优解。为测试数据的为测试数据的残差残差，则可以得到以，则可以得到以 为分量的残差向量为分量的残差向量 第第 五五 节节 最最 小小 二二 乘乘 法法二、二、残差残差 假定有一组离散数据假定有一组离散数据(ti,yi)，可以用函数，可以用函数 来近似表来近似表达，达，显然显然 ，若记，若记评价最优解的标准：通常采用欧氏范数的最小值来确定评价最优解的标准：通常采用欧氏范数的最小值来确定a*，b*，即即