凸优化
参考：数据炼金的机器学习数学基础，管老师
来，上概念
一些概念必须要清清楚楚：
- 仿射集：超平面
- 凸集
- 凸函数
- (凸函数的)上境图
- (一堆点的)凸组合：重心
- (集合的)凸包
- (函数的)凸闭包：包住函数的函数，呵呵
- 下确界：凸集的支撑平面
好，那，来吧：
仿射集 两点的连线的$\color{red}{直线}$还在集合内，这样的集合叫仿射集。 直线上的动点 $x=\theta x_1 + (1-\theta) x_2 x1,x2 \in C, \forall \theta \in R$ 典型的直线呀、平面、超平面（$AX=B$，X是n维向量，线性的） 所以大家老说，仿射函数就是线性函数的缘故
凸集
其实跟仿射很像，只不过，两点的直线，变成了$\color{red}{线段}$啦，
集合C中，任意两点的线段上的点，都在集合C中，那么这个集合叫凸集。
-
上面的两点，其实还有个多点的版本。 $x=\sum_{i=1}^{k}\theta x_i,$ 条件是：$\sum_{i=1}^{k} \theta_i = 1 , x1,…,x_k \in C$ 其实这个也是定义一个凸集出来。比如说，3个点，他们在这个约束下，会变成一个三角形，一个集合中任何3个点围成一个三角，然后这些三角不断地交集，最后搞成一个大凸集，就是这种感觉，这个数学定义真的是需要想象力的。
-
一些思考： 是仿射集一定是凸集, 凸集不一定是仿射集 这两段有点反直觉啊，你想啊，直线集合更大，线段是直线的子集，直线对仿射，线段对凸集，那么按理说，凸集应该是仿射的子集把。我靠！结论正好想法啊，难怪邹博都说错了。 不过，你再细想，其实凸集更自由，而仿射要求直线（也就是线性组合，其实约束更强了），其实，不用那么纠结，凸集就是个大锅，仿射就是个平面（高维就是个线性约束），你这么想就释然了。
-
凸集、凸集合：任意两点的连线的线段上的点还在凸集中 $\lambda x_1 + (1-\lambda) x2 \in \Omega$ $\forall x_1,x_2 \in \Omega, \lambda \in (0,1)$
凸函数： $f$是定义域$\Omega$是一个凸集，任意两点，他们的线段上的点都有如下性质： $f(\lambda x_1 + (1-\lambda) x2) <f(\lambda x_1) + f((1-\lambda) x2)$ $\forall x_1,x_2 \in \Omega, \lambda \in (0,1)$
不太严格地收，就是割线位于函数的上方。
直观上好理解凸函数，但是数学上有点拗口，直观上理解就是，中间的某个点的函数值，一定是在线段两端的点的函数值之间。
上境图：${ (x,y) : y\geq f(x), \forall x \in \Omega}$，对应由(x,y)组成的点的集合区域，就是上镜图。
说着吓人，说白了就是凸函数的上半部分（此处需要补个图）
凸集合和凸函数之间怎么联系起来呢？
一个函数是凸函数，当且仅当， f函数的上境图是凸集合。
凸组合 $w_i\geq 0, \sum w_i=1,$那么， $S = \sum_{i=1}^{n} w_i x_i$叫做一个凸组合，凸组合的含义是n个重点为$w_i$的点的整体重心。 重心一定在，由这些点组成的凸集合里面。<—-这个结论，Jensen不等式要用的吆 说白了，就是说，这样的一个组合就叫组凸组合。 凸组合是生成了一个重心点。
前面说这个凸组合的意义何在？老师说了一句话，点破，“调整几个点的凸组合的权值$w_i$，就可以覆盖住这几个点组成的凸形状里面的所有的点”，牛逼，这句话才是有用的，举个例子，
这个例子，里，这个三角形组成的点，每个点，都可以通过调整权值$w_i$获得。
集合的凸包 集合里面的点组成的所有的所有的凸组合，合成了那个集合，叫做凸包。 说白了，就是把$\color{red}{这些点全都包住的最小的凸集合}$。 讲人话，就是把一堆点变成了包围住他们的最小的凸集合。
函数的凸闭包，这个概念就是说，某个函数C’可以包住另外一个函数C，C’就是C的凸闭包函数。 有个推论，就是一个函数C的支撑函数，也一定是他的凸闭包函数的支撑平面。 $\color{red}{函数的凸闭包就是包住他的函数}$
g(x)是f(x)的凸闭包
有点晕，总结一下，就是，集合凸包包住所有点，函数凸闭包是用一个函数包住另外一个函数。
下确界 就是函数的极小值，就是与y轴（2维为例子）垂直的支撑平面，对应的y值，就是下确界。
一些性质，无关紧要，蛋疼地写在这里 还有些凸集合和凸函数的性质：
这个几个结论，大白话解释一下：
- 任意多个函数的逐点上确界仍是凸函数，就是说俩函数
，绿色那个曲线，是个凸函数。
- 凸函数的sublevel set都是凸集合 这是个啥意思？
如图，函数被一个值为$\alpha$的切面切出一个截面，投影到x,y坐标平面上，这个投影还是凸函数，就是说这个事，呵呵。
这些概念搞清楚了，引出有用的东西了：
Jensen不等式
Jensen不等式 函数的组合大于组合的函数。 $\sum_{i=1}^{n} w_i f(x_i) \geq f(\sum_{i=1}^{n} w_i x_i) $ 这玩意看着很玄幻，怎么推理出来的呢？ 我们知道上境图的定义是：${ (x,y) : y\geq f(x), \forall x \in \Omega}$，也就说，(x,y)这个点是在凸集里面的。 那么就可以吧jensen不等式理解成，（$\sum_{i=1}^{n} w_i x_i, \sum_{i=1}^{n} w_i f(x_i) $ ）这个点在上境图里，注意！，把这玩意看成是一个点了，他要是在凸集的上境图里的话，那他一定是满足这个jensen不等式了，对不对？对不对？ 那爱思考的你问了，为什么丫就在凸集里面呢？ 问的好，因为你可把（$\sum_{i=1}^{n} w_i x_i, \sum_{i=1}^{n} w_i f(x_i) $ ）看作是 （$\sum_{i=1}^{n} w_i (x_i, f(x_i)) $ ），这个就是条件里说的凸组合啊，凸组合的组成的这个点（重心），一定在这些点的凸包(凸包一定是凸集)里面，也就在上境图里，那么，就满足上境图的定义，就得出了结论了呀。
这里面，隐含着一个说明，这里面没说，就是$\sum w_i=1$，为何，因为这个是凸组合的定义里要求的，忘了？！回去看看。
Jenson不等式的几何含义，就是，
x是x1，x2的凸组合，那么x一定在函数的上境图里面，咳，其实就是说的这事，多直白啊，废话半天，就是这么一个直白的结论。
其实啊，Jensen不等式，EM算法采用呢，我们还会关心另外一个问题，就是臭名昭著，啊，不，是久负盛名的拉格朗日算子，专业解决凸优化问题，还有叫人想哭的KKT条件啥的，忍住你的眼泪，继续往下
凸优化
凸优化的一般形式：
最小化: $f_0(x)$ 条件：$f_i(x)\leq b_i , i=1,…,m$
$f_0, f_1, …, f_m$ 都得是凸函数，这样局部最优就是全局最优了。
有时候，非凸问题可以转化成凸问题，比如，先找到各个局部极小值点，然后把它们串成一个曲线，也就是用这些点去你和出一个函数，再求这个新函数的极小值点。
或者找到你这个问题的对偶问题，它恰恰是个凸问题，可求解。
任何一个优化问题，
最小化: $f_0(x)$ 条件：$f_i(x)\leq b_i , i=1,…,m$ 都可以转换成一个对偶形式，这个对偶都可以搞成凸函数，就可以求极值点了。
共轭函数
共轭函数干嘛用的？共轭函数，把原来的函数，变成了一个包含y的一个凸函数了，我理解是，就是把原来的非凸问题，转成了凸问题了。 这里的y是一个新引入的变量，可不是f(x)啊，别晕啊，就是引入个变量而已，跟f(x)也没啥关系，就是纯憋出来的一个变量。
最后这个共轭函数是自变量是y的函数而已。 但是，有意思的就是，他和原来的f(x)还有关系。
举个例子，y是有定义域和可行域的，比如y=1，那么这个时候，共轭函数$f^* $就变成了 $sup(yx-f(x))=>sup(x-f(x))$，就是上图里面左图，你要求啥来着？这个额函数$sup(x-f(x))$的上确界，也即是最大值，对吧？
怎么求啊，那肯定是x1这个点啊，你是找遍了x的定义域，终于在x1这个点发现，$x-f(x)$最大，就是那些文章里面说的切线啥的。客官，您可能说，x2（也就是红色距离）比x1（绿色）的大啊，是大，但是是负的！
别晕，我们得到了一个告诉我一个y，我给你一个值，你再给我一个y，我再给你一个值，这个就是个$R^n->R$的一个映射函数啊，变量就是y，这个就是对应于原来的那个函数的共轭函数。
讨论这样玩意干嘛呢？ 首先他有个牛逼性质：共轭函数是个凸函数，这个我就不再证明了，大概意思就是一堆凸函数的上确界还是凸函数，线性函数（yx-f(x)可看做是y的线性函数）是凸函数。 其次，这玩意，对偶里面会用，别急，后面会说到，你先记着。
网上的一些参考，都说的不明不白，很失望，姑且留着：
对偶问题
为什么引入对偶？本来如果是纯凸函数优化，就一个$f_0$，你用牛顿法啥的总是可以寻找到最小值点，局部最小值就是全局最小值。但是一旦你加入限定条件，你那些这法那法都不起作用了，您就无法梯度下降出溜下去了。怎么办？引入拉格朗日，把要求的$f_0$和那些限制条件揉在一起，重新变成一个凸函数，这个新的凸函数就可以寻找到最值点了吧。然后这个新函数和旧的$f_0$的极值又有关系，比如新函数的上确界就是旧函数的下确界啥的，这样从而让原问题求解完成。
优化问题 先提出优化问题，下面就是优化问题长这个样子：
先搞清楚可行域和定义域： 定义域：就是各个函数的自变量的定义域的交集 可行域：除了定义域之外，还包括每个等式、不等式对应的自变量的范围，举个例子吧： $f(x)=x^2<1$,这个时候，x的取值实际上是被限制到了 -1<x<1，这个就是可行域。
这个最优化问题怎么解呢？恩，当当当当当！拉格朗日隆重登场…. 拉格朗日对偶函数 拉格朗日大神，据说是为了解决力学问题，定义了这个朗格朗日算子$L(x,\lambda,\nu)$。不过，我们还定义了一个$g(\lambda,\nu)$，其中$g(\lambda,\nu)$是$L(x,\lambda,\nu)$的下确界。
$L(x,\lambda,\nu)=f_o(x)+\sum_{i=0}^{m} \lambda_i f_i(x) + \sum_{i=1}^{p} \nu_i h_i(x)$ $\lambda_i \geq 0$
$g(\lambda,\nu)=inf_{x \in D} L(x,\lambda,\nu) = $ $inf_{x \in D} ( f_o(x) + \sum_{i=0}^{m} \lambda_i f_i(x) + \sum_{i=1}^{p} \nu_i h_i(x))$ *$inf$是下确界 *$f_0, f_i$都是凸函数，$h_i$是仿射函数
得说搭说搭这个$g(\lambda,\nu)$，这个函数啥意思啊？你琢磨过么？我的理解就是，您x随便变，然后我对任意一对$\lambda, \nu$，都可以遍历所有的x，得到一个下确界，（其实也不是任意的$\lambda, \nu$啦，得是让下界存在的他们俩，他们俩要都在可行域里）
上面这段是我之前写的，自己都看不懂啥意思了，不舍得删，毕竟是自己的思考过程。我现在得再来说说g函数。我的理解是，他是一个关于$\lambda, \nu$的函数，啥意思，就是你取值某个$\lambda, \nu$，就会得到一个值，这叫函数呀。那这个值怎么来的呢？是拉格朗日函数的在x取值范围内的下确界，讲人话，就是你给定一个$\lambda_0, \nu_0$，我就去算整个拉格朗日L函数的下确界，就是最小值，这个值就是g的值；然后你再给定一个$\lambda_1, \nu_1$，我又去得到一个关于x作为自变量下拉格朗日L函数的最小值；。。。。；这样下来，就形成了一个$\lambda, \nu$到L最小值的映射关系，这个映射关系，就是g函数。
这个拉格朗日对偶函数有一个极其重要的性质，就是他可以为原问题提供一个下确界。
$\lambda \geq 0 $, 则 $g(\lambda, \nu) \leq p^* $ $p^* $ 是原问题的最优化（最小）值
听不懂啥意思吧，就说，$g(\lambda, \nu) $永远是小于等于，之前我们要求的$f_0$的极小值的。靠，说着真TMD绕，看看下面的证明，估计你就会豁然开朗。
你看，$g(\lambda, \nu) $<$L(x,\lambda,\nu)$(是L的下确界嘛) 在可行域里,$h_i=0$， $\lambda_i>0, f_i \leq0$,俩相乘肯定是小于等于0， 所以，$g(\lambda, \nu) $最大最大，也就是$f_0(x)$嘛， 所以，说$g(\lambda, \nu) \leq p* $不过分吧(p* 是f(x)的最小值)
这啥意思啊？在回过头来说一下，你发现$g(\lambda, \nu) $里面没有x了，也就是说，在你x在可行域里，我取遍所有的x，对某一个x来说，这个x一点固定，那么原来的拉格朗日函数就变成了$\lambda,\nu$的函数了，对这个函数取下界，下界是啥，下界就是一个值啊，一定在某对$\lambda,\nu$的取值的时刻，达到这个最下界。如果你还不理解，你可以想象 z=f（x,y）的一个函数，现在我固定一个x=3，那么你发现z就变成一个二维函数了了z=f（3,y），就是y=>z的一个映射了，那么我们的g函数现在就是求这个f（3,y）的下界，就是最小值。
对偶和共轭
如果优化问题的限制条件是线性条件的时候，可以用共轭函数来简化求解过程。 终于，共轭和对偶发生关系了，前面算是没白讲。
最小化：$f_0(x)$ 不等式条件：$Ax \leq b$ 等式条件：$Cx = d$
$g(\lambda,\nu)= inf_x f_0(x) + \lambda * (Ax-b) + \nu (Cx-d)$ $=-b\lambda - d\nu + inf_x(f_o(x)+ (A\lambda + C \nu) x)$ $= -b\lambda - d\nu - f_0^* (-A\lambda - C\nu)$ 这样，我们就可以把对偶转成共轭来计算了。
好，暂停一下，我们回顾下，我们得到一个新式子$g(\lambda, \nu) $，他永远比原问题的最小值（p* ）还小，那么我就让丫呢最大不就得了，这样我就最可能地逼近原问题的最小值呀。
这个新的对偶问题，变成了关于$\lambda, \nu$为变量的函数了，它也有自己的可行域、定义域，当然是关于$\lambda, \nu$的。
（我有个问题，即使是最大了，那也不一定是原问题的最小值呀？可能很接近吧，也可能连接近都不接近吧？？？） 佩服自己，我理解的对，不一定相等的，也就是小于等于的是弱对偶，而相等的叫强对偶。
所以，尽量要想办法，那咱就想办法，让其达变成强对偶呗。
Slater条件
对于一个凸优化问题：
最小化：$f_o(x)$ 不等式条件：$f_i(x)<0, i=1,..,m$ 等式条件：$h_i(x)=0, i=1,…,p$
如果存在一个可行域中的点x，使得$f_i(x)<0, i=1,..,m$，那么这个凸优化就满足强对偶性。
讲人话，就是，如果$f_0,f_i$都是凸函数，那么，大部分情况（就是存在一个$x_i$让$f(x_i)<0$）都是强对偶。
强对偶，就是：$ d^* = p^* $，也就是，拉格朗日函数$L(x,\lambda,\nu)$的下确界$ d^* $，和原函数$f_0$的最小值$ p^* $，是一样的。这样，我们就可以通过找对偶函数的最小值点，从而得到原问题的最小值点，然后反向解方程，解出最终的x是多少（我的理解，不知道对不对）
上面都是凸函数，那么如果不是凸函数怎么办？这就要引出KKT条件，
KKT条件
如果满足强对偶，$ d^* = p^* $， 条件是：
$f_i(x^* ) \leq 0$ $f_i(x^* ) \leq 0$ $h_i(x)=0 $ $ \lambda^* \leq 0$ 那么我们假设满足的时候，对应的最优解是$x^* , \lambda^* , \mu^* $，也就是满足这个式子： $d^* =g(\lambda^* , \mu^* )$，的时候，这仨分别对应的值。 $\leq f_o(x^* ) + \sum_{i=0}^{m} \lambda_i f_i(x^* ) + \sum_{i=1}^{p} \nu_i h_i(x^* )$ 最后一项，肯定是0，因为$h_i(x)=0$嘛。 $=f_o(x^* ) + \sum_{i=0}^{m} \lambda_i f_i(x^* )$ $\lambda^* \geq 0$ 和 $f_i(x^* ) \leq 0$，所以两者相乘肯定是小于0，所以： $\leq f_0(x^* )$ $=p^* $
所以，要让上面的$\leq$变成=，就得要求各个子项都是0， 也就是： $ \sum_{i=0}^{m} \lambda_i f_i(x^* ) = 0 $
还有一点， $g(\lambda^* ,\mu^* )=inf(L(x^* ,\lambda^* ,\mu^* ))$，这玩意叫下确界，也就是说，x随便取，取来取去，才得到了这个最小值，那么$L(x^* ,\lambda^* ,\mu^* )$对x求偏导，应该在$x^* $这个点上是驻点。 $\nabla_xL(x^* ,\lambda^* ,\mu^* )=0$,
合在一起：
得！终于可以一个非凸优化问题，变成了一个凸优化问题了，可解了。
总结
太JB乱了，我必须出去吹吹风，冷静一下：
先是一堆概念，才把凸优化问题说清楚，
说凸优化干嘛，无非是丫有唯一的极值呗，
凸优化有凸集合、凸函数，两者有关系，所有有上境图啥的，总之，这些概念要绕清楚。
然后引出了装孙（Jensen)不等式，EM那边会用到，
然后引出了共轭函数，我看后来也就是线性拉格朗日对偶问题的时候用了一下，剩下的时候也没用到，
然后才引出猪脚：
- 拉格朗日函数，就是$L(x,\lambda, \nu)$
- 拉格朗日对偶函数，就是$g(\lambda, \nu)$，他是个凹函数
对偶函数有个性质：他(丫是L拉格朗日函数的下确界)永远小于原函数($f_o$)的最小值 也就是$p^* \leq d^* $，这玩意叫弱对偶， 我们当然不想弱对偶了，我们想要强对偶呀$p^* \leq d^* $，
那么就引出俩事：
- 对于原问题是凸问题（就是原函数和约束函数都是凸函数),很容易就是强对偶，只要满足Slater条件（据说这个条件非常容易满足）
- 对于原问题不是凸问题的，这个就得满足KKT条件，就是那一大堆变态条件