该部分是svm的理解基础 https://www.cnblogs.com/dreamvibe/p/4349886.html（可参考） https://zhuanlan.zhihu.com/p/38182879(也可以去参考李航的统计学习方法中的附录部分) https://www.zhihu.com/question/58584814O（可参考） https://charlesliuyx.github.io/2017/09/20/拉格朗日乘法和KKT条件/（图和例题）
我们的问题针对的是下面的优化问题，在等式约束和不等式约束的情况下求函数的最小值。 min x ∈ R n f ( x ) s.t. c i ( x ) ≤ 0 , i = 1 , 2 , … , k h j ( x ) = 0 , j = 1 , 2 , … , l egin{array}{l} min _{x in R^{n}} f(x) \ ext { s.t. } quad c_{i}(x) leq 0, quad i=1,2, ldots, k \ quad h_{j}(x)=0, quad j=1,2, ldots, l end{array} minx∈Rnf(x) s.t. ci(x)≤0,i=1,2,…,khj(x)=0,j=1,2,…,l 对于等式约束，简单问题可以直接带入 f ( x ) f(x) f(x)进行求导。但是对于不等式约束，就难以解决了。（ c i ( x ) c_{i}(x) ci(x) 通常是小于等于0，不要写成大于等于0,便于之后的公式推导）
最优化中通常采用构造拉格朗日函数的对偶问题来解决上面的问题。构造的拉格朗日函数如下： L ( x , α , β ) = f ( x ) + ∑ i = 1 k α i c i ( x ) + ∑ i = 1 l β i h i ( x ) L(x, alpha, eta)=f(x)+sum_{i=1}^{k} alpha_{i} c_{i}(x)+sum_{i=1}^{l} eta_{i} h_{i}(x) L(x,α,β)=f(x)+i=1∑kαici(x)+i=1∑lβihi(x) 该函数把约束条件和目标函数放在了一起，这样我们就可以更方便的进行分析了。但是现在这个问题和我们的目标还不太一样，我们的目标只是求 min x f ( x ) min_xf(x) minxf(x)，而现在的 L ( x , α , β ) L(x, alpha, eta) L(x,α,β)多了后面的两个约束部分,并不是等价的，那么找个办法让它们等价，也就是让 min x L ( x , α , β ) min_xL(x, alpha, eta) minxL(x,α,β)等价于 min x f ( x ) min_xf(x) minxf(x)。直观的来看，如果 ∑ i = 1 m α i c i ( x ) + ∑ i = 1 m β i h i ( x ) sum_{i=1}^{m} alpha_{i} c_{i}(x)+sum_{i=1}^{m} eta_{i} h_{i}(x) ∑i=1mαici(x)+∑i=1mβihi(x)等于0，那这个问题岂不就相等了，当然，我们肯定也不能简单的让 α 、 β alpha、eta α、β等于0，那我们上面的就没有意义了。$$
现在我们的目标是让 ∑ i = 1 k α i c i ( x ) + ∑ i = 1 l β i h i ( x ) sum_{i=1}^{k} alpha_{i} c_{i}(x)+sum_{i=1}^{l} eta_{i} h_{i}(x) ∑i=1kαici(x)+∑i=1lβihi(x)这一坨为0，其实后面的等式约束我们可以暂时不考虑了，反正都等于0嘛。在 ∑ i = 1 m α i c i ( x ) sum_{i=1}^{m} alpha_{i} c_{i}(x) ∑i=1mαici(x)中，我们假定 α i ≥ 0 alpha_ige0 αi≥0,那么 ∑ i = 1 k α i c i ( x ) sum_{i=1}^{k}alpha_{i} c_{i}(x) ∑i=1kαici(x)就是小于等于0 ，那么不就是让这一部分取到最大嘛！即： θ P ( x ) = max α , β : α i ⩾ 0 [ f ( x ) + ∑ i = 1 k α i c i ( x ) + ∑ j = 1 l β j h j ( x ) ] heta_{P}(x)=max _{alpha, eta: alpha_{i} geqslant 0}left[f(x)+sum_{i=1}^{k} alpha_{i} c_{i}(x)+sum_{j=1}^{l} eta_{j} h_{j}(x) ight] θP(x)=α,β:αi⩾0max[f(x)+i=1∑kαici(x)+j=1∑lβjhj(x)]
θ P ( x ) = { f ( x ) , x 满足原始问题约束 + ∞ , 其他 heta_{P}(x)=left{egin{array}{ll} f(x), & x ext { 满足原始问题约束 } \ +infty, & ext { 其他 } end{array} ight. θP(x)={f(x),+∞,x 满足原始问题约束 其他
原始问题可表示为： min x θ P ( x ) = min x max α , β : α i ⩾ 0 L ( x , α , β ) min _{x} heta_{P}(x)=min _{x} max _{alpha, eta: alpha_{i} geqslant 0} L(x, alpha, eta) xminθP(x)=xminα,β:αi⩾0maxL(x,α,β) 但是写成这种形式对x不能求导，所以我们需要转换成max min的形式，这时候，x就在里面了，这样就能对x求导了(这句话我并没有真正理解，抄自于https://www.cnblogs.com/huangshiyu13/p/6580892.html)，也就是 max α , β ; α i ≥ 0 θ D ( α , β ) = max α , β ; α i ≥ 0 min x L ( x , α , β ) max _{alpha, eta ; alpha_{i} geq 0} heta_{D}(alpha, eta)=max _{alpha, eta ; alpha_{i} geq 0} min _{x} L(x, alpha, eta) α,β;αi≥0maxθD(α,β)=α,β;αi≥0maxxminL(x,α,β) 该问题就称之为原始问题的对偶问题。转化成这种形式后就可以先对x进行求导，然后再求 α alpha α的最大值了。(待补充例题)
该问题在一定条件（KKT条件）下是相等的（强对偶）。具体来说 d ∗ = max α , β ; α i ≥ 0 min x L ( x , α , β ) ≤ min x max α , β ; α i ≥ 0 L ( x , α , β ) = p ∗ d^{*}=max _{alpha, eta ; alpha_{i} geq 0} min _{x} L(x, alpha, eta) leq min _{x} max _{alpha, eta ; alpha_{i} geq 0} L(x, alpha, eta)=p^{*} d∗=α,β;αi≥0maxxminL(x,α,β)≤xminα,β;αi≥0maxL(x,α,β)=p∗ 当满足一定条件时， d ∗ = p ∗ d^{*}=p^{*} d∗=p∗，体现出强对偶性。这里的条件就有SVM中的KKT条件：
对于原始问题及其对偶问题，假设函数 f ( x ) f(x) f(x)和 c i ( x ) c_i(x) ci(x) 是凸函数， h i ( x ) h_i(x) hi(x)是仿射函数，且不等式约束 c i ( x ) c_i(x) ci(x)是严格可行的，即存在 x x x,对所有 i i i有 c i ( x ) < 0 c_i(x)