原问题和对偶问题

原问题

$$\begin{aligned} \min \quad & f(x) \\ s.t. \quad & g_i(x) \leq 0 \qquad i=1,...,m\\ & h_j(x)=0 \qquad j=1,...,l \\ & x \in X \end{aligned}$$

对偶问题

$$\begin{aligned} \max \ &\inf\ \bigg \{ f(x)+\sum_{i=1}^m\mu_ig_i(x)+\sum_{j=1}^l\xi_ih_j(x)\bigg\} \\ s.t. \quad &\mu_i \geq 0 \qquad i=1,...,m \end{aligned}$$

问题简化

为了便于用几何描述原问题和对偶问题的关系，把问题简化

简化后的原问题

$$\begin{aligned} \min \quad & f(x) \\ s.t. \quad & g(x) \leq 0\\ & h(x)=0\\ & x \in X \end{aligned}$$

简化后的对偶问题

$$\begin{aligned} \max \ &\inf\ \bigg \{ f(x)+\mu g(x)+\xi h(x)\bigg\} \\ s.t. \quad &\mu \geq 0 \end{aligned}$$

几何解释

强对偶

对偶问题的优化目标是最大化$f(x),h(x),g(x)$的线性组合的最小值，而这如何等价于在限制下最小化$f(x)$，需要观察$f(x),h(x),g(x)$的线性组合
将X集合中的所有元素x都通过变换投影到集合G中:
$$G={[h(x),g(x),f(x)], x \in X}$$
显然，G在$f(x),h(x),g(x)$的张成空间内。
为了在图形中表达对偶问题的优化过程，鉴于原问题的限制中有$h(x)=0$，再简化一下问题，只考虑对偶问题的G中位于$h(x)=0$薄片内的元素。如下图所示，因为最小值必须是G中最低的位置，又受到$g(x)\leq 0$的限制，所以原问题的最小值$f(x)_{min}$位于图中的红点位置。

对偶问题的目标函数是$f(x)+ug(x)$，我们令$a=f(x)+\mu g(x)$，它可以看作是[g(x),f(x)]平面内的直线$-\mu g(x)+a=f(x)$, 其中$-\mu$为斜率，a为截距。注意对偶问题中要求$\mu \leq 0$，因此我们只考虑斜率为负的情形。而直线的截距则是对偶问题的目标。

原问题中要求$x \in X$，那么对偶问题中$[h(x),g(x),f(x)]$必须在G内，$a=f(x)+\mu g(x)$的中的f(x)和g(x)必须在G以内，也就是说直线$a=f(x)+\mu g(x)$必须经过G。
固定$\mu$不变，为了取到下界$\inf{f(x)+\mu g(x)}$，必须保证直线$a=f(x)+\mu g(x)$与G的下边缘相切。只有相切才能让$a=f(x)+\mu g(x)$取到下界，而x不超出G的范围。