我对优化的认识

Introduction

这学期去蹭了一门课《最优化理论与工程应用》，授课老师是吕江滨老师和付立群老师。个人认为授课质量不错，是xmu值得听的研究生课。课程采用的教材是Stephen Boyd的Convex Optimization。听吕老师上课说他在NUS读博时，优化课的老师曾在standford听过Boyd亲自授课，Bolyd常强调几何直观结合数学推导。这样看来，我也算是Boyd的再传弟子了😁。

本文主要是想谈一下学完这门课，我对最优化的认识，趁着我脑海里优化的知识还没忘光，趁热打铁整理下有关优化的landscape。ps:本文的内容和用图均来参考自Stephen Boyd的Convex Optimization

Convex optimization problem

记得最早接触到优化时，是在大一的暑假，当时报名参加了学校的数学建模培训，有类题目便是属于运筹与优化。印象最深刻也是头一次遇到的是线性规划类——投资组合优化问题，大概是你手里有一定的本钱，市场上提供了多种资产供投资，在不超过本钱的情况下，尽可能使得你的收益达到最大。

负责这类题目的董老师经常向我们提到，对于线性规划问题，一般来说我们可以找到最优解，但是对于非线性规划问题，我们只能通过遗传算法、模拟退化算法等启发式算法找到一个局部最优解。因此，当时我面对优化问题时，一般是先判断是否是线性，如果是线性就皆大欢喜，遇到非线性便只会去套一些启发式算法。😓

但是研究生学完《最优化理论与工程应用》这门课，刷新了我对优化的认知。Bolyd的书中introduction部分写着这样一句话：

In fact the great watershed in optimization isn’t between linearity and nonlinearity, but convexity and nonconvexity.

原来优化问题能否被成功解决，在于问题的凸性convexity和非凸性nonconvexity。那么什么是convex- optimization凸优化问题呢？ $$ \begin{array}{lll}\text{minimize}&f_0(x)\\ \text{subject to}&f_i(x)\leq0,\quad i=1,\ldots,m\\ &h_i(x)=0,\quad i=1,\ldots,p\end{array} \tag{1} $$ 上面这个式子是优化问题的形式化表示，向量$x=(x_1,…,x_n)$为优化变量，$f_0(x)$是目标函数，例如收益函数。$f_i(x)$是约束函数，例如每种资产限额、投资花销等。当目标函数和不等式约束函数$f_0, …, f_m$均为凸函数，等式约束函数$h_i(x)=a_i^Tx-b_i$为Affine仿射函数时，该优化问题为convex凸优化问题。

我们称函数$f_i$为凸函数，对于任意$x, y\in\mathbf{R}^n$，$0\leq\theta\leq1$ ，函数满足 $$ f_i(\theta x+(1-\theta)y)\leq\theta f_i(x)+(1-\theta) f_i(y) \tag{2} $$ 当上式取等号，仅要求$\theta \in\mathbf{R}$时，转变为线性规划问题，也就是说凸优化问题是线性规划问题更general的版本。若优化问题不是线性的，则称之为非线性规划。

由于凸优化问题有一套成熟的理论，当我们能够判断这个问题是convex时，就能找到最优解。但是还有许许多多非线性非凸的问题，凸优化理论也能派上用场。例如，在非凸问题中，初始点的选取对于最终解的质量有很大的影响，我们首先可以将原问题近似为凸优化问题，找到一个比较好的解，再将其作为算法的初始解，用于求解原非凸问题，从而保证我们会有一个比较满意的可行解。

Figure 3.1 Graph of a convex function. The chord (i.e., line segment) between any two points on the graph lies above the graph.

这样看来，凸优化是我们求解最优化问题的基石。让我们围绕对凸函数的讨论，了解下整个凸优化问题的求解过程。在上面对凸函数的定义中其实是不严谨的，仅仅是对值域做了约束，凸函数还要求定义域是凸集convex set，否则式子2左侧没有意义，从几何上来讲，取集合中两点，如果两点连成的线段仍在集合中，那么该集合为convex set。i.e. if for any $x_1, x_2\in C$ and any $\theta$ with $0\leq\theta\leq1$, we have $$ \theta x_1+(1-\theta)x_2\in C. \tag{3} $$

Figure 2.2 Some simple convex and nonconvex sets. Left. The hexagon, which includes its boundary (shown darker), is convex. Middle. The kidney shaped set is not convex, since the line segment between the two points in the set shown as dots is not contained in the set.

凸函数最重要的性质莫过于局部最优$\iff$全局最优，这是由其一阶条件First-order conditions得到的。假设函数$f$可微，$f$是凸函数的充要条件为$\operatorname{dom}f$为凸集且对任意$x, y\in\operatorname{dom}f$，下式成立 $$ f(y)\geq f(x)+\nabla f(x)^T(y-x) \tag{4} $$ 右侧是函数$f$在$x$处的$\text{Talyor}$展开，上式表明，我们只需要知道某点的函数值以及该点的梯度（局部信息），便能推出函数的下界（全局信息）。特别地，当$\nabla f(x)=0$时，那么对于所有的$y\in\operatorname{dom}f$，有$f(y)\geq f(x)$，即$x$为函数$f$的全局极小点。

Figure 3.2 If f is convex and differentiable, then $f(x)+\nabla f(x)^T(y-x)\leq f(y)$ for all $x, y\in\operatorname{dom}f.$

实际上凸函数是一票难求的，我们有一些preserve convexity保凸的运算，例如非负加权求和、affine等。除了根据First-order,second-order判断凸函数外，还可通过restricting to a line。

限于篇幅，我们不得不结束对凸集和凸函数的讨论，不要忘了，我们的目的是求解式子1中的优化问题，那对于凸优化问题，是否存在最优点的判断呢？

下面给出目标函数$f_0$可微下的最优点判别准则：

$\text{ A feasible point} \ x\ \text{is optimal if and only if}$ $$ \nabla f_0(\boldsymbol{x})^T(\boldsymbol{y}-\boldsymbol{x})\geq0\quad\text{ for all feasible }\boldsymbol{y} \tag{5} $$

Figure 4.2 Geometric interpretation of the optimality condition (4.21). The feasible set $X$ is shown shaded. Some level curves of $f_0$ are shown as dashed lines. The point $x$ is optimal: $-\nabla f(x)$ defines a supporting hyperplane(shown as asolid line) to $X$ at $x$

上式从几何角度是很好理解的，我们找到可行解中的最优点，做一条切线（supporting hyperplane），撑起整个可行解feasible set，会发现在可行域中任意取一点和最优点构成的向量，和切线的法线作内积$\leq0.$

当式1中的凸优化问题属于无约束问题($i.e., m=0,p=0$)时，式1的最优点判别条件简化为: $$ \nabla f_0(\boldsymbol{x})=0 \tag{6} $$

Duality

$\text{Reformulating a problem in convex form is an art, there is no systematic way}.$

因此，有时当我们无能为力，可以尝试求解原始问题的对偶。在这里，介绍一种可以将原问题改写为convex形式的方法，这就是大名鼎鼎的Lagrange duality。其实除了拉格朗日对偶还有其他的对偶方法(i.e.Fenchel duality)

Duality的最绝妙之处在于：无论原始问题是否为凸，我们都可以构造原问题的对偶形式为convex。注意，对偶并不意味着我们等价解决了原问题，但这能为我们对原问题进行分析带来很大的帮助。

Lagrange dulity的基本思想是将约束函数加权求和与目标函数相加构造新的objective function。我们定义Lagrange dual funcrtion $g:\mathbf{R}^m\times\mathbf{R}^p\to\mathbf{R}$为Largrange函数关于$x$取得最小值：即对$\lambda\in\mathbf{R}^{m},{\nu}\in\mathbf{R}^{p}$，有 $$ g(\lambda,\nu)=\inf_{x\in\mathcal{D}}L(x,\lambda,\nu)=\inf_{x\in\mathcal{D}}\left(f_0(x)+\sum_{i=1}^m\lambda_if_i(x)+\sum_{i=1}^p\nu_ih_i(x)\right). \tag{7} $$ Since the dual function is the pointwise infimum of a family of affine functions of $\lambda,\nu$, it is concave, even when the problem (5.1) is not convex.

我们假设式子1原问题的最优值为$p^*=f_0(x^\star)$。容易证明，对于任意$\lambda \succeq0 $和$\nu$，下式成立:

$$ g(\lambda,\nu)\leq p^{\star}.\tag{8} $$

也就是说对偶函数构成了最优值的下界。我们想通过最大化$g(\lambda,\nu)$，从而找到$p^\star$最佳的下界，这就构成了dual problem。Largrange dual problem形式化如下： $$ \begin{array}{ll}\text{maximize}&g(\lambda,\nu)\\ \text{subject to}&\lambda\succeq0.\end{array} \tag{9} $$ 注意到，这是一个凸优化问题，因为目标函数是concave并且约束为linear。我们通过式子9得到的最优值记为$d^\star$，根据式子8，我们有 $$ d^{\star}\leq p^{\star}. \tag{10} $$ 上式对于原问题convex仍然成立，称为week duality弱对偶性。$p^{\star} - d^{\star}$被称为duality gap最优对偶间隙。当式子10取等号时，strong duality强对偶性成立。我们肯定很希望这样理想的情况，但事实上即使原问题是convex，strong duality usually(but not always)成立。当原问题convex且满足Slater’s condition时，强对偶性才成立。

谈到强对偶性，就不得不提一下KKT条件了。 $$ \begin{aligned} f_{i}(x^{\star})& \leq\quad0,\quad i=1,\ldots,m \\ h_i(x^{\star})& =\quad0,\quad i=1,\ldots,p \\ \lambda_{i}^{\star}& \geq\quad0,\quad i=1,\ldots,m \\ \lambda_{i}^{\star}f_{i}(x^{\star})&=\quad0,\quad i=1,\ldots,m \\ \nabla f_0(x^\star)+\sum_{i=1}^m\lambda_i^\star \nabla f_i(x^\star)+\sum_{i=1}^p\nu_i^\star\nabla h_i(x^\star)& =\quad0\\ \end{aligned}\tag{11} $$

上式中，$x^\star$和$\lambda^\star,\nu^\star$分别为原问题和对偶问题的最优点。对于目标函数和约束函数可微的任意优化问题，若强对偶性成立，那么任一对原问题最优解和对偶问题最优解都必须满足KKT条件（11）。在某些特殊情况下，我们通过解析求解KKT条件，从而完成对整个优化问题的求解。

Descent methods

但一般情况下，我们只能采用迭代算法对优化问题（式子1）进行求解，即计算点序列$x^{(0)}, x^{(1)},\ldots\in\operatorname{dom}f$使得$k\to\infty $时$f_0(x^{(k)})\to p^{\star}$。所有迭代算法的设计在于点序列的不同，也就是说，从当前点怎样迈向下一点。对于Descent method而言，下式成立: $$ x^{(k+1)}=x^{(k)}+t^{(k)}\Delta x^{(k)}\quad\text{with }f(x^{(k+1)})<f(x^{(k)})\tag{12} $$ 上式中$\Delta x$表示搜索方向，往哪个方向走。$t$表示步长，一次走多少。

在Descent Method中，最著名的便是梯度下降法，这个时候我们沿梯度的反方向进行搜索。

而在Deep learning中经典SGD，则是随机采样一些样本用来求梯度，$t$为学习率。

下面，我们讨论Steepest descent Method，可以看到Gradient descent为它的一个特例。对$f(x+v)$在$x$处进行一阶Talyor展开为: $$ f(x+v)\approx\widehat{f}(x+v)=f(x)+\nabla f(x)^Tv.\tag{13} $$ 其中 $\nabla f(x)^Tv$ 是$f$在$x$处沿$v$方向的方向导数，它近似给出了 $f$ 沿$v$方向会发生的变化。如果方向导数是负数，$v$就是下降方向。

现在我们讨论如何选取 $v$ 使得方向导数尽可能的小，令$\left|\left|\cdot\right|\right|$为$\mathrm{R}^n$上的任意范数，我们定义normalized steepest descent direction为 $$ \Delta x_{\mathrm{nsd}}=\mathrm{argmin}({{\nabla f(x)^Tv\mid||v||\leq1}}).\tag{14} $$ 我们也可考虑对normalized steepest descent direction乘以一个放缩因子，从而得到unnormalized steepest descent direction $\Delta x_{\mathrm{sd}}$

$$ \Delta x_{\mathrm{sd}}= \Delta x_{\mathrm{nsd}} ||f(x)||_{\star} \tag{15} $$

Steepest descent Method将steepest descent direction（方向导数最小）作为搜索方向，算法流程如下：

当我们取$\left|\cdot\right|$为Euclid范数时，$\Delta x_{\mathrm{sd}}=-\nabla f(x)$，因此，采用Euclid范数的Steepest descent method即为gradient method。而Newton Method则是在搜索方向的选取上还利用到了Hessian matrix（二阶导数信息）。

Figure 9.12 Steepest descent method, with quadratic norm

上图显示了取$\left|\cdot\right|$为quadratic norm的搜索情况，可以想象当取Euclid时，椭圆将变成圆，搜索方向将发生变化。

对于优化的梳理就到此吧，这门课只有36课时进行理论讲解，覆盖到的章节主要也就是我提到这些，当然还有些收敛性分析、保凸运算、quasiconvex没有提，只是把我认为比较重要的拎下。其实12周的理论课上完有些意犹未尽，后来等同学汇报完，我还傻乎乎地问是否有讲解新内容，没想到16周课便结束了。

学完这门课，有两个感想，一是做深度学习的人其实不太关心问题假设和分析，上一个算法跑只要有效即可。二是大模型参数动不动就是上亿，对数学家来说很难做分析，传统的理论在极为复杂的函数面前似乎都失效了，大家似乎都处于同一起跑线。

References

1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization. Cambridge, U.K.: Cambridge University Press, 2004.
2. Stephen Boyd / Lieven Vandenberghe. 凸优化[M]. 1. 清华大学出版社, 2013-1.

comments powered by Disqus