02无约束最优化方法的基本结构

Lingfeng 2024-09-19

02无约束最优化方法的基本结构

1. 收敛性和收敛速度

Definition (收敛速度)

若 $\lim_{ k \to \infty } \frac{\left\lVert x_{k+1}-x^{*} \right\rVert}{\left\lVert x_{k}-x^{*} \right\rVert }=a$ 当 $0<a<1$ 时，称算法是线性收敛的；当 $a=0$ 时，称算法是超线性收敛的。
若 $\lim_{ k \to \infty } \frac{\left\lVert x_{k+1}-x^{*} \right\rVert }{\left\lVert x_{k}-x^{*} \right\rVert ^{2}}=a$ 其中 $a$ 为任意常数，此时称算法是二阶收敛的。

2. 线搜索准则

2.1 精确线搜索准则

Definition (精确线搜索)

当迭代方向 $\boldsymbol{d}_{k}$ 已知时，精确线搜索准则使 $f(\boldsymbol{x})$ 沿 $\boldsymbol{d}_{k}$ 关于步长 $\alpha$ 取极小值，即 $\min_{\alpha}f(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})$

Theorem (精确线搜索性质)

达到精确线搜索时，令 $\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k}$ ，此时有 $g^{T}_{k+1}\boldsymbol{d}_{k}=0$

证明
令 $\frac{df(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})}{d\alpha}=0$ 注意到由链式法则 $\frac{df(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})}{d\alpha}=g(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})^{T}\boldsymbol{d_{k}}$ 即得 $g^{T}_{k+1}\boldsymbol{d}_{k}=0$

2.2 非精确线搜索准则

Definition (Armijo准则)

f(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})\leq f(\boldsymbol{x}_{k})+\rho g_{k}^{T}\boldsymbol{d}_{k}\alpha

Definition (Goldstein准则)

\begin{align*} f(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})&\leq f(\boldsymbol{x}_{k})+\rho g_{k}^{T}\boldsymbol{d} _{k}\alpha \\ f(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k}) &\geq f(\boldsymbol{x}_{k})+(1-\rho)g_{k}^{T}\boldsymbol{d}_{k}\alpha\end{align*}

Definition (Wolfe准则)

$\begin{align*} f(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})&\leq f(\boldsymbol{x}_{k})+\rho g_{k}^{T}\boldsymbol{d} _{k}\alpha \\ g(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})^{T}\boldsymbol{d}_{k}& \geq \sigma g_{k}^{T}\boldsymbol{d}_{k}\end{align*}$ 其中 $0<\rho<\sigma<1$ 。

Definition (强Wolfe准则)

$\begin{align*} f(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})&\leq f(\boldsymbol{x}_{k})+\rho g_{k}^{T}\boldsymbol{d} _{k}\alpha \\ \lvert g(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})^{T}\boldsymbol{d}_{k} \rvert & \leq -\sigma g_{k}^{T}\boldsymbol{d}_{k}\end{align*}$ 其中 $0<\rho<\sigma<1$ 。

3. 线搜索求步长

3.1 0.618方法

Definition (0.618方法)

通过进退法求得初始区间，其包含 $\phi(\alpha)=f(\boldsymbol{x}_{k}+\alpha \boldsymbol{d}_{k})$ 的极小点。
得到初始区间后，按照0.618比例不断缩小，使 $\phi(\alpha)$ 极小点 $\alpha^{*}$ 始终包含在缩小的区间中，直至区间足够小。

设 $\phi(\alpha)$ 是区间 $[a,b]$ 上的单峰函数， $[a_{0},b_{0}]=[a,b]$ ，选择两个点 $a_{0}^{l}$ ， $a_{0}^{r}$ 使得 $a_{0}^{r}-a_{0}=b_{0}-a_{0}^{l}=\tau(b_{0}-a_{0})$ 其中 $\tau>0.5$ 。此时若 $\phi(a_{0}^{l})<\phi(a_{0}^{r})$ ，则 $a^{*}\in[a_{0},a_{0}^{r}]$ ，取 $[a_{1},b_{1}]=[a_{0},a_{0}^{r}]$ ，反之取另一区间。

此时我们需要使用相同比例缩小区间，并且使得 $a_{1}^{r}$ 和 $a_{0}^{l}$ 是重合的。此时有 $a_{1}^{r}-a_{1}=\tau(b_{1}-a_{1})=(1-\tau)(b_{0}-a_{0})$ 因此 $\tau^{2}=1-\tau$ 即得到 $\tau=0.618$ 。

3.2 多项式插值法

Definition (多项式插值法)

构造近似 $\phi(\alpha)$ 的多项式函数，求其极小点，检验是否满足非精确线搜索准则。
若不满足，根据新信息构造新的多项式函数，如此反复。

Definition (两点二次插值法)

已知在 $0$ ， $\alpha_{0}$ 有 $\phi(0)=f(\boldsymbol{x}_{k})$ ， $\phi'(0)=g_{k}^{T}\boldsymbol{d}_{k}$ ， $\phi(\alpha_{0})=f(\boldsymbol{x}_{k}+\alpha_{0}\boldsymbol{d}_{k})$ ，且 $\alpha_{0}$ 不满足准则。此时构造 $p(\alpha)=a\alpha^{2}+b\alpha+c$ 计算出极小点 $\alpha_{1}$ 。

Definition (三点三次插值法)

已知在 $0$ ， $\alpha_{0}$ ， $\alpha_{1}$ 三个点有 $\phi(0)=f(\boldsymbol{x}_{k})$ ， $\phi'(0)=g_{k}^{T}\boldsymbol{d}_{k}$ ， $\phi(\alpha_{0})=f(\boldsymbol{x}_{k}+\alpha_{0}\boldsymbol{d}_{k})$ ， $\phi(\alpha_{0})=f(\boldsymbol{x}_{k}+\alpha_{0}\boldsymbol{d}_{k})$ ，且 $\alpha_{0}$ ， $\alpha_{1}$ 不满足准则。此时构造 $p(\alpha)=a\alpha^{3}+b\alpha^{2}+c\alpha^{2}+d$ 计算出极小点 $\alpha_{2}$ 。

4. 信赖域方法

4.1 定义

Definition (信赖域方法)

设定信赖域半径 $\Delta_{k}$ ，在领域内根据泰勒展开式用二次函数近似 $f(\boldsymbol{x}_{k}+\boldsymbol{d})$ ，即 $q_{k}(\boldsymbol{d})=f_{k}+g_{k}^{T}\boldsymbol{d}+ \frac{1}{2}\boldsymbol{d}^{T}G_{k}\boldsymbol{d}$ 此时求出 $q_{k}(\boldsymbol{d})$ 在领域内的极小点 $\begin{align*} & \min_{\boldsymbol{d}}q_{k}(\boldsymbol{d}) \\ & s.t. \left\lVert \boldsymbol{d} \right\rVert\leq \Delta_{k} \end{align*}$ 此时 $\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}+\boldsymbol{d}_{k}$ ，重复以上步骤。

其中定义比值 $\rho_{k}= \frac{f(\boldsymbol{x}_{k})-f(\boldsymbol{x}_{k}+\boldsymbol{d}_{k})}{q_{k}(0)-q_{k}(\boldsymbol{d_{k}})}$

若 $\rho_{k}$ 接近1（ $>0.75$ ），则增大 $\Delta_{k}$ （ $\Delta_{k+1}=2\Delta_{k}$ ）。
若 $\rho_{k}$ 接近0（ $<0.25$ ），则缩小 $\Delta_{k}$ （ $\Delta_{k+1}=0.25\Delta_{k}$ ）。
若 $\rho_{k} \in (0.25,0.75)$ ，则 $\Delta_{k+1}=\Delta_{k}$ ）。
若 $\rho_{k}<0$ ，则令 $\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}$ ，缩小 $\Delta_{k}$ ，重新求解。

4.2 信赖域子问题求解

Definition (Dogleg方法)

给出 $\Delta$ 。
计算 $\boldsymbol{d^{*}}=-G^{-1}g_{k}$ ，若 $\left\lVert \boldsymbol{d}_{k} \right\rVert\leq\Delta$ ，则 $\boldsymbol{d_{k}}=\boldsymbol{d}^{*}$ 。
如果 $\alpha \left\lVert g_{k} \right\rVert\geq\Delta$ ，则 $\boldsymbol{d}_{k}=-\Delta \frac{g}{\left\lVert g \right\rVert}$ 。
否则，计算 $\boldsymbol{d}=-(1-\beta)\alpha g_{k}+\beta \boldsymbol{d}^{*}$ ，使得 $\left\lVert \boldsymbol{d} \right\rVert=\Delta$ 。