最优化上机报告（信赖域）

2019-12-23 本文已影响0人苏格兰低地弟弟打滴滴

第三次上机作业

王秋皓

2015012101

本上机作业报告分成四个部分：一，信赖域方法概述；二，数值实验；三，总结/与线搜索比较

信赖与方法概述

函数在任意一点 $x_k$ 处有二次泰勒展开的形式： $f\left(x_{k}+p\right)=f_{k}+g_{k}^{T} p+\frac{1}{2} p^{T} \nabla^{2} f\left(x_{k}+t p\right) p$ ，信赖域方法的思想就是每一步用一个对称矩阵B替代二阶项里的hessian矩阵：

$m_{k}(p)=f_{k}+g_{k}^{T} p+\frac{1}{2} p^{T} B_{k} p$

得到一个 f 局部的逼近。然后在一个小范围内求解下面的优化问题：

$\min _{p \in R^{n}} m_{k}(p)=f_{k}+g_{k}^{T} p+\frac{1}{2} p^{T} B_{k} p \quad \text { s.t. }\|p\| \leq \Delta_{k}$

求出来的p作为x的更新方向。

由于我们往往难以得到上面优化问题准确的解，但是一个近似的解往往就有很好的效果。

在求出p之后，我们用系数： $\rho_{k}=\frac{f\left(x_{k}\right)-f\left(x_{k}+p_{k}\right)}{m_{k}(0)-m_{k}\left(p_{k}\right)}$ 衡量近似的效果。如果rho很接近1，说明二次近似拟合的很好，而且f得到了足够的下降，所以这时候我们的信赖域半径是比较可靠的，可以稍微放大以期更快的下降。如果rho特别小，甚至小于0（那 f 反而增加了），说明拟合效果不好，所以我们应该缩小信赖域半径，让函数拟合更好点。

基于这样的思路，在不同的选择p的框架下，算法中信赖域大小选择遵循以下的算法：

有以下三种常用的方法求p：

Cauchy方法：最速下降法本身就有全局收敛性质，所以直接往负梯度方向下降，限制步长为delta，是一种方法。设范数为delta的方向： $p_{k}^{s}=-\frac{\Delta_{k}}{\left\|g_{k}\right\|} g_{k}$ ,我们的下降的p取为 $p_{k}^{C}=-\tau_{k} \frac{\Delta_{k}}{\left\|g_{k}\right\|} g_{k}$ ，解二次函数极小值问题就很容易得到：

$\tau_{k}=\left\{\begin{array}{ll}{1} & {\text { if } g_{k}^{T} B_{k} g_{k} \leq 0} \\{\min \left(\left\|g_{k}\right\|^{3} /\left(\Delta_{k} g_{k}^{T} B_{k} g_{k}\right), 1\right)} & {\text { otherwise }}\end{array}\right.$

Hebden 方法 ：分析信赖域方法可知道，d*是最优的方向当且仅当 $\begin{array}{l}{(B+\lambda I) d^{*}=-g_{k}} \\{\lambda\left(\left\|d^{*}\right\|-\Delta\right)=0}\end{array}$ 以及 $(B+\lambda I)$ 是半正定成立。所以考虑正交分解： $B=Q \Lambda Q^{T}$

得到 $p(\lambda)=-(B+\lambda I)^{-1} g=-Q(\Lambda+\lambda I)^{-1} Q^{T} g=-\sum_{j=1}^{n} \frac{q_{j}^{T} g}{\lambda_{j}+\lambda} q_{j}$

根据q的正交性得到： $\|p(\lambda)\|^{2}=\sum_{j=1}^{n} \frac{\left(q_{j}^{T} g\right)^{2}}{\left(\lambda_{j}+\lambda\right)^{2}}$

我们想要找lambda让上式等于delta^2，简单分析可知在 $\lambda \in\left(-\lambda_{1}, \infty\right)$ 中刚好有一个lambda满足。

所以我们可以做一个子问题的迭代，去比较快找到这个lambda的近似。以下方法被证明是有效的：

考虑一个函数 $\phi_{2}(\lambda)=\frac{1}{\Delta}-\frac{1}{\|p(\lambda)\|}$ ，采用这样的迭代方式： $\lambda^{(l+1)}=\lambda^{(l)}-\frac{\phi_{2}\left(\lambda^{(l)}\right)}{\phi_{2}^{\prime}\left(\lambda^{(l)}\right)}$