为什么对偶问题一定是凸优化问题？

大家在学习SVM的对偶问题部分的时候一定会看到一句话：使用对偶问题的一个原因是对偶问题一定是凸优化问题。这句话可能没接触过凸优化人表示一头雾水。凭啥呀？

本文就给大家简单地证明一下。（前面主要是科普，有基础的可以直接跳到最后）

可能有些同学在一些英语课程中会学到这件事。那就是中文和英语对凸 / 凹函数的定义往往是相反的。比如，下面这个函数图像在中国大部分教材（包括同济的那本微积分）中叫做凹函数，英语中却叫convex function（凸函数）。具体是哪边思维比较反人类咱就不争论了，总之，在本博文中统一采取英语的起名法。即下面这个函数视作凸函数。

凸函数，首先它的几何特征就像是我们看到的上面那张图片一样，函数上方区域像是从平行于x轴的线上凸出来一块。由于其特殊的性质，还衍生出了高中数学竞赛中赫赫有名的琴生不等式，不过这里就不细提了。

凸函数的微分有一些很特别的性质，比如一个一元二阶可微函数在某区间是凸函数的充要条件是它在区间上的二阶导是非负的。不过这篇博文里用不到这些，就不多做介绍了。

仿射集(Affine set)：通过集合C中任意两个不同点的直线仍然在集合C内，则称集合C为仿射集。即 ∀ x 1 , x 2 ∈ C , ∀ θ ∈ R , 则 x = θ ∗ x 1 + ( 1 − θ ) ∗ x 2 ∈ C \forall x_1, x_2 \in C, \forall \theta\in R, 则x=\theta*x_1+(1-\theta)*x_2\in C ∀x1​,x2​∈C,∀θ∈R,则x=θ∗x1​+(1−θ)∗x2​∈C其实说着很高端，实际上就是线性变换。

举个例子，高中做解析几何的时候，博主喜欢在处理椭圆相切的时候变换坐标系，比如把椭圆 x 2 16 + y 2 4 = 1 \frac{x^2}{16}+\frac{y^2}{4}=1 16x2​+4y2​=1上的所有点的x坐标缩小一半，这就是一个半径为2的圆，只不过这个变换是对坐标系而言的，也就是说你不能只让椭圆上的点变呀，这不公平。所以整个坐标空间的点的x坐标都缩小了一半，包括之前相切的那条直线。这时候就可以只求和圆相切的直线，然后再把x坐标变回去。非常的爽。

这其实就是一个简单的仿射变换。

由于是线性变换，你可以认为存在一个变换矩阵 [ a 11 a 12 b 1 a 21 a 22 b 2 0 0 1 ] [ x y 1 ] = [ x ′ y ′ 1 ] \left[ \begin{matrix} a_{11} & a_{12} & b_1\\a_{21}&a_{22}&b_2\\0&0&1 \end{matrix} \right] \left[ \begin{matrix} x\\y\\1\end{matrix} \right]=\left[ \begin{matrix}x'\\y'\\1 \end{matrix} \right] ⎣⎡​a11​a21​0​a12​a22​0​b1​b2​1​⎦⎤​⎣⎡​xy1​⎦⎤​=⎣⎡​x′y′1​⎦⎤​看，这样是不是就一目了然了？所谓的仿射，不过是新的坐标等于原坐标的线性组合。

凸集(Convex set)：连接集合C中任意两个不同点的线段仍然在集合C内，则称集合C为凸集。即 ∀ x 1 , x 2 ∈ C , ∀ θ ∈ [ 0 , 1 ] , 则 x = θ ∗ x 1 + ( 1 − θ ) ∗ x 2 ∈ C \forall x_1, x_2 \in C, \forall \theta\in [0, 1], 则x=\theta*x_1+(1-\theta)*x_2\in C ∀x1​,x2​∈C,∀θ∈[0,1],则x=θ∗x1​+(1−θ)∗x2​∈C这个式子和仿射集定义很像，区别在哪呢？在于 θ \theta θ的取值，凸集限制更多。所以说仿射集一定是凸集，凸集是一种特殊的仿射集。

凸优化问题是这么一个问题： m i n 　 f ( x ) min　f(x) min　f(x) s . t . 　 h i ( x ) ≤ 0 　 i = 1 , 2 , . . . , m s.t.　h_i(x)\leq 0　i = 1,2,...,m s.t.　hi​(x)≤0　i=1,2,...,m g j ( x ) = 0 　 j = 1 , 2 , . . . , p g_j(x)=0　j=1,2,...,p gj​(x)=0　j=1,2,...,p 其 中 h i ( x ) 和 f ( x ) 都 是 凸 函 数 ， g j ( x ) 是 仿 射 函 数 其中h_i(x)和f(x)都是凸函数，g_j(x)是仿射函数 其中hi​(x)和f(x)都是凸函数，gj​(x)是仿射函数

很多人看到这里，可能会一拍脑袋：这不是KKT条件里的式子吗？没错，KKT条件，或者说拉格朗日乘子法本质上就是解决了一个凸优化问题。

SVM里花了那么多的功夫做对偶变换，只为了最后和你说一句：因为对偶问题一定是凸优化问题。为什么要转换成凸优化问题呢？

因为凸优化有一个很重要的性质：局部最优点必定是全局最优点。

关于这一点也很好证。我们假设 ∃ x 0 \exists x_0 ∃x0​，它是函数的局部最优点，另 ∃ x 1 ≠ x 0 \exists x_1 \neq x_0 ∃x1​​=x0​，它是函数的全局最优点。我们不妨假设 x 1 > x 0 x_1>x_0 x1​>x0​，随后 ∀ 0 < δ < x 1 − x 0 , ∃ k = x 0 − x 1 + δ x 0 − x 1 , 0 < k < 1 \forall 0 < \delta