散度、旋度、梯度释义+图解版 - 网盘合集 - 盘搜搜文件名:2017中级经济师-经济基础-精讲班-51、第二十四章描述统计-第二节离散程度的测度及第三节分布形态的测度（一）.doc 中级经济师 , 文件大小:1MB , 分享者:赵t**g俊 , 分享时间: , 下载次数:63次文件名:2017中级经济师-经济基础-精讲班-51、第二十四章描述统计-第二节离散程度的测度及第三节分布形态的测度（一）.mp4 中级经济师 , 文件大小:136MB , 分享者:赵t**g俊 , 分享时间: , 下载次数:58次文件名:新编常用公文写作范本全书
文书释义、格式模板、文书范本、写作技巧、场景案例、应用提示
精装版_PDF电子书下载 高清 带索引书签目录_sample_辛辉，荣丽双编著_P320_2016.01.pdf , 文件大小:5.9MB , 分享者:qq2*****2482 , 分享时间: , 下载次数:80次
文件名:最新激光散射粒度分析仪免费下载.exe , 文件大小:358.54KB , 分享者:sha****2145 , 分享时间: , 下载次数:20次文件名:新编常用公文写作范本全书
文书释义、格式模板、文书范本、写作技巧、场景案例、应用提示
精装版_PDF电子书下载 高清 带索引书签目录_sample_辛辉，荣丽双编著_P320_2016.01.pd , 文件大小:5.90 MB , 分享者:qq , 分享时间: , 下载次数:25 次文件名:《纽约时报》2016年度十大好书英文原版合集（epub+mobi）.rar , 文件大小:71.97MB , 分享者:132*****107 , 分享时间: , 下载次数:1次文件名:VIP版V56版直装去广告、破解VIP天数版.apk , 文件大小:55.46MB , 分享者:辉哥**老大 , 分享时间: , 下载次数:34次文件名:[国剧]绝代双骄(林志颖、苏有朋版)国语中字 , 文件大小:0B , 分享者:L**LT , 分享时间: , 下载次数:93次文件名:VIP版V56版直装去广告、破解VIP天数版.apk , 文件大小:55.46MB , 分享者:kg**海波 , 分享时间: , 下载次数:20次文件名:VIP版V56版直装去广告、破解VIP天数版.apk , 文件大小:55MB , 分享者:爱收**源网 , 分享时间: , 下载次数:26次带约束的最优化问题
支持向量机SVM的训练过程中需要求解带约束的最优化问题。
带约束的最优化问题通常表述如下：
objective:minwf(w)s.t.{gi(w)&0,hj(w)=0,i=1,2,3...n;j=1,2,3...m;不等式约束等式约束
gi(w),hj(w)和f(w)一般都是连续可导的。要求在满足gi(w)&0,hj(w)=0的前提下求能使得目标函数f(w)最小化的w。
学习支持向量机SVM时，拉格朗日对偶、Slater条件、KKT条件等一大堆概念席卷而来，让没学习过凸优化的笔者一头雾水，估计不少人都是这样吧。
不幸的是笔者在数学相关问题上经常一不小心就陷入死磕，遇到没想明白的问题就总惦记着。另外笔者还是个懒于动手的人，但好在数学是一门完全不需要动手的学科，你只要靠想就可以，最多需要在纸上画画，完全不用做什么实验或者手工体力活儿，嗯，很适合笔者这种懒人，这也是笔者为什么从一个电气工程学生慢慢偏离航向发展成一个程序猿的原因。
回到我们要说的SVM中的优化问题。为什么要引入一堆系数把约束条件与目标函数组合到一起？为什么满足了KKT条件就是符合条件的解? 为什么可以转化为对偶问题？什么是Slater条件？在讲SVM的资料中通常不会详细展开这些问题，只是告知读者有这么回事。带着一排排问号，翻阅文献、Wiki、博客，加上自己的一些思考，算是把不少问题整理清楚了。笔者希望能把这些问题用容易理解的方式讲述明白，通过这一系列博文，将相关问题由易到难一一做出解释，希望这个系列的文章能帮更多人解惑。
本系列文章包括：
1. 纯等式约束时的optimalize问题
2. 纯不等式约束时的optimalize问题
3.混合约束时的optimalize问题&&KKT条件与拉格朗日对偶问题
4.强对偶性的证明与Slater条件
1. 纯等式约束时的optimalize问题
这一类问题的范式如下：
objective:minwf(w)s.t:hj(w)=0,j=1,2,3...m;
在满足hj(w)=0的条件下使f(w)最小化。hj(w)和f(w)都应是连续可导的。上面纯代数的形式会让人不容易看到此类问题的本质，我们希望对这类问题有一个直观的几何理解。首先我们来看一下每个等式约束的含义。
等式约束的几何意义
对于 hj(w)=0，如果w是一个3维变量，那所有满足hj(w)=0的w点集通常会组成一个 2 维的曲面。特别当hj(w)是w的线性函数时，比如 ：
hj(w)=a1wx+a2wy+a3wz+b
其中wx、wy、wz分别是w在三个维度上的分量，a1、a2、a3、b是某些常数。这时 hj(w)=0就是三维空间中的一个平面。对于通常的非线性函数而言， hj(w)=0一般对应一个曲面。
如果w是更高维的变量，维数设为dw，那hj(w)=0一般对应一个(dw?1)维的子空间，或者说(dw?1)维的曲面。注意，当我们下面再提到&面&这个概念时，它不一定代表狭义的二维面，而可以是对任意维度的一个子空间的称谓。
借用下物理中的概念：如果将hj(w)看做空间中某个向量场的势函数，这个向量场就是hj(w)的梯度场?hj(w)，而hj(w)=0所对应的子空间就是该梯度场的0等势面。在等势面上任一点的梯度都与该点邻域内的等势面垂直，即若w?是等势面上一点，则?hj(w?)垂直于该等势面。（通常等势面是个曲面，当我们说垂直的时候，只是针对该面上某个点的切面）
进一步的，c?hj(w?)构成了一个1维的子空间Gj，这个子空间与(dw?1)维的0等势面（在w?处的切面）垂直，因此它们互为补空间（相互垂直且维度之和是dw）。这意味着，在w?处所有与0等势面垂直的向量都在Gj子空间中，即都可表示成一个常数与?hj(w?)相乘。
继续往下读之前先确保理解了上面几段的内容。提示：在本文中遇到高维相关结论，可以先在大脑里以我们熟悉的三维空间举例理解。
再回到我们的问题，这里我们有m个等式约束，每个约束都对应一个0等势面，m个约束同时作用，相当于把可行域限制在了这m个0等势面的交集上。这个交集是什么样子？它也是一个子空间，只不过维数可能更低。比如三维空间中两个不平行的面(2维)的交集，是一条1维的线。我们先称呼前面提到的这个交集为&公共0势面&。
假设公共0势面的维度是d0，通常d0=dw?m。而各hj(w)在公共0势面上某点w?处的梯度向量?hj(w?)都与公共0势面垂直，且共有m个这样的向量，因此这些梯度向量组合成的m维子空间G与公共0势面互补。意味着：w?处所有与公共0势面垂直的向量都在G子空间中,即都可表示成：
V=&j=1mcj?hj(w?)
当然，d0也有大于dw?m的时候，但这并不影响上面的结论。假如m个等势面中有某(t+1)个等势面是相切的，这时公共等势面变成了dw?(m?t)维，比正常时候多了t个维度；但另一方面，梯度空间G也会因此而减少t个维度，因为有(t+1)个梯度是平行的，它们只能提供1个维度。此时，上面的结论保持不变
公共0势面上的极值条件
我们已经知道，满足所有等式约束的点，都在前面提到的公共0势面上。那我们的目标函数f(w)的极值点怎么找呢？
通常，在没有约束的时候，我们要找f(w)的极值点，只要找f(w)梯度为0的点，即?f(w)是0。而我们把可行域限制在公共0势面上之后呢？对，我们只要要求梯度向量?f(w)在公共0势面上的分量为0即可，换句话说，梯度向量与公共0势面垂直。
为了表达具体一点我们不得不把倒霉的w?再抓回来当我们的小白鼠。我们继续把它在公共0势面上，看一下它怎样才能变成极值点。
我们要求f(w)在w?处的梯度向量?f(w?)与该处的公共0势面垂直，意味着?f(w?)必然在前面提到的梯度子空间G上，即它可以由各个等式约束函数在w?处的梯度线性组合而成，即存在一系列系数&j，满足下式：
?f(w?)+&j=1m&j?hj(w?)=0
这就是判定w?是否是可行域内极值点的方法。
当我们求解纯等式约束下的最优化问题时，我们只需求解如下方程组即可求得候选解，然后从中挑选最优解：
求解w和&{?f(w)+&mj=1&j?hj(w)=0hj(w)=0forj=1,2...m
或者我们可以构造一个能把约束条件与目标函数融合到一起的新函数：
L(w,&)=f(w)+&j=1m&jhj(w)
不错，狡猾的笔者偷偷把拉格朗日乘子式的雏形列了出来，就在读者察觉到怎么读了这么久还没看到拉格朗日大人的踪影是不是走错片场了的时候。
这时，上面的方程组其实就是
求解w和&????L?wk=0?L?&j=0fork=1,2,3...dw(w的维数)forj=1,2...m
多说两句，这个方程组中共有 (dw+m) 个未知量和方程。
其中?L?wk=0是同时包含w,&的方程，这样的方程共有dw个;
而?L?&j=hj(w)=0是只包含w的方程，这样的方程共有m个。为使w有解，m应小于w的维数dw，否则对w的约束方程数将大于w的变量个数导致约束太强、各约束方程无法同时被满足而无解；
因此当d&m时，上面的方程组通常是有解的。特别是当目标函数f(w)是w的二次函数、hj(w)都是w的一次函数即仿射函数时，上面的方程组就变了一个线性方程组，可以用线性代数方法直接求解
简单解释一下：
当f(w)是w的二次函数、hj(w)是w的一次函数时，他们对wk的偏导分别是w的一次和零次(常数)函数，所以他们的组合函数 L(w,&)对wk的偏导?L?wk就是w,&的一次函数，?L?wk=0就是一个线性方程；
而?L?&j=0等价于hj(w)=0，hi(w)是w的一次函数，因此所有的hj(w)=0也都是线性方程；
于是整个方程组就变成了线性方程组
一句话概括
求解等式约束下的最优化问题，只需要解个方程组就可以找到候选极值点，然后在方程组的各个解中筛选出满足条件的最小值点即可（该方程组有可能是多解的）。
如果目标函数是二次函数，且约束都是线性的，那我们只需要求解一个线性方程组。
2. 纯不等式约束时的optimalize问题
这一类问题的范式如下：
objective:minwf(w)s.t:gi(w)&0,i=1,2,3...n;
gi(w)和f(w)都应是连续可导的。为了方便理解，我们先看只有一个不等式约束时的情形
只有一个不等式约束的情况
objective:minwf(w)s.t:g1(w)&0
对于某个给定的 w?，如果它在可行域的内部，即g1(w?)&0时，只需判断 f(w) 在w?处的梯度?f(w?)是否为0即可判断其是否是可行域上的候选极值点。
而如果 w?在可行域的边界，即g1(w)=0时，情况就稍微复杂。首先，我们要保证至少在边界面上，w?是一个极值点（条件一）；其次，还要保证在可行域内部，w?的邻域内的其他点的函数值都比f(w?)大（条件二）。
为满足条件一，?f(w?)在边界面上的梯度分量应为0，即?f(w?)与边界面垂直。而边界面其实是g1(w)的零等势面，因此?g1(w?)也垂直于边界面。这样?f(w?)就应与?g1(w?)平行，即?f(w?)+&1?g1(w?)=0
但这还不够，我们还要考虑不在边界上的内点。设(w?+&Dw)是邻域内任一点，则当&Dw满足如下条件时：(注意&Dw与梯度一样都是向量，而非标量) ?g1(w?)?&Dw&0
(w?+&Dw)就是可行域上的点，因为这时满足 g1(w?+&Dw)=g1(w?)+?g1(w?)?&Dw&0。
为使f(w) 能在w?处取可行域上的极小值，对于可行域内的所有&Dw 须满足?f(w?)?&Dw&0，即
?&1?g1(w?)?&Dw&0
而?g1(w?)?&Dw&0，因此此时&1&0。
从几何角度来说，上面的两个条件对应的意义是：?f(w?)应与边界面垂直并指向包含可行域的一侧（边界面的一侧包含可行域，另一侧不包含可行域）。函数值沿着梯度方向是增长的，当f(w)在w?处的梯度指向可行域一侧时，可行域内部的函数值都比w?处大，w?才能是极小点
现在可以做个小结了：若w?是可行域上的极值点，则应满足：
{?f(w?)+&1?g1(w?)=0且&1&0?f(w?)=0w?是边界点，即g1(w?)=0时w?是内点，即g1(w?)&0时
或者换一种更统一的形式
?f(w?)+&1?g1(w?)=0其中&1&0，且当g1(w?)&0时只能取等号
我们甚至可以把原问题中的约束条件也包进来，构造一个完整的方程组：
求解w和&1????f(w)+&1?g1(w)=0&1g1(w)=0&1&0,g1(w)&0
巧妙的是，第二行的(&1g1(w)=0)和第三行的(&1&0,g1(w)&0)联合起来，正好暗示了一个规则：当g1(w)&0时，&1=0；只有当g1(w)=0时，&1才可能大于0
同时存在多个不等式约束的情况
objective:minwf(w)s.t:gi(w)&0,i=1,2,3...n;
多个不等式约束同时存在时，思路与前面大致相同。
如果w?不在边界上，只需判断 ?f(w?)是否为0；
如果w?只在其中某一个约束比如gi(w)&0的边界上，处理方法与前面一样；
唯一需要多加考虑的，是当w?同时在多个约束的公共边界上的情况，即w?在多个不同约束的边界面的交集上，比如，g1(w?)=g2(w?)=g3(w?)=g4(w?)=0。下面以此为例来说明。
首先，为使w?在公共边界上满足极值条件，?f(w?)应与公共边界垂直。
而公共边界同时属于g1(w?)、g2(w?)、g3(w?)、g4(w?)的0等势面，因此 ?g1(w?)、?g2(w?)、?g3(w?)、?g3(w?)分别都与公共边界垂直，且这四个向量张成的四维空间正好构成公共边界的补空间，所有与公共边界垂直的向量，都在这个补空间中，可以被这四个向量的线性组合表示。
因此 ?f(w?)+&i=14&i?gi(w?)=0
同样，我们还要关心可行域上、公共边界以外的其他点。
设(w?+&Dw)是邻域内任一点，当&Dw同时满足如下条件时：
?gi(w?)?&Dw&0，其中i=1,2,3,4
(w?+&Dw)就是可行域上的点。
为使f(w) 能在w?处取可行域上的极小值，对于可行域内的所有 &Dw 须满足 ?f(w?)?&Dw&0 ，即
?&i=14&i?gi(w?)?&Dw&0
同样的几何意义：?f(w?)应与公共边界面垂直并指向靠近可行域的方向。
这里说的&靠近可行域的方向&，是指与可行域夹角小于等于90&的方向。准确的说，对于所有能使(w?+&Dw)位于可行域上的微小位移向量 &Dw，与?f(w?)夹角都应小于等于90&，用内积表示就是?f(w?)?&Dw&0
结合?gi(w?)?&Dw&0，为保证对所有满足的条件的&Dw上式都能成立，必须要求每个&i都大于等于0。
否则，假如&1小于0，对于满足以下条件&Dw，?g1(w?)?&Dw&0,?g2(w?)?&Dw=0,?g3(w?)?&Dw=0,?g4(w?)?&Dw=0上面的式子就不成立了
总结起来就是，当w?在上述公共边界并是可行极值点时，应满足：
?f(w?)+&i=1n&1?g1(w?)=0仅当i=1,2,3,4时，&i&0，其他&i=0
OK，有了这个特例的辅助，我们很容易将结论一般化如下：
?f(w?)+&i=1n&1?g1(w?)=0其中&i&0，且当gi(w?)&0，即w?不在第i个约束边界时必须取等号
我们继续运用前面说到的巧妙办法，把原问题中的约束条件也包进来，构造一个完整的方程组：
求解w和&????f(w)+&ni=1&i?gi(w)=0&igi(w)=0&i&0,gi(w)&0fori=1,2...nfori=1,2...n
现在到再请出拉格朗日大人的时候了。我们构造一个能把约束和目标函数融合在一起的新函数，如下（拉格朗日乘子式）：
L(w,&)=f(w)+&i=1n&igi(w)
这时上面的方程组变成了
求解w和&??????????L?wk=0&i??L?&i=0&i&0,?L?&i&0fork=1,2,3...dw(w的维数)fori=1,2...nfori=1,2...n
这里共有dw+n个等式方程和dw+n个变量，可以先求解前两行构成的等式方程组，再排除掉其中不符合第三行条件的解，剩下的即是符合条件候选极值点。
然而，第二行的方程与纯等式约束时的情况不太一样，纯等式约束下只要求约束式的偏导为0，而这里是要求偏导与系数(也是待求的未知数)乘积为0，这增加了解方程的难度。即便当目标函数是二次的、不等式约束都是线性的时候，方程组整体也变成了二次方程组，很难直接求解。不过，这时不等式约束的数量n是可以大于d_w的，因为第二行的方程不在只包含w，同时也包含了&，不会出现w的约束太强而无解。
3. 混合约束时的optimalize问题&&KKT条件与拉格朗日对偶问题
这一类问题的范式如下：
objective:minwf(w)s.t.{gi(w)&0,hj(w)=0,i=1,2,3...n;j=1,2,3...m;不等式约束等式约束
gi(w),hj(w)和f(w)都应是连续可导的。
拉格朗日乘子式与KKT条件
有了前面纯等式和纯不等式约束问题的铺垫，我们可以轻松得出混合约束时的结论。
首先，还是先考虑最简单的情况，假如w?不在任何不等式的边界，即gi(w?)&0对所有 i=1,2...n 成立。&&被玩坏的w?肯定在抱怨：为什么又是我躺枪，隔壁w&闲了两天了！但显然无情的笔者才不打算关心这个声音。
但w?须仍在所有等式约束hj(w)的公共0势面上。这时相当于只有等式约束，w?是极值的条件是：
?f(w?)+&j=1m&j?hj(w?)=0
我们再把w?扔到不等式的边界上看看会发生什么。有了之前纯不等式约束的基础，我们直接考虑w?同时在多个不等式约束边界时的情况，假如w?在第1、2、3、4个不等式约束的公共边界面上，即：
???gi(w?)=0gi(w?)&0hj(w?)=0fori=1,2,3,4fori=otherforj=1,2...m
可见，这个公共边界面，属于 g1(w)、g2(w)、g3(w)、g4(w)和h1(w)、h2(w)...hm(w)的公共混合0势面的一部分。如果想让f(w)在w?处是可行域上的一个极值，首先要保证w?在这个公共混合0势面上是极值，即f(w)在w?处的梯度应垂直于该混合0势面，可以表示成：
?f(w?)+&j=1m&j?hj(w?)+&i=14&i?gi(w?)=0
但这还不够，为了保证可行域上w?所有邻域点(w?+&Dw)的目标函数值都比w?处大，&1...&4还应都是大于等于0的，具体分析过程与讲解纯不等式约束问题时类似，不再重复。
再强调下几何意义：?f(w?)应与公共混合0势面垂直并指向靠近可行域的方向。
将上面两种情况用统一的形式重写如下，w?是可行域上极值点的条件是：
?f(w?)+&j=1m&j?hj(w?)+&i=1n&1?g1(w?)=0其中&i&0，且当gi(w?)&0，即w?不在第i个不等式约束边界时只能取等号
因此，我们可以通过解以下方程组（前3行等式构成方程组）
求解w、&和&??????????f(w)+&mj=1&j?hj(w)+&ni=1&i?gi(w)=0hj(w)=0&igi(w)=0&i&0,gi(w)&0forj=1,2...mfori=1,2...nfori=1,2...n
然后排除掉不满足第4行的解，就可以得到可行域上的候选极值点。
然后，拉格朗日时间到。是时候引出完整版的拉格朗日乘子式了，我们构造一个融合目标函数和所有约束的新函数：
L(w,&,&)=f(w)+&i=1n&igi(w)+&j=1m&jhj(w)
然后前面的方程组就变成了
求解w、&和&????????????????L?wk=0?L?&j=0&i??L?&i=0&i&0,?L?&i&0fork=1,2,3...dw(w的维数)forj=1,2...mfori=1,2...nfori=1,2...n
是的，我们就这样得到了广为流传的KKT条件。对于某组给定的(w?,&?,&?)，如果能同时满足上面的条件，w?就是原问题的候选解，但候选解不一定是最优解。KKT条件只是最优解的必要条件。
拉格朗日对偶问题
前面KKT条件中的方程组通常是很难直接求解的。而有些时候，将原问题转换成另一种形式，可能更会容易求解。下面就介绍一种常见的转换形式，对偶问题。
我们先来看一个与原问题等价的问题。设
&(w)=max&&0,&L(w,&,&)注意条件，所有的&i&0
注意所有的 &i 都是大于等于0的。
&(w)={f(w)+&,所有等式和不等式约束均被满足有任意一个约束未被满足
如果不等式约束中有任意一个约束未被满足，比如若某个 w? 使得 gi(w?)&0 时, 那我们将对应的 &i 取 +& ，则 &igi(w?) 必然也是 +& ，导致 &(w?) 变为 +& 。
同理如果原问题的等式约束中有任意一个约束未被满足，比如若某个w?使得 hj(w?)&0时, 那我们将对应的&j 取&j={?&+&,hj(w?)&0hj(w?)&0
则&jhj(w?)必然是+&，，导致&(w?) 变为+&。
只有当w?满足所有的等式约束和不等式约束时，&(w?)才不会变为无穷大。而且由于此时等式约束被满足，导致所有的&jhj(w?)项被直接消去，因为他们都等于0；另一方面由于所有的&i&0,gi(w?)&0 ，因此 &igi(w?) 取最大时必然也是0，即所有的&igi(w?)项也被消去，只剩下了f(w)。于是就有上面的结果
&(w)={f(w)+&,constraint satisfiedconstraint not satisfied
这样一来，求原问题中的 minwf(w) 就等价于求 minw&(w) 。
原问题等价于：
objective:minwmax&,&L(w,&,&)s.t.&i&0,for i=1,2,3...n
如果调换上面 min 和 max 的顺序，就得到该问题的对偶问题。
对偶问题 ：
objective:max&,&minwL(w,&,&)s.t.&i&0,for i=1,2,3...n
引入一个新函数： &D(&,&)=minwL(w,&,&) ，这时对偶问题变成：
objective:max&,&&D(&,&)s.t.&i&0,for i=1,2,3...n
根据&D的定义可知，对于任意的(w,&,&&0)，有&D(&,&)&L(w,&,&)；
根据&的定义可知，对于任意的(w,&,&&0)，有&(w)&L(w,&,&)；
如果设p?=&(w?)=minw&(w),d?=&D(&?,&?)=min&&0,&&D(&,&)
则d?=&D(&?,&?)&L(w?,&?,&?)&&(w?)=p?
即d?&p?，这个特性被称为&弱对偶性&，(p??d?)被称为&对偶间隙&，对偶间隙是大于等于0的。通过求解对偶问题，可以求出原问题的一个下限，在实际中这对寻求原问题最优解有一定的帮助。
如果对偶间隙为0即d?=p?，则称之为&强对偶性&，此时对偶问题于原问题等价，只需求解对偶问题即可，(w?,&?,&?)同时是原问题和对偶问题的解。
那什么情况下强对偶性才能被满足呢？我们介绍一个能在凸优化问题中保证强对偶性的充分条件，下一节再证明这个结论。
定义: 凸优化问题
当且仅当目标函数f(w)和所有的不等式约束函数gi(w)都是凸函数，所有的等式约束hj(w)都是线性(仿射)函数时，相应的最优化问题属于凸优化问题。
Slater条件
对于凸优化问题，如果可行域满足Slater条件，强对偶性保证成立。
Slater条件是指，可行域存在一点 w&同时满足：{gi(w&)&0hj(w&)=0fori=1,2...n(注意是&不再是&)forj=1,2...m
如果不等式约束中存在线性约束，比如前t个不等式约束都是线性约束时，Slater条件可以弱化为：???gi(w&)&0gi(w&)&0hj(w&)=0fori=1,2...tfori=t+1,t+2...nforj=1,2...m
KKT条件的充分性
之前的分析中，KKT条件只能作为最优解的必要条件，但满足KKT条件的解不一定是最优解。而对于凸优化问题，KKT条件同时也是最优解的充分条件。
如果(w?,&?,&?)是满足KKT条件的一组解，即
??????????????????L?w?k=0?L?&?j=0&?i??L?&?i=0&?i&0,?L?&?i&0fork=1,2,3...dw(w的维数)forj=1,2...mfori=1,2...nfori=1,2...n
由于&?&0，以及凸优化问题中各不等式约束函数和目标函数都是凸函数的特点，易知L(w,&?,&?)是w的凸函数，而KKT条件的第一行说明w?是使得L(w,&?,&?)对w导数为0的点，因此
L(w?,&?,&?)=minwL(w,&?,&?)=&D(&?,&?)
同时，KKT条件的第二行h(w?)=0和第三行&?g(w?)=0使得
L(w?,&?,&?)=f(w?)=&(w?)
因此有&D(&?,&?)=&(w?)。
而同时\theta_D(\alpha^*,\beta^*)\le d^*\le p^*\le \theta(w^*)&D(&?,&?)&d?&p?&&(w?)，这其实暗示了d^*= p^*d?=p?，即强对偶性成立，且(w^*,\alpha^*,\beta^*)(w?,&?,&?)正好是原问题和对偶问题的最优解。
因此，对于凸优化问题，满足KKT条件的解一定是最优解，且满足KKT条件暗示了强对偶性成立。
4. 强对偶性的证明与Slater条件
强对偶性的一种比较直观的证明是用几何方法。
先介绍一条关于凸集的定理。这个定理表达的意思很直观。比如在二维空间中，二维平面上的任意一个凸图形（比如一个圆），在其边缘上任一点处做切线，该图形必在切线的同一侧，而不会被切割成多个部分并分居两侧。该定理的完整表述如下：
引理： 支撑超平面定理
设集合 CC 是 \mathbb{R}^nRn 空间中的闭凸集， xˉ 是 C 边界上一点，则必存在一个过点 xˉ 的超平面，使得 C 位于它的一个闭半空间。即存在法向量 a ，使得对于 C 中任意点 x ，有：
a?x?a?xˉ&0
进一步地，如果已知 xin 是 C 的一个内点，则：
a?xin?a?xˉ&0
回到我们的问题。我们要研是凸优化问题中强对偶性成立的条件，首先做一个基本假设：
基本假设：假设原问题是凸优化问题，即f(w),gi(w)都是凸函数，hj(w)都是线性函数，且所有的hj(w)相互之间都是线性独立的。
w&Rdw，我们按如下方式将Rdw空间中一点w映射为R(n+m+1)空间中的点E：
E(w)=(u1,u2,...un,v1,v2,...vm,t)其中???ui=gi(w)vj=hj(w)t=f(w)i=1,2,3...nj=1,2,3...m
简化表示为E=(u,v,t)。
设所有点E组成的集合为Go，
Go={(u,v,t):u=g(w),v=h(w),t=f(w),w&Rdw}
然而，即便有了前面的基本假设，我们也不能保证Go是凸集。但是如果把它简单扩展一下，设：
Ge={(u,v,t):u&g(w),v=h(w),t&f(w),w&Rdw}
容易证明Ge是一个凸集，且Go?Ge。
若A(ua,va,ta)和B(ub,vb,tb)是Ge内的两个点，按照Ge的定义可知必然存在wa和wb，使得
va=h(wa),ua&g(wa),ta&f(wa)vb=h(wb),ub&g(wb),tb&f(wb)
设0&c&1,wc=cwa+(1?c)wb,C=cA+(1?c)B=(uc,,tc)，则
uc=cua+(1?c)ubvc=cva+(1?c)vbtc=cta+(1?c)tb
由于h(w)是w的线性函数，因此
c?h(wa)+(1?c)h(wb)=h[cwa+(1?c)wb]=h(wc)
即vc=h(wc)；
由于g(w),f(w)都是w的凸函数，因此
c?g(wa)+(1?c)g(wb)&g[cwa+(1?c)wb]=g(wc)c?f(wa)+(1?c)f(wb)&f[cwa+(1?c)wb]=f(wc)
而同时ua&g(wa),ta&f(wa),ub&g(wb),tb&f(wb)，于是
cua+(1?c)ub&c?g(wa)+(1?c)g(wb)cta+(1?c)tb&c?f(wa)+(1?c)f(wb)
即uc&g(wc),tc&f(wc)。再结合vc=h(wc)，可知(uc,vc,tc)&Ge，即C=cA+(1?c)B&Ge。由于前述 A,B,c 的选取具有任意性，因此对于任意两点A,B&Ge，连线ABˉˉˉˉˉ上的所有点都属于Ge，Ge是凸集。
除此之外，我们还知道E?=(0,0,p?) 必是Ge 的一个边界点，其中p?=minw&(w)，&(w)的定义同上一节。
若w? 是目标函数f(w) 在可行域内的极小点，则p?=f(w?)，且由于在可行域内，必然满足g(w?)&0、h(w?)=0，因此(0,0,p?)&Ge;
又由于p? 是可行域上即区间 {g(w?)&0,h(w?)=0}上的最小值(边界值)，对于任意小的正数&，(0,0,p??&)?Ge，因此(0,0,p?) 在边界上。
即E?=(0,0,p?) 是Ge 的一个边界点。
利用上面关于边界点的支撑超平面定理，我们知道必存在一个法向量a=(&a,&a,&a)，使得对于Ge内任一点Ee=(ue,ve,te)，满足：
a?Ee?a?E?&0即&aue+&ave+&ate&&ap?((1-a))
由于ue,te可以随意取正无穷大，p?是个定值，为使上面的大于等于恒成立，&a和&a必须大于等于0。否则，如果他们任意一个取负，当ue,te取正无穷大时，左边会变成负无穷而导致上式无法被满足。
h(w)是w的线性函数，因此ve=h(w)也可以取到正无穷，甚至负无穷也可以。但ve不能单独、随意 地增大，因为ve完全由w确定，而ue和te只是被w确定了下限，它们可以单独增大，且仍保证在集合Ge内。
&a&0的情况
假如&a&0，此时令&?=&a/&a,&?=&a/&a，则式(1-a)可重写如下：
&?ue+&?ve+te&p?((2-a))
由于&a&0，&?&0。
由于Go?Ge，因此Go中任意一点E(u,v,t)=(g(w),h(w),f(w))也都满足上式。
即必然存在一组&?,&?，对任意的w&Rdw，始终满足：
&?g(w)+&?h(w)+f(w)&p?&&0
我们上面都使用了简化后的表示方式，如果将上式完整展开，就是：存在一组&?,&?使得下式对所有的w&Rdw成立。
&i=1n&?igi(w)+&j=1m&?jhj(w)+f(w)=L(w,&?,&?)&p?&?i&0,fori=1,2,3...n
由于上式对任意的w都成立，因此
&D(&?,&?)=minwL(w,&?,&?)&p?
进一步由于d?=max&&0,&&D(&,&)&&D(&?,&?)
于是得到d?&p?。而由弱对偶性，d?&p?。因此d?=p?，强对偶性成立。
&a=0的情况，Slater条件的作用
这不是我们期望出现的情况，因为一旦&a=0，我们就无法将式(1-a)的左边转换成跟L(w,&,&)相同的形式了。实际上，只要上节中提到的Slater条件被满足（通常这个条件都是满足的），就不会出现&a=0的情况。下面我们分析为什么不会出现。
假如&a=0，此时式(1-a)变成
&aue+&ave+&ate&0((4-a))
Slater条件保证了在可行域内，存在 w& 使得g(w&)&0,h(w&)=0，设
E1=(g(w&),h(w&),f(w&))&GeE2=(g(w&)+&Dg,h(w&),f(w&)+&Df)&intGe其中&Dg和&Df是任意大于0的值，这两个正增量保证了E2是Ge的内点
&ag(w&)+&ah(w&)+&af(w&)&0(4-b)
&a[g(w&)+&Dg]+&ah(w&)+&a[f(w&)+&Df]&0(4-c)
式(4-c)中可以用大于号是因为E2是Ge的内点，上面介绍引理时专门提到对于内点可以用大于号。
考虑到h(w&)=0,&a=0，由式(4-b)可得&ag(w&)&0；
再由g(w&)&0,&&0，可得&a=0；
而将&a=0和h(w&)=0,&a=0代入式(4-c)，会得到式(4-c)左边等于0的结论，这与式(4-c)中的大于号矛盾。
因此，当Slater条件被满足时，不会出现&a=0的情况。
Slater条件的表述似乎加强了对可行域的要求。实际上，只要要求对于每一个不等式约束 gi(w)，在可行域内分别存在一个 wi能使得gi(wi)&0即可，这就足以支持我们推出上面的矛盾(将上面的简化表达式完整展开并推导出每个&i=0即可推出矛盾)。而不须要求存在某个 w&使其同时满足所有的不等式约束。然而如果所有的gi(w)都是连续可导的话，这两种表述似乎也是等价的，不过这个结论的推理过程可能有些繁杂。
之前还提到了弱化的Slater条件(Weak Slater Condition)，弱化的Slater条件放宽了对线性不等式约束的要求。
实际上，当原Slater条件未被满足，但弱化的Slater条件能被满足时，说明存在某个线性不等式约束 gi(w)，在可行域内找不到任何点能使得gi(w)&0成立，即在整个可行域内gi(w)=0。这意味着所有等式约束hj(w)=0，它们与gi(w)&0的交集和与gi(w)=0的交集一样。考虑到hj(w)和gi(w)都是w的线性函数，这只会发生在gi(w)正好是所有所有等式约束hj(w)的线性组合时，即
gi(w)=&j=1mcjhj(w)
而这时，可以认为g_i(w)完全不起约束作用，直接为其分配系数&i=0，然后按正常方式为其他不等式约束分配系数即可。因此只要满足弱化的Slater条件，就可以保证强对偶性。
综上，只要f(w),gi(w)都是凸函数，hj(w)都是线性函数，且可行域满足弱化的Slater条件时，强对偶性可以被保证。
附录：支撑超平面定理的证明(截图)
以下截图来自博文：}