对偶问题几何解释

一直以来对对偶问题的几何解释比较懵逼
最近看到一张PPT，对理解这个问题有一些帮助，搬过来了

假设我们要求解原问题

m i n f (x), s . t . g (x) < = 0, x \in X

定义如下集合：

G = (y, z) : y = g (x), z = f (x) f o r s o m e x \in X

那么(y,z) 的几何图形如下图所示。最小化f(x),其实就是寻找使得y<=0 同时z最小的点，很明显(y¯,z¯)是使得z最小的点

对偶问题就是求解

m a x α (u), s . t . u > 0

当y=0时，z取得最小值，其实就是通过平移，转动直线α=z+uy使得z的值最小。那么就只有红色的点满足要求。

对偶问题几何解释

这幅图片是对非凸问题，原问题和对偶问题间隙的一个解释，原问题的最优解就比对偶问题的最优解大，且对偶间隙不为0.

对偶问题几何解释