无约束优化

梯度下降法(Gradient descent)

梯度下降法(Gradient descent)或最速下降法(Steepest descent)是求解无约束最优化问题的一种最常见的方法，有实现简单的有点。梯度下降法是迭代算法，每一步需要求解目标函数的梯度向量。

假设 f(x)f(x) 是 RnR^n 是具有一阶连续偏导数的函数，要求解的无约束最优化问题是：

min⁡x∈Rnf(x)\mathop{\min}\limits_{x\in R^n}f(x)

梯度下降法是一种迭代算法，选取适当的初值 x(0)x^{(0)} ，不断迭代，更新 xx 的值，进行目标函数的极小化，直到收敛。由于负梯度方向是使函数值下降最快的方向，在迭代的每一步，以负梯度方向更新 xx 的值，从而达到减少函数值的目的。

由于f(x)f(x)具有一阶连续偏导数，若第 kk 次迭代值为 x(k)x^{(k)} ，则可将 f(x)f(x) 在 x(k)x^{(k)} 附近进行一阶泰勒展开

f(x)=f(x(k))+gkT(x−x(k))f(x) = f(x^{(k)})+g_k^T(x-x^{(k)})

这里， gk=g(x(k))=∇f(x(k))g_k=g(x^{(k)}) = \nabla f(x^{(k)}) 为 f(x)f(x) 在 x(k)x^{(k)} 的梯度，求出第 k+1k+1 次迭代值 x(k+1)x^{(k+1)}

x(k)+λkpk→x(k+1)x^{(k)}+\lambda_kp_k \to x^{(k+1)}

其中， pkp_k 是搜索方向，取负梯度方向 pk=−∇f(x(k))p_k=-\nabla f(x^{(k)}) ， λk\lambda_k 是步长，由一维搜索确定，即 λk\lambda_k 使得

f(x(k)+λkpk)=min⁡λ≥0f(x(k)+λpk)f(x^{(k)}+\lambda_kp_k) = \mathop{\min}\limits_{\lambda\geq 0}f(x^{(k)}+\lambda p_k)

具体算法

输入：目标函数 f(x)f(x) ，梯度函数 g(x)=∇f(x)g(x)=\nabla f(x) ，计算精度 ε\varepsilon ；输出： f(x)f(x) 的极小点 x∗x^*

  1. (1) 取初始值 x(0)∈Rnx^{(0)}\in R^n ，置 k=0k = 0

  2. (2) 计算 f(x(k))f(x^{(k)})

  3. (3) 计算梯度gk=g(x(k))g_k=g(x^{(k)})：

  4. 当∣∣gk∣∣<ε||g_k||<\varepsilon时，停止迭代，令x∗=x(k)x^* = x^{(k)}；

  5. 否则，令pk=−g(x(k))p_k=-g(x^{(k)})，求 λk\lambda_k ，使 f(x(k)+λkpk)=min⁡λ≥0f(x(k)+λpk)f(x^{(k)}+\lambda_kp_k)=\mathop{\min}\limits_{\lambda\geq0}f(x^{(k)}+\lambda p_k)

  6. (4) 置 x(k+1)=x(k)+λkpkx^{(k+1)}=x^{(k)}+\lambda_kp_k ，计算 f(x(k+1))f(x^{(k+1)})

  7. 当∣∣f(x(k+1))−f(x(k))∣∣<ε||f(x^{(k+1)})-f(x^{(k)})||<\varepsilon或∣∣x(k+1)−x(k)∣∣<ε||x^{(k+1)}-x^{(k)}||<\varepsilon时，停止迭代，令 x∗=x(k+1)x^*=x^{(k+1)}

  8. (5) 否则，置 k=k+1k = k+1 ，转(3)

当目标函数是凸函数时，梯度下降法的解是全局最优解。一般情况下，其解不保证是全局最优解，梯度下降法的收敛速度也未必是很快的。

牛顿法(Newton's method)

优化问题的最优解一般出现在函数的极值点上，也就 f′(x)=0f'(x)=0 的解，所以，牛顿法求解优化问题即求 f′(x)f'(x) 的零点。

首先，随机选择初始值 x0x_0，对于 函数 f(x)f(x) ，计算相应的 f(x0)f(x_0) 和切线斜率 f′(x0)f'(x_0)(这里 f′f' 即表示 ff 的导数)。然后我们计算穿过点 (x0,f(x0))(x_0,f(x_0)) 并且斜率为 f′(x0)f'(x_0) 的直线和 xx 轴的交点的 xx 坐标，也就是

0=f′(x0)(x−x0)+f(x0)0=f'(x_0)(x-x_0)+f(x_0)

我们将新求得的点的 xx 坐标命名为 x1x_1 ，通常 x1x_1 会比 x0x_0 更接近方程 f(x)=0f(x)=0 的解（ f(x)=f(x0)+(x−x0)f′(x0)f(x)=f(x_0)+(x-x_0)f'(x_0) 处其实并不是完全相等的，而是近似相等，因为只做了一阶泰勒展开，当进行了无限阶泰勒展开全加起来才是等式。由于相对而言一阶变换量是最大的，所以我们先只考虑一阶展开）。因此我们可以利用 x1x_1 开始下一轮迭代。迭代公式可简化为下式：

0=f′(x0)(x−x0)+f(x0)0=f'(x_0)(x-x_0)+f(x_0)

⇒−f(x0)=f′(x0)(x−x0)\Rightarrow -f(x_0)=f'(x_0)(x-x_0)

⇒−f(x0)f′(x0)=(x−x0)\Rightarrow -\frac{f(x_0)}{f'(x_0)}=(x-x_0)

⇒x0−f(x0)f′(x0)=x\Rightarrow x_0-\frac{f(x_0)}{f'(x_0)}=x

⇒xn+1=xn−f(xn)f′(xn)\Rightarrow x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}

通过迭代，这个式子必在 f(x∗)=0f(x^*) = 0 的时候收敛，具体过程如下图。

在优化问题中，其任务就是优化一个目标函数 ff ，求这个函数 ff 的极大极小问题，可以转化为求解函数的导数 f′=0f'=0 的问题了。这就和上面说的牛顿求解很相似了。

为了求导数 f′=0f'=0 的根，我们要把 f(x)f(x) 在探索点 xnx_n 处泰勒展开，展开到二阶泰勒近似，即要考虑导数的导数：

f(x)=f(xn)+f′(xn)(x−xn)+f′′(xn)(x−xn)22f(x)=f(x_n)+f'(x_n)(x-x_n)+f''(x_n)\frac{(x-x_n)^2}{2}

我们考虑二阶导，即导数的导数：

f′(xn+1)=f′(xn)+f′′(xn)(xn+1−xn)=0f'(x_{n+1})=f'(x_n)+f''(x_n)(x_{n+1}-x_n)=0

求得迭代公式：

xn+1=xn−f′(xn)f′′(xn)x_{n+1}=x_n-\frac{f'(x_n)}{f''(x_n)}

上面解释了牛顿法的优化，都是以一维举例的（就一个变量 xx ）。从一维问题的迭代推广至多维问题只需将导数替换为梯度 ∇f(x)\nabla f(x) ，并将二阶导数的倒数替换为Hessian矩阵的逆矩阵 H(x)−1H(x)^{-1} , 即：

xn+1=xn−H(xn)−1∇f(xn), n≥0x_{n+1} = x_n-H(x_n)^{-1}\nabla f(x_n),\ n\geq 0

通常，使用牛顿法时会加入一个步长变量 γ∈(0,1)\gamma\in(0,1) 作微调，即：

xn+1=xn−γH(xn)−1∇f(xn)x_{n+1} = x_n-\gamma H(x_n)^{-1}\nabla f(x_n)

这个方法即被称为无约束牛顿法, 通常用于第一步之后的迭代。

统计学习方法（李航）牛顿法详解

考虑无约束最优化问题： min⁡x∈Rnf(x)\mathop{\min}\limits_{x\in R^n}f(x)

假设f(x)f(x)具有二阶连续偏导数，若第 kk 次迭代值为 x(k)x^{(k)} ，则可将 f(x)f(x) 在 x(k)x^{(k)} 附近进行二阶泰勒展开

f(x)=f(x(k))+gkT(x−x(k))+12(x−x(k))TH(x(k))(x−x(k))f(x)=f(x^{(k)})+g^T_k(x-x^{(k)})+\frac{1}{2}(x-x^{(k)})^TH(x^{(k)})(x-x^{(k)})

这里， gk=g(x(k))=∇f(x(k))g_k=g(x^{(k)})=\nabla f(x^{(k)}) 是 f(x)f(x) 的梯度向量在点 x(k)x^{(k)} 的值， H(x(k))H(x^{(k)}) 是 f(x)f(x) 的海赛矩阵

H(x)=[∂2f∂xi∂xj]n×nH(x)=[\frac{\partial^2f}{\partial x_i \partial x_j}]_{n\times n}

函数 f(x)f(x) 有极值的必要条件是在极值点处一阶导数为 00 ，即梯度向量为 00 特别是当 H(x(k))H(x^{(k)}) 是正定矩阵时，函数 f(x)f(x) 的极值为极小值。牛顿法利用极小值的必要条件 ∇f(x)=0\nabla f(x)=0 ，每次迭代从点 x(k)x^{(k)}开始，求目标函数的极小点，作为第 k+1k+1次迭代值 x(k+1)x^{(k+1)} ，具体地，假设 x(k+1)x^{(k+1)}满足 ∇f(x(k+1))=0\nabla f(x^{(k+1)}) = 0 结合泰勒展开则有

∇f(x)=gk+Hk(x−x(k))\nabla f(x)=g_k+H_k(x-x^{(k)})

其中 Hk=H(x(k))H_k=H(x^{(k)}) ，这样

gk+Hk(x(k+1)−x(k))=0g_k+H_k(x^{(k+1)}-x^{(k)})=0

因此，

x(k+1)=x(k)−Hk−1gkx^{(k+1)}=x^{(k)}-H^{-1}_kg_k

将上式作为迭代公式的算法就是牛顿法。

具体算法

输入：目标函数 f(x)f(x) ，梯度 g(x)=∇f(x)g(x)=\nabla f(x) ，海塞矩阵 H(x)H(x) ，精度要求 ε\varepsilon

输出： f(x)f(x) 的极小点 x∗x^*

  1. (1) 取初始值 x(0)x^{(0)} ，置 k=0k = 0

  2. (2) 计算 gk=g(x(k))g_k=g(x^{(k)})

  3. (3) 若 ∣∣gk∣∣<ε||g_k||<\varepsilon ，则停止计算，得近似解 x∗=x(k)x^*=x^{(k)}

  4. (4) 计算 Hk=H(x(k))H_k=H(x^{(k)}) ，并求 pkp_k ： Hkpk=−gkH_kp_k=-g_k

  5. (5) 置 x(k+1)=x(k)+pkx^{(k+1)}=x^{(k)}+p_k

  6. (6) 置 k=k+1k = k+1 ，转(2)

应用举例

我们刷leetcode时有这样一道题，求解平方根(只保留整数部分)。牛顿迭代法是已知的实现求方根最快的方法之一，只需要迭代几次后就能得到相当精确的结果。设 xx 的 mm 次方根为 aa，则推导公式如下 ：

f(x)=xm−af(x)=x^m-a f′(x)=mxm−1f'(x)=mx^{m-1}

代入牛顿法公式

⇒xn+1=xn−f(xn)f′(xn)=xn−xnm−amxnm−1=xn−(xnmmxnm−1−amxnm−1)\Rightarrow x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n^m-a}{mx_n^{m-1}}=x_n-(\frac{x_n^m}{mx_n^{m-1}}-\frac{a}{mx_n^{m-1}})

=xn−(xm−amxnm−1)=xn−xnm+amxnm−1=(1−1m)xn+amxnm−1=x_n-(\frac{x}{m}-\frac{a}{mx_n^{m-1}})=x_n-\frac{x_n}{m}+\frac{a}{mx_n^{m-1}}=(1-\frac{1}{m})x_n+\frac{a}{mx_n^{m-1}}

代码如下(求平方根，即 m=2m = 2 ， xn+1=(1−12)xn+a2xn2−1=12(xn+axn)x_{n+1} = (1-\frac{1}{2})x_n+\frac{a}{2x_n^{2-1}}=\frac{1}{2}(x_n+\frac{a}{x_n}) )：

class Solution:
    def mySqrt(self, a):
        x = a
        while x > a / x:
            x = (x + a / x) // 2
        return int(r)

拟牛顿法(quasi-Newton method)

在牛顿法的迭代中，需要计算海赛矩阵的逆矩阵，这一计算比较复杂，考虑用一个 nn 阶矩阵 Gk=G(x(k))G_k=G(x^{(k)}) 来近似替代 H−1=H−1(x(k))H^{-1}=H^{-1}(x^{(k)}) 。这就是拟牛顿法的基本想法。先看牛顿法迭代中海赛矩阵 HkH_k 满足的条件。首先， HkH_k 满足以下关系。在 ∇f(x)=gk+Hk(x−x(k))\nabla f(x)=g_k+H_k(x-x^{(k)}) 中取 x=x(k)x = x^{(k)} ，得

gk+1−gk=Hk(x(k+1)−x(k))g_{k+1}-g_k=H_k(x^{(k+1)}-x^{(k)})

记 yk=gk+1−gky_k=g_{k+1}-g_k ， δk=x(k+1)−x(k)\delta_k=x^{(k+1)}-x^{(k)} ，则

yk=Hkδky_k=H_k\delta_k 或 Hk−1yk=δkH_k^{-1}y_k=\delta_k

上式即称为拟牛顿条件。如果 HkH_k 是正定的( Hk−1H^{-1}_k也是正定的)，那么可以保证牛顿法搜索方向 pkp_k 是下降方向。这是因为搜索方向是 pk=−Hk−1gkp_k=-H^{-1}_kg_k ，结合牛顿法迭代式 x(k+1)=x(k)−Hk−1gkx^{(k+1)}=x^{(k)}-H^{-1}_kg_k 有

x=x(k)+λpk=x(k)−λHk−1gkx=x^{(k)}+\lambda p_k=x^{(k)}-\lambda H^{-1}_kg_k

所以 f(x)f(x) 在 x(k)x^{(k)} 的泰勒展开式可以近似写成

f(x)=f(x(k))−λgkTHk−1gkf(x)=f(x^{(k)})-\lambda g^T_kH^{-1}_kg_k

因 Hk−1H^{-1}_k 正定，故有 gkTHk−1gk>0g^T_kH^{-1}_kg_k>0 当 λ\lambda 为一个充分小的正数时，总有 f(x)<f(x(k))f(x)<f(x^{(k)}) ，也就是说 pkp_k 是下降方向。

拟牛顿法将 GkG_k 作为 Hk−1H^{-1}_k 的近似，要求矩阵 GkG_k 满足同样的条件。首先，每次迭代矩阵 GkG_k 是正定的。同时， GkG_k 满足下面的拟牛顿条件：

Gk+1yk=δkG_{k+1}y_k=\delta_k

按照拟牛顿条件选择 GkG_k 作为 Hk−1H^{-1}_k 的近似或选择 BkB_k 作为 HkH_k 的近似的算法称为拟牛顿法。按照拟牛顿条件，在每次迭代中可以选择更新矩阵 Gk+1G_{k+1} ：

Gk+1=Gk+ΔGkG_{k+1}=G_k+\Delta G_k

DFP

DFP算法选择 Gk+1G_{k+1} 的方法是，假设每一步迭代中矩阵 Gk+1G_{k+1} 是由 GkG_k 加上两个附加项构成的，即

Gk+1=Gk+Pk+QkG_{k+1}=G_k+P_k+Q_k

其中 Pk, QkP_k,\ Q_k 是待定矩阵。这时，

Gk+1yk=Gkyk+Pkyk+QkykG_{k+1}y_k=G_ky_k+P_ky_k+Q_ky_k

为使 Gk+1G_{k+1} 满足拟牛顿条件，可使 PkP_k 和 QkQ_k 满足：

Pkyk=δkP_ky_k=\delta_k Qkyk=−GkykQ_ky_k=-G_ky_k

事实上，不难找出这样的 PkP_k 和 QkQ_k ，例如取

Pk=δkδkTδkTykP_k=\frac{\delta_k\delta_k^T}{\delta_k^Ty_k} Qk=−GkykykTGkykTGkykQ_k = -\frac{G_ky_ky^T_kG_k}{y_k^TG_ky_k}

这样就可得到矩阵 Gk+1G_{k+1} 的迭代公式：

Gk+1=Gk+δkδkTδkTyk−GkykykTGkykTGkykG_{k+1}=G_k+\frac{\delta_k\delta_k^T}{\delta_k^Ty_k} -\frac{G_ky_ky^T_kG_k}{y_k^TG_ky_k}

称为DFP算法。可以证明，如果初始矩阵 G0G_0 是正定的，则迭代过程中的每个矩阵 GkG_k 都是正定的。

  1. 输入：目标函数 f(x)f(x) ，梯度 g(x)=∇f(x)g(x)=\nabla f(x) ，精度要求 ε\varepsilon ；输出： f(x)f(x) 的极小点 x∗x^*

  2. (1) 选定初始点 x(0)x^{(0)} ，取 G0G_0 为正定对称矩阵，置 k=0k = 0

  3. (2) 计算 gk=g(x(k))g_k=g(x^{(k)}) 若 ∣∣gk∣∣<ε||g_k||<\varepsilon ，则停止计算，得近似解 x∗=x(k)x^*=x^{(k)}

  4. (3) 置 pk=−Gkgkp_k=-G_kg_k

  5. (4) 一维搜索：求 λk\lambda_k 使得 f(x(k)+λkpk)=min⁡λ≥0f(x(k)+λpk)f(x^{(k)}+\lambda_kp_k)=\mathop{\min}\limits_{\lambda\geq0}f(x^{(k)}+\lambda p_k)

  6. (5) 置 x(k+1)=x(k)+λkpkx^{(k+1)}=x^{(k)}+\lambda_kp_k

  7. (6) 计算 gk+1=g(x(k+1))g_{k+1}=g(x^{(k+1)})

  8. 若 ∣∣gk∣∣<ε||g_k||<\varepsilon ，则停止计算，得近似解 x∗=x(k+1)x^*=x^{(k+1)} ；

  9. 否则，按 Gk+1=Gk+δkδkTδkTyk−GkykykTGkykTGkykG_{k+1}=G_k+\frac{\delta_k\delta_k^T}{\delta_k^Ty_k} -\frac{G_ky_ky^T_kG_k}{y_k^TG_ky_k} 计算出 Gk+1G_{k+1}

  10. (7) 置 k=k+1k = k+1 ，转(3)

BFGS

BFGS算法是最流行的拟牛顿算法。可以考虑用 GkG_k 逼近海赛矩阵的逆矩阵 H−1H^{-1} ，也可以考虑用 BkB_k 逼近海赛矩阵 HH 。这时，相应的拟牛顿条件是

Bk+1δk=ykB_{k+1}\delta_k=y_k

可以用同样的方法得到另一迭代公式。首先令

Bk+1=Bk+Pk+QkB_{k+1}=B_k+P_k+Q_k

Bk+1δk=Bkδk+Pkδk+QkδkB_{k+1}\delta_k=B_k\delta_k+P_k\delta_k+Q_k\delta_k

考虑使 PkP_k 和 QkQ_k 满足：

Pkδk=ykP_k\delta_k=y_k Qkδk=−BkδkQ_k\delta_k=-B_k\delta_k

找出适合条件的 PkP_k 和 QkQ_k，得到BFGS算法矩阵 Bk+1B_{k+1} 的迭代公式：

Bk+1=Bk+ykykTykTδk−BkδkδkTBkδkTBkδkB_{k+1}=B_k+\frac{y_ky_k^T}{y^T_k\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}

可以证明，如果初始矩阵 B0B_0 是正定的，则迭代过程中的每个矩阵 BkB_k 都是正定的。

  1. 输入：目标函数 f(x)f(x) ，梯度 g(x)=∇f(x)g(x)=\nabla f(x) ，精度要求 ε\varepsilon ；输出： f(x)f(x) 的极小点 x∗x^*

  2. (1) 选定初始点 x(0)x^{(0)} ，取 B0B_0 为正定对称矩阵，置 k=0k = 0

  3. (2) 计算 gk=g(x(k))g_k=g(x^{(k)}) 若 ∣∣gk∣∣<ε||g_k||<\varepsilon ，则停止计算，得近似解 x∗=x(k)x^*=x^{(k)}

  4. (3) 由 Bkpk=−gkB_kp_k = -g_k 求出 pkp_k

  5. (4) 一维搜索：求 λk\lambda_k 使得 f(x(k)+λkpk)=min⁡λ≥0f(x(k)+λpk)f(x^{(k)}+\lambda_kp_k)=\mathop{\min}\limits_{\lambda\geq0}f(x^{(k)}+\lambda p_k)

  6. (5) 置 x(k+1)=x(k)+λkpkx^{(k+1)} = x^{(k)}+\lambda_k p_k

  7. (6) 计算 gk+1=g(x(k+1))g_{k+1} = g(x^{(k+1)})

  8. 若 ∣∣gk+1∣∣<ε||g_{k+1}||<\varepsilon ，则停止计算，得近似解 x∗=x(k+1)x^*=x^{(k+1)}

  9. 否则，按 Bk+1=Bk+ykykTykTδk−BkδkδkTBkδkTBkδkB_{k+1}=B_k+\frac{y_ky_k^T}{y^T_k\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k} 计算出 Bk+1B_{k+1}

  10. (7) 置 k=k+1k = k+1 ，转(3)

坐标下降法(Coordinate descent)

坐标下降法是一种非梯度优化方法，它在每步迭代中沿一个坐标方向进行搜索，通过循环使用不用的坐标方向来达到目标函数的局部极小值。

假设我们求解 f(x)f(x) 的极小值，其中 x=(x1,x2,…,xd)T∈Rdx=(x_1,x_2,\dots,x_d)^T\in \mathbb{R}^d 是一个 dd 维向量。从初始点 x0x^0 开始，坐标下降法通过迭代地构造序列 x0,x1,x2,…x^0,x^1,x^2,\dots 来解决问题， xt+1x^{t+1} 的第 ii 个分量 xit+1x_i^{t+1} 构造为：

xit+1=arg⁡min⁡y∈Rf(x1t+1,…,xi−1t+1,y,xi+1t,…,xdt)x_i^{t+1}=\mathop{\arg \min}\limits_{y\in\mathbb{R}}f(x_1^{t+1},\dots,x_{i-1}^{t+1},y,x^t_{i+1},\dots,x_d^t)

通过执行此操作，显然有

f(x0)≥f(x1)≥f(x2)≥…f(x^0)\geq f(x^1) \geq f(x^2)\geq\dots

与梯度下降法类似，通过迭代执行该过程，序列 x0,x1,x2,…x^0,x^1,x^2,\dots 能收敛到所期望的局部极小点或驻点。坐标下降法不需计算目标函数的梯度，在每次迭代中仅需求解一维搜索问题，对于某些复杂问题计算较为简便。但若目标函数不光滑，则坐标下降法有可能陷入非驻点。

最小二乘法(Least squares)

最小二乘法是无约束的数学优化方法，通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小，即

min⁡θ∑i=1n(y^−yi)2\mathop{\min}\limits_\theta \sum_{i=1}^n(\hat{y}-y_i)^2

最小值可以通过对上式参数分别求偏导数，然后使它们等于零得到。

应用举例

某次实验得到了四个数据点 (x,y)(x,y) ： (1,6)、(2,5)、(3,7)、(4,10)(1,6)、(2,5)、(3,7)、(4,10) 。我们希望找出一条和这四个点最匹配的直线 y=β1+β2xy = \beta_1+\beta_2 x， 即找出在“最佳情况”下能够大致符合如下超定线性方程组的 β1\beta_1 和 β2\beta_2：

β1+1β2=6\beta_1+1\beta_2 = 6 β1+2β2=5\beta_1+2\beta_2 = 5 β1+3β2=7\beta_1+3\beta_2 = 7 β1+4β2=10\beta_1+4\beta_2 = 10

最小二乘法采用的手段是尽量使得等号两边的方差最小，也就是找出这个函数的最小值：

S(β1,β2)=[6−(β1+1β2)]2+[5−(β1+2β2)]2+[7−(β1+3β2)]2+[10−(β1+4β2)]2S(\beta_1,\beta_2) = [6-(\beta_1+1\beta_2)]^2+[5-(\beta_1+2\beta_2)]^2+[7-(\beta_1+3\beta_2)]^2+[10-(\beta_1+4\beta_2)]^2

最小值可以通过对 S(β1,β2)S(\beta_1,\beta_2) 分别求 β1\beta_1 和 β2\beta_2 的偏导数，然后使它们等于零得到。

∂S∂β1=0=8β1+20β2−56\frac{\partial S}{\partial\beta_1} = 0 =8\beta_1+20\beta_2-56 ∂S∂β2=0=20β1+60β2−154\frac{\partial S}{\partial\beta_2} = 0 =20\beta_1+60\beta_2-154

如此就得到了一个只有两个未知数的方程组，易得 β1=3.5, β2=1.4\beta_1=3.5,\ \beta_2 = 1.4 ，所以 y=3.5+1.4xy = 3.5+1.4x 最佳

置信域方法（Trust-region methods）

置信域方法（Trust-region methods）又称为信赖域方法，它是一种最优化方法，能够保证最优化方法总体收敛。

思想框架

考虑 min⁡x∈Rnf(x)\min\limits_{x\in R^n}f(x) ，其中 f(x)f(x) 是定义在 RnR^n 上的二阶连续可微函数。定义当前点的邻域 Ωk={x∈Rn｜∣∣x−xk∣∣≤Δk}\Omega_k=\{x\in R^n｜|| x-x_k||\leq \Delta_k\} 。这里 Δk\Delta_k 称为置信域半径。假定在这个邻域中，二次模型是目标函数 f(x)f(x) 的一个合适的近似，则在这个邻域（称为置信域）中极小化二次模型，得到近似极小点 sks_k ，并取，其中 ∣∣sk∣∣≤Δk||s_k||\leq \Delta_k 。

置信域方法的模型子问题是

\begin{equation} \left\{ \begin{array}{lr} \min q^{(k)} (s)=f(x_k)+g^T_ks+\frac{1}{2}s^TB_ks \\ s.t.\ ||s||\leq\Delta_k \end{array} \right. \end{equation}

其中， s=x−xks=x-x_k ， gk=∇f(xk)g_k=\nabla f(x_k) ， BkB_k 是一个对称矩阵，它是Hessian矩阵 ∇2f(xk)\nabla^2f(x_k) 或其近似， Δk>0\Delta_k>0 为置信域半径， ∣∣s∣∣||s|| 为某一范数，通常我们采用L2范数。选择 Δk\Delta_k 的方法：根据模型函数 q(k)(s)q^{(k)}(s) 对目标函数 f(x)f(x) 的拟合程度来调整置信域半径 Δk\Delta_k 。对于置信域方法的模型子问题的解 sks_k ，设目标函数的下降量

Aredk=f(xk)−f(xk+sk)\text{Ared}_k=f(x_k)-f(x_k+s_k)

为实际下降量，设模型函数的下降量

Predk=q(k)(0)−q(k)(sk)\text{Pred}_k=q^{(k)}(0)-q^{(k)}(s_k)

为预测下降量。 定义比值

rk=AredkPredk=f(xk)−f(xk+sk)q(k)(0)−q(k)(sk)r_k=\frac{\text{Ared}_k}{\text{Pred}_k}=\frac{f(x_k)-f(x_k+s_k)}{q^{(k)}(0)-q^{(k)}(s_k)}

它用来衡量模型函数 q(k)q^{(k)} 与目标函数 ff 的一致性程度。

具体算法

Step 1：给出初始点 x0x_0 ，置信域半径的上界 Δˉ\bar{\Delta} ， Δ0∈(0,Δˉ)\Delta_0\in (0,\bar{\Delta}) ， ε≥0\varepsilon \geq 0 ， 0<η1≤η2<10<\eta_1\leq\eta_2<1 ， 0<γ1<10<\gamma_1<1 ， k:=0k:=0

Step 2：如果 ∣∣gk∣∣≤ε||g_k||\leq \varepsilon ，停止

Step 3：(近似地)求解置信域方法的模型子问题，得到 sks_k

Step 4：计算 f(xk+sk)f(x_k+s_k) 和 rkr_k 。令

x_{k+1}=\begin{equation} \left\{ \begin{array}{lr} x_k+s_k,\ \ \text{if}\ r_k\geq \eta_1 &\\ x_k, \ \ \ \ \ \ \ \ \ \ \ \text{else} \end{array} \right. \end{equation}

Step 5：校正置信域半径，令

Δk+1∈(0,γ1Δk],                       if  rk<η1Δk+1∈[γ1Δk,Δk],                     if  rk∈[η1,η2)Δk+1∈[Δk,min⁡{γ2Δk,Δˉ}],     if  rk≥η2\Delta_{k+1}\in (0,\gamma_1\Delta_k],\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{if}\ \ r_k<\eta_1\\ \Delta_{k+1}\in [\gamma_1\Delta_k,\Delta_k], \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{if}\ \ r_k\in[\eta_1,\eta_2)\\ \Delta_{k+1}\in [\Delta_k,\min\{\gamma_2\Delta_k,\bar{\Delta}\}], \ \ \ \ \ \text{if}\ \ r_k\geq\eta_2

Step 6：产生 Bk+1B_{k+1} ，校正 qkq^{k} ，令 k:=k+1k:=k+1 ，转Step 2

Previous连续可微Next有约束优化

Last updated