数值最优化：线搜索技术

作者: Bocchi | 来源:发表于2019-11-18 19:50 被阅读0次

数值最优化：线搜索技术
Line search and Step length线搜索与步
高级SEO关键词优化企业SEO推广技术SEO优化网站关键词排名
博客SEO优化技巧之二
博客SEO优化技巧之一
搜索引擎系统原理剖析
安利一下前端SEO技巧
使用不规范的URL对搜索引擎非常不利
进化策略与有限差分近似
凸优化，梯度下降和优化算法进阶

1 简介

对于求解无约束优化模型 $\min_\limits{x\in R^n} f(x)$ 通常会有下面的一种迭代步：
通过某种搜索方法确定步长因子 $\alpha_k$ ，使得 $f(x_k+\alpha_k d_k) < f(x_k)$ 这实际上是目标函数 $f(x)$ 在规定的一个方向上移动所形成的单变量优化问题，也就是所谓的 “线搜索” 技术，令 $\phi(\alpha)=f(x_k+\alpha d_k)$ 这样，搜索式等价于求步长 $\alpha_k$ 使得 $\phi(\alpha_k)<\phi(0)$

线搜索方法有 精确线搜索 和 非精确线搜索 之分
精确线搜索：指求 $\alpha_k$ 使目标函数 $f$ 沿方向 $d_k$ 达到极小
非精确线搜索：指选取 $\alpha_k$ 使目标函数 $f$ 得到 可以接受的下降量

2 精确线搜索

精确线搜索的基本思想：首先确定包含问题最优解的 搜索区间，然后采用某种插值或分割技术缩小区间，进行搜索求解。
由于不少精确线搜索算法都是针对单峰函数建立起来的，下面介绍一种确定搜索区间并保证具有 近似单峰性质 的数值算法——进退法

算法1：进退法
S1：给出 $x_0\in R$ , $h>0$ , $t>1$ ;
计算 $x_2=x0$ , $x1=x_0+h$ ;
S2：如果 $f({{x}_{2}})>f({{x}_{1}})$ 则转 S4;
如果 $f({{x}_{2}})<f({{x}_{1}})$ 则转 S6;
S3：令 ${{x}_{1}}=({{x}_{1}}+{{x}_{2}})/2$ , 如果 $f({{x}_{2}})=f({{x}_{1}})$ 则转 S3;
如果 $f({{x}_{2}})<f({{x}_{1}})$ 则转 S6;
${{x}_{3}}=2{{x}_{1}}-{{x}_{2}}$ , 转 S7;
S4：令 $h=t\cdot h,{{x}_{3}}={{x}_{1}}+h$ , 如果 $f({{x}_{3}})>f({{x}_{1}})$ 则转 S7;
如果 $f({{x}_{3}})=f({{x}_{1}})$ 则转 S5;
令 ${{x}_{2}}={{x}_{1}},{{x}_{1}}={{x}_{3}}$ , 转S4；
S5：令 $\hat{x}=({{x}_{1}}+{{x}_{3}})/2$ , 如果 $f(\hat{x})>f({{x}_{1}})$ , 则令 ${{x}_{3}}=\hat{x}$ , 转 S7;
如果 $f(\hat{x})<f({{x}_{1}})$ , 则令 ${{x}_{2}}={{x}_{1}},{{x}_{1}}=\hat{x}$ , 转 S7;
令 ${{x}_{3}}=\hat{x}$ , 转 S5.
S6：令 $\hat{x}={{x}_{1}},{{x}_{1}}={{x}_{2}},{{x}_{2}}=\hat{x},h=-h$ , 转 S2;
S7：令 $L=\min\{x_1,x_2,x_3\},R=\max\{x_1,x_2,x_3\}$ , 即停。

function [a,b]=Brackeing(f,x0,h,t)
flag=0;

x2=x0;
x1=x0+h;

if f(x2)==f(x1)
    while f(x2)==f(x1)
       x1=(x1+x2)/2; 
    end
    if f(x2)>f(x1)
        x3=2*x1-x2;
        flag=1;
    end
end

if f(x2)<f(x1)
    x1=x1+x2;
    x2=x1-x2;
    x1=x1-x2;
    h=-h;
end

if flag==0
    h=t*h;
    x3=x1+h;
    while f(x3)<f(x2)
        x2=x1;
        x1=x3;
        h=t*h;
        x3=x1+h;
    end
    if f(x3)==f(x1)
        xm=(X1+x3)/2;
        while f(xm)==f(x1)
            x3=xm;
            xm=(x1+x3)/2;
        end
        if f(xm)>f(x1)
            x3=xm;
        end
        if f(xm)<f(x1)
            x2=x1;
            x1=xm;
        end
    end 
end
a=min([x1 x2 x3]);
b=max([x1 x2 x3]);
end

例1：利用进退法求解极值区间实例。取初始点 $x_0=0$ ，步长 $h=0.1$ ，用进退法求函数 $f(t)={{({{t}^{2}}-1)}^{2}}+{{(t-1)}^{2}}+3$ 的极值区间。

format short
clear
clc

f=inline('(t.^2-1).^2+(t-1).^2+3','t');
x0=0;
h=0.1;
t=2;

[a,b]=Brackeing(f,x0,h,t)
-----------ans--------------
a = 0.30000
b = 1.50000
----------------------------

2.1 黄金分割法（0.618法）

黄金分割法又称 0.618 法，其基本思想是通过试探函数值的比较，使得包含极小点的搜索区间不断缩小，直至区间内的值足够接近极小值为止。该方法仅需要计算函数值，适用范围广，使用方便。下面我们来推导 0.618 法的计算公式。
设 $\phi(s)=f(x_k+sd_k)$ 其中 $\phi(s)$ 是搜索区间 $[a_0,b_0]$ 的单峰函数。
假设在第 $i$ 次迭代时搜索区间为 $[a_i,b_i]$ , 为确定下一次迭代区间，我们取两个试探点 $p_i,q_i\in [a_i,b_i]\text{, }(p_i<q_i)$ , 计算得到 $\phi(p_i)$ 和 $\phi(q_i)$ , 存在两种情况：
（1）若 $\phi(p_i)\leqslant\phi(q_i)$ , 则令 $a_{i+1}=a_i,b_{i+1}=q_i$ ;
（2）若 $\phi(p_i)>\phi(q_i)$ , 则令 $a_{i+1}=p_i,b_{i+1}=b_i$ ;
我们要求两试探点满足如下条件：
（1） $[a_i,q_i]$ 与 $[p_i,b_i]$ 长度相同，即 $b_i-p_i=q_i-a_i$ ;
（2）区间长度的缩短率相同，即 $b_{i+1}-a_{i+1}=\tau(b_i-a_i)$ .
从而可得 $p_i=a_i+(1-\tau)(b_i-a_i),\quad q_i=a_i+\tau(b_i-a_i)$ 由于两区间长度一致，不妨假设新的迭代区间为 $[a_{i+1},b_{i+1}]=[a_i,q_i]$ 为进一步缩小区间，取新的试探点 $p_{i+1},q_{i+1}$ , 得 $\begin{align}q_{i+1}&=a_{i+1}+\tau (b_{i+1}-a_{i+1})\\&=a_i+\tau (q_i-a_i)\\&=a_i+\tau^2(b_i-a_i)\end{align}$ 若令 $\tau^2=1-\tau,\quad\tau>0$ 则 $q_{i+1}=a_i+(1-\tau)(b_i-a_i)=p_i$ 这样，新的试探点就不用重新计算。得到区间的缩短率为 $\tau=\frac{\sqrt{5}-1}{2}\approx 0.618$

算法2：黄金分割法（0.618法）
S1：选定区间 $[a,b]$ 及精度 $\varepsilon >0$ , 令 $k=1$ , 计算试探点
$\alpha =a1+0.382*(b-a)$
$\beta =a1+0.618*(b-a)$
S2：若 $b1-a1<\varepsilon$ ,则停止计算;
否则，当 $f(\alpha )>f(\beta )$ 时转 S3；当 $f(\alpha )\leqslant f(\beta )$ 时转 S4；
S3：令 $a=\alpha ,\alpha =\beta ,\beta =a+0.618*(b-a)$ , 转 S5;
S4：令 $b=\beta ,\beta=\alpha ,\alpha =a+0.382*(b-a)$ , 转 S5;
S5：令 $k=k+1$ , 转 S2.

function [x,miny,k]=Golden(f,a,b,esp)
l=a+0.382*(b-a);
r=a+0.618*(b-a);
k=1;

while(b-a)>esp
    if f(l)>f(r)
        a=l;
        l=r;
        r=a+0.618*(b-a);
    else
        b=r;
        r=l;
        l=a+0.382*(b-a);
    end
    k=k+1;
end
x=(a+b)/2;
miny=f(x);
end

例2：利用黄金分割法求解极值实例。利用黄金分割法求下面函数的极小值 $f(t)={{({{t}^{2}}-1)}^{2}}+{{(t-1)}^{2}}+3,\quad t\in [-10,10]$

f=inline('(t.^2-1).^2+(t-1).^2+3','t');
a=-10;
b=10;
esp=0.001;

[x,miny,steps]=Golden(f,a,b,esp)
-----------ans--------------
x = 0.99998
miny = 3.00000
steps = 22
----------------------------

2.3 基本牛顿法

基本牛顿法是一种是用导数的算法，它每一步的迭代方向都是沿着当前点函数值下降的方向。其基本思想是：用 $\varphi(x)$ 在探索点 $t_k$ 处的二阶 Taylor 展开式得到的二次函数 $g(t)$ 来近似代替 $\varphi(x)$ ： $g(t) = \varphi ({t_k}) + \varphi '({t_k})(t - {t_k}) + \frac{1}{2}\varphi ''({t_k}){(t - {t_k})^2}$ 其中， $g(t)$ 可以认为是 $\varphi(x)$ 的近似。因此，求函数 $\varphi(x)$ 的极小值点近似于求解 $g(t)$ 的极小值点，函数 $g(t)$ 应该满足一阶必要条件： $g'(t)=\varphi'(t_k)+\varphi''(t_k)(t-t_k)=0$ 即 $t=t_k-\frac{\varphi'(t_k)}{\varphi''(t_k)}$ 上式即为牛顿法的迭代公式，当 $f′′(x)>0$ 时，对于区间内的 $x$ 都成立；反之当 $f''(x)<0$ 时，牛顿法可能收敛到极大值点。

算法3：基本牛顿法
S1：给出 $x_0\in R$ 精度 $\varepsilon >0$ , 令 $k=0$ ;
S2：若 $\left| {f}'({{x}_{k}}) \right|\le \varepsilon$ , 停止, 极小值点为 ${{x}_{k}}$ ；
S3：令 ${{x}_{k+1}}={{x}_{k}}-\frac{{f}'({{x}_{k}})}{{f}''({{x}_{k}})}$ ;
S4：令 $k=k+1$ , 转 S2.

function [x,minf,k]=Newton(f,x0,eps)
% 其中 f 为符号函数
df=diff(f);
ddf=diff(df);
f=inline(f);
df=inline(df);
ddf=inline(ddf);

k=0;

while abs(df(x0))>eps
    x0=x0-df(x0)/ddf(x0);
    k=k+1;
end

x=x0;
minf=f(x);
end

例3：取初始点 $x_0=2$ ，用牛顿法求 $f(t)={{t}^{2}}-\ln t-5$ 的任一极小值点。

syms t
f=t.^2-log(t)-5;
x0=2;
eps=0.001;

[x,minf,steps]=Newton(f,x0,eps)
-----------ans--------------
x = 0.70710
b = -4.15343
steps = 4
----------------------------

3 非精确线搜索

线搜索技术是求解许多优化文体下降算法的基本组成部分，但精确线搜索往往需要计算很多的函数值和梯度值，从而耗费较多的计算资源。特别是当迭代点远离最优点是，线搜索方法通常不是十分有效和合理的。因此，既能保证目标函数具有可接受的下降量又能使最终新城的迭代序列收敛的非精确线搜索越来越流行。常用的有 Walf 准则与 Armijo 准则。

3.1 阻尼牛顿法

牛顿法最突出的优点是收敛速度快，具有局部二阶收敛性，但基本牛顿法初始点需要足够“靠近”极小点，否则有可能导致算法不收敛。这样就引入了 阻尼牛顿法（也称全局牛顿法），阻尼牛顿法最核心的一点在于可以修改每次迭代的步长，通过沿着牛顿法确定的方向一维搜索最优的步长，最终选择使得函数值最小的步长。
阻尼牛顿法是基于 Armijo 准则的搜索，满足 Armijo 准则： $f(x_k+\alpha d_k)\leqslant f(x_k)+\rho g_k^Td_k\alpha,\quad \rho\in(0,1)$ 一般的，可取 $\rho$ 为 $10^{-3}$ 或更小的值。由于 $d_k$ 时下降方向，不等式右边是关于 $\alpha$ 的线性减函数。因此只要 $\alpha$ 不取的太小，不等式可以保证新迭代点 $x_k+\alpha d_k$ 的函数值较 $x_k$ 有一定量的下降。

算法4：阻尼牛顿法（全局牛顿法）
S1：给出 $x_0\in R$ 精度 $\varepsilon >0$ , 令 $k=0$ ;
S2：计算 $f'({x_{k}})$ , ${f}''({{x}_{k}})$ , 若 ${f}'({{x}_{k}})\neq 0$ 则转 S4;
若 ${f}''({{x}_{k}})\ge 0$ 则停止;
令初始值 $\delta =\varepsilon$ ;
S3：令 $\delta =\delta /2$ , 如果 $f({x_k}+\delta )\geqslant f({{x}_{k}})$ , 则转 S3;
令 ${{x}_{k+1}}={{x}_{k}}+\delta$ , $k=k+1$ , 转 S2；
S4：令 ${{\beta }_{k}}={f}''({{x}_{k}})$ , 如果 ${{\beta }_{k}}\leqslant 0$ , 则令 ${{\beta }_{k}}=1$ , 置 ${{\alpha }_{k}}=1$ ;
S5：如果 $f({{x}_{k}}-\frac{{{\alpha }_{k}}{f}'({{x}_{k}})}{{{\beta }_{k}}})\leqslant f({{x}_{k}})-\frac{{{\alpha }_{k}}}{4{{\beta }_{k}}}{{\left[ {f}'({{x}_{k}}) \right]}^{2}}$
则转 S6；置 ${{\alpha }_{k}}=\frac{{\alpha }_{k}}{2}$ ；转 S5;
S6：令 ${{x}_{k+1}}={{x}_{k}}-\frac{{{\alpha }_{k}}{f}'({{x}_{k}})}{{{\beta }_{k}}}$ , $k=k+1$ , 转 S2.

function [x,miny,steps]=GlobalNewton(f,x0,eps)
% 其中 f 为符号函数

df=diff(f);
ddf=diff(df);
f=inline(f);
df=inline(df);
ddf=inline(ddf);
k=0;

while 1
    if (df(x0)<eps) && (df(x0)>-eps)
        if ddf(x0)>=0
            break;
        end
        
        delta=esp/2;
        while f(x0+delta)>=f(x0)
            delta=delta/2;
        end
        x0=x0+delta;
        k=k+1;
    else
        beta=ddf(x0);
        alpha=1;
        if beta<=0
            beta=1;
        end
        
        while f(x0-alpha*df(x0)/beta)>f(x0)-alpha*(df(x0)).^2/(4*beta)
            alpha=alpha/2;
        end
        
        x0=x0-alpha*df(x0)/beta;
        k=k+1;
    end
end
x=x0;
miny=f(x);
steps=k;
end

例4：取初始点 $x_0=5$ ，用全局牛顿法求函数 $f(t)={{t}^{3}}-3t+2$ 的极小值点。

syms t
f=t.^3-3*t+2;
x0=5;
eps=0.0001;

[x,miny,steps]=GlobalNewton(f,x0,eps)
-----------ans--------------
x = 1.000004635
b = 6.44676446e-11
steps = 4
----------------------------

数值最优化：线搜索技术
1 简介对于求解无约束优化模型通常会有下面的一种迭代步：通过某种搜索方法确定步长因子，使得这实际上...
Line search and Step length线搜索与步
Welcome To My Blog在最优化(optimization)问题中,线搜索(line search)和...
高级SEO关键词优化企业SEO推广技术SEO优化网站关键词排名
高级SEO关键词优化企业SEO推广技术SEO优化网站关键词排名搜索引擎优化百度自然搜索基础视频教程在互联网营销...
博客SEO优化技巧之二
SEO优化也就是搜索引擎优化，搜索引擎优化也就是博客内容被搜索引擎收录及优先排序，以此增加博客的点击率和曝光度，最...
博客SEO优化技巧之一
SEO优化也就是搜索引擎优化，搜索引擎优化也就是博客内容被搜索引擎收录及优先排序，以此增加博客的点击率和曝光度，最...
搜索引擎系统原理剖析
目录【1】搜索引擎概述【2】搜索引擎的基础技术【3】搜索引擎的平台基础【4】搜索结果的改善优化【1】搜索...
安利一下前端SEO技巧
SEO技术大致可以分为白帽优化和黑帽优化，白帽优化就是指通过遵循搜索引擎公司建议的手段进行优化，黑帽优化就是...
使用不规范的URL对搜索引擎非常不利
使用不规范的URL对搜索引擎非常不利搜索引擎优化不仅仅是入站营销。因为它有大量的重叠，所以对于搜索引擎优化技术来...
进化策略与有限差分近似
进化策略又称随机搜索（random search）或梯度的随机有限差分近似，是一类数值优化方法，它不仅适用于不连续...
凸优化，梯度下降和优化算法进阶
1. 凸优化优化方法目标：训练集损失函数值深度学习目标：测试集损失函数值（泛化性） 1.1 优化在深度学习中的挑...