Numerical Optimization(数值优化)读书笔记1——无约束优化概述

​ 对于无约束优化,我们在实数域对目标函数进行优化,且对于变量没有任何限制,数学表达式为:
\min_xf(x)\tag{1}
​ 其中x\in\mathbb R^n,n>1f:\mathbb R^n \rightarrow \mathbb R为光滑函数。

算法概述

​ 优化算法多是迭代形式,某一次的迭代值x_k是由之前的迭代值x_0,x_1,\cdots ,x_{k-1}决定的,虽然不能保证每次迭代让函数f递减,但对于大多数算法,经过m此迭代后,函数值会下降f(x_k)>f(x_{k+m})

​ 从x_kx_{k+1}的策略有两种,一种是线性搜索,一种是信赖域

  • 线性搜索

    在线性搜索算法中,首先需要确定一个方向p_k,然后算法从第k次的迭代点x_k出发,沿着方向p_k前进一段距离作为下一个迭代点x_{k+1},这一段距离叫做步长\alpha
    \min _{\alpha > 0}f(x_k+\alpha p_k)\tag{2}

    通过求解(2)式,可以一步得到最优解,但这样做是耗费算力的、复杂的。线性搜索方法往往是通过有限的步长去逼近(2)式的最小值,然后在新的迭代点重新进行线性搜索。

  • 信赖域

    在信赖域算法中,首先需要找到一个在x_k的邻域内足够逼近f模型函数m_k,由于m_k在远离x_k时不能逼近f,因此还需要对m_k的搜寻范围做出限制,这个范围便被称为信赖域。算法过程的数学表达式为:
    \min_pm_k(x_k+p)\tag{3}
    其中x_k+p处于信赖域中,若在当前信赖域中不能找到合适的方向p使得函数f下降,则称当前信赖域太大,需要缩小信赖域,然后再次计算(3)式。信赖域的性状往往是圆形,即||p||_2<\Delta,常数\Delta>0称为信赖域半径。

    对于上文中提到的模型函数m_k,我们通常使用二次函数的形式:
    m_k(x_k+p)=f_k+p^T\nabla f_k+\frac12p^TB_kp\tag{4}
    其中,f_k,\nabla f_k,B_k分别为常数、向量和矩阵。f_k代表x_k处的函数值,\nabla f_k代表x_k处的梯度,B_k代表x_k处的海森矩阵\nabla^2f_k

  • 线性搜索与信赖域的关系

    线性搜索与信赖域在迭代过程中选择方向和距离的顺序不一样。线性搜索算法首先确定了方向p_k,然后再确定合适的步长\alpha_k;而在信赖域算法中,我们首先选择了较大的距离\Delta_k,然后在信赖域中寻找合适的方向,如果当前迭代表现不好,则需要选择更小的距离\Delta_k然后重复上述步骤。

线性搜索方向

最速下降

​ 直觉上来说,梯度方向-\nabla f_k是最显而易见的搜索方向,接下来我们试图说明为什么是这样。首先对线性搜索方程做泰勒展开:
f(x_k+\alpha p)=f(x_k)+\alpha p^T\nabla f_k+\frac{1}{2}\alpha^2p^T\nabla^2f(x_k+tp)p,t\in(0,\alpha)
​ 上式最后一项为拉格朗日余项,线性搜索方程可以由前两项近似,那么函数fx_k点随\alpha的变化速率为p^T\nabla f(x_k),为了让变化速率最快,则需要让该式最小,由此得到以下优化问题
\min_p p^T\nabla f_k\\ s.t. \space ||p||=1
​ 由于p^T\nabla f_k=||p||\space||\nabla f_k||\space \cos \theta=||\nabla f_k||\space \cos \theta,其中\theta表示方向p与梯度\nabla f_k的夹角,从上式中不难发现,当\cos \theta = -1时,上述目标函数由最小值。此时\theta=\pi,代表方向p与梯度\nabla f_k方向相反,那么
p=- \frac{\nabla f_k}{||\nabla f_k||}
​ 最速下降的一个优点是,它只需要一阶导数,但是最速下降法在比较困难的问题上收敛速度慢。

牛顿方向

​ 牛顿方向是由二阶泰勒展开得到的:
f(x_k+ p)\approx f(x_k)+ p^T\nabla f_k+\frac{1}{2}p^T\nabla^2f(x_k)p\triangleq m_k(p)
​ 假设\nabla^2f(x_k)正定,若要求得上式的最小值,对m_k(p)求导,
\frac{dm_k(p)}{dp}=\nabla f_k + p\nabla^2f_k
​ 令导数为零,求得最优值:
p_k=-\nabla^2f_k^{-1}\nabla f_k
​ 当近似方程m_k(p)与原方程f(x_k+p)差距不大时,牛顿方向是收敛的。将上式代入线性搜索方向p^T\nabla f_k:
p_k^T\nabla f_k=\nabla f_k^Tp_k=-p_k^T\nabla^2f_kp_k
​ 可见,上式是一个二次项式,若二次梯度\nabla^2f_k是正定的,则搜索方向的符号是确定的,即:
p_k^T\nabla f_k=-p_k^T\nabla^2f_kp_k\leq-\sigma_k||p_k||^2\leq0
​ 因此,牛顿方向也是一个下降方向,但不像最速下降方向,牛顿方向的步长会更加自然,一般来说,牛顿方向的步长\alpha往往设置为1,仅在下降效果不好时才调整步长。

​ 牛顿方向拥有较快的收敛速度,特别对于二次项目标函数来说,但牛顿 方向也有个显而易见的缺点,那就是需要计算海森矩阵\nabla^2f(x),先不说得保证这个矩阵正定,光是计算海森矩阵就很麻烦和耗时。

伪牛顿方向

​ 牛顿方向不好用时,伪牛顿方向提供了另一种选择。伪牛顿方向将海森矩阵\nabla ^2f(x)替换为一个实时更新的估计式B_k。先考虑简单的情况,考虑用一阶梯度\nabla f(x)估计海森矩阵\nabla^2f(x),先将一阶梯度梯度展开:
\nabla f(x+p)=\nabla f(x)+\nabla ^2f(x)p+\int^1_0[\nabla^2f(x+tp)-\nabla^2f(x)]pdt
​ 由于一阶梯度\nabla f(x)是连续的,因此上式最后一项可以看作p的高阶无穷小,即o(p)。接下来将上式改成迭代形式,令x=x_k,p=x_{k+1}-x_{k},我们得到:
\nabla f_{k+1}=\nabla f_k+\nabla^2f_k(x_{k+1}-x_k)+o(x_{k+1}-x_k)
​ 若忽略最后一项,则可以得到海森矩阵的近似式,也就是所谓的切方程(secant equation):
\nabla^2f_{k+1}(x_{k+1}-x_k)\approx\mathbf B_ks_k=y_k
​ 其中,s_k=x_{k+1}-x_k,y_k=\nabla f_{k+1}-\nabla f_{k}

​ 有时,我们还需要对\mathbf B_k增加其他性质,比如阶数、对称性。对于不同的性质要求,会有不同的迭代方程,比如SR1、BFGS。

​ 因此,伪牛顿方法确定的方向伪:
p_k=-\mathbf B_k^{-1}\nabla f_k

非线性共轭梯度方法

​ 它有如下形式:
p_k=-\nabla f(x)+\beta_k p_{k-1}
​ 其中\beta_k为一个常数,它用来确保p_kp_{k-1}共轭,关于共轭的定义之后会给出。

信赖域

​ 前文提到过信赖域方法与线性搜索方法的关系,两者的区别就在于步长和方向的选择顺序。比如对于最速下降法,我们可以写出其对应的信赖域方法,令(4)式中的B_k=0,并使用二范数定义信赖域,那么问题变为:
\min_p f_k+p^T\nabla f_k\\ s.t. \space||p||_2\leq\Delta_k
​ 步长先确定为\Delta_k,然后确定方向,方向就用最速下降法-\frac{\nabla f_k}{||\nabla f_k||},那么:
p_k=-\frac{\Delta_k\nabla f_k}{||\nabla f_k||}
​ 若将(4)式中的B_k替换为海森矩阵,就可以得到牛顿方向信赖域方法。若将(4)式中的B_k替换为海森矩阵的近似式\mathbf B_k,就可以得到伪牛顿方向信赖域方法。

收敛速度

​ 收敛速度有两种标准,分别为R速率(R代表root)和Q速率(Q代表quotient),常用的是Q速率。称收敛速率为Q线性,若存在常数r\in(0,1)满足:
\frac{||x_{k+1}-x^{\star}||}{||x_{k}-x^{\star}||}\leq r, k充分大
​ 比如序列1+0.5^k的收敛速度就是Q线性的。

​ 我们称满足下式的序列为Q超线性:
\lim_{k\rightarrow \infty}\frac{||x_{k+1}-x^{\star}||}{||x_{k}-x^{\star}||}=0
​ 比如序列1+k^{-k}就是Q超线性的。

​ 我们称满足下式的序列为Q二次收敛,其中M为正常数,不必要小于1.
\frac{||x_{k+1}-x^{\star}||}{||x_{k}-x^{\star}||^2}\leq M, k充分大
​ 比如序列1+0.5^{2^k}就是Q二次收敛的。

​ 显然,若一个序列是Q二次收敛的,那么它也是Q超线性的,也是Q线性的。伪牛顿方法是典型的Q超线性的,而牛顿方法是Q二次收敛的,最速下降法则是Q线性的。