无约束优化-----最速下降法和二分线搜索方法
无约束最优化问题:
\[\begin{align*} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\ \text{s.t.} &~ ~ ~x ∈ X ⊆ R^n \end{align*} \]1最速下降法思想
方向\(d = −∇f(\bar{x})\),叫做\(\bar{x}\)点处最速下降方向，注意，\(∇f(\bar{x})^T d < 0\)只要\(∇f(x) \neq 0\)。
算法流程：
给定起始点$ x_0\in dom \ f,k=0 $，容许误差 $\epsilon >0 $,
-
计算方向\(d^k=− ∇f({x}^k)\) 。
-
停止条件：如果 \(d^k=0,或者(d^k)^2/2<\epsilon\)则退出。
-
直线搜索：用精确性搜索或者非精确性搜索选择步长 \(α_k\)，用 \(α_k\)求出\(\min_α ~ ~ ~ f(x^k + α_kd^k)\)
-
迭代： \(x^{k+1} = x^k + α_kd^k, k = k + 1\). 转到步骤1。
2二次型函数的最速下降法
二次型函数最小化问题:
\[\begin{equation}min~~~ f \left( x \right) = \frac{1}{2} x^TA x - b^T x \tag{2} \end{equation} \]如果对该函数求导，并令导数为零，我们得到
\[\begin{equation} \nabla f \left( x \right) = A x - b = 0 \tag{3} \end{equation} \]如何得到\(f(x)\)的最小值?
有一个形象的方法,从任意一点\(x_{(0)}\)出发,每次沿着当前位置下降最快的方向走,也就是该点处的负梯度方向。
从而得到一系列的解序列:\(x_{(1)},x_{(2),}…\)直到两次下降的差小于给定的误差限为止。
由公式(3),每次迭代的梯度记为\(f′(x_{(i)})=Ax_{(i)}−b\)，下面记误差(error)为\(e_{(i)}=x_{(i)}−x\)，负梯度方向为\(r_{(i)}=b−Ax_{(i)}\).
于是有
\[\begin{array}{**lr**} r_{(i)}=-f'(x_{(i)})\\ x_{(i+1)}=x_{(i)}+\alpha_{(i)}r_{(i)} \end{array} \]其中\(\alpha_{(i)}\)为第\(i\)步沿着方向\(r_{(i)}\)的步长.
如何选取步长\(\alpha_{(i)}\)呢？朴素的想法是选取的步长尽量要让\(f(x_{i+1})\)的值最小,这样才能更快的到达\(f(x)\)的全局最小值。
我们把\(f(x_{i+1})\)看作含有\(\alpha_{(i)}\)的函数,要使得步长最合适,也就相当于导数=0：
\[\frac{d}{d\alpha_{(i)}}f(x_{(i+1)})=0 \]根据链式法则
\[% <![CDATA[ \begin{align*} \frac{d}{d\alpha_{(i)}}f(x_{(i+1)})&=f'(x_{(i+1)})^T\frac{d}{d\alpha_{(i)}}x_{(i+1)}\\ &=-r_{(i+1)}^Tr_{(i)} \end{align*} %]]> \]也就是说,\(r_{(i)}\)与\(r_{(i+1)}\)正交
\[% <![CDATA[ \begin{align*} r_{(i+1)}^Tr_{(i)}&=0\\ (b-Ax_{(i+1)})^Tr_{(i)}&=0\\ (b-A(x_{(i)}+\alpha_{(i)}r_{(i)}))^Tr_{(i)}&=0\\ (b-Ax_{(i)})^Tr_{(i)}-\alpha_{(i)}(Ar_{(i)})^Tr_{(i)}&=0\\ (b-Ax_{(i)})^Tr_{(i)}&=\alpha_{(i)}(Ar_{(i)})^Tr_{(i)}\\ \alpha_{(i)}&=\frac{r_{(i)}^Tr_{(i)}}{r_{(i)}^TAr_{(i)}}. \end{align*} %]]> \]也就是说,每一步的步长都可以根据当前的负梯度方向\(r_{(i)}\)来确定
总结一下,最速下降法就是:
\[% <![CDATA[ \begin{align*} r_{(i)}&=b-Ax_{(i)}\\ \alpha_{(i)}&=\frac{r_{(i)}^Tr_{(i)}}{r_{(i)}^TAr_{(i)}}\\ x_{(i+1)}&=x_{(i)}+\alpha_{(i)}r_{(i)}. \end{align*} %]]> \]这样迭代下去,直到达到事先给定的最小误差限制\(ϵ\)为止
当然,有的时候,出于减小复杂度的考虑,我们会换用这种手段来求\(r_{(i)}\)
\[r_{(i+1)}=r_{(i)}-\alpha_{(i)}Ar_{(i)} \]这个公式是在\(x_{(i+1)}=x_{(i)}+\alpha_{(i)}r_{(i)}\)的两边左乘\(−A\)再加上b得到的。
这样每次迭代过程我们只需要算一次矩阵乘法,可以减少运算。
https://zhuanlan.zhihu.com/p/165619326
https://zhuanlan.zhihu.com/p/104947883
https://zhuanlan.zhihu.com/p/23776390
https://blog.csdn.net/Timingspace/article/details/50963564
https://zhuanlan.zhihu.com/p/67564794