前言

如果原目标函数是非凸的，那么一般我们很难去解决这个问题，因为一个函数如果是非凸的，那么它的局部最优解不一定是全局最优解，所以一般我们会把这个非凸的问题用拉格朗日对偶的方法转化为凸优化问题，也就是凸函数，只有凸函数，它的局部最优解才是全局最优解，那么我们只要通过求偏导来求出其中的局部最优解就可以求得对偶函数的最优解了。但是求得拉格朗日对偶函数的最优解之后要怎么样才能求得目标函数的最优解呢？这就要证明这个对偶是否是强对偶了，如果是强对偶那么对偶间隙就是0，这样对偶函数的最优值就等于原目标函数的最优值。那么为什么拉格朗日对偶问题一定是凸的呢？下面就来看下《Convex Optimization》这本书中所写的证明。

证明



以上证明出自《Convex Optimization》，虽然这里很好的证明了不论原问题是不是凸优化问题，它的对偶问题一定是凸优化问题，在实际的场景中用拉格朗日对偶来解决凸优化问题能很容易的证明强对偶性，从而可以通过拉格朗日对偶的方法来求得原问题得最优解，因为满足强对偶性的原问题和对偶问题之间的对偶间隙为0，所有可以很容易得到对偶问题的最优解就是原问题的最优解，但是如果原问题是非凸优化问题呢？非凸优化问题很难求出原问题与对偶问题之间的对偶间隙，并且也很难证明强对偶性，所以一般的非凸优化问题中只是满足了弱对偶性。

参考文献

[1] Stephen Boyd, et al. Convex Optimization. Cambridge university press, 2004. 

目录

1.写在前面

2.什么是KKT条件（3组，5个条件）

1.写在前面

        上一节，我们介绍了slater条件，假如说我们遇到一个凸优化问题+slater条件，那么一定满足强对偶关系。强对偶关系是说p*是原问题的解，d*是对偶函数的解，满足p*=d*。p*对应最优解是x*，d*对应最优解是λ*和η*。怎么求出来这三个最优解呢？KKT就给定了这三者之间的一个关系，可以求出这三个最优解。并且KKT条件和强对偶关系属于充要条件，可以互相推导。我们这一节就介绍什么是KKT条件。



2.什么是KKT条件（3组，5个条件）

        KKT条件可以分为3组，第一组是满足可行域或者可行条件；第二组是满足互补松弛条件；第三组是梯度为0。



        互补松弛条件是什么呢？我们思考d*是什么，是对偶问题的最优值，可以直接代入λ*和η*：



        上面那个式子我们可以得到互补松弛条件，如果d*=p*，只能取等号。下面蓝框中就是我们推出的互补松弛条件。





        我们看第三组梯度等于0，因为上面绿色公式推导中要取等号，我们可以单独拿出来讨论：当x=x*时候，取得最小值。



        所以如果L对x求偏导，在x=x*时候，一定会等于0，因为必须要有最小值。其实第二组互补松弛条件和第三组梯度为0条件都是从不等式取等号推导出来的。最后的KTT三组条件为（三组+五个条件）：



 

2.学习的对偶算法
（本篇建议在读完本章第1节硬间隔SVM学习的对偶算法相关知识之后阅读）
直接上公式，原始问题的对偶问题是：
公式看得很舒服，怎么来的呢？接下来然我们一起推导一遍：
由上一小节内容我们得到了软间隔最大化原始问题为：
对该原始问题，我们构造拉格朗日函数是：
其中， 
则原始问题可以写成极小极大问题： 
 (关于这方面的理解，前面已经讲得很清楚了)
它的对偶问题为极大极小问题： 
 ，
先求内部的极小：
由偏导
得
将上面3个等式带入到拉格朗日函数，得
再求外部的极大，即得到对偶问题：
将上述条件不等式进行变换，消去 
 ，从而只留下变量 
 ，并将约束写成：
进一步，我们将这个求极大问题，等价转化为求极小问题，就得到了：
接着通过求解对偶问题就可以得到原始问题的解了，进一步可以确定分离超平面和分类决策函数。我们写成定理：
设 
 是对偶问题的一个解，若存在 
 的一个分量 
 ，则原始问题的解 
 可按下式求得：
     (这两个等式不多说了，不理解的话可以看看前几篇关于
硬间隔的内容）
原始问题是凸二次规划问题，解满足KKT条件。具体证明过程就不给出了。
由上面的定理可知，分离超平面就可以写成：
分类决策函数可以写成：
  这就是
线性SVM的对偶形式。
对前面的结果，有下面的算法：
线性支持向量机学习算法
输入：训练数据集 
 ，其中， 
 ；
输出：分离超平面和分类决策函数。
（1）选择惩罚参数 
 ，构造并求解凸二次规划问题
求得最优解 
 。
（2）计算 
选择 
 的一个分量 
 适合条件 
 ，计算
（3）求得分离超平面： 
分类决策函数： 
以上就是线性支持向量机的学习算法。
最后再次说明，从理论上来说，原始问题对 
 的解
可能不唯一。

前了个言
关于凸函数性质的汇总，证明并没有给出。
定了个义
定义1 设 
  在区间 
  上有定义， 
  在 
 上称为
凸函数，iff 
 有 
把 
  改成 
 就是 
严格~了。对于凹函数，与凸函数概念在不等式符号上对偶，所以不加赘述。
定义2 
  是区间 
 上凸函数（f有定义省略，下同），iff 
  ，有 
还有类似的定义
定义3 
 是区间 
 上凸函数，iff 
 ，有 
此外，从几何上来描述
定义4 
 是区间 
 上凸函数，iff 曲线 
  的切线恒保持在曲线一下，则称 
  为凸函数。严格凸可类似推广。
以上就是常见定义~
在念叨念叨性质~
关于以上定义的性：
性质 1：定义2与定义3等价。
性质 2：在连续条件下，定义1，2，3相互等价。
从几何角度来看，有如下性质：假设 
 为凸函数
 ， 
  ， 
  围成的有向面积为 
总结上述结论，能够推出如下关于斜率上的推论。（以下考虑凸函数）。
推论1 
推论2 
  ，弦斜率 
 是增的。
推论3 由 
 ，可以有 
推论4 任意点的单侧导必然存在, 
  和 
 ,皆为增函数，且 
推论5 在任意内点上连续。
但是要注意，推论4，5对端点值不完全成立。
另一个等价定义
定义5 凸函数充要条件， 
  ， 
 ，使得 
 有 
通过上面的推论4就能够做到互推。
推论6 
  可导时，则凸的充要条件为 
推论7（分离性定理） 若为凸函数，则可在 
  作一条直线，位于 
  下方， 
所以，当导数存在时，可以给出这样的定义：
定义6  
  单增。
推论8 
至此，回顾定义2，3，它们便可以推广为如下形式:
  ， 
 ，有 
 不全为0， 
 ，有 
与一致连续的关系
现在给出几个命题（网上都可以查到相应证明，我先不给证明了~）
命题1 设函数 
  在区间 
 为凸函数，则 
  在 
  的任一闭子空间上有界。
这说明，给出函数凹凸性就能找到有界性。
命题2 设 
  为区间 
 内的凸函数，则 
 在 
  的任一内闭区间 
  满足Lipschitz条件。
也就是说，有凹凸性就有Lipschitz条件满足，也就是说，能够得到一致连续。于是乎，便可以有 Cauchy列映射到Cauchy列的子集了。其实，就是这篇文章说的东西满足了：数分随记 关于一致连续性
先写这些，等有什么新的再续。。。