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

拉格朗日乘子法

在数学分析中，如果我们需要计算多元函数的极值，我们可以通过让多元函数的偏导数等于零来计算方向上的拐点。如果需要计算局部最大值就需要使用到拉格朗日乘子法，思路是组合条件与原函数成为拉格朗日函数，计算拉格朗日函数的导数值为0的点。

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

凸优化在做什么

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

首先我们需要区分一下凸的意思，我们在一元函数中学过如果一个函数的二级导数不为零，当它大于零是函数叫做凸函数（或者我们叫他下凸函数），当它小于0是我们叫他凹函数（或者叫上凸函数）。如果一个集合拥有这种性质我们就叫做凸集（连通集）

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

任意两点间的连线可能会在图形外部。所有的凹函数只需加个符号就可以变成凸优化问题，如果是非凸优化问题呢？如何转化？经典的做法是保凸运算。

非负加权

我们很容易知道函数为双线性函数，我们可以提出内部的参数得到：

$$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)]$$

维度变换

我们可以定义一个新的函数，让他作为函数本身的自变量，然后让自变量变成一个线性平面。

$$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-f(x))$$

我们知道$\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)≥1$$

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

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

留个作业

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

结语

参考文档：

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

通过阅读本文，读者可以学会如何使用凸优化计算SVM中的对偶问题，了解运筹学领域的冰山一角，在分类问题的领域中能够更加的如鱼得水，能够更好的接受更多的关于机器学习的知识。