精品一区、二区、三区,青青艹综合视频

1 下降算法中的搜索方向

1.1 下降方向的判定

根據(jù)泰勒展開 $f(x_k+\alpha_kd_k)=f(x_k)+\alpha_kg^T_kd_k+o(||\alpha_kd_k||^2)$ ，忽略極小項后，我們可以在 $x_k$ 點處找到 $f(x)$ 的一條切線 $s(\alpha)=f(x_k)+g_k^Td_k \alpha$ ，這條切線的斜率是 $g_k^Td_k$ 。我們不難得出結論，如果 $g_k^Td_k<0$ ，則該方向為下降方向。

1.2 下降算法的收斂性

前面我們給出過下降算法的收斂性的定義：對于迭代序列 $x^{(k)}$ ，k趨近于無窮時一階偏導向量的范數(shù)為0。之后我們在介紹精確搜索與非精確搜索時均強調(diào)了搜索方向必須是下降方向。事實上，如果步長由精確搜索或者Wolfe-Powell搜索產(chǎn)生，而每一步的搜索方向都是下降方向，則必定滿足下降算法的收斂性。（證明見附錄1）

因此接下來我們在研究計算搜索方向的算法時，最重要的前提就是計算出的搜索方向應當是下降方向。而步長計算則使用精確搜索、Wolfe-Powell搜索或強條件的Wolfe-Powell搜索。

2 最速梯度下降法

2.1 最速梯度下降法步驟

既然我們要尋找下降方向，我們首先想到的就是梯度的反方向。函數(shù)沿著梯度方向數(shù)值上升最快，那么沿著梯度的反方向數(shù)值下降也就最快。所以，對于每一步，將負梯度方向作為下降方向的方法，又叫最速梯度下降法。

在這里插入圖片描述

步驟：

給定初始點 $x_0\in R^n$ ，精度 $\epsilon>0$ ，令 $k=0$
若 $||\nabla f(x_k)||\leq\epsilon$ ，則得解 $x_k$ ，算法終止
計算 $d_k=-\nabla f(x_k)$
計算步長 $\alpha_k$
令 $x_{k+1}=x_k+\alpha_kd_k,k=k+1$ ，轉(zhuǎn)步2

2.2 性能評估

收斂性：因為每一步均產(chǎn)生下降方向，所以必定收斂。
收斂速度：用正定二次函數(shù)逼近點附近的函數(shù)。若該正定二次函數(shù)黑森矩陣的所有特征值相等，則超線性收斂；其余時候線性收斂。（證明見附錄2）
二次終止性：顯然滿足
計算量：小，只需要計算梯度
儲存空間：小，只需要儲存梯度

2.3 實戰(zhàn)測試

對于本文集的第一篇文章深入淺出最優(yōu)化(1) 最優(yōu)化問題概念與基本知識中提出的最小二乘問題， $x_1,x_2,x_3,x_4$ 的初值均在 $[-2,2]$ 的范圍內(nèi)隨機生成，總共生成100組起點。統(tǒng)計迭代成功（在1000步內(nèi)得到最優(yōu)解且單次步長搜索迭代次數(shù)不超過1000次）的樣本的平均迭代步數(shù)、平均迭代時間和得到的最優(yōu)解及殘差平方和最小值。

平均迭代步數(shù)	平均迭代時間	最優(yōu)解	殘差平方和最小值
234.68	3.31s	$x_1=0.1755~x_2=0.3717~x_3=0.0439~ x_4=0.2290$	$2.3065\times10^{-4}$

3 阻尼牛頓法

3.1 阻尼牛頓法步驟

古典牛頓法的思想是用近似二次函數(shù)的極小點作為原問題的新的近似解。 $f(x)$ 在 $x_k$ 處二階泰勒展開式為 $f(x)=f(x_k)+\nabla f(x_k)^T(x-x_k)+\frac{1}{2}(x-x_k)^T\nabla^2f(x_k)(x-x_k)+o(||x-x_k||^2)$ ，二次近似函數(shù) $Q(x)=f(x_k)+\nabla f(x_k)^T(x-x_k)+\frac{1}{2}(x-x_k)^T\nabla^2f(x_k)(x-x_k)$ ，且 $\nabla Q(x)=\nabla f(x_k)+\nabla^2f(x_k)(x-x_k)$ ，若 $\nabla^2f(x_k)$ 正定，則 $Q(x)$ 的極小點為 $\nabla f(x_k)+\nabla^2f(x_k)(x-x_k)$ 的解，把二次函數(shù)的極小點作為 $x_{k+1}$ ，則 $x_{k+1}=x_k-\nabla^2f(x_k)^{-1}\nabla f(x_k)$ ，稱該迭代公式為古典牛頓法的迭代公式，其中 $d_k=-\nabla^2f(x_k)^{-1}\nabla(x_k)$ 為 $x_k$ 處的牛頓方向。

在這里插入圖片描述

如果目標函數(shù)就是二次函數(shù)，則向著牛頓方向步長為1的搜索可以直接搜索到局部最優(yōu)解。但如果二次函數(shù)僅僅是目標函數(shù)的近似，則步長需要使用Wolfe-Powell搜索來求取，這時候算法被稱為阻尼牛頓法。

步驟：

定初始點 $x_0\in R^n$ ，精度 $\epsilon>0$ ，令 $k=0$
若 $||\nabla f(x_k)||\leq\epsilon$ ，則得解 $x_k$ ，算法終止
$d_k=-\nabla^2f(x_k)^{-1}\nabla(x_k)$
計算步長 $\alpha_k$
令 $x_{k+1}=x_k+\alpha_kd_k,k=k+1$ ，轉(zhuǎn)步2

3.2 性能評估

收斂性：當且僅當每一步都有目標函數(shù)的黑森矩陣，也就是近似二次函數(shù)的黑森矩陣正定時，牛頓方向才是下降方向，所以收斂性不能保證。
收斂速度：若在最優(yōu)解附近二階連續(xù)可微且最優(yōu)解處梯度為0、黑森矩陣正定，則算法超線性收斂。特別地，若目標函數(shù)在最優(yōu)解處二階李普希茲連續(xù)，則算法二階收斂。（證明見附錄3）
二次終止性：顯然滿足
計算量：大，需要計算黑森矩陣，在變量數(shù)目多時計算量大
儲存空間：大，需要儲存黑森矩陣，在變量數(shù)目多時需要儲存空間大

4 牛頓-梯度下降混合法

4.1 牛頓-梯度下降混合法步驟

由于我們不能保證牛頓法產(chǎn)生下降方向，但又希望能夠借助牛頓法的二階收斂性提高最速梯度下降法的收斂速度，我們可以將兩者進行融合。對于牛頓法無法產(chǎn)生下降方向的時刻，使用最速梯度下降法來產(chǎn)生下降方向。

步驟：

定初始點 $x_0\in R^n$ ，精度 $\epsilon>0$ ，令 $k=0$
若 $||\nabla f(x_k)||\leq\epsilon$ ，則得解 $x_k$ ，算法終止
$d_k=-\nabla^2f(x_k)^{-1}\nabla(x_k)$
若 $\nabla f(x_k)^Td_k\geq0$ ，取 $d_k=-\nabla f(x_k)$
計算步長 $\alpha_k$
令 $x_{k+1}=x_k+\alpha_kd_k,k=k+1$ ，轉(zhuǎn)步2

4.2 實戰(zhàn)測試

對于本文集的第一篇文章深入淺出最優(yōu)化(1) 最優(yōu)化問題概念與基本知識中提出的最小二乘問題， $x_1,x_2,x_3,x_4$ 的初值均在 $[-2,2]$ 的范圍內(nèi)隨機生成，總共生成100組起點。統(tǒng)計迭代成功率（在1000步內(nèi)得到最優(yōu)解且單次步長搜索迭代次數(shù)不超過1000次）、平均迭代步數(shù)、平均迭代時間和得到的最優(yōu)解及殘差平方和最小值。

平均迭代步數(shù)	平均迭代時間	最優(yōu)解	殘差平方和最小值
56.0	1.02s	$x_1=0.1926~x_2=0.1816~x_3=0.1158~ x_4=0.1321$	$1.5397\times10^{-4}$

代碼實現(xiàn)

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

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

最速下降法：

import numpy as np
from Function import Function   #定義法求導工具
from lagb import *  #線性代數(shù)工具庫

n=2 #x的長度

def myFunc(x):  #x是一個包含所有參數(shù)的列表
    return x[0]**2 + 2*x[1]**2 + 2*x[0] - 6*x[1] +1 #目標方程

x=np.zeros(n)   #初值點
rho=0.6
beta=1
sigma=0.4
e=0.001
k=0
tar=Function(myFunc)
while tar.norm(x)>e:
    d=-tar.grad(x)
    a=1
    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=beta
        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
    x+=a*d
    k+=1
    print(k)
print(x)

牛頓-梯度下降混合法：

import numpy as np
from Function import Function   #定義法求導工具
from lagb import *  #線性代數(shù)工具庫
from scipy import linalg

n=2 #x的長度

def myFunc(x):  #x是一個包含所有參數(shù)的列表
    return x[0]**2 + 2*x[1]**2 + 2*x[0] - 6*x[1] +1 #目標方程

x=np.zeros(n)   #初值點
rho=0.6
beta=1
e=0.001
sigma=0.4
k=0
tar=Function(myFunc)
while tar.norm(x)>e:
    try:
        d=linalg.solve(tar.hesse(x),-tar.grad(x))
        if tar.value(x)-tar.value(x+d)<0:
            d=-tar.grad(x)
    except Exception:
        d=-tar.grad(x)
    a=1
    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=beta
        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
    x+=a*d
    k+=1
    print(k)
print(x)

附錄

記向量 $d_k$ 和 $-\nabla f(x_k)$ 的夾角為 $\theta_k$ ，則有 $cos=\frac{-\nabla f(x_k)^Td_k}{||\nabla f(x_k)||~||d_k||}$

給出下面的基本假設： $f(x)$ 連續(xù)可微且有下界，且 $\nabla f(x)$ 李普希茲連續(xù)，即存在常數(shù) $L>0$ ，使得 $||\nabla f(x)-\nabla f(y)||\leq L||x-y||$

則有定理，若序列 $\{x_k\}$ 由下降算法產(chǎn)生，其中步長 $\alpha_k$ 由精確搜索或Wolfe-Powell搜索產(chǎn)生，則 $\displaystyle\sum_{k=0}^∞||\nabla f(x_k)||^2cos^2\theta_k<+∞$ 。特別地，若存在常數(shù) $\delta>0$ 使得 $cos\theta_k\geq\delta$ ，則 $\displaystyle\lim_{k→∞}||\nabla f(x_k)||=0$ 。這個定理說明了產(chǎn)生的方向與負梯度方向夾角小于 $\frac{\pi}{2}$ 時，可以保證算法收斂性。

下面根據(jù)假設證明該定理：由Wolfe-Powell搜索條件及假設，我們有 $-(1-\sigma)\nabla f(x_k)^Td_k\leq[\nabla f(x_k+\alpha_kd_k)-\nabla f(x_k)]^Td_k\leq\alpha_kL||d_k||^2$ ，即可得 $\alpha_k\geq-\frac{1-\sigma}{L}\frac{\nabla f(x_k)^Td_k}{||d_k||^2}=-c_1\frac{\nabla f(x_k)^Td_k}{||d_k||^2}$ 。這里 $c_1=\frac{1-\sigma}{L}$ ，進一步由Wolfe-Powell搜索第一個條件，得 $f(x_k+\alpha_kd_k)-f(x_k)\leq-\rho c_1\frac{[\nabla f(x_k)^Td_k]^2}{||d_k||^2}=-\rho c_1||\nabla f(x_k)||^2cos^2\theta_k$

將上面的不等式左右兩邊從 $k=0$ 到 $∞$ 相加，并注意到 $f(x)$ 有下界，可以得到定理第一條成立，由無窮級數(shù)收斂的必要條件可以得到第二條定理成立。

最速梯度下降法收斂速度證明：https://blog.csdn.net/weixin_43010548/article/details/97619095
牛頓法收斂速度證明：

提出定理：設 $f$ 在 $x^*\in R^n$ 的某個鄰域內(nèi)二次連續(xù)可微且 $x^*$ 滿足 $\nabla f(x^*)=0$ ， $\nabla^2 f(x^*)$ 正定，則存在常數(shù) $\delta>0$ ，使得當 $x_0\in U_\delta(x^*)=\{x|||x-x^*||<\delta\}$ 時，由單位步長牛頓法 $x_{k+1}=x_k-\nabla^2 f(x_k)^{-1}\nabla f(x_k),k=0,1,2,...$ 產(chǎn)生的序列超線性收斂于 $x^*$ ，此外，若 $\nabla^2f$ 在 $x^*$ 李普希茲連續(xù)，則序列 $\{x_k\}$ 二次收斂于 $x^*$ 。