无约束优化：基本概念总结

凸优化是优化问题的重要分支之一，也是研究机器学习的重要工具之一。本文和其他几篇以“凸优化”为主题的博客都是我在学习Boyd所著《Convex Optimization》这本书时的笔记。因此，这些博客的内容结构和书中第5、9-11章节的框架相似，我在这里只不过罗列了书中的一些要点和个人的一点思考。

带有等式约束、不等式约束的凸优化问题可以通过一些技巧转化成无约束问题。因此，研究无约束凸优化问题是学习凸优化算法的基础。本文主要介绍无约束优化问题的基本概念，如下水平集、条件数等。了解和掌握这些概念对认识和分析无约束凸优化问题有重要的帮助。

我们研究下面形式的无约束优化问题 $$ \min f(x) $$ 其中 $f：\mathbb{R}^n\rightarrow \mathbb{R}$ 是二次可微凸函数。我们假定该问题存在最优解 $x^*$，对应最优值 $p^ *=\inf_x f(x)=f(x^ *)$。既然 $f$ 是可微凸函数，那么最优点应当满足最优性一阶微分条件，即 $$ abla f(x^ *)=0 $$ 这样，最小化 $f$ 就变成求解 $n$ 个变量 $x_1,\ldots,x_n$ 的 $n$ 个方程问题了。除了一些特殊情况，我们通常很难解析的求解上述一阶微分问题。实际中，我们一般采用迭代算法进行求解，也即是构造点列 $x^{(0)}$，$x^{(1)}$，$\ldots$ $\in extrm{dom} f$，使得 $k\rightarrow\infty$ 时 $f(x^{(k)})\rightarrow p^ *$。这样的点列称之为优化问题的极小化点列。实际计算时通常给定容许误差 $\epsilon$，当 $f(x^{(k)})-p^ *<\epsilon$ 时算法终止。

函数 $f$ 的 $\alpha$-下水平集（sublevel sets） $C_{\alpha}$ 定义成 $$ C_{\alpha}=\lbrace x\in extrm{dom}f | f(x)\leq \alpha \rbrace $$ 根据定义，$\alpha$-下水平集描述的是那些让 $f$ 取值小于等于 $\alpha$ 的 $x$ 所构成的集合，即定义域 $ extrm{dom}f$ 的一个子集。关于凸函数的$\alpha$-下水平集，我们有如下的结论：

【定理】 凸函数的 $\alpha$-下水平集仍然是凸集，反之则不成立。

【证明】 根据凸集的定义证明即可。假设 $f$ 是凸函数，考虑其 $\alpha$-下水平集 $C_{\alpha}$ 中的任意两点 $x_1$ 和 $x_2$，则 $$ f(x_1)\leq \alpha,\quad f(x_2)\leq \alpha $$ 结合函数的凸性不难得到 $$ \begin{split} f( heta x_1 + (1 - heta x_2)) &\leq heta f(x_1) + (1- heta)f(x_2) ewline &\leq heta \alpha + (1- heta)\alpha ewline &=\alpha \end{split} $$ 表明 $C_{\alpha}$ 确实是凸集。

反之不成立。我们考虑函数 $f=-e^{x}$，如下图所示

可见，对于任意的 $\alpha$，$f$ 的 $\alpha$-下水平集 $C_{\alpha}$ 都是凸集，但是 $f$ 显然是严格凹的。$\blacksquare$

我们后续介绍的求解无约束问题的方法需要一个适当的初始点 $x^{(0)}\in extrm{dom}f$，且其下水平集 $$ S=\lbrace x\in extrm{dom}f | f(x)\leq f(x_0) \rbrace $$ 必须是闭集。此外，在下面的内容中我们还将看到下水平集和优化问题之间的重要联系。

关于无约束优化问题，我们大多数情况都假设目标函数在 $S$ 上是强凸的，也即是存在 $m>0$，使得 $$ abla^2 f(x) \succeq m I \qquad (1) $$ 对任意的 $x\in S$ 都成立。

强凸性可以推出若干有意义的结果。例如，对 $x, y \in S$，我们有 $$ f(y)=f(x) + abla f(x)^T(y - x) + \frac12 (y - x)^T abla^2 f(z)(y - x) \qquad (2) $$ 其中 $z$ 属于线段 $[x, y]$。此时，根据强凸性式（1）的结果，式（2）的最后一项不会小于 $1/2\Vert y-x\Vert_2^2$，因此 $$ f(y) \geq f(x) + abla f(x)^T(y - x) + \frac m2 \Vert y - x\Vert_2^2 \qquad (3) $$ 对 $ S $ 中任意的 $x$ 和 $y$ 都成立。当 $m=0$ 时，式（3）就变回描述凸性的基本不等式；当 $m > 0$ 时，对 $f(y)$ 的下界我们可以比单独用凸性更好的结果。

现在，我们说明可以利用式（3）给出 $f(x) - p^* $，所得上界结果可表明 $x$ 是其目标值和最优目标值的偏差正比于 $\Vert abla f(x)\Vert_2 $ 的次优解。对于任意固定的 $x$，式（3）的不等式右侧是关于 $y$ 的二次函数，它在 $\bar{y}=x - (1/m) abla f(x)$ 处取得最小值，即 $$ \begin{split} f(y) &\geq f(x) + abla f(x)^T(y - x) + \frac m2 \Vert y - x\Vert_2^2 ewline &\leq f(x) + abla f(x)^T(\bar{y} - x) + \frac m2 \Vert \bar{y} - x\Vert_2^2 ewline &=f(x) - \frac{1}{2m}\Vert abla f(x)\Vert_2^2 \end{split} $$

既然该式对任意的 $y\in S$ 都成立，那么可以得到 $$ p^ * \geq f(x) - \frac{1}{2m} \Vert abla f(x)\Vert_2^2 \qquad (4) $$

由此可见，任何梯度足够小的点都是近似最优解。不等式（4）是最优性条件的推广。由于 $$ \Vert abla f(x)\Vert_2 \leq (2m\epsilon)^{1/2} \Rightarrow f(x) - p^* \leq \epsilon \qquad (5) $$

我们可以将其解释成次优性条件。

不等式（3）表明，$ S $ 所包含的所有下水平集都有界，因此，$ S $ 本身作为一个下水平集也有界。由于 $ abla^2 f(x) $ 的最大特征值是 $ x $ 在 $ S $ 上的连续函数，所以它在 $ S $ 上有界，即存在常数 $ M $ 使得 $$ abla^2 f(x) \preceq MI \qquad (6) $$ 对所有 $x\in S$ 都成立。这意味着，对所有的 $x, y\in S$， $$ f(y) \leq f(x) + abla f(x)^T (y - x) + \frac{M}{2}\Vert y - x\Vert_2^2 \qquad (7) $$ 类似的，对右边关于 $y$ 求极小，又可以得到 $$ p^* \leq f(x) - \frac{1}{2M}\Vert abla f(x)\Vert_2^2 \qquad (8) $$ 这是和式（4）相对应的不等式。

根据强凸性，我们得到了关于Hessian矩阵的不等式（1）和（6），即对任意的 $x\in S$ 都成立 $$ mI \preceq abla^2 f(x) \preceq MI $$ 因此，比值 $\kappa=M/m$ 是矩阵 $ abla^2 f(x)$ 的条件数（其最大特征值和最小特征值之比）的上界。下面我们基于 $f$ 的下水平集给出一个几何解释。

对于任意满足 $\Vert q\Vert_2=1$ 的方向向量 $q$，我们定义凸集 $C\subseteq R^n$ 的宽度如下 $$ W(C, q)=\sup_{z\in C} q^Tz - \inf_{z\in C} q^Tz $$ 再定义 $C$ 的最小宽度和最大宽度 $$ W_{\min}=\inf_{\Vert q\Vert_2=1} W(C, q),\quad W_{\max}=\sup_{\Vert q\Vert_2=1} W(C, q) $$ 于是，凸集 $C$ 的条件数可以表示成 $$ extrm{cond}(C)=\frac{W_{\max}^2}{W_{\min}^2} $$

即最大宽度和最小宽度的平方比值。该式表明，$C$ 的条件数给出了各向异性或离心率的一种测度。换句话说，如果 $C$ 的条件数小（接近1），表明集合在所有方向上的宽度近似相等，即几乎是一个球体。如果 $C$ 的条件数大，表明集合在某些方向上的宽度远比其他一些方向的宽度大。

下面，我们来研究 $f$ 的下水平集和最优性的关系。假定 $f$ 满足 $mI \preceq abla^2 f(x) \preceq MI$。令 $C_{\alpha}=\lbrace x| f(x)\leq \alpha\rbrace$，其中 $p^* <\alpha \leq f(x_0)$，以及下面两个集合 $$ \begin{split} B_{inner} &=\lbrace y | \Vert y - x^* \Vert_2 \leq (2(\alpha - p^* )/M)^{1/2}\rbrace ewline B_{outer} &=\lbrace y | \Vert y - x^* \Vert_2 \leq (2(\alpha - p^* )/m)^{1/2}\rbrace \end{split} $$

将 $x=x^* $ 带入到式（3）和式（7）中得到 $$ p^* + \frac{M}{2}\Vert y - x^* \Vert_2^2 \geq f(y) \geq p^* + \frac{m}{2}\Vert y - x^* \Vert_2^2 $$

这意味着 $B_{inner} \subseteq C_{\alpha} \subseteq B_{outer}$ 成立（可以根据集合包含关系的定义来证明）。根据 $B_{inner}$ 和 $B_{outer}$ 的定义，两者分别表示半径为 $2(\alpha - p^* )/M$ 和 $2(\alpha-p^* )/m$ 的球体。那么， $B_{inner}$ 和 $B_{outer}$ 的半径平方之比就给出了下水平集 $C_{\alpha}$ 的条件数的一个上界： $$ extrm{cond}(C_{\alpha}) \leq \frac{M}{m} $$ 我们也可以对最优解处Hessian矩阵的条件数 $\kappa( abla^2 f(x^* ))$ 给出一种几何解释。将 $f$ 在 $x^* $ 处进行Taylor展开 $$ f(y)=p^* + \frac12 (y-x^* )^T abla^2 f(x^* )(y - x^* ) $$ 可以看出，对于充分靠近 $p^* $ 的 $\alpha$ 有 $$ C_{\alpha} \approx \lbrace y |(y-x^* )^T abla^2 f(x^* )(y - x^* )\leq 2(\alpha - p^* )\rbrace $$ 即中心为 $x^* $ 的椭球可以很好的逼近下水平集。因此 $$ \lim_{\alpha\rightarrow p^* } extrm{cond}(C_{\alpha})=\kappa ( abla^2 f(x^* )) $$

我们将发现，对于一些常用的无约束优化算法，$f$ 的下水平集的条件数是影响其计算效率的重要因素 。

本文主要介绍了无约束凸优化问题的一些重要概念。我们着重讨论了强凸性在优化问题中的含义，重点揭示了 $f$ 的下水平集和最优解之间的联系。这些概念将在具体的无约束优化算法的讨论中体现其含义和价值。