精确线搜索——抛物线法

大家好，欢迎来到IT知识分享网。

抛物线法1

抛物线法

抛物线法也叫二次插值法，二次插值法的基本思想是: 在搜索区间中不断地使用二次多项式去近似目标函数, 并逐步用插值多项式的极小点去逼近线搜索问题

m i n s > 0 ϕ (s) = f (x k + s d k)

$\underset{s>0}{min}\ \phi(s)=f(x_k+sd_k)$

s 0, s 1 = s 0 + h, s 2 = s 0 + 2 h (h > 0)

$s_0,\ s_1=s_0+h,\ s_2=s_0+2h\ (h>0)$

处的函数值 $\phi_0,\phi_1, \phi_2$ ,且满足

ϕ 1 < ϕ 0, ϕ 1 < ϕ 2 .

$\phi_1<\phi_0, \ \phi_1<\phi_2.$
上述条件保证了函数 $\phi$ 在区间 $[s_0,s_2]$ 上是单峰函数. 则满足上述条件的二次 Lagrabge插值多项式为

q (s) = ( s - s 1 ) ( s - s 2 ) 2 h 2 ϕ 0 - ( s - s 0 ) ( s - s 2 ) h 2 ϕ 1 + ( s - s 0 ) ( s - s 1 ) ϕ 2

$q(s)=\frac{(s-s_1)(s-s_2)}{2h^2}\phi_0-\frac{(s-s_0)(s-s_2)}{h^2}\phi_1+\frac{(s-s_0)(s-s_1)}\phi_2$
$q(s)$ 的一阶导数为

q' (s) = 2 s - s 1 - s 2 2 h 2 ϕ 0 - 2 s - s 0 - s 2 h 2 ϕ 1 + 2 s - s 0 - s 1 2 h 2 ϕ 2

$q'(s)=\frac{2s-s_1-s_2}{2h^2}\phi_0-\frac{2s-s_0-s_2}{h^2}\phi_1+\frac{2s-s_0-s_1}{2h^2}\phi_2$
令 $q'(s)=0$ 解得

s ¯ = ( s 1 + s 2 ) ϕ 0 - 2 ( s 0 + s 2 ) ϕ 1 + ( s 0 + s 1 ) ϕ 2 2 ( ϕ 0 - 2 ϕ 1 + ϕ 2 ) = ( 2 s 0 + 3 h ) ϕ 0 - 2 ( 2 s 0 + 2 h ) ϕ 1 + ( 2 s 0 + h ) ϕ 2 2 ( ϕ 0 - 2 ϕ 1 + ϕ 2 ) = s 0 + ( 3 ϕ 0 - 4 ϕ 1 + ϕ 2 ) h 2 ( ϕ 0 - 2 ϕ 1 + ϕ 2 ) = s 0 + h ¯

$\begin{aligned} \overline{s}&=\frac{(s_1+s_2)\phi_0-2(s_0+s_2)\phi_1+(s_0+s_1)\phi_2}{2(\phi_0-2\phi_1+\phi_2)}\\ &=\frac{(2s_0+3h)\phi_0-2(2s_0+2h)\phi_1+(2s_0+h)\phi_2}{2(\phi_0-2\phi_1+\phi_2)}\\ &=s_0+\frac{(3\phi_0-4\phi_1+\phi_2)h}{2(\phi_0-2\phi_1+\phi_2)}\\ &=s_0+\overline{h} \end{aligned}$
这里

h ¯ = ( 3 ϕ 0 - 4 ϕ 1 + ϕ 2 ) h 2 ( ϕ 0 - 2 ϕ 1 + ϕ 2 ) = ( 4 ϕ 1 - 3 ϕ 0 - ϕ 2 ) h 2 ( 2 ϕ 1 - ϕ 0 - ϕ 2 ) > 0

$\overline{h}=\frac{(3\phi_0-4\phi_1+\phi_2)h}{2(\phi_0-2\phi_1+\phi_2)}=\frac{(4\phi_1-3\phi_0-\phi_2)h}{2(2\phi_1-\phi_0-\phi_2)} > 0$
又 $q(s)$ 的二阶导数为

q'' (s) = ϕ 0 h 2 - 2 ϕ 1 h 2 + ϕ 2 h 2 = ϕ 0 - 2 ϕ 1 + ϕ 2 h 2 > 0

$q''(s)=\frac{\phi_0}{h^2}-\frac{2\phi_1}{h^2}+\frac{\phi_2}{h^2}=\frac{\phi_0-2\phi_1+\phi_2}{h^2}>0$
故 $q(s)$ 为凸二次函数, 从而 $s_min$ 是 $q(s)$ 的全局极小点.
注意到 $\overline{s}=s_0+\overline{h}$ 比 $s_0$ 更好地逼近 $s^*$ . 故可用 $\overline{s},\overline{h}$ 分别替换 $s_0$ 和 $h$ 并重复上述计算过程, 求出新的$\overline{s} 和新的\overline{h}. 重复这一迭代过程, 直到得到所需的精度为止. 值得说明的是, 这一算法中目标函数的一阶导数用来隐式地确定二次插值多项式的极小点, 而算法的程序实现中并不需要使用导数值.

算法3（抛物线法）

步骤0，由进退法确定三点 $s_0 <s_1<s_2< script=""> , 对应的函数值 ϕ0,ϕ1,ϕ2 <script type="math/tex" id="MathJax-Element-25">\phi_0,\phi_1,\phi_2$ 满足

ϕ 1 < ϕ 0, ϕ 1 < ϕ 2 .

$\phi_1<\phi_0,\ \phi_1<\phi_2.$
设定容许误差 $0\leqslant\epsilon\ll1$ .
步骤1，若 $|s_2-s_0|<\epsilon$ ，停算，输出 $s^*\approx s_1$
步骤2，计算插值点. 根据 $\overline{s}$ 公式计算 $\overline{s}$ 和 $\overline{\phi}=\phi(\overline{s})$ .若 $\phi_1\leq \overline{\phi}$ ，转步骤4；否则，转步骤3
步骤3，若 $s_1>\overline{s}$ ，则 $s_2=s_1$ ， $s_1=\overline{s}$ ， $\phi_2=\phi_1$ ， $\phi_1=\overline{\phi}$ ，转步骤1；否则， $s_0=s_1$ ， $s_1=\overline{s}$ ， $\phi_0=\phi_1$ ， $\phi_1=\overline{\phi}$ ，转步骤1
步骤4，若 $s_1<\overline{s}$ ，则 $s_2=\overline{s}$ ， $\phi_2=\overline{\phi}$ ，转步骤1；否则， $s_0=\overline{s}$ ， $\phi_0=\overline{\phi}$ ，转步骤1.

MATLAB实现

function [s,phis,i,E,S]=paowxf(phi,a,b,delta,epsilon) %功能: 精确线搜索之抛物线法 %输入: phi 是目标函数, a和b是搜索区间的端点 % delta,epsilon是容许误差 %输出: i是迭代次数 % s是近似极小点, phis是对应的近似极小值; % E=[ds,dphi], 分别是s和phis的误差限分别是s, phis的误差界;  % S是迭代向量 s0=a;s2=b; h=(s2-s0)/2;s1=s0+h; phi0=feval(phi,s0);phi1=feval(phi,s1);phi2=feval(phi,s2);bars=s0; i=0; while(1) i=i+1; S(i,:)=[s0,s1,s2,bars]; %step1 if (abs(s2-s0)>=epsilon) || ((phi2-phi0)>=delta) %step2 % h=(s2-s0)/2;s1=s0+h; % phi0=feval(phi,s0);phi1=feval(phi,s1);phi2=feval(phi,s2); barh=h*(4*phi1-3*phi0-phi2)/(2*phi1-phi0-phi2)/2; bars=s0+barh; barphi=feval(phi,bars); if phi1<=barphi %step4 if s1<bars s2=bars; phi2=barphi; h=barh-h; s0=s1-h; phi0=feval(phi,s0); else s0=bars; phi0=barphi; h=h-barh; s2=s1+h; phi2=feval(phi,s2); end else %step3 if s1>bars if h>2*barh s1=bars;h=barh;s2=s1+h; phi1=barphi;phi2=feval(phi,s2); else s1=bars;h=h-barh;s2=s1;s0=s1-h; phi1=barphi;phi2=phi1;phi0=feval(phi,s0); end else if 2*barh<3*h s0=s1;h=barh-h;s1=bars;s2=s1+h; phi0=phi1;phi1=barphi;phi2=feval(phi,s2); else s1=bars;h=2*h-barh;s0=s1-h; phi1=barphi;phi0=feval(phi,s0); end end end else break; end end s=s1; phis=feval(phi,s1); ds=abs(s-s0); dphi=abs(phi1-phi0); E=[ds dphi];

MATLA实验结果

>> phi = @(x)3*x^2-2*tan(x); >> delta=1e-5;epsilon=1e-4; >> a=0;b=1; >> [s,phis,i,E,S]=paowxf(phi,a,b,delta,epsilon); >> [s,phis,i,E] ans = Columns 1 through 3 0.7377 -0.4081 8 Columns 4 through 5 1.533e-10 1.516e-16

程序对于函数 $\phi (x)=3x^2-2tan(x)$ ，在区间 $[0,1]$ ，进过8次迭代便可得到较高精度解。

马昌凤. 最优化方法及其Matlab程序设计[M]. 科学出版社, 2010. ↩

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/130660.html