13. 无约束优化

# 概述

无约束可微优化问题可以直接利用梯度信息求解。主要关注两个问题：

• 如何计算搜索方向
• 如何计算前进步长

# 下降算法与直线搜索

1. （梯度）下降算法通用框架

   对于无约束优化问题 $\min_x f(x)$，下降算法的通用框架如下：

   Step 1：确定初始点 $x^0 \in \text{dom}\ f$，令 $k = 0$

   Step 2：判断是否停止：如果 $\|\nabla f(x^k)\| \leq \varepsilon$，停止

   Step 3：计算 $x^k$ 处的下降方向：确定 $d^k$ 满足

   $$\nabla f(x^k)^T d^k < 0$$

   这确保 $d^k$ 是下降方向（函数值在该方向上会减少）。

   Step 4：确定步长（通常直线搜索）：若 $t^k > 0$ 满足

   $$f(x^k + t^k d^k) < f(x^k)$$

   令 $x^{k+1} = x^k + t^k d^k$，$k \Rightarrow k+1$，回 Step 2。

2. 步长选择的重要性

   步长太大：如果简单地取 $t_k = t$ 对所有 $k = 1, 2, 3, \ldots$，且 $t$ 太大，算法可能发散。

   步长太小：如果 $t$ 太小，算法收敛会很慢。

   合适的步长：当 $t$ "刚好合适"时，算法收敛良好。收敛性分析会给出"刚好合适"的精确概念。

3. 精确搜索与非精确搜索

   一般来说，当我们选定了前进方向，可以通过精确搜索或非精确搜索来决定合适的前进步长。

   精确搜索算法（Exact Line Search）

   求沿选定方向出发，使得函数最小的步长：

   $$t^k = \arg\min_{t \geq 0} f(x^k + t d^k)$$

   精确搜索算法是单变量优化问题。一般来说，精确搜索所花的时间代价小于求出搜索方向的时间代价。

4. 精确搜索的基本途径

   1）确定初始区间

   用试探法确定一个单谷区间。可用步长加倍或减倍的方法。

   2）逐步压缩区间

   按照一定规则在上述区间内选点，通过计算并比较这些点上的函数值逐步缩小包含局部最优解的区间，直至区间长度小于给定阈值。

5. 单谷/单峰函数

   单峰函数（Unimodal Function）

   在所考虑的区间中只有一个严格局部极大值（峰值）的实值函数。如果函数 $f(x)$ 在区间 $[a, b]$ 上只有唯一的最大值点 $C$，而在最大值点 $C$ 的左侧，函数单调增加；在点 $C$ 的右侧，函数单调减少，则称这个函数为区间 $[a, b]$ 上的单峰函数。

   单谷函数（Unimodal Function）

   在所考虑的区间中只有一个严格局部极小值（谷值）的实值函数。如果函数 $f(x)$ 在区间 $[a, b]$ 上只有唯一的最小值点 $C$，而在最小值点 $C$ 的左侧，函数单调减少；在点 $C$ 的右侧，函数单调增加，则称这个函数为区间 $[a, b]$ 上的单谷函数。

   与凸函数的关系

   • 单谷函数不一定是凸函数
   • 凸函数在任意区间上都是单谷的
   • 单谷性质使得可以使用区间压缩方法

6. 区间压缩原理

   已知闭区间 $[a, b]$ 是单谷区间，在其内部任取两点 $a_1 < b_1$，计算 $\varphi(a_1), \varphi(b_1)$：

   • 如果 $\varphi(a_1) < \varphi(b_1)$，局部最优解在区间 $[a, b_1]$
   • 否则，局部最优解在区间 $[a_1, b]$

   两种情况均能压缩区间。

7. 0.618 法（黄金分割法，Golden Section Method）

   基本想法

   每计算一个函数值能将区间压缩一个固定比值 $c$。

   设区间 $[a, b]$ 内有两个点 $t_1 < t_2$：

   $$a \quad t_1 \quad t_2 \quad b$$

   如果 $\varphi(t_1) < \varphi(t_2)$，则最优解在 $[a, t_2]$：

   $$a \quad t_3 \quad t_1 \quad t_2 \quad b$$

   如果 $\varphi(t_1) > \varphi(t_2)$，则最优解在 $[t_1, b]$：

   $$a \quad t_1 \quad t_2 \quad t_3 \quad b$$

   算法步骤

   步骤 1：确定单谷区间

   选定 $\gamma > 1$，$\delta > 0$，令 $s^0 = 0$，$s^i = \gamma^{i-1}\delta$，$\forall i \geq 1$。选取第一个满足 $f(x^k + s^i d^k) > f(x^k + s^{i-1} d^k)$ 的 $s^i$，获得单谷区间 $[0, s^i]$。

   步骤 2：确定最优步长

   确定满足 $f(x^k + t^k d^k) = \min_{t > 0} f(x^k + t d^k)$ 的 $t^k$。

   单谷区间为 $[a^i, b^i]$ 时，取：

   $$s' = a^i + (1-c)(b^i - a^i), \quad s'' = a^i + c(b^i - a^i)$$

   其中 $c = (\sqrt{5} - 1)/2 \approx 0.618$ 是方程 $(1-c)/c = c/1$ 的正数解。

   • 如果 $f(x^k + s' d^k) > f(x^k + s'' d^k)$，令 $a^{i+1} = s'$，$b^{i+1} = b^i$，用当前 $s''$ 替换 $s'$，再令 $s'' = a^{i+1} + c(b^{i+1} - a^{i+1})$
   • 否则，令 $a^{i+1} = a^i$，$b^{i+1} = s''$，用当前 $s'$ 替换 $s''$，再令 $s' = a^{i+1} + (1-c)(b^{i+1} - a^{i+1})$

   重复直至单谷区间长度足够小。

# 梯度下降算法

1. 基本思想

   梯度下降算法（Gradient Descent Algorithm）是最简单的一阶优化方法，使用负梯度方向作为搜索方向：

   $$d^k = -\nabla f(x^k)$$

   更新公式：

   $$x^{k+1} = x^k - t^k \nabla f(x^k)$$

   其中 $t^k > 0$ 是步长。

2. 下降方向的条件

   梯度下降方向满足下降方向条件：

   $$\nabla f(x^k)^T d^k = \nabla f(x^k)^T (-\nabla f(x^k)) = -\|\nabla f(x^k)\|^2 < 0$$

   只要 $\nabla f(x^k) \neq 0$，负梯度方向就是下降方向。

3. 步长选择

   固定步长

   取 $t^k = t$（常数），但需要选择合适的 $t$：

   • $t$ 太大：可能发散
   • $t$ 太小：收敛很慢
   • $t$ 合适：收敛良好

   精确直线搜索

   使用精确直线搜索：

   $$t^k = \arg\min_{t \geq 0} f(x^k - t \nabla f(x^k))$$

   非精确直线搜索

   使用 Armijo 条件、Wolfe 条件等非精确搜索准则。

4. 算法特点

   优点：

   • 算法简单，易于实现
   • 只需要一阶导数信息
   • 每次迭代计算成本低
   • 适用于大规模问题

   缺点：

   • 收敛速度可能较慢（特别是条件数大的问题）
   • 可能产生锯齿形路径
   • 对步长选择敏感

# 最速下降算法

1. 基本思想

   最速下降算法（Steepest Descent Algorithm）是梯度下降算法的一种，使用精确直线搜索来确定步长：

   $$t^k = \arg\min_{t \geq 0} f(x^k - t \nabla f(x^k))$$

   更新公式：

   $$x^{k+1} = x^k - t^k \nabla f(x^k)$$

   其中 $t^k$ 是通过精确直线搜索得到的。

2. 算法名称的由来

   "最速下降"指的是在当前位置，负梯度方向是使函数值下降最快的方向（在单位步长下）。通过精确直线搜索，算法沿着这个方向找到使函数值最小的点。

3. 算法步骤

   Step 1：初始化 $x^0 \in \text{dom}\ f$，令 $k = 0$

   Step 2：如果 $\|\nabla f(x^k)\| \leq \varepsilon$，停止

   Step 3：计算搜索方向：$d^k = -\nabla f(x^k)$

   Step 4：精确直线搜索：$t^k = \arg\min_{t \geq 0} f(x^k + t d^k)$

   Step 5：更新：$x^{k+1} = x^k + t^k d^k$，$k \Rightarrow k+1$，回 Step 2

4. 收敛性质

   收敛性

   对于强凸函数，最速下降算法保证收敛到全局最优解。

   收敛速度

   • 对于强凸函数，收敛速度是线性的
   • 收敛速度取决于条件数（condition number）
   • 条件数越大，收敛越慢

5. 与梯度下降的关系

   • 最速下降是梯度下降的一种特殊情况（使用精确直线搜索）
   • 梯度下降可以使用固定步长或非精确搜索
   • 最速下降使用精确搜索，理论上每步下降最多

6. 应用场景

   • 适用于大规模优化问题
   • 适用于条件数不太大的问题
   • 作为其他算法的子程序

# Newton 方法

1. 基本思想

   牛顿方法（Newton's Method）是一种二阶优化方法，使用目标函数的 Hessian 矩阵信息来构造搜索方向。相比梯度下降，牛顿方法通常具有更快的收敛速度。

   搜索方向

   牛顿方法的搜索方向为：

   $$d^k = -\nabla^2 f(x^k)^{-1} \nabla f(x^k)$$

   这称为牛顿方向（Newton direction）。

   更新公式

   $$x^{k+1} = x^k - t^k \nabla^2 f(x^k)^{-1} \nabla f(x^k)$$

   其中 $t^k > 0$ 是步长。当 $t^k = 1$ 时，称为纯牛顿步（pure Newton step）。

2. 算法步骤

   Step 1：初始化 $x^0 \in \text{dom}\ f$，令 $k = 0$

   Step 2：如果 $\|\nabla f(x^k)\| \leq \varepsilon$，停止

   Step 3：计算牛顿方向：$d^k = -\nabla^2 f(x^k)^{-1} \nabla f(x^k)$

   Step 4：确定步长 $t^k$（可以使用精确搜索或非精确搜索）

   Step 5：更新：$x^{k+1} = x^k + t^k d^k$，$k \Rightarrow k+1$，回 Step 2

3. 牛顿方向的几何解释

   二次近似

   牛顿方向可以通过对目标函数进行二次近似得到：

   $$f(x^k + d) \approx f(x^k) + \nabla f(x^k)^T d + \frac{1}{2} d^T \nabla^2 f(x^k) d$$

   最小化这个二次近似，得到：

   $$d^k = \arg\min_d \left\{ \nabla f(x^k)^T d + \frac{1}{2} d^T \nabla^2 f(x^k) d \right\} = -\nabla^2 f(x^k)^{-1} \nabla f(x^k)$$

   最优性

   如果 $\nabla^2 f(x^k) \succ 0$（正定），则牛顿方向是下降方向：

   $$\nabla f(x^k)^T d^k = -\nabla f(x^k)^T \nabla^2 f(x^k)^{-1} \nabla f(x^k) < 0$$

4. 纯牛顿步 vs 阻尼牛顿步

   纯牛顿步（$t^k = 1$）

   • 当初始点接近最优解时，纯牛顿步通常收敛很快（二次收敛）
   • 当初始点远离最优解时，可能不收敛或发散

   阻尼牛顿步（$t^k < 1$）

   • 使用直线搜索确定步长，保证函数值下降
   • 更稳健，适用于远离最优解的情况
   • 收敛速度可能较慢

5. 算法特点

   优点：

   • 收敛速度快（二次收敛）
   • 对于强凸函数，具有很好的理论保证
   • 对于自和谐函数，有完整的收敛性分析

   缺点：

   • 需要计算和存储 Hessian 矩阵（$O(n^2)$ 存储，$O(n^3)$ 计算）
   • 需要求解线性方程组（$O(n^3)$ 计算）
   • 对于大规模问题，计算成本高
   • 需要 Hessian 矩阵正定

# 收敛性分析

对于自和谐函数，牛顿方法具有完整的收敛性分析。这里主要讨论自和谐函数上的收敛性。

1. 牛顿减量（Newton Decrement）

   定义牛顿减量为：

   $$\lambda(x) = \left( \nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x) \right)^{1/2}$$

   性质：

   • $\lambda(x) \geq 0$，且 $\lambda(x) = 0$ 当且仅当 $\nabla f(x) = 0$
   • $\lambda(x)$ 是 $f(x) - p^*$ 的上界估计
   • 对于自和谐函数，有 $f(x) - p^* \leq \lambda(x)^2$

2. 收敛阶段

   对于自和谐函数，牛顿方法的收敛可以分为两个阶段：

   阻尼牛顿阶段（Damped Newton Phase）

   当 $\lambda(x^k) > \eta$（其中 $\eta$ 是某个阈值）时，算法处于阻尼牛顿阶段：

   • 使用阻尼步长 $t^k < 1$
   • 函数值单调下降
   • 收敛速度是线性的

   二次收敛阶段（Quadratic Convergence Phase）

   当 $\lambda(x^k) \leq \eta$ 时，算法进入二次收敛阶段：

   • 可以使用纯牛顿步（$t^k = 1$）
   • 收敛速度是二次的
   • $\lambda(x)$ 快速减小

3. 进入二次收敛的条件

   进入二次收敛的条件是：

   $$\lambda(x^k) \leq \frac{1-2\alpha}{4}$$

   其中 $\alpha$ 是直线搜索的参数（如 Armijo 条件中的参数）。

   在这个条件下，可以证明：

   • 纯牛顿步（$t = 1$）满足下降条件
   • $\lambda(x^{k+1}) \leq 2\lambda(x^k)^2$
   • 算法进入二次收敛

4. 二次收敛阶段的迭代次数上界

   取 $\eta = \frac{1-2\alpha}{4}$。

   如果 $\lambda(x^k) \leq \eta$，因为 $t^k = 1$，$2\lambda(x^{k+1}) \leq (2\lambda(x^k))^2$，对所有 $l \geq k$ 有：

   $$2\lambda(x^l) \leq (2\lambda(x^k))^{2^{l-k}} \leq \left(2 \times \frac{1}{4}\right)^{2^{l-k}} = \left(\frac{1}{2}\right)^{2^{l-k}}$$

   因此：

   $$f(x^l) - p^* \leq \lambda(x^l)^2 \leq \frac{1}{4}\lambda(x^l) \leq \left(\frac{1}{2}\right)^{2^{l-k+1}}$$

   只要 $l - k + 1 \geq \log_2(\log_2(1/\varepsilon))$，就有 $f(x^l) - p^* \leq \varepsilon$。

   这意味着二次收敛阶段的迭代次数上界是 $O(\log\log(1/\varepsilon))$，这是双对数级别的，非常快。

5. 阻尼牛顿阶段的迭代次数上界

   取 $\gamma = \alpha \beta \frac{\eta^2}{1+\eta}$，利用 $f(x^k) - f(x^{k+1}) \geq \alpha \beta \frac{\lambda(x^k)^2}{1+\lambda(x^k)}$。

   当 $\lambda(x^k) > \eta$ 时：

   $$f(x^k) - f(x^{k+1}) \geq \alpha \beta \frac{\lambda(x^k)^2}{1+\lambda(x^k)} \geq \alpha \beta \frac{\eta^2}{1+\eta} = \gamma$$

   因此阻尼牛顿阶段的迭代次数上界为：

   $$K_1 \leq \frac{f(x^0) - p^*}{\gamma}$$

6. 总迭代次数上界

   总的迭代次数上界为：

   $$\frac{f(x^0) - p^*}{\gamma} + \log_2(\log_2(1/\varepsilon)) = \frac{20-8\alpha}{\alpha\beta(1-2\alpha)^2}(f(x^0) - p^*) + \log_2(\log_2(1/\varepsilon))$$

   这个上界表明：

   • 阻尼牛顿阶段的迭代次数与初始函数值与最优值的差距成正比
   • 二次收敛阶段的迭代次数是双对数级别的，非常少
   • 总体而言，牛顿方法在自和谐函数上具有很好的收敛性

# 自和谐性

自和谐性（Self-Concordance）是凸优化中的一个重要概念，它为牛顿方法提供了完整的收敛性分析框架。

1. 自和谐函数的定义

   函数 $f: \mathbb{R}^n \to \mathbb{R}$ 是自和谐的，如果：

   • $f$ 是闭凸函数
   • $\text{dom}\ f$ 是开集
   • 对于所有 $x \in \text{dom}\ f$ 和所有 $v \in \mathbb{R}^n$，有：

     $$|D^3 f(x)[v, v, v]| \leq 2(v^T \nabla^2 f(x) v)^{3/2}$$

   其中 $D^3 f(x)[v, v, v]$ 是 $f$ 在 $x$ 处沿方向 $v$ 的三阶方向导数。

2. 自和谐函数的性质

   局部性质

   • 自和谐函数在其定义域内具有良好的局部性质
   • Hessian 矩阵的变化是"受控的"
   • 这使得可以在局部使用二次近似，并保证全局收敛性

   全局性质

   • 自和谐函数允许从任意初始点开始，使用牛顿方法全局收敛
   • 不需要强凸性或 Lipschitz 梯度连续性
   • 收敛性分析不依赖于问题的条件数

3. 常见的自和谐函数

   对数函数

   • $-\log(x)$ 在 $(0, \infty)$ 上是自和谐的
   • 这是自和谐函数的基本例子

   对数障碍函数

   • 对于线性不等式约束 $a_i^T x \leq b_i$，对数障碍函数：

     $$f(x) = -\sum_{i=1}^m \log(b_i - a_i^T x)$$

     是自和谐的

   熵函数

   • 负熵函数 $f(x) = \sum_{i=1}^n x_i \log x_i$ 在适当定义域上是自和谐的

4. 自和谐函数上的牛顿方法

   优势

   • 对于自和谐函数，牛顿方法具有完整的收敛性分析
   • 不需要强凸性假设
   • 不需要 Lipschitz 梯度连续性
   • 收敛性不依赖于条件数

   收敛性保证

   • 从任意初始点开始，算法保证收敛
   • 具有明确的迭代次数上界
   • 分为阻尼牛顿阶段和二次收敛阶段

5. 自和谐性与内点法

   自和谐性在内点法（Interior Point Methods）中发挥重要作用：

   • 内点法使用对数障碍函数，这些函数是自和谐的
   • 自和谐性保证了内点法的全局收敛性
   • 不需要问题的强凸性或 Lipschitz 梯度连续性

6. 自和谐性的意义

   理论意义

   • 提供了不依赖于条件数的收敛性分析框架
   • 统一了内点法和牛顿方法的理论
   • 为凸优化提供了更一般的收敛性理论

   实际意义

   • 解释了为什么内点法在实际应用中表现良好
   • 提供了算法参数选择的指导
   • 为算法设计提供了理论基础