优化方法：凸优化与拉格朗日乘子法

拉格朗日乘子法

在数学分析中，如果需要计算多元函数的极值，可以通过让偏导数等于零来求驻点。如果带约束条件，就要用到拉格朗日乘子法，思路是把约束条件和原函数组合成拉格朗日函数，再计算拉格朗日函数的导数为0的点。

此法在数学分析中讲解得十分详细，乘子仅作为沟通不同偏导数的桥梁，使用线性代数的知识也可以十分轻松的计算出对应的结果。

凸优化在做什么

国内外对凸函数的定义是相反的，这里为了方便做论文的同学使用了国外的定义。

首先我们需要区分一下凸的意思。一元函数里我们学过，如果二阶导数大于零，函数叫凸函数（也叫下凸函数），小于零时叫凹函数（也叫上凸函数）。如果集合中任意两点的连线都落在集合内部，就把它叫做凸集。

我们看到凸集内各点都是连通的，不存在两点间连线有部分在图形外，非凸集则不同：

任意两点间的连线可能会在图形外部。凹函数问题只需加个负号就可以转化成凸优化问题，那非凸问题呢？很难直接转化，不过下面几种运算可以保持凸性，方便我们判断和构造凸函数。

非负加权

凸函数的定义就是下面这个不等式，对任意的x、y和0≤θ≤1都成立：

$$f(\theta x + (1-\theta)y)≤\theta f(x)+(1-\theta)f(y)$$

对多个凸函数做非负加权求和，凸性依然保持。

$$\sum w f(\theta x + (1-\theta)y)≤\sum w[\theta f(x)+(1-\theta)f(y)]$$

维度变换

我们可以对自变量做一次仿射变换，也就是把自变量换成Ax+b，再定义一个新函数。

$$x ← Ax+b$$

定义：

$$g(\theta x + (1-\theta)y)=f(A(\theta x+(1-\theta)y)+b)$$

展开我们有

$$f(\theta A x + b + (1-\theta) Ay) = f(\theta Ax + \theta b + (1-\theta)(Ay+b) )$$

我们将内部的系数提取出来就能得到不等关系：

$$f(\theta Ax + \theta b + (1-\theta)(Ay+b) )≤\theta f(Ax+b)+(1-\theta)f(Ay+b)$$ $$\theta g(x)+(1-\theta)g(y)$$

最大值

如果同时存在多个凸函数，取它们的逐点最大值，得到的还是凸函数，也就是：

$$MAXf(x)=max\{f_1(x),f_2(x)\}$$

用凸函数定义放缩一下就能证明这一点。

对偶问题

掌握了一些保凸运算我们就可以学一下对偶问题，在机器学习内有一种分类算法叫做支持向量机(SVM)，这种算法的要点就是核函数的计算和对偶问题，为了能让我们的超平面能划分的更居中一些，我们首先定义一下超平面和我们需要的关系：

$$f(x)=w^Tx+b$$ $$L(w,b,a)=\frac{1}{2}||w||^2+\sum a_i(1-y_if(x_i))$$

我们知道$\frac{1}{2}||w||^2$和分类间隔有关，最小化它等价于让超平面到两类最近点的距离尽量大，剩余的部分是我们需要满足的约束条件，对于这个函数我们很容易证明这是一个凸函数，所以我们需要求出他的最优解，即对这个拉格朗日函数进行拉格朗日对偶优化，我们分别对L求出关于w和b的偏导数：

$$w=\sum a_iy_ix_i$$ $$\sum a_iy_i = 0$$

代入我们的拉格朗日函数中得到：

$$max\{\sum a_i - \frac{1}{2}\sum_i^m \sum_j^m a_i a_j y_iy_jx_i^Tx_j\}$$

加入限制条件后，我们得到最后的结果：

$$f(x)=\sum_i^ma_iy_ix_i^Tx+b$$

对偶问题的约束需要用KKT条件来刻画，这个名字没有文字含义，就是三个人名的缩写。

$$a_i≥0$$ $$y_if(\vec x_i)≥1$$ $$a_i(y_if(\vec x_i)-1)=0$$

在某些教材上会把对偶问题简化为：

$$max\{ min f(x)\}≤min\{ max f(x)\}$$

留个作业

我们知道多元函数可以使用矩阵的形式进行便捷表达，这种做法的优化问题我们应该怎么做呢？这种优化方法其实已经说了，大家可以简单了解一下~

结语

参考文档：

运筹学学习笔记: https://zhuanlan.zhihu.com/p/87485105

凸优化和SVM对偶就讲到这里，运筹学里还有更多内容，感兴趣可以顺着参考文档继续看，后面遇到分类问题再回来翻翻就好。