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

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

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

3、搜索时，假定有索时，假定有n个变量，则只有个变量，则只有xi在变化，其余在变化，其余(n-1)个变量个变量都取给定点的值保持不变。这样依次从都取给定点的值保持不变。这样依次从x1到到xn做了做了n次单变次单变量的一维搜索，完成了变量轮换法的一次迭代。量的一维搜索，完成了变量轮换法的一次迭代。第第 一一 节节 变变 量量 轮轮 换换 法法二、算法步骤二、算法步骤设问题为设问题为()()min,nf xxRf xR挝记记()()0,.,1,.,01,2,.,Tiein=即即ei为第为第i个分量为个分量为1，其余分量为，其余分量为0的单位向量。的单位向量。第第1 1步：给定初始点步：给定初始点()(

4、)112,.,Tnxc cc=第第2 2步：步：从从x(1)出发，先沿第出发，先沿第1个坐标轴方向个坐标轴方向e1进行一维搜索，记求得进行一维搜索，记求得的最优步长为的最优步长为l l1，则可得到新的点，则可得到新的点x(2)：()()()()()()()()2111 11211 1minf xf xef xexxellll=+=+=+第第 一一 节节 变变 量量 轮轮 换换 法法再再从从x(2)出发，先沿第出发，先沿第2个坐标轴方个坐标轴方向向e2进行一维搜索，记求得的最优进行一维搜索，记求得的最优步长为步长为l l2，则可得到新的点，则可得到新的点x(3)：()()()()()()()()

5、11 11minnnnn nnnn nf xf xef xexxellll+=+=+=+()()()()()()()()3222 21322 2minf xf xef xexxellll=+=+=+完成了变量轮换完成了变量轮换法的一次迭代法的一次迭代第第 一一 节节 变变 量量 轮轮 换换 法法第第3步：令步：令x(1)=x(n+1)，返回第二步，再沿着各坐标轴方向依次进行，返回第二步，再沿着各坐标轴方向依次进行一维搜索。直到最新点一维搜索。直到最新点x(n+1)满足给定的精度要求为止，输出满足给定的精度要求为止，输出x(n+1)作作为为f(x)极小点的近似值。极小点的近似值。1.坐标轮换法是

6、每次搜索只允许一个变量变化，其余变量保持不坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量的优化问题；问题轮流地转化成单变量的优化问题；特点总结：特点总结：2.算法的基本思想简单，不需要进行导数运算；算法的基本思想简单，不需要进行导数运算；3.搜索效率低，收敛速度慢，只有对那些具有特殊结构的函数使用搜索效率低，收敛速度慢，只有对那些具有特殊结构的函数使用起来尚好。起来尚好。第第 一一 节节 变变 量量 轮轮 换换 法法第第 一一 节节 变变 量量 轮轮 换

7、换 法法例题例题1 1 用变量轮换法求解用变量轮换法求解()222123min32f xxxx=+给定初始点给定初始点()()11,2,3Tx=当当()()110.01nxx+-时，停止迭代时，停止迭代答案：答案：()()10,0,0Tx=第第 二二 节节 最最 速速 下下 降降 法法解：解：()()()()()()()()()()()()()()()123111221221121211,0,0,0,1,0,0,0,11,2,31112023033 12233 1170111021 02303TTTTeeexxef xefxxef xlllllllll=轾轾轾+犏犏犏犏犏犏+=+=犏犏犏犏犏犏

8、臌臌臌+=+=+=-轾轾轾犏犏犏犏犏犏=+=+-=犏犏犏犏犏犏臌臌臌17从初始点从初始点出发，沿出发，沿x1轴方向轴方向e1进行一维搜索：进行一维搜索：()()()()()()()()()222223232 20002123032 290200022 109303xef xfxxef xlllllll轾轾轾犏犏犏犏犏犏+=+=+犏犏犏犏犏犏臌臌臌=+=-轾轾轾犏犏犏犏犏犏=+=+-=犏犏犏犏犏犏臌臌臌第第 二二 节节 最最 速速 下下 降降 法法再从再从x(2)点点 出发，沿出发，沿x2轴方向轴方向e2进行一维搜索：进行一维搜索：第第 二二 节节 最最 速速 下下 降降 法法()()()()(

9、)()()()3323334343 30000003133030000 xef xefxxef xllllllll轾轾轾犏犏犏犏犏犏+=+=犏犏犏犏犏犏+臌臌臌+=+=-轾犏犏=+=犏犏臌再从再从x(3)点点 出发，沿出发，沿x3轴方向轴方向e3进行一维搜索：进行一维搜索：故故 即为极小点。即为极小点。f(x(4)=0第第 二二 节节 最最 速速 下下 降降 法法()()()()()()()()()()()()()()()()141112211341440,0,0010000003000,0,00,0,000.010,0,0TTTTxxxef xfxxexxxxxlllllll=轾轾轾犏犏犏犏

10、犏犏+=+=犏犏犏犏犏犏臌臌臌=+=-=设问题为设问题为()()min,nf xxRf xR挝一、基本思想一、基本思想式中式中f(x)具有一阶连续偏导数，有极小点具有一阶连续偏导数，有极小点x*。若现已求得若现已求得x*的第的第k次近似值次近似值x(k)，为了求得第，为了求得第k+1次近似值次近似值x(k+1)，需选定方向需选定方向p(k)。p(k)有什么特征呢？有什么特征呢？令令()()kkxpxl+=，其中，其中()0,1.kpl=p(k)为某个下降方向。为某个下降方向。现将现将f(x)在在p(k)处展开：处展开：第第 二二 节节 最最 速速 下下 降降 法法()()()()()()()(

11、)()()Tkkkkkkf xf xpf xf xpoplll=+=+略去无穷小，可以得到略去无穷小，可以得到()()()()()()()()Tkkkkkf xpf xf xpll+-谎由于由于所以所以()()()()()0,0kkkf xpf xll+-()()()0Tkkf xp()0 x()()kf x若若 ，停止计算，输出，停止计算，输出x(k)作为极小点的近作为极小点的近似值，否则转到下一步。似值，否则转到下一步。()()kf xe轾犏=犏臌蜒=蜒求最佳步长求最佳步长l l0第第 二二 节节 最最 速速 下下 降降 法法则：则：()()()()()()()10001102110212

12、00.011*1xxf xf xxxle轾轾轾-犏犏犏=-=-=犏犏犏-臌臌臌=()()kf x()()kf x()()kf xe()()()()()()-12kkkpf xf x=-蜒()()()1kkkxxp+=+第第 三三 节节 牛牛 顿顿 法法例题例题3 用牛顿法求解用牛顿法求解()2212min25f xxx=+给定初始点给定初始点答案：答案：()()10,0Tx=()062,102xe-轾犏=犏臌与最速下降法的对比：与最速下降法的对比：(1)牛顿法对于二次正定函数只需做牛顿法对于二次正定函数只需做1次迭代就得到最优解，特别次迭代就得到最优解，特别是在极小点附近，收敛性很好，收敛速度

13、快；是在极小点附近，收敛性很好，收敛速度快；(2)最速下降法在极小点附近收敛速度很差。最速下降法在极小点附近收敛速度很差。第第 三三 节节 牛牛 顿顿 法法()()()()()()()()122002102220,05050420,0501001021050 xf xf xxf xf xf x-轾轾犏犏=犏犏臌臌轾轾犏犏=犏犏臌臌轾犏犏轾=犏犏臌犏犏臌解：解：()()()()()()()()()()()()()1000210011110422110020502202200,000pf xf xxxpf xf xxe-轾犏轾轾犏轾犏犏=-蜒=-=-犏犏犏犏臌犏臌臌犏臌轾轾轾犏犏犏=+=-=犏犏犏

14、臌臌臌轾犏=第第2步：步：求梯度向量求梯度向量 ，并计算，并计算若若 ，停止迭代，输出，停止迭代，输出x(k)作为极小点的近作为极小点的近似值，否则转到下一步。似值，否则转到下一步。()()kf x()()kf x()()kf xe第第3步：步：构造牛顿方向。根据构造牛顿方向。根据 确定确定 ()()()()()()-12kkkpf xf x=-蜒()()()()()()0minkkkkkf xpf xplll+=+()()()1kkkkxxpl+=+第第 三三 节节 牛牛 顿顿 法法例题例题4 用修正牛顿法求解用修正牛顿法求解()22121122min22f xxxxx xx=-+给定初始点

15、给定初始点答案：答案：()()1*1,3/2Txx=-()062,102xe-轾犏=犏臌第第 三三 节节 牛牛 顿顿 法法()()()()()()()()1221200210214242,22122142,2211122112xxf xf xxxf xf xf x-轾轾+犏犏=犏犏-+臌臌轾轾犏犏=犏犏-臌臌轾-犏犏轾=犏犏臌犏-犏臌解：解：第第 三三 节节 牛牛 顿顿 法法()()()()()()()()()()()()()100020000200011112231112210330225542550122pf xf xxpf xpfxplllllllllll-轾轾-犏轾犏犏轾犏=-蜒=-=

16、犏犏犏犏臌-犏犏臌-犏犏臌臌轾轾-轾犏犏犏+=+=犏犏犏犏犏臌犏犏臌臌+=-+=-=构造牛顿方向：构造牛顿方向：从从x(0)出发，沿牛顿方向做出发，沿牛顿方向做一维搜索一维搜索，令步长变量为，令步长变量为l l，最优步长为，最优步长为l l0第第 三三 节节 牛牛 顿顿 法法()()()()()()()()()()100111132314120230121221*32xxpf xf xxxle轾-犏=+=犏犏犏臌轾+-+犏轾犏犏=犏犏犏臌-+-+犏臌=xxxxx()()()()()()()()()()()()()()()()()()()11001111121112229028921028917

17、101100TTff=+fAbfblle轾-犏犏=-+=犏-犏犏臌=-=轾犏=犏臌轾犏=+=犏臌pxpxppApxxpxxx()()()211111=+l轾犏=犏臌xxp为最优解为最优解第第 五五 节节 最最 小小 二二 乘乘 法法一、测试数据的最小二乘拟合一、测试数据的最小二乘拟合 假设通过某实验获得以下数据假设通过某实验获得以下数据 ti24589yi2.012.983.505.025.47可以假定其近似表达式为线性函数可以假定其近似表达式为线性函数()*ytabt=+则有则有2.0122.9843.5055.0285.479ababababab=+=+=+=+=+超定方程，怎么办？超定方

18、程，怎么办？第第 五五 节节 最最 小小 二二 乘乘 法法1.选点法：选点法：2.0121.04000.48502.984abytab=+=+=+2.9840.90030.52003.505abytab=+=+=+2.平均法：平均法：(前三组和后两组分别平均前三组和后两组分别平均)2.833.670.9950.55.2458.5abytab=+=+=+问题：问题：(1)前面两种方法本身没有给出评价解的好坏标准，即怎样的解才前面两种方法本身没有给出评价解的好坏标准，即怎样的解才是最优的？是最优的？(2)前面两种方法也未指出用何种方法求得最优解。前面两种方法也未指出用何种方法求得最优解。为测试数据的为测试数据的残差残差，则可以得到以，则可以得到以 为分量的残差向量为分量的残差向量 第第 五五 节节 最最 小小 二二 乘乘 法法二、二、残差残差 假定有一组离散数据假定有一组离散数据(ti,yi)，可以用函数，可以用函数 来近似来近似表达，表达，显然显然 ，若记，若记()*iytab t=+*iiyy()*iiiiyyab tyg=-=+-ig()()*12,.,na bg gg=g g评价最优解的标准：通常采用欧氏范数的最小值来确定评价最优解的标准：通常采用欧氏范数的最小值来确定a*，b*，即即 ()()()222221min,niia ba ba bg=g gg g