三无约束非线性规划.ppt

第三章 无约束非线性规划 数学系 何郁波 无约束非线性规划 第一节 最优性条件 引言 本章讨论如下的优化模型 预备知识 预备知识 预备知识 最优性条件 最优性条件 最优性条件 迭代法 迭代法 最优性条件 迭代算法 一维搜索 一维搜索——二分法 一维搜索——二分法 一维搜索——黄金分割法 一维搜索——黄金分割法 一维搜索——黄金分割法 一维搜索——黄金分割法 function [x,minf] = minHJ(f,a,b,eps) format long; if nargin == 3 eps = 1.0e-6; end l = a + 0.382*(b-a); u = a + 0.618*(b-a); k=1; tol = b-a; while toleps k100000 fl = subs(f , findsym(f), l); fu = subs(f , findsym(f), u); if fl fu a = l; l = u; u = a + 0.618*(b - a); else b = u; u = l; l = a + 0.382*(b-a); 一维搜索——牛顿法 一维搜索——牛顿法 一维搜索——牛顿法 牛顿法程序 function [x,minf] = minNewton(f,x0,eps) format long; if nargin == 2 eps = 1.0e-6; end df = diff(f); d2f = diff(df); k = 0; tol = 1; while toleps dfx = subs(df,findsym(df),x0); if diff(d2f) == 0 d2fx = double(d2f); else d2fx = subs(d2f,findsym(d2f),x0); end x1 = x0 - dfx/d2fx; k = k + 1; tol = abs(dfx); x0 = x1; end x = x1; minf = subs(f,findsym(f),x); format short; 最速下降法和共轭梯度法 最速下降法 最速下降法 最速下降法 最速下降法 最速下降法 最速下降法 最速下降法 最速下降法源程序 共轭梯度法 1.算法原理 共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。 共轭梯度法 共轭梯度法最早是由Hestenes和Stiefel(1952)提出来的，用于解正定系数矩阵的线性方程组。在这个基础上，Fletcher和Reeves(1964)首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的。而这些搜索方向 仅仅是负梯度方向 与上一次迭代的搜索方向 的组合。因此存储量小，计算方便。 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法 共轭梯度法源程序 共轭梯度法小结 共轭梯度法小结 共轭梯度法小结 共轭梯度法小结 牛顿法 牛顿法 牛顿法 牛顿法源程序 拟牛顿法(变尺度法) 牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息，但计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出，这就导致了一个想法:能否仅利用目标函数值和一阶导数的信息，构造出目标函数的曲率近似，使方法具有类似牛顿法的收敛速度快的优点。拟牛顿法就是这样的一类算法。由于它不需要二阶导数，拟牛顿法往往比牛顿法更有效。 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法(变尺度法) 拟牛顿法源程序 信赖域算法 信赖域算法 信赖域算法 信赖域算法 信赖域算法 信赖域算法 信赖域算法 信赖域算法源程序 信赖域算法运行结果 拟牛顿算法 DFP校正是第一个拟牛顿校正，是1959年由Davidon提出的，