我对优化的认识

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.

$$ \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(\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.

$$ \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.

$$ 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$可微下的最优点判别准则：

$$ \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.$

$$ \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。注意，对偶并不意味着我们等价解决了原问题，但这能为我们对原问题进行分析带来很大的帮助。

$$ 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} $$$$ \begin{array}{ll}\text{maximize}&g(\lambda,\nu)\\\ \text{subject to}&\lambda\succeq0.\end{array} \tag{9} $$$$ 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时，强对偶性才成立。

$$ \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

$$ x^{(k+1)}=x^{(k)}+t^{(k)}\Delta x^{(k)}\quad\text{with }f(x^{(k+1)}) 上式中$\Delta x$表示搜索方向，往哪个方向走。$t$表示步长，一次走多少。

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

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

$$ 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$就是下降方向。

$$ \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