无约束优化-----最速下降法和二分线搜索方法

无约束最优化问题:

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 $,

1. 计算方向\(d^k=? ?f({x}^k)\) 。

2. 停止条件：如果 \(d^k=0,或者(d^k)^2/2<\epsilon\)则退出。

3. 直线搜索：用精确性搜索或者非精确性搜索选择步长 \(α_k\)，用 \(α_k\)求出\(\min_α ~ ~ ~ f(x^k + α_kd^k)\)

4. 迭代： \(x^{k+1} = x^k + α_kd^k, k = k + 1\). 转到步骤1。

2二次型函数的最速下降法

二次型函数最小化问题:

如果对该函数求导，并令导数为零，我们得到

如何得到\(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)}\).

于是有

其中\(\alpha_{(i)}\)为第\(i\)步沿着方向\(r_{(i)}\)的步长.

如何选取步长\(\alpha_{(i)}\)呢？朴素的想法是选取的步长尽量要让\(f(x_{i+1})\)的值最小,这样才能更快的到达\(f(x)\)的全局最小值。

我们把\(f(x_{i+1})\)看作含有\(\alpha_{(i)}\)的函数,要使得步长最合适,也就相当于导数=0：

根据链式法则

也就是说,\(r_{(i)}\)与\(r_{(i+1)}\)正交

也就是说,每一步的步长都可以根据当前的负梯度方向\(r_{(i)}\)来确定

总结一下,最速下降法就是:

这样迭代下去,直到达到事先给定的最小误差限制\(?\)为止

当然,有的时候,出于减小复杂度的考虑,我们会换用这种手段来求\(r_{(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

优化04

原文：https://www.cnblogs.com/liangjiangjun/p/14022650.html