03-无约束优化

问题

minimize $f(\mathbf{x})$ 其中, 函数 $f:{\mathbb{R}}^n\to \mathbb{R}$ 是一个实值函数。 $\Omega ={\mathbb{R}}^n$ subject to $\mathbf{x}\in \Omega$

函数梯度迭代示意图

梯度方法

• 思想：令$x^0$作为初始搜索点，沿着梯度负方向构造一个新点$x^0-\alpha ▽f(x^0)$，如果$▽f(x^0)\ne 0$，那么$\alpha >0$足够小时，有$f(x^0-\alpha ▽f(x^0))<f(x^0)$.
• 迭代公式：$x^{k+1}=x^k-{\alpha }_k▽f(x^k)$.
• 最速下降法：选择合适的步长${\alpha }_k$，使得目标函数能够得到最大程度的减小。

$${\alpha }_k={argmin}_{a\ge 0}f(x^k-\alpha ▽f(x^k))$$

---

最速下降法

• 定理： 最速下降法搜索函数 $f:{\mathbb{R}}^2\to \mathbb{R}$ 的极小点, 迭代过程产生的序列为 ${\left\{{\mathbf{x}}^{(k)}\right\}}_{k=0}^{\infty }$, 那么, ${\mathbf{x}}^{(k+1)}-{\mathbf{x}}^{(k)}$ 与 ${\mathbf{x}}^{(k+2)}-{\mathbf{x}}^{(k+1)}$ 正交对于所有的 $k⩾0$ 都成立。
• 下降性质：利用梯度的本质，只要$▽f(x^k)\ne 0$，就能保证每次迭代得到的新数值比原数值小。
• 实际计算中的停止搜索准则：定义最小变化量。 一阶必要条件: $\Vert \nabla f\left({\mathbf{x}}^{(k)}\right)\Vert <\epsilon$

最速下降法例题

最速下降法求 $f\left(x_1,x_2,x_3\right)={\left(x_1-4\right)}^4+{\left(x_2-3\right)}^2+4{\left(x_3+5\right)}^4$ 的极小点。初始搜索点为 ${\mathbf{x}}^{(0)}=[4,2-1{]}^{\top }$, 开展 3 次迭代。

• Step1:

$$\begin{array}{rl}{\alpha }_0& =\underset{\alpha ⩾0}{\mathrm{argmin}}f\left({\mathbf{x}}^{(0)}-\alpha \nabla f\left({\mathbf{x}}^{(0)}\right)\right)\\ & =\underset{\alpha ⩾0}{\mathrm{argmin}}\left(0+(2+2\alpha -3{)}^2+4(-1-1024\alpha +5{)}^4\right)=3.967\times 10^{-3}\\ {\mathbf{x}}^{(1)}& ={\mathbf{x}}^{(0)}-{\alpha }_0\nabla f\left({\mathbf{x}}^{(0)}\right)=[4.000,2.008,-5.062{]}^{\top }\end{array}$$

Step2: ${\alpha }_1=\underset{\alpha ⩾0}{\mathrm{argmin}}\left(0+(2.008+1.984\alpha -3{)}^2+4(-5.062+0.003875\alpha +5{)}^4\right)=0.5000$ ${\mathbf{x}}^{(2)}={\mathbf{x}}^{(1)}-{\alpha }_1\nabla f\left({\mathbf{x}}^{(1)}\right)=[4.000,3.000,-5.060{]}^{\top }$ Step3: ${\alpha }_2=\underset{\alpha ⩾0}{\mathrm{argmin}}\left(0.000+0.000+4(-5.060+0.003525\alpha +5{)}^4\right)=16.29$ ${\mathbf{x}}^{(3)}=[4.000,3.000,-5.002{]}^{\top }$ 理论上：函数 $f$ 的极小点就是 $[4,3,-5{]}^{\top }$

梯度方法特性以及收敛性分析

• 特性： 单调下降算法；全局收敛
• 收敛性分析： 将目标函数设定为二次函数：

$$\begin{array}{rl}V(\mathbf{x})=f(\mathbf{x})+\frac{1}{2}{\mathbf{x}}^{\ast \top }\mathbf{Q}{\mathbf{x}}^{\ast }& =\frac{1}{2}{\left(\mathbf{x}-{\mathbf{x}}^{\ast }\right)}^{\top }\mathbf{Q}\left(\mathbf{x}-{\mathbf{x}}^{\ast }\right)\\ ▽f(x)& =Qx-b\end{array}$$

其中, $\mathbf{Q}={\mathbf{Q}}^{\top }>0$ ${\mathbf{x}}^{\ast }={\mathbf{Q}}^{-1}\mathbf{b}$

• 瑞利不等式：对于任意的 $\mathbf{Q}={\mathbf{Q}}^{\top }>0$, 有

$$\begin{array}{c}{\lambda }_{\min }(\mathbf{Q})\Vert \mathbf{x}{\Vert }^2⩽{\mathbf{x}}^{\top }\mathbf{Q}\mathbf{x}⩽{\lambda }_{\max }(\mathbf{Q})\Vert \mathbf{x}{\Vert }^2\\ {\lambda }_{\min }\left({\mathbf{Q}}^{-1}\right)\Vert \mathbf{x}{\Vert }^2⩽{\mathbf{x}}^{\top }{\mathbf{Q}}^{-1}\mathbf{x}⩽{\lambda }_{\max }\left({\mathbf{Q}}^{-1}\right)\Vert \mathbf{x}{\Vert }^2\end{array}$$

• 收敛性: 对于最速下降法，对于任意的初始点 ${\mathbf{x}}^{(0)}$ ,都有 ${\mathbf{x}}^{(k)}\to {\mathbf{x}}^{\ast }$ 。

固定步长梯度法

对于所有步长 ${\alpha }_k=\alpha \in \mathbb{R}$,迭代公式为：${\mathbf{x}}^{(k+1)}={\mathbf{x}}^{(k)}-\alpha {\mathbf{g}}^{(k)}$

• 定理8.3: 对于步长固定梯度法, 当且仅当步长

$$0<\alpha <\frac{2}{{\lambda }_{\max }(\mathbf{Q})}$$

时, ${\mathbf{x}}^{(k)}\to {\mathbf{x}}^{\ast }$ 。

---

收敛率

• 定义8.1(收敛阶): 存在一个序列 $\left\{{\mathbf{x}}^{(k)}\right\}$, 能够收敛到 ${\mathbf{x}}^{\ast }$, 即 ${\lim }_{k\to \infty }\Vert {\mathbf{x}}^{(k)}-{\mathbf{x}}^{\ast }\Vert =0$ 。 如果

$$0<\underset{k\to \infty }{\lim }\frac{\Vert {\mathbf{x}}^{(k+1)}-{\mathbf{x}}^{\ast }\Vert }{\Vert {\mathbf{x}}^{(k)}-{\mathbf{x}}^{\ast }{\Vert }^p}<\infty$$

则序列 $\left\{{\mathbf{x}}^{(k)}\right\}$ 的收敛阶数为 $p$, 其中, $p\in {\mathbb{R}}_{\text{。 }}$ 如果对任意的 $p>0$ ，上式极限都为 $0$ ，那么称收敛阶数为 $\infty$ 。

• 定理8.6： 最速下降法在求解目标函数 $f$ 的极小点时,产生一个收敛的迭代点 $\left\{{\mathbf{x}}^{(k)}\right\}$, 该序列在最坏情况下的收敛阶数为 1 。也就是说, 存在一个目标函数 $f$ 和某 始点 ${\mathbf{x}}^{(0)}$, 能够使得 $\left\{{\mathbf{x}}^{(k)}\right\}$ 的收敛阶数为 1 。

牛顿法

• 思路：最速下降法只用到了目标函数的一阶导数，如果能够在迭代方法中引入高阶导数，其效率可能优于最速下降法。

  • 首先构造一个二次型函数，其与目标函数在该点的一阶和二阶导数相等，以此可以作为目标函数的近似表达式。
  • 求改二次型函数的极小点，以此作为下一次迭代的起始点。
  • 重复上述过程，直到满足迭代条件后退出。

• 迭代操作 目标函数 $f:{\mathbb{R}}^n\to \mathbb{R}$ 二阶连续可微, 将函数 $f$ 在点 ${\mathbf{x}}^{(k)}$ 处进行泰勒展开, 可得到二次型近似函数:

$$f(\mathbf{x})\approx f\left({\mathbf{x}}^{(k)}\right)+{\left(\mathbf{x}-{\mathbf{x}}^{(k)}\right)}^{\top }{\mathbf{g}}^{(k)}+\frac{1}{2}{\left(\mathbf{x}-{\mathbf{x}}^{(k)}\right)}^{\bar{\top }}\mathbf{F}\left({\mathbf{x}}^{(k)}\right)\left(\mathbf{x}-{\mathbf{x}}^{(k)}\right)\triangleq q(\mathbf{x})$$

其中 ${\mathbf{g}}^{(k)}=\nabla \mathbf{f}\left({\mathbf{x}}^{(k)}\right)$,局部极小点的一阶必要条件

$$0=\nabla q(\mathbf{x})={\mathbf{g}}^{(k)}+\mathbf{F}\left({\mathbf{x}}^{(k)}\right)\left(\mathbf{x}-{\mathbf{x}}^{(k)}\right)$$

如果 $\mathbf{F}\left({\mathbf{x}}^{(k)}\right)>0$, 函数 $q$ 的极小点为${\mathbf{x}}^{(k+1)}={\mathbf{x}}^{(k)}-\mathbf{F}{\left({\mathbf{x}}^{(k)}\right)}^{-1}{\mathbf{g}}^{(k)}$

牛顿法收敛性分析

• 如果初始点靠近极大（小）点，那么牛顿法将具有非常好的收敛性，如果初始点离极大（小）点较远，牛顿法并不一定收敛。

修正牛顿法

• 带步长牛顿法：${\mathbf{x}}^{(k+1)}={\mathbf{x}}^{(k)}-{\alpha }_k\mathbf{F}{\left({\mathbf{x}}^{(k)}\right)}^{-1}{\mathbf{g}}^{(k)}$ , ${\alpha }_k=argminf({\mathbf{x}}^{(k)}-\alpha \mathbf{F}({\mathbf{x}}^{(k)}{)}^{-1}{\mathbf{g}}^{(k)})$

牛顿法求解非线性最小二乘

• 非线性最小二乘问题 $minimize{\sum }_{i=1}^m{\left(r_i(\mathbf{x})\right)}^2$ 其中, $r_i:{\mathbb{R}}^n\to \mathbb{R},i=1,\cdots ,m$ 为给定的函数。
• 分析：令 $\mathbf{r}={\left[r_1,\cdots ,r_m\right]}^{\top }$, 可将目标函数写为 $f(\mathbf{x})=\mathbf{r}(\mathbf{x}{)}^{\top }\mathbf{r}(\mathbf{x})$ 。 计算函数 $f$ 的梯度和黑塞矩阵

$$(\nabla f(\mathbf{x}){)}_j=\frac{\partial f}{\partial x_j}(\mathbf{x})=2\sum _{i=1}^m{r}_i(\mathbf{x})\frac{\partial r_i}{\partial x_j}(\mathbf{x})$$

$\mathbf{r}$ 的雅可比矩阵为：

$$\begin{array}{r}\mathbf{J}(\mathbf{x})=\left[\begin{array}{ccc}\frac{\partial r_1}{\partial x_1}(\mathbf{x})& \cdots & \frac{\partial r_1}{\partial x_n}(\mathbf{x})\\ ⋮& & ⋮\\ \frac{\partial r_m}{\partial x_1}(\mathbf{x})& \cdots & \frac{\partial r_m}{\partial x_n}(\mathbf{x})\end{array}\right]\end{array}$$

函数 $\mathbf{f}$ 的梯度可以表示为 $\nabla f(\mathbf{x})=2\mathbf{J}(\mathbf{x}{)}^{\top }\mathbf{r}(\mathbf{x})$ 函数 $\mathbf{f}$ 的黑塞矩阵$\mathbf{F}(\mathbf{x})=2\left(\mathbf{J}(\mathbf{x}{)}^{\top }\mathbf{J}(\mathbf{x})+\mathbf{S}(\mathbf{x})\right)$ $\mathbf{S}(\mathbf{x}{)}_{k,j}={\sum }_{i=1}^m{r}_i(\mathbf{x})\frac{{\partial }^2{r}_i}{\partial x_k\partial x_j}(\mathbf{x})$ 牛顿法求解非线性最小二乘迭代公式：

$${\mathbf{x}}^{(k+1)}={\mathbf{x}}^{(k)}-{\left(\mathbf{J}(\mathbf{x}{)}^{\top }\mathbf{J}(\mathbf{x})+\mathbf{S}(\mathbf{x})\right)}^{-1}\mathbf{J}(\mathbf{x}{)}^{\top }\mathbf{r}(\mathbf{x})$$

矩阵 $\mathbf{S}(\mathbf{x})$ 包含函数 $\mathbf{r}$ 的二阶导数, 其中的元素都很小 高斯一牛顿法求解非线性最小二乘迭代公式：即略掉 $S(x)$ 项

$${\mathbf{x}}^{(k+1)}={\mathbf{x}}^{(k)}-{\left(\mathbf{J}(\mathbf{x}{)}^{\top }\mathbf{J}(\mathbf{x})\right)}^{-1}\mathbf{J}(\mathbf{x}{)}^{\top }\mathbf{r}(\mathbf{x})$$

---

共轭类方法

方法特性：

1. 对于n维二次型问题，能够在n步之内得到结果。
2. 共轭梯度法不需要计算黑塞矩阵
3. 不需要储存n·n矩阵，也不需要对矩阵进行求逆
4. 计算速度介于最速下降法和牛顿法之间。

定义10.1(共轭)： $Q$ 为 $n\times n$ 的对称实矩阵, 对于方向 ${\mathbf{d}}^{(0)},{\mathbf{d}}^{(1)},{\mathbf{d}}^{(2)},\cdots ,{\mathbf{d}}^{(m)}$, 如果对 于所有的 $i\ne j$, 有 ${\mathbf{d}}^{(i)}\mathbf{Q}{\mathbf{d}}^{(j)}=0$, 则称它们是关于 $\mathbf{Q}$ 共轭的

引理10.1： $Q$ 为 $n\times n$ 的对称正定矩阵, 如果方向 ${\mathbf{d}}^{(0)},{\mathbf{d}}^{(1)},\cdots ,{\mathbf{d}}^{(k)}\in {\mathbb{R}}^n,k⩽n-$ 1 非零, 且是关于 $\mathbf{Q}$ 共轭的, 那么它们是线性无关的。

---

共轭方向法

针对 $n$ 维二次型函数的最小化问题:

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Q}\mathbf{x}-{\mathbf{x}}^{\top }\mathbf{b}$$

其中, $\mathbf{Q}={\mathbf{Q}}^{\top }>0,\mathbf{x}\in {\mathbb{R}}^n$ 。注意, 由于 $\mathbf{Q}>0$, 因此函数 $f$ 有一个全局极小点, 可通过求解 $Qx=b$ 得到。

基本的共轭方向算法 给定初始点 ${\mathbf{x}}^{(0)}$ 和一组关于 $\mathbf{Q}$ 共轭的方向 ${\mathbf{d}}^{(0)},{\mathbf{d}}^{(1)},\cdots$, ${\mathbf{d}}^{(n-1)}$

$$\begin{array}{rl}{\mathbf{g}}^{(k)}& =\nabla f\left({\mathbf{x}}^{(k)}\right)=\mathbf{Q}{\mathbf{x}}^{(k)}-\mathbf{b}\\ {\alpha }_k& =-\frac{{\mathbf{g}}^{(k)\top }{\mathbf{d}}^{(k)}}{{\mathbf{d}}^{(k)\top }\mathbf{Q}{\mathbf{d}}^{(k)}}\\ {\mathbf{x}}^{(k+1)}& ={\mathbf{x}}^{(k)}+{\alpha }_k{\mathbf{d}}^{(k)}\end{array}$$

定理10.1： 对于任意的初始点 ${\mathbf{x}}^{(0)}$，基本的共轭方向算法都能在 $n$ 次迭代之内收敛到唯一的全局极小点 ${\mathbf{x}}^{\ast }$ ,即 ${\mathbf{x}}^{(n)}={\mathbf{x}}^{\ast }$ 。

引理10.2(精确步长)： 在共轭方向算法中, 对于所有 $k,0⩽k⩽n-1,0⩽i⩽k$, 都有

$${\mathbf{g}}^{(k+1)\top }{\mathbf{d}}^{(i)}=0$$

扩展子空间定理

共轭方向法满足 $f\left({\mathbf{x}}^{(k+1)}\right)={\min }_{\alpha }f\left({\mathbf{x}}^{(k)}+\alpha d^{(k)}\right)$, 而且还能满足 $f\left({\mathbf{x}}^{(k+1)}\right)={\min }_{a_0,\cdots ,a_k}f\left({\mathbf{x}}^{(0)}+{\sum }_{i=0}^k{a}_i{\mathbf{d}}^{(i)}\right)$ 记 ${\mathcal{V}}_k={\mathbf{x}}^{(0)}+\mathrm{span}\left[{\mathbf{d}}^{(0)},{\mathbf{d}}^{(1)},\cdots ,{\mathbf{d}}^{(k)}\right]$ 则有 $f\left({\mathbf{x}}^{(k+1)}\right)={\min }_{\mathbf{x}\in {\nu }_k}f(\mathbf{x})$

---

共轭梯度法

特性： 共轭方向法虽然计算效率高，但是需要提供一组 $Q$ 共轭方向，共轭梯度法不需要预先给定 $Q$ 共轭方向，而是随着迭代的进行不断产生 $Q$共轭方向。利用上一个搜索方向和目标函数在当前已经产生的搜索方向组成 $Q$ 共轭方向。

计算步骤:

1. 令 $k=0$; 选择初始值 ${\mathbf{x}}^{(0)}$ 。
2. 计算 ${\mathbf{g}}^{(0)}=\nabla f\left({\mathbf{x}}^{(0)}\right)$, 如果 ${\mathbf{g}}^{(0)}=0$, 停止迭代; 否则, 令 ${\mathbf{d}}^{(0)}=-{\mathbf{g}}^{(0)}$ 。
3. 计算 ${\alpha }_k=-\frac{{\mathbf{g}}^{(k)\top }{\mathbf{d}}^{(k)}}{{\mathbf{d}}^{(k)\top }\mathbf{Q}{\mathbf{d}}^{(k)}}$ 。
4. 计算 ${\mathbf{x}}^{(k+1)}={\mathbf{x}}^{(k)}+{\alpha }_k{\mathbf{d}}^{(k)}$ 。
5. 计算 ${\mathbf{g}}^{(k+1)}=\nabla f\left({\mathbf{x}}^{(k+1)}\right)$, 如果 ${\mathbf{g}}^{(k+1)}=0$, 停止迭代。
6. 计算 ${\beta }_k=\frac{{\mathbf{g}}^{(k+1)\top }\mathbf{Q}{\mathbf{d}}^{(k)}}{{\mathbf{d}}^{(k)\top }\mathbf{Q}{\mathbf{d}}^{(k)}}$ 。
7. 计算 ${\mathbf{d}}^{(k+1)}=-{\mathbf{g}}^{(k+1)}+{\beta }_k{\mathbf{d}}^{(k)}$ 。
8. 令 $k:=k+1$, 回到第 3 步。

共轭梯度法实例

例: $f\left(x_1,x_2,x_3\right)=\frac{3}{2}{x}_1^2+2x_2^2+\frac{3}{2}{x}_3^2+x_1{x}_3+2x_2{x}_3-3x_1-x_3$ 用共轭梯度法求其极小点, 初始点为 ${\mathbf{x}}^{(0)}=[0,0,0{]}^{\top }$ 。

$$\begin{array}{ll}\text{ Step 1: }& {\mathbf{g}}^{(0)}=[-3,0,-1{]}^{\top }{\mathbf{d}}^{(0)}=-{\mathbf{g}}^{(0)}\\ & {\alpha }_0=-\frac{{\mathbf{g}}^{(0)\top }{\mathbf{d}}^{(0)}}{{\mathbf{d}}^{(0)\top }\mathbf{Q}{\mathbf{d}}^{(0)}}=\frac{10}{36}\\ & {\mathbf{x}}^{(1)}={\mathbf{x}}^{(0)}+{\alpha }_0{\mathbf{d}}^{(0)}=[0.8333,0,0.2778{]}^{\top }\\ & \\ \text{ Step 2: }& {\mathbf{g}}^{(1)}=\nabla f\left({\mathbf{x}}^{(1)}\right)=[-0.2222,0.5556,0.6667{]}^{\top }\\ & {\beta }_0=\frac{{\mathbf{g}}^{(1)\top }\mathbf{Q}{\mathbf{d}}^{(0)}}{{\mathbf{d}}^{(0)\top }\mathbf{Q}{\mathbf{d}}^{(0)}}=0.08025\\ & {\mathbf{d}}^{(1)}=-{\mathbf{g}}^{(1)}+{\beta }_0{\mathbf{d}}^{(0)}=[0.4630,-0.5556,-0.5864{]}^{\top }\\ & {\alpha }_1=-\frac{{\mathbf{g}}^{(1)\top }{\mathbf{d}}^{(1)}}{{\mathbf{d}}^{(1)\top }\mathbf{Q}{\mathbf{d}}^{(1)}}=0.2187\\ & {\mathbf{x}}^{(2)}={\mathbf{x}}^{(1)}+{\alpha }_1{\mathbf{d}}^{(1)}=[0.9346,-0.1215,0.1495{]}^{\top }\\ & \\ \text{ Step 3: }& {\mathbf{g}}^{(2)}=\nabla f\left({\mathbf{x}}^{(2)}\right)=[-0.04673,-0.1869,0.1402{]}^{\top }\\ & {\beta }_1=\frac{{\mathbf{g}}^{(2)\top }\mathbf{Q}{\mathbf{d}}^{(1)}}{{\mathbf{d}}^{(1)\top }\mathbf{Q}{\mathbf{d}}^{(1)}}=0.07075\\ & {\mathbf{d}}^{(2)}=-{\mathbf{g}}^{(2)}+{\beta }_1{\mathbf{d}}^{(1)}=[0.07948,0.1476,-0.1817{]}^{\top }\\ & {\alpha }_2=-\frac{{\mathbf{g}}^{(2)\top }{\mathbf{d}}^{(2)}}{{\mathbf{d}}^{(2)\top }\mathbf{Q}{\mathbf{d}}^{(2)}}=0.8231\\ & {\mathbf{x}}^{(3)}={\mathbf{x}}^{(2)}+{\alpha }_2{\mathbf{d}}^{(2)}=[1.000,0.000,0.000{]}^{\top }\\ & \\ & {\mathbf{g}}^{(3)}=\nabla f\left({\mathbf{x}}^{(3)}\right)=0\text{ 即 }{\mathbf{x}}^{\ast }={\mathbf{x}}^{(3)}\end{array}$$

---

非线性共轭梯度法

理论上把线性共轭梯度法中的矩阵 Q 换成黑 塞矩阵。但是，对一般的非线性函数，每次迭代都必须重新计算黑 塞矩阵，这需要非常大的运算量 所以需要对其进行修改，消除每次迭代中进行求黑塞矩阵的环节。

• Hestenes-Stiefel公式：

$${\beta }_k=\frac{{\mathbf{g}}^{(k+1)\top }\left[{\mathbf{g}}^{(k+1)}-{\mathbf{g}}^{(k)}\right]}{{\mathbf{d}}^{(k)\top }\left[{\mathbf{g}}^{(k+1)}-{\mathbf{g}}^{(k)}\right]}$$

• Polak-Ribiere公式: 将 $Hestenes-Stiefel$ 公式的分母部分展开。

$${\beta }_k=\frac{{\mathbf{g}}^{(k+1)\top }\left[{\mathbf{g}}^{(k+1)}-{\mathbf{g}}^{(k)}\right]}{{\mathbf{g}}^{(k)\top }{\mathbf{g}}^{(k)}}$$

• Fletcher_reeves公式： 将 $Polak-Ribiere$ 公式的分子部分展开。

$${\beta }_k=\frac{{\mathbf{g}}^{(k+1)\top }{\mathbf{g}}^{(k+1)}}{{\mathbf{g}}^{(k)\top }{\mathbf{g}}^{(k)}}$$

对于二次型问题，这三个公式是等价的；但是。当目标函数为一般的非线性函数时，这三个公式并不一致。

---

拟牛顿法

• 牛顿法的缺陷:

1. 当目标函数为一般性的非线性函数时，牛顿法不能保证能够从任意起始点 ${\mathbf{x}}^{(0)}$ 收敛到函数的极小点。
2. 必须计算黑塞矩阵 $\mathbf{F}({\mathbf{x}}^{(k)})$ 和求解方程 $\mathbf{F}({\mathbf{x}}^{(k)}){\mathbf{d}}^{(k)}=-{\mathbf{g}}^{(k)}$ 上进行一维搜索。
3. 黑塞矩阵是非正定或奇异的。

• 拟牛顿法的思路： 设计黑塞矩阵的近似矩阵来代替黑塞矩阵。此时需要用到目标函数值和梯度。令 ${\mathbf{H}}_0,{\mathbf{H}}_1,{\mathbf{H}}_2,\dots$ 表示对应黑塞矩阵的逆的一系列近似矩阵。 则 ${\mathbf{H}}_k$ 满足：

1. 对称正定。(保证函数值迭代后下降)
2. 从${\mathbf{H}}_{k-1}$ 到 ${\mathbf{H}}_k$ 计算量较小。
3. ${\mathbf{H}}_k$ 与对应的黑塞矩阵近似。

---

分析: 黑塞矩阵性质 (即二阶导)： 1维：近似计算 $f^{\prime \prime }\left(x^{(k)}\right):\frac{f^{\prime }\left(x^{(k)}\right)-f^{\prime }\left(x^{(k-1)}\right)}{x^{(k)}-x^{(k-1)}}$ $f^{\prime }\left(x^{(k-1)}\right)\approx f^{\prime }\left(x^{(k)}\right)+f^{\prime \prime }\left(x^{(k)}\right)\left(x^{(k-1)}-x^{(k)}\right)$ n维: $\nabla f\left(x^{(k-1)}\right)\approx \nabla f\left(x^{(k)}\right)+{\nabla }^{2}f\left(x^{(k)}\right)\left(x^{(k-1)}-x^{(k)}\right)$ 记 $\Delta g^{(k-1)}=\nabla f\left(x^{(k)}\right)-\nabla f\left(x^{(k-1)}\right),\Delta x^{(k-1)}=x^{(k)}-x^{(k-1)}$ 简化为: $\Delta g^{(k-1)}\approx {\nabla }^{2}f\left(x^{(k)}\right)\Delta x^{(k-1)}$ 或 ${\left[{\nabla }^{2}f\left(x^{(k)}\right)\right]}^{-1}\Delta g^{(k-1)}\approx \Delta x^{(k-1)}$ 因此：${\mathbf{H}}_k\Delta {\mathbf{g}}^{(k-1)}=\Delta {\mathbf{x}}^{(k-1)}$

• 拟牛顿法迭代公式:

$$\begin{array}{rl}{\mathbf{d}}^{(k)}& =-{\mathbf{H}}_k{\mathbf{g}}^{(k)}\\ {\alpha }_k& =\underset{\alpha ⩾0}{\mathrm{argmin}}f\left({\mathbf{x}}^{(k)}+\alpha {\mathbf{d}}^{(k)}\right)\\ {\mathbf{x}}^{(k+1)}& ={\mathbf{x}}^{(k)}+{\alpha }_k{\mathbf{d}}^{(k)}\end{array}$$

其中, 矩阵 ${\mathbf{H}}_0,{\mathbf{H}}_1,{\mathbf{H}}_2,\cdots$ 是$n\times n$ 对称实矩阵，是对黑塞矩阵的逆的近似。目标函数为二次型函数时, 它们必须满足

$${\mathbf{H}}_{k+1}\Delta {\mathbf{g}}^{(i)}=\Delta {\mathbf{x}}^{(i)},0⩽i⩽k$$

其中, $\Delta {\mathbf{x}}^{(i)}={\mathbf{x}}^{(i+1)}-{\mathbf{x}}^{(i)}={\alpha }_i{\mathbf{d}}^{(i)},\Delta {\mathbf{g}}^{(i)}={\mathbf{g}}^{(i+1)}-{\mathbf{g}}^{(i)}=\mathbf{Q}\Delta {\mathbf{x}}^{(i)}$ 。实际上, 拟牛顿法也是 一种共轭方向法, 接下来给出证明。

• 定理 11. 1: 将拟牛顿法应用到二次型问题中, 黑塞矩阵为 $\mathbf{Q}={\mathbf{Q}}^{\top }$, 对于 $0⩽k<n-1$, 有

$${\mathbf{H}}_{k+1}\Delta {\mathbf{g}}^{(i)}=\Delta {\mathbf{x}}^{(i)},0⩽i⩽k$$

其中, ${\mathbf{H}}_{k+1}={\mathbf{H}}_{k+1}^{\top }$ 。 如果 ${\alpha }_i\ne 0,0⩽i⩽k$, 那么 ${\mathbf{d}}^{(0)},{\mathbf{d}}^{(1)},\cdots ,{\mathbf{d}}^{(k+1)}$ 是 $\mathbf{Q}$ 共轭的。

从矩阵 ${\mathbf{H}}_k$ 必须满足的方程来看，${\mathbf{H}}_k$ 并不能唯一确定，常见的矩阵${\mathbf{H}}_{k+1}$ 是通过在矩阵 ${\mathbf{H}}_k$ 上增加一个修正项来得到。(秩1修正、DFP，BFGS)

---

秩1修正公式

$${\mathbf{H}}_{k+1}={\mathbf{H}}_k+a_k{\mathbf{z}}^{(k)}{\mathbf{z}}^{(k)\top }$$ $${\mathbf{H}}_{k+1}\Delta {\mathbf{g}}^{(k)}=\Delta {\mathbf{x}}^{(k)}$$

在给定 ${\mathbf{H}}_k,\Delta {\mathbf{g}}^{(k)},\Delta {\mathbf{x}}^{(k)}$ 后, 确定 $a_k$ 和 ${\mathbf{z}}^{(k)}$

$${\mathbf{H}}_{k+1}={\mathbf{H}}_k+\frac{\left(\Delta {\mathbf{x}}^{(k)}-{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}\right){\left(\Delta {\mathbf{x}}^{(k)}-{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}\right)}^{\top }}{\Delta {\mathbf{g}}^{(k)\top }\left(\Delta {\mathbf{x}}^{(k)}-{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}\right)}$$

• 算法步骤：

1. 令 $k=0$; 选择初始点 ${\mathbf{x}}^{(0)}$, 任选一个对称正定实矩阵 ${\mathbf{H}}_0$ 。
2. 如果 ${\mathbf{g}}^{(k)}=0$, 停止迭代; 否则, 令 ${\mathbf{d}}^{(k)}=-{\mathbf{H}}_k{\mathbf{g}}^{(k)}$ 。
3. 计算 $\begin{array}{r}{\alpha }_k=\underset{\alpha ⩾0}{\mathrm{argmin}}f\left({\mathbf{x}}^{(k)}+\alpha d^{(k)}\right)\\ {\mathbf{x}}^{(k+1)}={\mathbf{x}}^{(k)}+{\alpha }_k{\mathbf{d}}^{(k)}\end{array}$
4. 计算 $\Delta {\mathbf{x}}^{(k)}={\alpha }_k{\mathbf{d}}^{(k)}$

$$\begin{array}{rl}\Delta {\mathbf{g}}^{(k)}& ={\mathbf{g}}^{(k+1)}-{\mathbf{g}}^{(k)}\\ {\mathbf{H}}_{k+1}& ={\mathbf{H}}_k+\frac{\left(\Delta {\mathbf{x}}^{(k)}-{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}\right){\left(\Delta {\mathbf{x}}^{(k)}-{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}\right)}^{\top }}{\Delta {\mathbf{g}}^{(k)\top }\left(\Delta {\mathbf{x}}^{(k)}-{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}\right)}\end{array}$$

5. 令 $k:=k+1$, 回到第 2 步。

秩1校正公式实例

例：用秩 1 算法求函数 $f$ 极小点。 $f\left(x_1,x_2\right)=x_1^2+\frac{1}{2}{x}_2^2+3$ 初始值为 ${\mathbf{x}}^{(0)}=[1,2{]}^{\top },{\mathbf{H}}_0={\mathbf{I}}_2$ 解:

$${\mathbf{g}}^{(k)}=\left[\begin{array}{ll}2& 0\\ 0& 1\end{array}\right]{\mathbf{x}}^{(k)}$$

Step 1:

$$\begin{array}{rl}& {\mathbf{d}}^{(0)}=-{\mathbf{g}}^{(0)}=[-2,-2{]}^{\top }\\ & {\alpha }_0=\underset{\alpha ⩾0}{\mathrm{argmin}}f\left({\mathbf{x}}^{(0)}+\alpha {\mathbf{d}}^{(0)}\right)=-\frac{{\mathbf{g}}^{(0)\top }{\mathbf{d}}^{(0)}}{{\mathbf{d}}^{(0)\top }\mathbf{Q}{\mathbf{d}}^{(0)}}=\frac{2}{3}\\ & {\mathbf{x}}^{(1)}={\mathbf{x}}^{(0)}+{\alpha }_0{\mathbf{d}}^{(0)}={\left[-\frac{1}{3},\frac{2}{3}\right]}^{\top }\end{array}$$

Step 2:

$$\begin{array}{rl}& \Delta {\mathbf{x}}^{(0)}={\alpha }_0{\mathbf{d}}^{(0)}={\left[-\frac{4}{3},-\frac{4}{3}\right]}^{\top }\\ & {\mathbf{g}}^{(1)}=\mathbf{Q}{\mathbf{x}}^{(1)}={\left[-\frac{2}{3},\frac{2}{3}\right]}^{\top }\\ & \Delta {\mathbf{g}}^{(0)}={\mathbf{g}}^{(1)}-{\mathbf{g}}^{(0)}={\left[-\frac{8}{3},-\frac{4}{3}\right]}^{\top }\\ & {\mathbf{H}}_1={\mathbf{H}}_0+\frac{\left(\Delta {\mathbf{x}}^{(0)}-{\mathbf{H}}_0\Delta {\mathbf{g}}^{(0)}\right){\left(\Delta {\mathbf{x}}^{(0)}-{\mathbf{H}}_0\Delta {\mathbf{g}}^{(0)}\right)}^{\top }}{\Delta {\mathbf{g}}^{(0)\top }\left(\Delta {\mathbf{x}}^{(0)}-{\mathbf{H}}_0\Delta {\mathbf{g}}^{(0)}\right)}=\left[\begin{array}{ll}\frac{1}{2}& 0\\ 0& 1\end{array}\right]\\ & {\mathbf{d}}^{(1)}=-{\mathbf{H}}_1{\mathbf{g}}^{(1)}={\left[\frac{1}{3},-\frac{2}{3}\right]}^{\top }\\ & {\alpha }_1=-\frac{{\mathbf{g}}^{(1)\top }{\mathbf{d}}^{(1)}}{{\mathbf{d}}^{(1)\top }{\mathbf{Qd}}^{(1)}}=1\\ & {\mathbf{x}}^{(2)}={\mathbf{x}}^{(1)}+{\alpha }_1{\mathbf{d}}^{(1)}=[0,0{]}^{\top }{\mathbf{g}}^{(2)}=0,\text{ 也就是说 }{\mathbf{x}}^{(2)}={\mathbf{x}}^{\ast }\end{array}$$

---

DFP算法

• 秩一修正公式缺陷

1. 秩1算法产生的矩阵 ${\mathbf{H}}_{k+1}$ 可能非正定, 将导致 $d^{(k+1)}$ 可能不是下降方向(即使是二次型问题）。
2. 秩 1 公式的分母如果接近 0 ,会出现计算困难。

---

寻找 $\mathbf{F}{\left({\mathbf{x}}^{(k)}\right)}^{-1}$ 的近似 具体公式:

$$\begin{array}{rl}& \Delta {\mathbf{x}}^{(k)}={\alpha }_k{\mathbf{d}}^{(k)}\\ & \Delta {\mathbf{g}}^{(k)}={\mathbf{g}}^{(k+1)}-{\mathbf{g}}^{(k)}\\ & {\mathbf{H}}_{k+1}={\mathbf{H}}_k+\frac{\Delta {\mathbf{x}}^{(k)}\Delta {\mathbf{x}}^{(k)\top }}{\Delta {\mathbf{x}}^{(k)\top }\Delta {\mathbf{g}}^{(k)}}-\frac{\left[{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}\right]{\left[{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}\right]}^{\top }}{\Delta {\mathbf{g}}^{(k)\top }{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}}\end{array}$$

使用秩一算法或者 $DFP$ 算法求解二次型问题时，黑塞矩阵为 $\mathbf{Q}={\mathbf{Q}}^{\top }$ 有 ${\mathbf{H}}_{k+1}\Delta {\mathbf{g}}^{(i}=\Delta {\mathbf{x}}^{(i)}$ ，$0\le \mathbf{i}\le \mathbf{k}$

• DFP算法特性：
• 在 $DFP$ 算法中，只要矩阵 ${\mathbf{H}}_k$ 正定，${\mathbf{H}}_{k+1}$ 就一定是正定的。
• 当矩阵 ${\mathbf{H}}_k$ 接近为奇异矩阵时，迭代有时无法展开。

DFP公式实例

例：用 DFP 算法求函数 $f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^{\top }\left[\begin{array}{ll}4& 2\\ 2& 2\end{array}\right]\mathbf{x}-{\mathbf{x}}^{\top }\left[\begin{array}{c}-1\\ 1\end{array}\right],\mathbf{x}\in {\mathbb{R}}^2$ 的极小点。初始点为 ${\mathbf{x}}^{(0)}=[0,0{]}^{\top },{\mathbf{H}}_0={\mathbf{I}}_2$ 。 step 1:

$$\begin{array}{rl}& {\mathbf{g}}^{(0)}=[1,-1{]}^{\top }\\ & {\mathbf{d}}^{(0)}=-{\mathbf{H}}_0{\mathbf{g}}^{(0)}=\left[\begin{array}{c}-1\\ 1\end{array}\right]\\ & {\alpha }_0=\underset{\alpha ⩾0}{\mathrm{argmin}}f\left({\mathbf{x}}^{(0)}+\alpha {\mathbf{d}}^{(0)}\right)=1\\ & {\mathbf{x}}^{(1)}={\mathbf{x}}^{(0)}+{\alpha }_0{\mathbf{d}}^{(0)}=[-1,1{]}^{\top }\\ & {\mathbf{g}}^{(k)}=\left[\begin{array}{ll}4& 2\\ 2& 2\end{array}\right]{\mathbf{x}}^{(k)}-\left[\begin{array}{c}-1\\ 1\end{array}\right]\end{array}$$

step 2:

$$\begin{array}{rl}& {\mathbf{g}}^{(1)}=\left[\begin{array}{ll}4& 2\\ 2& 2\end{array}\right]\left[\begin{array}{c}-1\\ 1\end{array}\right]-\left[\begin{array}{c}-1\\ 1\end{array}\right]=\left[\begin{array}{l}-1\\ -1\end{array}\right]\\ & \Delta {\mathbf{g}}^{(0)}=g^{(1)}-g^{(0)}=[-2,0{]}^{\top }\\ & \Delta {\mathbf{x}}^{(0)}={\mathbf{x}}^{(1)}-{\mathbf{x}}^{(0)}=[-1,1{]}^{\top }\\ & {\mathbf{H}}_1={\mathbf{H}}_0+\frac{\Delta {\mathbf{x}}^{(0)}\Delta {\mathbf{x}}^{(0)\top }}{\Delta {\mathbf{x}}^{(0)\top }\Delta {\mathbf{g}}^{(0)}}-\frac{\left({\mathbf{H}}_0\Delta {\mathbf{g}}^{(0)}\right){\left({\mathbf{H}}_0\Delta {\mathbf{g}}^{(0)}\right)}^{\top }}{\Delta {\mathbf{g}}^{(0)\top }{\mathbf{H}}_0\Delta {\mathbf{g}}^{(0)}}=\left[\begin{array}{cc}\frac{1}{2}& -\frac{1}{2}\\ -\frac{1}{2}& \frac{3}{2}\end{array}\right]\\ & {\mathbf{d}}^{(1)}=-{\mathbf{H}}_1{\mathbf{g}}^{(1)}=[0,1{]}^{\top }\\ & {\alpha }_1=\underset{\alpha ⩾0}{\mathrm{argmin}}f\left({\mathbf{x}}^{(1)}+\alpha {\mathbf{d}}^{(1)}\right)=\frac{1}{2}\\ & {\mathbf{x}}^{(2)}={\mathbf{x}}^{(1)}+{\alpha }_1{\mathbf{d}}^{(1)}=[-1,3/2{]}^{\top }\\ & \end{array}$$

函数 $f$ 为两变量二次型函数, ${\mathbf{x}}^{(2)}$ 就是极小点 ${\mathbf{x}}^{\ast }$。可以验证 ${\mathbf{d}}^{(0)}$ 和 ${\mathbf{d}}^{(1)}$ 是 $\mathbf{Q}$ 共轭方向。

---

BFSGS公式

• 旧思路：根据 $\Delta {\mathbf{g}}^{(i)}=\mathbf{Q}\Delta {\mathbf{x}}^{(i)},0⩽i⩽k$ 黑塞矩阵逆矩阵的近似矩阵需要满足以下条件:

$${\mathbf{H}}_{k+1}\Delta {\mathbf{g}}^{(i)}=\Delta {\mathbf{x}}^{(i)},0⩽i⩽k$$

基于上述等式, 可以构造黑塞矩阵逆矩阵 $Q^{-1}$ 的近似矩阵的更新公式。 如秩1公式和DFP公式都是据此而来的。

• 新思路: 除了构造 $Q^{-1}$ 的近似矩阵, 还可以构造矩阵 $Q$ 的近似矩阵 令矩阵 $B_k$ 表示在第 $k$ 次迭代中关于矩阵 $Q$ 的估计 则 ${\mathbf{B}}_{\mathbf{k}+1}$ 应该满足 $\Delta {\mathbf{g}}^{(i)}={\mathbf{B}}_{k+1}\Delta {\mathbf{x}}^{(i)},0⩽i⩽k$

由DFP公式: ${\mathbf{H}}_{k+1}^{\mathrm{DFP}}={\mathbf{H}}_k+\frac{\Delta {\mathbf{x}}^{(k)}\Delta {\mathbf{x}}^{(k)\top }}{\Delta {\mathbf{x}}^{(k)\top }\Delta {\mathbf{g}}^{(k)}}-\frac{{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}\Delta {\mathbf{g}}^{(k)\top }{\mathbf{H}}_k}{\Delta {\mathbf{g}}^{(k)\top }{\mathbf{H}}_k\Delta {\mathbf{g}}^{(k)}}$ 用对称性，得BFGS公式

$${\mathbf{B}}_{k+1}={\mathbf{B}}_k+\frac{\Delta {\mathbf{g}}^{(k)}\Delta {\mathbf{g}}^{(k)\top }}{\Delta {\mathbf{g}}^{(k)\top }\Delta {\mathbf{x}}^{(k)}}-\frac{{\mathbf{B}}_k\Delta {\mathbf{x}}^{(k)}\Delta {\mathbf{x}}^{(k)\top }{\mathbf{B}}_k}{\Delta {\mathbf{x}}^{(k)\top }{\mathbf{B}}_k\Delta {\mathbf{x}}^{(k)}}$$

注: DFP公式与BFGS公式称为互补的（或对偶的）

• BFGS公式的逆矩阵

$${\left({\mathbf{B}}_{k+1}\right)}^{-1}={\left({\mathbf{B}}_k+\frac{\Delta {\mathbf{g}}^{(k)}\Delta {\mathbf{g}}^{(k)T}}{\Delta {\mathbf{g}}^{(k)\top }\Delta {\mathbf{x}}^{(k)}}-\frac{{\mathbf{B}}_k\Delta {\mathbf{x}}^{(k)}\Delta {\mathbf{x}}^{(k)\top }{\mathbf{B}}_k}{\Delta {\mathbf{x}}^{(k)\top }{\mathbf{B}}_k\Delta {\mathbf{x}}^{(k)}}\right)}^{-1}$$

原理：应用两次 Sherman-Morison公式 即可