编者按：
许多精确算法在理论上能保证我们的目标函数值一直下降。在随机梯度下降以及无导数优化等情况下，目标移动方向受到噪声干扰，与实际下降方向往往会存在偏差。本文将分析噪声和下降偏差对于梯度下降法等算法的影响，并且介绍常用的改进方法。
应用背景
通常意义下，我们考虑的优化问题可写成
min ϕ ( x ) , s.t. c i ( x ) ≥ 0 , i ∈ I . \begin{equation}\nonumber \min \phi(x), \quad \text{s.t.} c_i(x)\geq0, i\in I. \end{equation} minϕ(x),s.t.ci(x)≥0,i∈I.
我们会对 ϕ \phi ϕ和 c i ( i ∈ I ) c_i (i\in I) ci(i∈I)的性质做出一些假设 (例如函数是凸的、Lipschitz连续的), 然后在这些假设的基础上，构造具有一定收敛性的优化算法。这些收敛性结果需要一个共同的前提：对于任意的 x ∈ R n x\in\mathbb{R}^n x∈Rn, 我们都能获得 ϕ ( x ) \phi(x) ϕ(x)和 c i ( x ) c_i(x) ci(x)的精确值。如果算法中涉及 (高阶) 导数的计算，那我们也假设这些导数都能够被精确算出。
然而在实际问题中，这个前提未必成立。其中一个原因在于有些优化问题涉及大量的样本，而所求的函数值被表示为不同样本对应值的平均。对于这类问题，许多随机算法应运而生，目前已有较为成熟的理论和系统的应用。这里不再赘述。在本文中，我们主要考虑另一类问题——自变量的规模不一定很大，但问题不满足上述精确性假设。
其中一个例子是阻尼器的分配 [ 1 ] ^{[1]} [1]。为了减小地震带来的经济损失，我们会在两栋相邻的建筑物之间安置阻尼器，使得建筑物具有更稳定的结构。然而阻尼器的成本较高，因此我们需要建立相应的优化问题，在尽可能少的阻尼器之下获得尽可能大的减震效果。这类优化问题的目标函数是通过地震模拟器产生的一个数值积分。由于它具有积分的形式，我们有理由认为它是可微的；但又由于它是一个黑箱函数，我们无法直接得到梯度的精确值。
类似的实际问题还有很多 [ 2 ] − [ 4 ] ^{[2]-[4]} [2]−[4]，而这些问题大致可以分为两类。第一类可分为两种情况：(1) 函数本身不可微；(2) 由于问题的实际背景，我们无法得到可靠的近似梯度 (当然，我们可以通过差分等方式得到梯度的近似值；但如果我们在数值算法中使用这些近似值，无法得到理想的实验结果)。这类问题的求解往往需要无导数算法。在另一类问题中，函数值和导数值都可能具有一定的计算误差，但误差的大小是我们可以估计甚至控制的。对于这类问题，我们可以通过改进原有的优化算法，在新的情境下建立收敛结果。我们接下来介绍几个相应的例子。若不加说明，我们默认下文中出现的 ∥ ⋅ ∥ \|\cdot\| ∥⋅∥表示2-范数。
在噪声下的BFGS算法 [ 5 ] ^{[5]} [5]
考虑无约束的优化问题 min x ∈ R n ϕ ( x ) , \min_{x\in\mathbb{R}^{n}} \phi(x), x∈Rnminϕ(x),
其中 ϕ ∈ C 1 ( R n ) \phi {\in} C^{1}(\mathbb{R}^n) ϕ∈C1(Rn), 但函数与梯度值无法直接计算。对应地，我们可以获得它们的近似值 f f f和 g g g:
f ( x ) = ϕ ( x ) + ε ( x ) , g ( x ) = ∇ ϕ ( x ) + e ( x ) , \begin{equation}\nonumber f(x)=\phi(x)+\varepsilon(x), \quad g(x)=\nabla \phi(x)+e(x), \end{equation} f(x)=ϕ(x)+ε(x),g(x)=∇ϕ(x)+e(x),
其中误差有界，可写作 ∣ ε ( x ) ∣ ≤ ϵ f |\varepsilon(x)|\leq\epsilon_f ∣ε(x)∣≤ϵf和 ∥ g ( x ) ∥ ≤ ϵ g \|g(x)\|\leq\epsilon_g ∥g(x)∥≤ϵg。由于误差的大小只能估计，不能进一步控制 (例如让 ∣ ε ( x k ) ∣ |\varepsilon (x_k)| ∣ε(xk)∣趋于 0 0 0)，我们可将它看作是噪声。
对于上述问题，我们可以改进BFGS算法，它对于L-smooth的强凸函数具有全局收敛的结论。证明中的一个重要部分是对于线搜索的分析。对于噪声下的更新方向 p k = − H k g ( x k ) p_k =−H_kg(x_k) pk=−Hkg(xk), 我们寻找步长 α \alpha α满足
f ( x k + α p k ) ≤ f ( x k ) + c 1 α p k T g ( x k ) , p k T g ( x k + α p k ) ≥ c 2 p k T g ( x k ) . \begin{equation}\nonumber f(x_k + αp_k) ≤ f(x_k) + c_1α p^T_k g(x_k), \quad p^T_k g(x_k + α p_k) ≥ c_2p ^T_k g(x_k).\quad \quad \quad \end{equation} f(xk+αpk)≤f(xk)+c1αpkTg(xk),pkTg(xk+αpk)≥c2pkTg(xk).
其中 c 1 , c 2 c_1,c_2 c1,c2是给定参数。如果没有噪声，这样的 α \alpha α是一定存在的。我们在用 f f f和 g g g替换 ϕ \phi ϕ和 ∇ ϕ \nabla\phi ∇ϕ之后，需要重新分析步长 α \alpha α是否存在 (在必要的时候，可以调整线搜索准则)。可以证明，当 ∥ ∇ ϕ ( x k ) ∥ \|\nabla\phi(x_k)\| ∥∇ϕ(xk)∥足够大时，我们可以找到满足上述条件的步长 α \alpha α, 而且它在特定的线搜索参数 c 1 ′ , c 2 ′ c_1', c_2' c1′,c2′之下满足精确值对应的线搜索准则，即
ϕ ( x k + α p k ) ≤ ϕ ( x k ) + c 1 ′ α p k T ∇ ϕ ( x k ) , p k T ∇ ϕ ( x k + α p k ) ≥ c 2 ′ p k T ∇ ϕ ( x k ) . \begin{equation} \nonumber \phi(x_k + αp_k) ≤ \phi(x_k) + c_1'α p^T_k \nabla\phi(x_k), \quad p^T_k \nabla\phi(x_k + α p_k) ≥ c_2'p ^T_k \nabla\phi(x_k). \end{equation} ϕ(xk+αpk)≤ϕ(xk)+c1′αpkT∇ϕ(xk),pkT∇ϕ(xk+αpk)≥c2′pkT∇ϕ(xk).
总之，这样的线搜索是良定义的，且步长满足原先(无噪声)步长的一些特性。结合改进算法的性质和误差的特点，我们最终可以得到以下收敛性结论：
**定理1：**假设 ϕ \phi ϕ是有下界且二次连续可微的强凸函数，其梯度满足lipschitz条件 ∥ ∇ ϕ ( x ) − ∇ ϕ ( y ) ∥ ≤ M ∥ x − y ∥ , ∀ x , y ∈ R n \|\nabla\phi(x)-\nabla\phi(y)\|\leq{M}\|x-y\|, \forall x,y\in\mathbb{R}^n ∥∇ϕ(x)−∇ϕ(y)∥≤M∥x−y∥,∀x,y∈Rn
计算误差始终满足 ∣ ε ( x ) ∣ ≤ ϵ f |\varepsilon(x)|\leq\epsilon_f ∣ε(x)∣≤ϵf和 ∥ g ( x ) ∥ ≤ ϵ g \|g(x)\|\leq\epsilon_g ∥g(x)∥≤ϵg； c 1 , c 2 c_1,c_2 c1,c2是线搜索中用到的参数； β 1 ∈ ( 0 , 1 ) \beta_1\in(0,1) β1∈(0,1)是事先取定的参数。根据 [5] 中的改进算法，我们可以证明 { x k } \{x_k\} {xk}以线性收敛的速度趋向于最优解邻域
N 1 = { x ∣ ∥ ∇ φ ( x ) ∥ ≤ max { A M ϵ f β 1 , B ϵ g β 1 } } , \begin{equation}\nonumber \mathcal{N}_1 = \left\{x\mid \|∇φ(x)\| ≤ \max \left\{A\sqrt{\frac{M\epsilon_f}{β_1}} , \frac{B\epsilon_g}{β_1} \right\}\right\}, \end{equation} N1={x∣∥∇φ(x)∥≤max{Aβ1Mϵf,β1Bϵg}},
其中 A = max { 16 2 ( c 2 − c 1 ) ( 4 − c 1 − 3 c 2 ) , 8 c 1 ( 1 − c 2 ) } A = \max \left\{ \frac{16\sqrt{2}}{ \sqrt{(c_2 − c_1)(4 − c_1 − 3c_2)}} , \frac{8}{\sqrt{c_1(1 − c_2)}} \right\} A=max{(c2−c1)(4−c1−3c2)162,c1(1−c2)8}, B = max { 8 1 − c 2 , 8 ( 1 + c 1 ) c 2 − c 1 + 6 } B = \max \left\{\frac{8}{1 − c_2}, \frac{8(1 + c_1)}{c_2 − c_1} + 6 \right\} B=max{1−c28,c2−c18(1+c1)+6}.
可以看出，当误差 ϵ f = ϵ g = 0 \epsilon_f = \epsilon_g=0 ϵf=ϵg=0时，对应有 N 1 = { x ∗ } \mathcal{N}_1 = \{x^{*}\} N1={x∗}。此时定理1与BFGS算法目前在精确性假设下的最好收敛性结论对应。更进一步，我们还可以证明：
定理2：沿用定理1中的条件和算法设置。设
ϕ ^ = max x ∈ N 1 ϕ ( x ) , N 2 = { x ∣ ϕ ( x ) ≤ ϕ ^ + 2 ϵ f } . \begin{equation}\nonumber \hat{\phi}=\max_{x\in\mathcal{N}_1}\phi(x),\quad \mathcal{N}_2 = \{x|\phi(x)\leq\hat{\phi}+2\epsilon_f\}. \end{equation} ϕ^=x∈N1maxϕ(x),N2={x∣ϕ(x)≤ϕ^+2ϵf}.
可证明，对任意的 k > K = min { k ∈ N ∣ x k ∈ N 1 } k>K=\min\{k\in\mathbb{N}|x_k\in\mathcal{N}_1\} k>K=min{k∈N∣xk∈N1}， x k x_k xk都在最优解邻域 N 2 \mathcal{N}_2 N2中。
可控制误差下的改进算法
与噪声不同，我们考虑另一类问题，其中函数值与梯度值的误差可以被控制。例如问题 min x ∈ R n ϕ ( x ) = ∫ t ∈ Ω h ( x , t ) d t , \min_{x\in\mathbb{R}^{n}} \phi(x)=\int_{t\in\Omega}h(x,t)dt, x∈Rnminϕ(x)=∫t∈Ωh(x,t)dt,
其中 h h h连续可微， Ω = [ a , b ] n \Omega=[a,b]^{n} Ω=[a,b]n , a<b。由于 ϕ \phi ϕ和 ∇ ϕ \nabla \phi ∇ϕ的计算涉及数值积分 (且积分无显示表达式)，我们只能获得它们的近似值，但计算的误差是可以控制的。此时我们希望改进原有的算法，且尽可能保留原先的收敛性结论
一个简单的例子是对梯度法的改进。原先的线搜索准则可写为
ϕ ( x k − α ∇ ϕ k ) ≤ ϕ k − σ α ∥ ∇ ϕ k ∥ 2 , \begin{equation}\nonumber \phi(x_k-\alpha\nabla\phi_k)\leq\phi_k-\sigma\alpha{\|\nabla\phi_k\|}^2, \end{equation} ϕ(xk−α∇ϕk)≤ϕk−σα∥∇ϕk∥2,
其中 σ ∈ ( 0 , 1 ) \sigma\in(0,1) σ∈(0,1)是给定的参数。根据Taylor一阶展开，我们知道这样的步长存在。然而对于 f k = ϕ k + ε ( x k ) f_k=\phi_k+\varepsilon(x_k) fk=ϕk+ε(xk)和$ g_k=\nabla\phi_k+e(x_k) , 我们无法得到 , 我们无法得到 ,我们无法得到f(x_k-h{g}_k)\leq{f}_k-h|g_k|2+O(h2) ) 的性质。因此，我们考虑一个新的线搜索准则： ) 的性质。因此，我们考虑一个新的线搜索准则： )的性质。因此，我们考虑一个新的线搜索准则： f ( x k − α g k ) ≤ f k − σ α ∥ g k ∥ 2 + ξ k , f(x_k-\alpha{g}_k)\leq {f}_k-\sigma\alpha{\|g_k\|}^2+\xi_k, f(xk−αgk)≤fk−σα∥gk∥2+ξk,$
其中 ξ k ≥ ∣ ϵ ( x k − α g k ) ∣ + ∣ ϵ ( x k ) ∣ \xi_k\geq|\epsilon(x_k-\alpha{g}_k)|+|\epsilon(x_k)| ξk≥∣ϵ(xk−αgk)∣+∣ϵ(xk)∣。如果不等式取">"，显然线搜索是良定义的；如果我们在计算时保证 ∥ e ( x k ) ∥ < ω ∥ g k ∥ \|e(x_k)\|<\omega\|g_k\| ∥e(xk)∥<ω∥gk∥，其中 ω < 1 \omega<1 ω<1, 则可知 ϕ ( x k − h g k ) ≤ ϕ k − h g k T ∇ ϕ k + O ( h 2 ) ≤ ϕ k − h ( 1 − ω ) ∥ g k ∥ 2 + O ( h 2 ) . \begin{equation}\nonumber \phi(x_k-h{g}_k)\leq{\phi}_k-hg_k^T\nabla\phi_k+O(h^2)\leq{\phi}_k-h(1-\omega)\|g_k\|^2+O(h^2). \end{equation} ϕ(xk−hgk)≤ϕk−hgkT∇ϕk+O(h2)≤ϕk−h(1−ω)∥gk∥2+O(h2).
此时 g k g_k gk是一个下降方向，因此我们可以选择 σ < 1 − ω \sigma<1-\omega σ<1−ω, 并取 ξ k = ∣ ϵ ( x k − α g k ) ∣ + ∣ ϵ ( x k ) ∣ \xi_k =|\epsilon(x_k-\alpha{g}_k)|+|\epsilon(x_k)| ξk=∣ϵ(xk−αgk)∣+∣ϵ(xk)∣。为了进一步建立收敛性结论，**我们通常需要控制计算中的误差，来保证 ∑ ξ k < ∞ \sum\xi_k<\infty ∑ξk<∞。**实际上对于满足精确性假设的问题，也曾出现过类似的做法 [ 6 ] ^{[6]} [6](在线搜索中引入 ξ k \xi_k ξk项并要求 ∑ ξ k < ∞ \sum\xi_k<\infty ∑ξk<∞)。
梯度法是一个很特殊的例子。包括梯度法在内，很多方法在精确性假设下计算出的更新方向 d k d_k dk是 ϕ \phi ϕ的下降方向。然而对于其中的一部分算法， d k d_k dk的计算涉及到历史梯度值 ( g k − 1 , g k − 2 ⋯ g_{k-1}, g_{k-2}\cdots gk−1,gk−2⋯)。此时我们很难给出一个误差的限值标准，使得按标准计算的 { f i } i ≤ k \{f_i\}_{i\leq{k}} {fi}i≤k和 { g i } i ≤ k \{g_i\}_{i\leq{k}} {gi}i≤k能够生成一个 ϕ \phi ϕ的下降方向。尽管如此，我们仍然可以刻画算法的收敛性结果。一个常见的思路是考虑凸函数，通过 ∥ ∇ ϕ ( x ) ∥ = 0 \|\nabla\phi(x)\|=0 ∥∇ϕ(x)∥=0来说明算法到达函数的极小值。
为了建立算法的收敛性结果，我们需要对误差的大小做出要求。这里我们介绍一种常见的设置 [ 7 ] [ 8 ] ^{[7][8]} [7][8]。假设 ϕ \phi ϕ是 R n \mathbb{R}^n Rn上L-smooth的凸函数，即满足条件：
0 ≤ ϕ ( x ) − ϕ ( y ) + < ∇ ϕ ( y ) , x − y > ≤ M 2 ∥ x − y ∥ 2 , ∀ x , y ∈ R n , 0 ≤ \phi(x) − \phi(y) +\left<∇\phi (y), x − y\right> ≤ \frac{M}{2}\|x − y\|^2, \quad \forall x,y\in\mathbb{R}^{n}, 0≤ϕ(x)−ϕ(y)+⟨∇ϕ(y),x−y⟩≤2M∥x−y∥2,∀x,y∈Rn,
其中 M > 0 M>0 M>0是强凸参数。我们接下来给出一阶 ( δ , L ) (\delta,L) (δ,L)信息的定义。
定义1 对于 δ , L > 0 \delta, L>0 δ,L>0, 函数 ϕ \phi ϕ具备一阶 ( δ , L ) (\delta,L) (δ,L)信息，当且仅当对任意的 y ∈ R n y\in\mathbb{R}^n y∈Rn, 我们都能计算出一组 ( f ( y ) , g ( y ) ) (f(y),g(y)) (f(y),g(y))满足 0 ≤ f ( x ) − f ( y ) + < g ( y ) , x − y > ≤ L ∥ x − y ∥ 2 + δ , ∀ x ∈ R n . 0 ≤ f (x) − f(y) + \left<g(y), x − y\right> ≤ L \|x − y\|^2 + δ, \quad \forall x ∈ \mathbb{R}^n. 0≤f(x)−f(y)+⟨g(y),x−y⟩≤L∥x−y∥2+δ,∀x∈Rn.
以上定义可拓展到定义在 Q Q Q上的函数，其中 Q Q Q是一个闭凸集。
假设对于**任意小的 δ > 0 \delta>0 δ>0**和足够大的 L L L, 函数 ϕ \phi ϕ具有一阶 ( δ , L ) (\delta,L) (δ,L)信息。对于许多常见的一阶算法，我们可以适当选择 { δ k } \{\delta_k\} {δk}和 { L k } \{L_k\} {Lk}, 在第 k k k次迭代时按照一阶 ( δ k , L k ) (\delta_k,L_k) (δk,Lk)信息的标准来计算 ( f k , g k ) (f_k,g_k) (fk,gk)，并用它代替 ( ϕ k , ∇ ϕ k ) (\phi_k,\nabla{\phi}_k) (ϕk,∇ϕk)。以梯度法 (Primal Gradient Method) 为例，它对应的收敛性结果 [ 7 ] ^{[7]} [7]为 ∑ i = 0 k − 1 1 L i [ ϕ ( x i + 1 ) − ϕ ( x ∗ ) ] ≤ 1 2 ∥ x 0 − x ∗ ∥ 2 + ∑ i = 0 k − 1 δ i L i . \begin{equation}\nonumber \sum_{i=0}^{k-1}\frac{1}{L_i} [ \phi(x_{i+1}) − \phi(x^∗)] ≤ \frac{1}{2}\| x_0 − x^∗\|^2 \color{red}+\sum_{i=0}^{k-1}\frac{\delta_i}{L_i}. \end{equation} i=0∑k−1Li1[ϕ(xi+1)−ϕ(x∗)]≤21∥x0−x∗∥2+i=0∑k−1Liδi.
于 ϕ \phi ϕ是L-smooth的函数，我们可以认为 { L k } \{L_k\} {Lk}有上界，且 M M M是它的一个下界。而上式可改写为
min i = 0 , ⋯ , k − 1 { 1 L i [ ϕ ( x i + 1 ) − ϕ ( x ∗ ) ] } ≤ 1 2 k ∥ x 0 − x ∗ ∥ 2 + 1 k ∑ i = 0 k − 1 δ i L i . \begin{equation}\nonumber \min_{i=0,\cdots,k-1}\left\{\frac{1}{L_i} [\phi(x_{i+1}) − \phi(x^∗)]\right\} ≤ \frac{1}{2k}\| x_0 − x^∗\|^2 \color{red}+ \frac{1}{k} \sum_{i=0}^{k-1}\frac{\delta_i}{L_i}. \end{equation} i=0,⋯,k−1min{Li1[ϕ(xi+1)−ϕ(x∗)]}≤2k1∥x0−x∗∥2+k1i=0∑k−1Liδi.
因此如果 lim k → ∞ 1 k ∑ i = 0 k − 1 δ i L i = 0 \lim_{k\to\infty}\frac{1}{k}\sum_{i=0}^{k-1}\frac{\delta_i}{L_i}=0 limk→∞k1∑i=0k−1Liδi=0, 我们可推出 lim k → ∞ min i = 0 , ⋯ , k − 1 ϕ ( x i + 1 ) = ϕ ( x ∗ ) \lim_{k\to\infty}\min_{i = 0, \cdots,k-1}\phi(x_{i+1})=\phi(x^*) limk→∞mini=0,⋯,k−1ϕ(xi+1)=ϕ(x∗), 即算法在 x ∗ x^* x∗处终止或存在子列趋近于唯一的最优解 x ∗ x^* x∗。其他的算法也有类似的收敛性结论，这里不再展开。
总结回顾
传统意义下，我们考虑的优化问题满足精确性假设，即目标 (约束) 函数和它的导数都可以被精确求出，然而在实际中许多问题并不满足这样的假设。对于具有大规模样本的问题，我们可以采用随机算法。在剩下的问题中，如果不能获得可靠的梯度信息，那么我们通常考虑无导数优化。如果我们能获得可靠的梯度信息，而函数值和梯度值伴随着可以估计大小的误差，那么我们考虑改进已有的一阶算法。面对具有误差的信息，一项重要的工作是制定合适的线搜索准则 (如果需要线搜索的话)，并验证它是良定义的。如果误差的大小只能估计而不能控制，我们希望在足够多次迭代之后，算法能够到达最优解的某个小邻域中；如果误差的大小可以控制，我们可以通过一阶 ( δ , L ) (\delta,L) (δ,L)信息等工具，给出误差的限制标准，并在这样的标准下得到算法全局收敛的结论。
[1] Audet, C., & Hare, W. (2017). Derivative-free and blackbox optimization.
[2] Booker, A. J., Dennis Jr, J. E., Frank, P. D., Serafini, D. B., Torczon, V., & Trosset, M. W. (1999). A Rigorous Framework by Surrogates for Optimization of Expensive Functions. Structural Optimization, 17, 1-13.
[3] Begin, T., Baynat, B., Sourd, F., & Brandwajn, A. (2010). A DFO technique to calibrate queueing models. Computers & Operations Research, 37(2), 273-281.
[4] Kannan, A., & Wild, S. M. (2012, June). Benefits of deeper analysis in simulation-based groundwater optimization problems. In Proceedings of the XIX International Conference on Computational Methods in Water Resources (CMWR 2012) (Vol. 4, No. 5, p. 10).
[5] Xie, Y., Byrd, R. H., & Nocedal, J. (2020). Analysis of the BFGS method with errors. SIAM Journal on Optimization, 30(1), 182-209.
[6] Han, S. P. (1977). A globally convergent method for nonlinear programming. Journal of optimization theory and applications, 22(3), 297-309.
[7] Devolder, O., Glineur, F., & Nesterov, Y. (2014). First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146, 37-75.
[8] Devolder, O. (2013). Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization (Doctoral dissertation, PhD thesis).
