Chapter 12 无约束优化 {Optimization without constraintss}

12.1 例子

之前我们讨论了许多优化问题：

问题	目标函数	约束
最小二乘法	\(E(\vec{x}) = \parallel A\vec{x} - \vec{b} \parallel^2\)	无
把\(\vec{b}\) 投影到 \(\vec{a}\) 上	\(E(c) = \parallel c\vec{a} - \vec{b} \parallel^2\)	无
实对称矩阵的特征向量	\(E(\vec{x}) = \vec{x}^TA\vec{x}\)	\(\parallel \vec{x} \parallel = 1\)
Pseudoinverse	\(E(\vec{x}) = \parallel \vec{x} \parallel^2\)	\(A^TA\vec{x} = A^T\vec{b}\)
主成分分析	\(E(C) = \parallel X - CC^TX \parallel_{Fro}\)	\(C^TC = I_{d \times d}\)
Broyden step	\(E(J_k) = \parallel J_k - J_{k-1} \parallel_{Fro}^2\)	\(J_k \cdot (\vec{x}_k - \vec{x}_{k-1}) = f(\vec{x}_k) - f(\vec{x}_{k-1})\)

有些是有约束的，有些没有，我们现在先考虑无约束的问题，set up 如下：

\[ min_{\vec{x}} f(\vec{x}) \]

• 例子一

可以有很多例子，比如数据拟合，类似最小二乘法，不过现在我们是想用一个指数来拟合：

\[ E(a, c) = \sum_i (y_i - c e^{ax_i})^2 \]

• 例子二

给一堆数据，怀疑正态分布，用正态分布来拟合：

\[ g(h; \mu, \sigma)={\frac {1}{\sigma {\sqrt {2\pi }}}}e^{-(h - \mu)^2/2 \sigma^2} \]

给一大堆独立数据 \({h_1, \cdots, h_n}\) ：

\[ P({h_1, \cdots, h_n}; \mu, \sigma) = \prod_i g(h_i, \mu, \sigma) \]

要求估算出 \(\mu, \sigma\) 来最大化概率分布， 感觉 贝叶斯/NLP 中间会有很多这种模型的应用。

• 例子三

给一堆数据，我们想找到它的几何中心（geometric median），注意这个不同于质心，比如下图：

蓝色的店是质心，黄色的点是几何中心，几何中心满足：

\[ E(\vec{x}) = \sum_i \parallel \vec{x} - \vec{x}_i \parallel_2 \]

注意这里只是 l2 norm, 并没有平方。

12.2 极值

全局最小值：

\[ \vec{x}^* \in \mathbb{R}^n \\ f: \mathbb{R}^n \to \mathbb{R} \\ \forall \vec{x} \in \mathbb{R}^n f(\vec{x})^* \le f(\vec{x}) \]

局部最小值：

\[ \vec{x}^* \in \mathbb{R}^n \\ f: \mathbb{R}^n \to \mathbb{R} \\ \forall \parallel \vec{x} - \vec{x}^* \parallel < \varepsilon, f(\vec{x})^* \le f(\vec{x}) \]

最大值的定义也是类似的，无约束优化其实就是一个求极值的问题。求极值这个问题我们在数学上还是比较熟悉的。同样，我们从一元函数开始。

12.3 一元函数

12.3.1 牛顿法

\(f: \mathbb{R} \to \mathbb{R}\)， 如果函数可微，那么极值的可能出现点就包括了 驻点、边界以及导数不存在的点，此处我们集中讨论驻点的情况。也就是导数 \(f'(x) = 0\) 的点 。 鉴于之前我们已经讨论过一元函数求根 \(f(x) = 0\)。 这里无非也就是变成了求解 \(f'(x) = 0\)， 那么依旧可以使用 牛顿法：

\[ {\displaystyle x_{k+1} = x_{k}-{\frac {f'(x_{k})}{f''(x_{k})}}.} \]

12.3.2 黄金分割搜索 Golden-section search

适用条件： 单峰函数 Unimodal function， 顾名思义 单峰 unimodular 就是指的有一个峰值。

单峰：

unimodular.png

双峰：

Bimodal.png

单峰定义： \(f: [a, b] \to \mathbb{R}\) 存在 \(x^* \in [a, b]\) 满足 f 在 \(x \in [a, x^*]\) 是递减， 在 \(x \in [x^*, b]\) 递增。

我们可以利用单峰的性质来用之前类似二分的思路求解。

unimodal_01.png

假设 \(a < x_0 < x_1 < b\), 假设我们有：

• \(f(x_0) \le f(x_1)\) , 那么对于 \(x \in [x_1, b]\), 都有 \(f(x) \ge f(x_0)\), 最小值点 \(x^* \in [a, x_1]\), 所以可以丢掉区间 \([x_1, b]\)
• \(f(x_0) \ge f(x_1)\) , 那么对于 \(x \in [a, x_0]\), 都有 \(f(x) \ge f(x_1)\), 最小值点 \(x^* \in [x_0, b]\), 所以可以丢掉区间 \([a, x_0]\)

但是这样每一轮需要计算 \(f(x_0)， f(x_1)\), 懒的本性想让我们重复利用之前的计算结果，所以我们这样来考虑，假设 a = 0, b = 1, 第一轮我们计算：

\[x_0 = \alpha, x_1 = 1 - \alpha, \alpha \in (0, \frac{1}{2})\]

• 假设是上面的 \(f(x_0) \le f(x_1)\) 的情况的话，区间变成：

\[[a, x_1] = [0, 1- \alpha]\]

第二轮我们的选择点是：

\[\alpha(1- \alpha), (1 - \alpha)^2\]

如果

\[x_0 = \alpha = (1 - \alpha)^2 \]

那么 我们就可以减少一次计算：

\[\alpha^2 - 3 \alpha + 1 = 0 \\ \alpha = \frac{1}{2}(3 - \sqrt{5}) \\ 1 - \alpha = \frac{1}{2}(\sqrt{5} - 1) \]

\(1 - \alpha = \tau\) 满足黄金分割比例。

• 假设是上面的 \(f(x_0) \ge f(x_1)\) 的状况， 区间变成：

\[ [x_0, 1] = [\alpha, 1] \]

第二轮选择点是：

\[\alpha + \alpha(1- \alpha), \alpha + (1 - \alpha)^2\]

如果：

\[x_0 = 1 - \alpha = \alpha + \alpha(1 - \alpha) \]

得到相同的方程式，相同的解，所以我们可以有 黄金分割搜索：

1. 初始化 a, b 使得 f 在 [a, b] 上是 unimodular
2. \(x_0 = a + (1-\tau)(b-a), x_1 = a + \tau(b-a), f_0 = f(x_0), f_1 = f(x_1)\)
3. 迭代直到 b - a 足够小：
   • \(f_0 \ge f_1\), 丢掉 \([a, x_0]\)
     • \(a \gets x_0\)
     • \(x_0 \gets x_1, f_0 \gets f_1\)
     • \(x_1 \gets a + \tau(b-a), f_1 \gets f(x_1)\)
   • \(f_1 > f_0\), 丢掉 \([x_1, b]\)
     • \(b \gets x_1\)
     • \(x_1 \gets x_0, f_1 \gets f_0\)
     • \(x_0 \gets a + (1-\tau)(b-a), f_0 \gets f(x_0)\)

12.4 多元函数

\(f: \mathbb{R}^n \to \mathbb{R}\), 针对多元函数，感觉最出名就是梯度下降了（类比下山）。

12.4.1 梯度下降法

梯度下降方法基于以下的观察：如果实值函数 \(F(\vec{x})\) 在点 \(\vec {a}\) 处可微且有定义，那么函数 \(F(\vec{x})\) 在 \(\vec{a}\) 点沿着梯度相反的方向 \(-\nabla F({\vec {a}})\) 下降最多。

因而，如果 \({\vec {b}}={\vec {a}}-\gamma \nabla F({\vec {a}})\) 对于 $ >0$ 为一个够小数值时成立，那么 \(F({\vec {a}})\geq F({\vec {b}})\)。

所以我们可以有梯度下降法的明确步骤：

• 随机预估的 \(x_0\)
• \(g_k(t) = f(\vec{x}_k - t \nabla f(\vec{x}_k))\)
• 搜索找到 \(t^* \ge 0\) 同时最小化 \(g_k\)
• \(\vec{x}_{k+1} = \vec{x}_k - t^* \nabla f(\vec{x}_k)\)

12.4.2 牛顿法

同样类似一元函数，我们可以推广牛顿法：

\[\vec{x}_{k+1} = \vec{x}_k - [H_f(\vec{x}_k)]^{-1} \nabla f(\vec{x}_k)\]

使用牛顿法的问题在于 \(\nabla f(\vec{x})\) 已经比较难计算了，而再加上 Hessian 矩阵，痛苦+n， 所以我们依旧寻求之前的 单变量 拟牛顿法 Quasi-Newton method 来前进。

12.4.3 BFGS

想不到 BFGS 的全称是 Broyden–Fletcher–Goldfarb–Shanno algorithm，此 Shanno 非彼 Shanno，是四位研究优化的数学家的名字，这个算法类似之前出现过的 Broyden’s method， 我们用矩阵来近似Hessian 矩阵 :

\[ \vec{x}_{k+1} = \vec{x}_k - \alpha_k B_{k}^{-1}\nabla f(\vec{x}_k) \\ B_k \approx H_f(\vec{x}_k) \]

\[ B_{k+1} ( \vec{x}_{k+1} - \vec{x}_k) = \nabla f(\vec{x}_{k+1}) - \nabla f(\vec{x}_{k}) \]

B 有一些很好的性质：

• 对称
• 半正定

所以我们需要做的优化就是：

\[ min_{B_{k+1}} \parallel B_{k+1} - B_k \parallel \\ s.t. B_{k+1}^T = B_{k+1} \\ B_{k+1} ( \vec{x}_{k+1} - \vec{x}_k) = \nabla f(\vec{x}_{k+1}) - \nabla f(\vec{x}_{k}) \]

而 $B_{k+1} - B_k $ 最小化 并不能保证 $B_{k+1}^{-1} - B_k^{-1} $ 很小，所以我们应当要求解的是：

\[ min_{H_{k+1}} \parallel H_{k+1} - H_k \parallel \\ s.t. H_{k+1}^T = H_{k+1} \\ \vec{x}_{k+1} - \vec{x}_k = H_{k+1} ( \nabla f(\vec{x}_{k+1}) - \nabla f(\vec{x}_{k}) ) \]

更多关于此算法参考：

Broyden–Fletcher–Goldfarb–Shanno algorithm