数值优化（Numerical Optimization）(2)-信赖域法

2024-02-29 18:11:46

数值优化（Numerical Optimization）(2)-信赖域法

养生的控制人浙江大学控制科学与工程博士在读

信赖域子问题与 Fidelity

信赖域法的思想很好理解：就是利用一个好解的局部模型 $m_x(p)$ 来近似当前迭代点附近 (附近就是一个区域 $||p||\le \Delta$ ) 的函数情况 $f(x+p)$ 。

信赖域子问题的定义：假设 $x\in \mathbb{R}^n$ 且 $f:\mathbb{R}^n \rightarrow \mathbb{R}$ 为目标函数，在区域 $||p||\le \Delta$ 内目标函数的近似函数为 $m_x(p)$ ，则置信域子问题的目的是寻找

$\arg\min \{m_x(p):||p|||\le \Delta \}$

也就是说信赖域子问题求的是近似函数在信赖域内取最小时对应的自变量取值 $p$ 。通常近似函数可以用二次函数来表示（注意这是关于 $p$ 的函数）

$m_x(p)=f(x)+\nabla f_x^T p + \frac{1}{2}p^TBp$

其中 $B$ 为模型 Hessian，这里并没有要求它是正定的。

近似函数 $m_x$ 在点 $p+x$ 的 Fidelity 定义为：（可以理解为两个函数斜率的比值，用来衡量近似函数的可信程度）

$\rho (m_x,f,p,\Delta)=\frac{f(x+p)-f(x)}{m_x(p)-m_x(0)}$

我们需要根据近似函数 $m_x$ 对目标函数 $f$ 的近似程度的好坏来调整信赖域的大小：令 $0<c_1<c_2<1$

如果 $\rho \ge c_2$ 且 $p$ 是用于函数下降，函数 $m_x$ 能够很好地近似 $f$ ，此时我们能够增大置信域；（可以理解为 $f$ 和近似函数的斜率（导数）相近，所以 $m_x$ 能够较好近似 $f$ ）
如果 $\rho \le c_1$ 且 $p$ 是用于函数下降，函数 $m_x$ 不能有效近似 $f$ ，此时应该收缩置信域；（可以理解为函数的导数偏差大，近似效果肯定不好了）
其他情况下不需要对信赖域做出调整。

假设 $p$ 是函数 $m_x$ 的下降方向，令 $\eta \in (0,1/4]$

如果 $\rho < \eta$ 则方向 $p$ 并不能使得函数 $f$ 具有一定的下降量， $x_{k+1}=x_k$
如果 $\rho \ge \eta$ 则方向 $p$ 能够使得函数 $f$ 有较大的下降， $x_{k+1}=x_k+p$

Fidelity 算法

信赖域调整算法

输入：阈值 $0<c_1<c_2<1$ (通常取 $c_1 = 1/4,c_2 = 3/4$ )，信赖域 $\Delta,\Delta_{max},\rho_x$

判断：

如果 $\rho_x >c_2$ (可以理解为扩大信赖域，但又不能超过最大信赖域的约束)
如果 $\rho < c_1$ 则 $\Delta \leftarrow \Delta /2$ （可以理解为缩小信赖域）

输出： $\Delta$

解的接受算法

输入：阈值 $\eta \in (0,1/4], \rho,x,p$

判断：

如果 $\rho_x(p)\ge \eta$ 则 $x_{k+1}=x_k+p$
否则 $x_{k+1}=x_k$

输出： $x_{k+1}$

子问题的近似解

柯西点

定义：令 $m_x$ 为函数 $f$ 在 $||p||\le \Delta$ 的近似函数， $p^S$ 为 $m_x(0)$ 处的单位最陡下降方向（ $||p^S||=1$ ），求解关于 $\tau$ 的优化命题

$\arg\min \{m_x(\tau p^S):\tau \le \Delta\}$

则 $p^C=\tau p^S$ 为函数 $m_x$ 的柯西点。可以理解为柯西点是函数 $m_x$ 在区域 $||p||\le \Delta$ 内沿着最陡下降方向进行线搜得到的最小点。

柯西点的计算：令 $m_x$ 是函数 $f$ 在区间 $||p||\le \Delta$ 的一个二次近似模型

$m_x(p)=f(x)+g^Tp+\frac{1}{2}p^TBp$

则柯西点为（其实就是高中的二次函数求最值问题，需要考虑边界条件）

$p^C=\begin{cases} \frac{-g}{||g||}\min \left( \Delta ,\frac{||g||^3}{g^TBg} \right)& \,\,g^TBg>0\ \frac{-g}{||g||}\Delta& \,\,g^TBg\le 0\ \end{cases}$

注：使用柯西点的收敛速率并不高。

Dogleg 法

狗腿路径的定义：令 $m_x$ 为函数 $f$ 的二次近似函数且 $B>0$ ，令 $p^C$ 为柯西点， $p^{min}=-B^{-1}g$ 为近似函数的无约束情况下的最小点，狗腿路径 $p^{DL}(t)$ 为

$p^{DL}\left( t \right) =\begin{cases} p^Ct& \,\,t\in \left[ 0,1 \right]\\ p^C+\left( t-1 \right) \left( p^{min}-p^C \right)& \,\,t\in \left[ 1,2 \right]\\ \end{cases}$

狗腿路径可以理解为一种两阶段的方法，先朝最陡方向走，再往近似函数的无约束最小点走(如果碰到信赖域的边界就不走了)。

狗腿法的定义：选择 $x$ 的迭代点 $x_{k+1}=x_k + p^{DL}(\tau)$ 且 $||p^{DL}(\tau)||=\Delta$ 。

狗腿路径的性质：假设 $p^{DL}(t)$ 为二次函数 $m_x$ 的狗腿路径且半径 $\Delta = \infty$ ，模型的 Hessian $B>0$

$m_x(p^{DL}(t))$ 是下降的
$||p^{DL}(t)||$ 是上升的

柯西点法的全局收敛性

引理1：柯西点 $p_k^c$ 满足

$m_k(p_k^C)-m_k(0)\le \frac{1}{2}||g_k|| \min (\Delta_k,\frac{||g_k||}{||B_k||})$

引理2：狗腿步长 $p_k^{DL}$ 满足

$m_k(p_k^{DL})-m_k(0)\le \frac{1}{2}||g_k|| \min (\Delta_k,\frac{||g_k||}{||B_k||})$

引理3：假设一个方法采用的步长 $p_k$ 满足 $m_k(p_k)-m_k(0)\le c(m_k(p_k^C)-m_k(0))$ 且 $c\in (0,1)$ ，则 $p_k$ 满足

$m_k(p_k)-m_k(0)\le \frac{1}{2}c||g_k|| \min (\Delta_k,\frac{||g_k||}{||B_k||})$

可以证明在一定条件下，柯西点法能够使得： $\lim_{k \rightarrow \infty} ||g_k|| = 0$ 。

子问题的迭代解

子问题的精确解

最小化二次函数的条件：假设 $m$ 为二次函数

$m(p)=g^Tp + \frac{1}{2}p^TBp$

其中 $B$ 是对称矩阵

$m$ 取得最小值当且仅当 $B\ge 0$ 且 $g \in Im(B)$ ，如果 $B\ge 0$ 则所有满足 $Bp=-g$ 的 $p$ 均是 $m$ 的全局最小点
$m$ 具有唯一最小点当且仅当 $B>0$

精确解满足定理：向量 $p^*$ 是信赖域问题的解

$\min_{p\in \mathbb{R}^n} f(x)+g^Tp +\frac{1}{2}p^TBp:||p||\le \Delta$

当且仅当 $p^*$ 是可行的且存在 $\lambda >0$

$(B+\lambda I)p^* = g$
$\lambda (||p^*||-\Delta)=0$
$B+\lambda I \ge 0$

子问题的迭代解

精确解定理保证了解的存在性，因此我们需要找到满足条件的 $\lambda$ ，可以利用牛顿法求根的思想进行迭代求解。

算例及matlab代码

这里采用信赖域法来求解一个无约束问题，信赖域子问题的求解采用柯西点法。优化问题为

$\min f(x_1,x_2)=(x_2-0.129x_1^2+1.6x_1-6)^2+6.07cos(x_1)+10$

这一函数也叫做 Branin 函数，经常被用作测试函数，它有三个全局最优。

算法流程为：

初始化
重复以下步骤直到满足收敛条件
求解局部二次函数的最小值得到 $p_k$
计算 $\rho_k$
解的接受算法
信赖域调整算法

求解过程：

假设初始点为 $x_1=6.00$ ， $x_2=14.00$ ，迭代的终止条件为 $g_k\le 0.01$ ，信赖域半径为 $\Delta_0 =2.0$ ， $\Delta_{max}=5.0$ ，

目标函数的梯度 $g$ 为

$g=\left[ \begin{array}{c} 2\left( x_2-0.129x_{1}^{2}+1.6x_1-6 \right) \left( -0.258x_1+1.6 \right) -6.07\sin \left( x_1 \right)\\ 2\left( x_2-0.129x_{1}^{2}+1.6x_1-6 \right)\\ \end{array} \right]$

目标函数的严格 Hessian 为

$B=\left[ \begin{matrix} 2\left( -0.258x_1+1.6 \right) ^2-0.516\left( x_2-0.129x_{1}^{2}+1.6x_1-6 \right) -6.07\cos \left( x_1 \right)& \left( -0.516x_1+3.2 \right)\\ -0.516x_1+3.2& 2\\ \end{matrix} \right]$

解的接受算法中的阈值 $\eta =0.2$ ，信赖域调整算法中的 $c1=0.25,c2=0.75$

%% 定义函数、梯度和Hessian
f = @(x1,x2) (x2-0.129*x1^2+1.6*x1-6)^2+6.07*cos(x1)+10;
g = @(x1,x2) [2*(x2-0.129*x1^2+1.6*x1-6)*(-0.258*x1+1.6)-6.07*sin(x1);...
    2*(x2-0.129*x1^2+1.6*x1-6)];
B = @(x1,x2) [2*(-0.258*x1+1.6)^2-0.516*(x2-0.128*x1^2+1.6*x1-6)-6.07*cos(x1),...
    -0.516*x1+3.2;-0.516*x1+3.2,2];

%% 初始参数设置
epsilon = 0.01;
Delta_0 = 2;
Delta_max = 5;
x0 = [6;14];
c1 = 0.25;
c2 = 0.75;
eta = 0.2;

%% 迭代求解
while 1
    if norm(g(x0(1),x0(2)),2) <= 0.01
        break
    end
    g_k = g(x0(1),x0(2));
    B_k = B(x0(1),x0(2));
    if g_k'*B_k*g_k > 0
        p = -g_k/norm(g_k,2)*min(Delta_0,(norm(g_k,2)^3)/(g_k'*B_k*g_k));
    else
        p = -g_k/norm(g_k,2)*Delta_0;
    end
    x_temp = x0 + p;
    rho = (f(x_temp(1),x_temp(2))-f(x0(1),x0(2)))/(g_k'*p+0.5*p'*B_k*p);
    if rho > c2
        Delta_0 = min(2*Delta_0,Delta_max);
    else
        Delta_0 = 0.5*Delta_0;
    end
    if rho >= eta
        x0 = x0 + p;
    end
end

求解的结果：左图为自变量 $x$ 的优化轨迹，右图为函数值随迭代次数的变化。

下图在等高线图中展示优化路径

编辑于 08-29

码农公寓

数值优化（Numerical Optimization）(2)-信赖域法

信赖域子问题与 Fidelity

Fidelity 算法

子问题的近似解

柯西点

Dogleg 法

柯西点法的全局收敛性

子问题的迭代解

子问题的精确解

子问题的迭代解

算例及matlab代码

相关文章