SVM中的对偶问题原理

0.摘要

本文仅从SVM的“对偶问题”出发去阐述优化求解问题中的数学原理。


1.“对偶原理”

1.1 原问题：

minimize:f0(x)minimize: f_0(x)minimize:f0​(x)
s.t.gi(x),i=1,2...,ms.t. \quad g_i(x),i=1,2...,ms.t.gi​(x),i=1,2...,m
hj(x),j=1,2,...n\qquad h_j(x),j=1,2,...nhj​(x),j=1,2,...n
原问题在于将生活中的优化问题和其需要满足的条件以一般化的数学语言表达出来

1.2拉格朗日对偶问题：

L(x,α,β)=f(x)+αTg(x)+βTh(x)L(x,\alpha,\beta)=f(x)+\alpha^Tg(x)+\beta^Th(x)L(x,α,β)=f(x)+αTg(x)+βTh(x)
人为设定
1.αi>=01.\alpha_i>=01.αi​>=0
$2.g(\alpha ,\beta )=infL(x,\alpha ,\beta )$

1.3 对偶问题的对偶间隙

f(x∗)=minf(x)≥L(x,α,β)≥infL(x,α,β)=d(α,β)f(x^*)=minf(x)\geq L(x,\alpha,\beta)\geq infL(x,\alpha,\beta)= d(\alpha,\beta)f(x∗)=minf(x)≥L(x,α,β)≥infL(x,α,β)=d(α,β)
即f(x∗)=P∗≥Q∗=d(α∗,β∗)f(x^*)=P^*\geq Q^*=d(\alpha^*,\beta^*)f(x∗)=P∗≥Q∗=d(α∗,β∗)
定义：gep=P∗−Q∗gep = P^* - Q^*gep=P∗−Q∗为对偶间隙，由此引发除了弱对偶定理和强对偶定理(strong duality).
定理：slater条件

1. 任意问题的弱对偶均成立
2. 对于部分问题的强对偶成立：凸优化问题成立，非凸优化问题部分成立

1.4KKT条件的推导

其中互补性的证明：