掌握机器学习数学基础之凸优化理论（二）

这篇文章继续介绍关于凸优化的知识，目录如下：

仿射集,凸集和凸锥

超平面，半空间及凸集分离定理

不改变凸性的运算

凸函数及凸优化简述

无约束的优化，等式约束优化，不等式约束优化

线性规划中对偶理论

拉格朗日对偶理论

读完估计需要10min，这里主要讲解第二部分～

凸函数及凸优化简述

凸函数：就是一个定义域在某个向量空间的凸子集C上的实值函数。

凸优化问题：”凸优化“ 是指一种比较特殊的优化，是指求取最小值的目标函数为凸函数的一类优化问题。其中，目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。而目标函数和不等式约束函数均为凸函数，等式约束函数为仿射函数，并且定义域为凸集的优化问题为约束优化问题

在优化问题中，凸优化问题由于具有优良的性质（局部最优解即是全局解），受到广泛研究。对于一个含约束的优化问题：

将上面的约束条件的形式更加明确一点，一个凸优化问题可以写成：

以上便是凸优化问题的一般形式。常见的线性规划、二次规划、二次约束二次规划等优化问题都是凸优化问题。

无约束的优化，等式约束优化，不等式约束优化

说了凸优化问题之后，我们再从无约束的优化，等式约束优化和不等式约束优化全面了解优化的类型的求解：

图中的等高线表示的值。此时在局部极小值点处的梯度必然为0，比较容易理解。这个梯度为零的条件是局部极小值点的必要条件。这样，优化问题的求解变成了对该必要条件解方程组。这个是很简单的一种优化，直接。

带等式约束的优化问题：

s.t. 表示条件

与无约束的问题不同。我们所要求的极小值点被限制在曲线上，我们将

称为可行域, 解只能在这个可行域里取。如下图所示，曲线（黑色实曲线）经过无约束极小值点（黑点）附近。那么满足约束的极小值点应该与黑点尽可能近。我们将f(x)的等高线不断放大，直到与曲线相切，切点即为所求。相切是关键，也是极小值点的条件。

因此带等式约束的优化问题转化为了无约束的优化问题，只需要对拉格朗日条件解方程组即可。这里λ就是拉格朗日乘子，有多少个等式约束就有多少个拉格朗日乘子。

带不等式约束的优化问题：

当只有一个不等式时, 如我们把问题2里的等式约束改为，如下图所示，可行域变成了阴影部分，最小值点还是切点，情况和问题2完全一样，只需要把不等号当做等号去求解即可。

当两个不等式起作用时，那么问题就来了

如下图，当 f(x)的等高线慢慢扩大时，等高线与可行域(阴影部分)第一次相遇的点是个顶点，2个不等式同时起作用了。满足约束的最小值点从原来的黑点位置(切点)移动到了红点位置，现在跟哪条约束函数曲线都不相切。那怎么才能找到这个黑点并求解？这时候就需要用到kkt条件了。这里的“条件”是指：某一个点它如果是最小值点的话，就必须满足这个条件（在含不等式约束的优化问题里）。这是个必要条件，前面说的也全部是必要条件。

其中，μ叫KKT乘子，有多少个不等式约束就有多少个KKT乘子。加上问题3中的约束部分，就是完整版的KKT条件。（注意：对于有等式的情况，你把其中一个不等式约束换成等式，可行域变成了半条曲线，最小值点还是那个红点，和下面这种情况是一样的。）

说完KKT条件是什么，然后说说KKT条件是怎么来的？：

注意：以上所有都是局部极小值点的必要条件。据此求得的解不一定是局部极小值点（更别提全局了），原因是上图中我所画的等高线也许根本就不闭合，也就是说我们一直想要靠近的等高线中间的黑点压根就是个鞍点或者近似鞍点。所以，很多时候，我们都是求其对偶问题来使得上面的条件变成充要条件，而一般问题也变成凸优化问题，具体下面讲解。

以上讲解主要参考《An Introduction to optimization》和知乎彭一洋关于优化的解答，在此表示感谢！

AI遇见机器学习

mltoai