久久伊人网在线视频,超碰碰精品分类,久久久999在线观看

在上節(jié)中本教程介紹了迭代搜索的基本步驟?？紤]基本步驟中的每一步的基本元素：步長、下降方向和終止準(zhǔn)則，其中終止準(zhǔn)則是我們已經(jīng)明確給出的，而步長和下降方向可以是任意的。但任意并不代表隨機(jī)，一個隨機(jī)的迭代搜索算法是無法保證收斂性的。步長和下降方向需要我們針對每一步搜索到的點(diǎn)的情況來求解，不僅要保證算法的收斂性，還要使得算法具有盡可能快的收斂速度。

在本節(jié)中本教程將介紹迭代搜索過程中步長的計(jì)算方法，而下降方向的計(jì)算方法會在接下來幾節(jié)內(nèi)給出。

1 步長的精確搜索

若我們已經(jīng)知道了一個下降方向 $d_k$ ，就只需要求參數(shù) $\alpha$ 使其滿足一維優(yōu)化問題 $minf(x_k+\alpha d_k)$ 的解，令 $\phi(\alpha)=f(x_k+\alpha d_k)$ ，則 $\phi'(\alpha)=\nabla f(x_k+\alpha d_k)^Td_k=0$ ，求解該線性方程組即可。

對于簡單的方程，精確搜索是非常快速有效甚至有現(xiàn)成結(jié)論的。例如對于任意二次函數(shù) $\frac{1}{2}x^TGx+c(x)$ （黑森矩陣G中值任意所以可以表示任意二次函數(shù)），有 $\alpha=-\frac{\nabla f(x)^T d}{d^TGd}$ 。（證明見附錄）

但我們知道，計(jì)算機(jī)求解線性方程組的方法是高斯消元法，這是一個時間復(fù)雜度為 $o(n^3)$ 的算法。不僅對于高維情況耗時長，就算是低維情況、單次求解的耗時可以忍受，當(dāng)我們把求步長的算法整合進(jìn)整個迭代算法體系中、在每次迭代時都求解步長時，積累起來就是一個巨大的時間開銷。所以，如果目標(biāo)函數(shù)較為復(fù)雜，我們不能得出與任意二次函數(shù)的步長求解相似的結(jié)論時，我們通常使用非精確搜索。

2 步長的非精確搜索

2.1 Armijo線搜索

考慮泰勒展開 $f(x_k+\alpha_kd_k)=f(x_k)+\alpha_kg^T_kd_k+o(||\alpha_kd_k||^2)$ ，去掉極小項(xiàng)，我們可以在 $x_k$ 點(diǎn)處找到 $f(x)$ 的一條切線 $s(\alpha)=f(x_k)+g_k^Td_k \alpha$

在這里插入圖片描述

如圖所示的曲線為 $d_k$ 方向上函數(shù)的截線。結(jié)合圖像不難理解，若局部為凸函數(shù)，則局部最優(yōu)解出現(xiàn)在過 $x_k$ 點(diǎn)平行于 $\alpha$ 軸的直線與切線 $s(\alpha)=f(x_k)+g_k^Td_k \alpha$ 所夾范圍之間

我們讓 $s(\alpha)$ 向著平行于 $\alpha$ 軸的直線方向旋轉(zhuǎn)一個角度得到 $s'(\alpha)$ ，使 $s'(\alpha)$ 被 $s(\alpha)$ 和平行于 $\alpha$ 軸的直線所夾。其具體方法是在斜率上乘上一個 $0<\rho<1$ ，那么如圖紅色部分的點(diǎn)比起 $x_k$ 將更接近局部最優(yōu)解。

在這里插入圖片描述

這樣我們就使得函數(shù)的值在我們選取的方向上有了一定程度的下降。也許我們不能一次求出最優(yōu)解，但只要我們不斷迭代，并每次都保證搜索方向?yàn)橄陆捣较?/strong>，就能使得Armijo線搜索收斂到該方向上的一個局部最優(yōu)解。

例如，考慮最基本的情況，若函數(shù)只存在 $d_k$ 方向及其反方向，在紅色部分選取任意一個點(diǎn)（比如下降方向上 $s'(\alpha)$ 與 $f(x_k+\alpha_kd_k)$ 的第一個交點(diǎn)）作為 $x_{k+1}$ ，尋找下降方向并重復(fù)上述過程，最終就會以如圖所示的形式收斂到最優(yōu)解。

在這里插入圖片描述

因此Armijo線搜索的關(guān)鍵在于找到一個位于紅色區(qū)域內(nèi)的點(diǎn)。其具體方法是先假設(shè)一個步長 $\alpha$ ，若不滿足Armijo線性搜索條件就縮短該步長，直到滿足線性搜索條件。因?yàn)槲覀儽ＷC了 $s'(\alpha)$ 的斜率小于 $s(\alpha)$ ，所以這樣的步長必定是存在的，結(jié)合圖像也不難理解。

Armijo線搜索條件：給定 $\rho\in(0,1)$ ，計(jì)算 $\alpha_k$ 滿足 $f(x_k+\alpha_kd_k)\leq f(x_k)+\rho\alpha_k\nabla f(x_k)^Td_k$

步驟：

選取一個參數(shù) $\rho_1 \in (0,0.5)$

取 $\alpha_k=1$ ，若 $\alpha_k$ 滿足線性搜索條件，則得到 $\alpha_k$

取 $\alpha_k=\beta>0$ ，若 $\alpha_k$ 滿足線性搜索條件，則得到 $\alpha_k$

取 $\alpha_k=\rho_1 \alpha_k$

若 $\alpha_k$ 滿足線性搜索條件，則得到 $\alpha_k$ ，否則轉(zhuǎn)4

2.2 Wolfe-Powell搜索

在Armijo搜索的條件基礎(chǔ)上增加防止步長過小的條件，使得 $x_k+\alpha_kd_k$ 處曲線切線斜率 $\nabla f(x_k+\alpha_kd_k)^Td_k$ 具有下界 $\sigma\nabla f(x_k)^Td_k$ 。在之后的教程中我們會提到，這使得算法收斂性得到保證。

為保證 $\alpha_k$ 的存在性，通常取 $0<\sigma<\frac{1}{2}$

在這里插入圖片描述

則有Wolfe-Powell線搜索條件：給定 $\rho\in(0,1),\sigma\in(0,\frac{1}{2})$ ，計(jì)算 $\alpha_k$ 滿足 $\begin{cases}f(x_k+\alpha_kd_k)\leq f(x_k)+\rho\alpha_k\nabla f(x_k)^Td_k\\\nabla f(x_k+\alpha_kd_k)^Td_k\geq \sigma\nabla f(x_k)^Td_k\end{cases}$

步驟：

若 $\alpha_k=1$ 滿足Wolfe-Powell線搜索條件，則取 $\alpha_k=1$

給定常數(shù) $\beta>0$ ， $\rho_1\in(0,1)$ ，令 $\alpha_k^{(0)}$ 是集合 $\{\beta\rho_1^j\}$ 中滿足條件1的最大者，令i=0

若 $\alpha_k^{(i)}$ 滿足條件2，則取 $\alpha_k=\alpha_k^{(i)}$ ，否則令 $\beta_k=\rho^{-1}_1\alpha_k^{(i)}$

令 $\alpha_k^{(i+1)}$ 是集合 $\{\alpha_k^{(i)}+\rho_1^j(\beta_k^{(i)}-\alpha_k^{(i)}),j=0,1,2...\}$ 中滿足條件1的最大者，令 $i=i+1$ ，轉(zhuǎn)步3

這個搜索過程可以直觀地使用下圖理解:

在這里插入圖片描述

2.3 強(qiáng)條件的Wolfe-Powell搜索

在Wolfe-Powell搜索的條件基礎(chǔ)上增加防止步長過大的條件，使得 $x_k+\alpha_kd_k$ 處曲線切線斜率 $\nabla f(x_k+\alpha_kd_k)^Td_k$ 具有上界 $-\sigma\nabla f(x_k)^Td_k$ ，也就是說條件轉(zhuǎn)化為了：給定 $\rho\in(0,1),\sigma\in(0,\frac{1}{2})$ ，計(jì)算 $\alpha_k$ 滿足 $\begin{cases}f(x_k+\alpha_kd_k)\leq f(x_k)+\rho\alpha_k\nabla f(x_k)^Td_k\\\nabla f(x_k+\alpha_kd_k)^Td_k\geq \sigma\nabla f(x_k)^Td_k\\\nabla f(x_k+\alpha_kd_k)^Td_k\leq -\sigma\nabla f(x_k)^Td_k\end{cases}$

步驟：

若 $\alpha_k=1$ 滿足Wolfe-Powell線搜索條件，則取 $\alpha_k=1$

給定常數(shù) $\beta>0$ ， $\rho_1\in(0,1)$ ，令 $\alpha_k^{(0)}$ 是集合 $\{\beta\rho_1^j\}$ 中滿足條件1和條件3的最大者，令i=0

若 $\alpha_k^{(i)}$ 滿足條件2，則取 $\alpha_k=\alpha_k^{(i)}$ ，否則令 $\beta_k=\rho^{-1}_1\alpha_k^{(i)}$

令 $\alpha_k^{(i+1)}$ 是集合 $\{\alpha_k^{(i)}+\rho_1^j(\beta_k^{(i)}-\alpha_k^{(i)}),j=0,1,2...\}$ 中滿足條件1和條件3的最大者，令 $i=i+1$ ，轉(zhuǎn)步3

一般情況下的步長計(jì)算問題，只需要用普通的Wolfe-Powell搜索即可。而強(qiáng)條件的Wolfe-Powell搜索則在一些特殊的下降算法中有用武之地，這在我們之后的教程中會提到。

代碼實(shí)現(xiàn)

本博客所有代碼在https://github.com/HarmoniaLeo/optimization-in-a-nutshell開源，如果幫助到你，請點(diǎn)個star，謝謝這對我真的很重要！

你可以在上面的GitHub鏈接或本文集的第一篇文章深入淺出最優(yōu)化(1) 最優(yōu)化問題概念與基本知識中找到Function.py和lagb.py

Armijo線搜索：

import numpy as np from Function import Function #定義法求導(dǎo)工具 from lagb import * #線性代數(shù)工具庫 #假設(shè)d已經(jīng)給出 a=1 #步長初值 beta1=1 #β值 rho=0.55 #ρ1值 tar=Function(myFunc) #初始化函數(shù) if not (tar.value(x+a*d)<=tar.value(x)+rho*a*dot(turn(tar.grad(x)),d): a=beta1 while tar.value(x+a*d)>tar.value(x)+rho*a*dot(turn(tar.grad(x)),d)): a*=rho

Wolfe-Powell搜索：

import numpy as np from Function import Function #定義法求導(dǎo)工具 from lagb import * #線性代數(shù)工具庫 #假設(shè)d已經(jīng)給出 a=1 #步長初值 beta1=1 #β值 rho=0.55 #ρ1值 sigma=0.4 #σ值 tar=Function(myFunc) #初始化函數(shù) if not (tar.value(x+a*d)<=tar.value(x)+rho*a*dot(turn(tar.grad(x)),d) and dot(turn(tar.grad(x+a*d)),d)>=sigma*dot(turn(tar.grad(x)),d)): a=beta1 while tar.value(x+a*d)>tar.value(x)+rho*a*dot(turn(tar.grad(x)),d): a*=rho while dot(turn(tar.grad(x+a*d)),d)<sigma*dot(turn(tar.grad(x)),d): a1=a/rho da=a1-a while tar.value(x+(a+da)*d)>tar.value(x)+rho*(a+da)*dot(turn(tar.grad(x)),d): da*=rho a+=da

強(qiáng)條件的Wolfe-Powell搜索：

import numpy as np from Function import Function #定義法求導(dǎo)工具 from lagb import * #線性代數(shù)工具庫 #假設(shè)d已經(jīng)給出 a=1 #步長初值 beta1=1 #β值 rho=0.55 #ρ1值 sigma=0.4 #σ值 tar=Function(myFunc) #初始化函數(shù) if not (tar.value(x+a*d)<=tar.value(x)+rho*a*dot(turn(tar.grad(x)),d) and np.abs(dot(turn(tar.grad(x+a*d)),d))>=sigma*dot(turn(tar.grad(x)),d)): a=beta1 while tar.value(x+a*d)>tar.value(x)+rho*a*dot(turn(tar.grad(x)),d) and dot(turn(tar.grad(x+a*d)),d)>-sigma*dot(turn(tar.grad(x)),d): a*=rho while dot(turn(tar.grad(x+a*d)),d)<sigma*dot(turn(tar.grad(x)),d): a1=a/rho da=a1-a while tar.value(x+(a+da)*d)>tar.value(x)+rho*(a+da)*dot(turn(tar.grad(x)),d) and dot(turn(tar.grad(x+a*d)),d)>-sigma*dot(turn(tar.grad(x)),d): da*=rho a+=da

附錄

二次函數(shù)步長求法：

對于 $f(x)=\frac{1}{2}x^TQx+q^Tx+c$ ，

在這里插入圖片描述