大数据计算方法 课件 chap8-非线性方程与无约束优化求解

1大数据计算方法Chap8：非线性方程与无约束优化求解求解非线性方程的方法简单的无约束优化方法基于求导的无约束优化方法Outline2求解非线性方程的方法二分法牛顿法割线法逆二次插值法解非线性方程组的牛顿法3非线性方程基本理论

4

二分法

5

0

小结

6>>f=@(x)x-1-1/x;牛顿法原理利用曲线上点(xk,f(xk))处的切线,求xk+1计算公式程序my_Newtonx*xk+1

xkxy(xk,

f(xk))

k=0;whileabs(x-xprev)>tol*abs(x)xprev=x;x=x-f(x)/fprime(x);k=k+1;end

若对于收敛快的算法，是误差的估计若tol=eps,基本上达最准其他优点：可以算复数根、解方程组7若准确解为0?修改循环结束条件(f(x)=0时退出循环)牛顿法的问题

8对任意初值都不收敛的例子一阶导数间断点另两个缺点：2阶收敛速度!割线法

x*xk

xk-1xy

k=0;whileabs(b-a)>eps*abs(b)c=b;%b是x的近似解b=b+(b-a)/(f(a)/f(b)-1);a=c;%a是上一个近似解k=k+1;end

超线性收敛速度：

9缺点:需要两个较好的初值逆二次插值法

抛物线xk+10xyxk

xk-1

xk-2

也可用polyfit,polyval算10

逆二次插值法插值函数P满足:则是

它与x轴交点程序优缺点收敛速度快f(xk-2),f(xk-1),f(xk)虽不等,若值很接近,

得到的xk+1将远远偏离求解区间割线法也有这种不稳定性(斜率~0)k=0;whileabs(c-b)>eps*abs(c)x=polyinterp([f(a),f(b),f(c)],[a,b,c],0)a=b;b=c;c=x;k=k+1;endIQI算法(Inversequadraticinterpolation)11

xf(x)

...

通用求根算法zeroin算法的特点每步迭代都使有根区间缩小抛弃逆二次插值/割线法得到的”不满意”解按”逆二次插值,割线法,二分法”的优先顺序生成下一步解，保证较快的收敛速度算法稳定、通用性强，是Matlab命令fzero的基础NCM中的演示程序fzeroguiNCM中的fzerotx.m12>>fzerogui>>bessj0=@(x)besselj(0,x);>>fzerogui(bessj0,[03.83])缺省f(x)=x^3-2x-5fzero命令

>>bessj0=@(x)besselj(0,x);>>ezplot(bessj0,[0,10*pi]);forn=1:10z(n)=fzero(bessj0,[(n-1)n]*pi);endholdon;plot(z,zeros(1,10),'o')13optimset设置结构(求单变量连续函数的零点)>>opt=optimset('tolX',1e-2);非线性方程组

14

非线性方程组例:用牛顿法求解15

解方程

解方程

该方程的Jacobi矩阵

简单的无约束优化方法黄金分割搜索下山单纯形法非线性最小二乘问题16无约束优化

17

不涉及导数

(本节)涉及导数

(下一节)例如：黄金分割搜索

*abuv

黄金分割搜索！

18少算一次f(x)黄金分割搜索进一步改进黄金分割搜索很稳定,收敛速度仍慢类似割线法/IQI法,用抛物线近似被优化函数的局部(需3个点做插值,如其函数值”高-低-高”时)何时选用抛物线的解?

在区间内,相邻解间距缩小,等fminbndMatlab命令fminbnd,求单变量函数区间上最小值[x,fval,exitflag,output]=fminbnd(fun,x1,x2,opt)x1<x2,为区间两端点;fval为目标函数(极小)值exitflag退出标记,output包含算法、函数求值次数等用optimset设置opt中选项的值(同fzero)可再与黄金分割搜索结合！abuv19*(类似于zeroin算法,见fminQI程序)fminQI程序程序停止的判据黄金分割搜索与抛物线法whileabs(x-xm)>tolr=(x-w)*(fx-fv);q=(x-v)*(fx-fw);p=(x-v)*q-(x-w)*r;q=2.0*(q-r);ifq>0.0,p=-p;endq=abs(q);r=e;e=d;%Istheparabolaacceptable?para=((abs(p)<abs(0.5*q*r))&(p>q*(a-x))&(p<q*(b-x)));ifparad=p/q;end含极小值

区间的中点x+p/q在区间[a,b]内,且相邻解间距缩小根据x,w,v这三点数据造抛物线p,或q取相反数20fminbnd的简化版本u=fminQI(F,a,b,tol,varargin)近似极小点详见课本8.2.1小节的fminQI程序最优化与fminbndfminbnd/fminQI的例子求-humps(x)的极小值搜索过程显示(习题8.5)21

>>F=@(x)-humps(x);>>fminQI(F,-1,2,1.e-4)fminbnd缺省的tolX是1e-4但结果与fminQI的不一样设opt=optimset('tolX',1e-6)试试?

下山单纯形法主要思路黄金分割搜索和fminbnd只能用于单变量问题在多维空间,通过计算单纯形顶点处函数值，然后再对它做调整(反射、扩展、收缩等)，不断重复操作，找到最小值点也叫Nelder–Mead法，是Matlab命令fminsearch的基础n维空间的单纯形n+1个非退化的点构成的形体22(2维空间的例子)3个不共线的点构成的三角形是一个单纯形这3个点共线,不构成单纯形

下山单纯形法23二维空间的例子最差点新点单位阵的第i列最好点扩展操作(expansion)向代价函数最小

顶点的方向扩展收缩操作(contraction)如果单纯形的形状

比较“狭长”两个顶点向代价函

数变小的方向收缩收缩操作2(shrink)扩展操作的逆缺点:对高维的问题收敛速度慢、可能不收敛、局部极小优点:不需要算导数(代价函数不光滑...)下山单纯形法24最好点fminserach命令求多元实函数的最小值，使用下山单纯形法[x,fval]=fminsearch(fun,x0,options)可分离的非线性最小二乘问题拟合公式中含非线性参数与线性参数例:求解最小二乘问题若已知非线性参数(

1/2)的值,则用\可求线性参数值(

1/2)最小化的是残差的2-范数:它是非线性参数(

1/2)的函数非线性最优化+线性最小二乘fminserach命令及其应用

25后面加给fun的参数带入fminsearch中的fun比全看成非线性参数直接用fminsearch求解更有效/可靠例子数据:t=(0:.1:2)'y=[5.89553.56392.51731.9790...,0.13700.22110.17040.2636]';

1,2的初值为:[36]'求解过程与演示线性最小二乘的解定义为函数:

res=expfitfun(lambda,t,y)非线性最小化:fminsearch(@expfitfun,lambda0,[],t,y)程序细节与动态演示程序

expfitdemofminserach命令及其应用(放射性物质衰变的观测)最小化过程收敛时对应的拟合曲线将观测数据设为函数参数>>editexpfitfun.m;>>editexpfitdemo.m;26基于求导的无约束优化方法梯度下降法牛顿法共轭梯度法27无约束优化方法分类黄金分割搜索及其变种算法下山单纯形法(downhillsimplexmethod)梯度下降法(gradientmethod)牛顿法(Newtonmethod)共轭梯度法(conjugategradientmethod)梯度下降法若代价函数光滑,其导数

可用于搜索最优解28

不涉及导数涉及导数

(本节)另一个思路:解方程无约束优化

29

梯度为0解单变量

无约束优化无约束优化

30

非线性方程组,用牛顿法解

=0

代价函数减少！

对称正定近似计算Hessian矩阵或它的逆无约束优化

31

无约束优化

32

Fletcher-Reeves公式

Polak-Ribiere公式存在一些经验性的尝试

Polak-Ribiere公式

如果收敛停滞,每N次迭代后可重置搜索方向为负梯度方向理论上严格下降,且收敛无约束