Duality

对偶是优化里非常重要的一个工具。

拉格朗日对偶函数

对偶问题是研究优化问题的有力武器。考虑一个具有标准形式的优化问题：

$$\begin{array}{ll}\mathrm{minimize}& f_0(x)\\ \text{subject to }& f_i(x)\le 0,i=1,\dots ,m\\ & h_i(x)=0,i=1,\dots ,p\end{array}$$

记整个的可行域为 $\mathcal{D}$，定义上述问题对应的 拉格朗日函数（Lagrangian） 为

$$L(x,\lambda ,\nu )=f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x)$$

其中 ${\lambda }_i,{\nu }_i$ 称为拉格朗日乘子（Lagrange multiplier），或者对偶变量。 $\mathrm{dom}L=\mathcal{D}\times {\mathbf{R}}^m\times {\mathbf{R}}^p$

接着，我们定义拉格朗日对偶函数（Lagrange dual function） $g:{\mathbf{R}}^m\times {\mathbf{R}}^p\to \mathbf{R}$：

$$g(\lambda ,\nu )=\underset{x\in \mathcal{D}}{inf}L(x,\lambda ,\nu )=\underset{x\in \mathcal{D}}{inf}(f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x))$$

如果拉格朗日函数没有下界，就记 $g=-\mathrm{\infty }$。$L(x,\lambda ,\nu )$ 是关于 $\lambda ,\nu$ 的仿射函数，从而，对偶函数 $g$ 是一个凹函数，即使原来的优化问题不是凸的。

假设 $\tilde{x}\in \mathcal{D}$，如果 $\lambda ⪰0$ ，我们可以得到：

$$\sum _{i=1}^m{\lambda }_i{f}_i(\tilde{x})+\sum _{i=1}^p{\nu }_i{h}_i(\tilde{x})\le 0$$

进而：

$$g(\lambda ,\nu )=\underset{x\in \mathcal{D}}{inf}L(x,\lambda ,\nu )\le L(\tilde{x},\lambda ,\nu )\le f_0(\tilde{x})$$

因为 $g(\lambda ,\nu )\le f_0(\tilde{x})$ 对 $\mathrm{\forall }\tilde{x}\in \mathcal{D}$ 都成立，对两边取下确界，就有：

$$g(\lambda ,\nu )\le p^{\ast }$$

$p^{\ast }$ 是优化问题的最优值。

这说明，原优化问题的最优值是对偶函数的一个上界！ 这个性质是接下来提出对偶问题的基本出发点。

如果是一个 maximize 的问题，拉格朗日函数应为： $$L(x,\lambda ,\nu )=f_0(x)-\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x)$$ 对偶函数为： $$g(\lambda ,\nu )=\underset{x\in \mathcal{D}}{sup}L(x,\lambda ,\nu )\ge L(\tilde{x},\lambda ,\nu )\ge f_0(\tilde{x})$$

对偶函数可以用来求一个困难问题的界。例如下面这个非凸最优化问题：

$$\begin{array}{ll}\mathrm{minimize}& x^{T}Wx\\ \text{subject to }& x_i^2=1,i=1,\dots ,n\end{array}$$

它其实是一个组合问题，向量 $x$ 的每个分量要么是 $1$ 要么是 $-1$。写出它的拉格朗日函数：

$$\begin{array}{rl}L(x,\nu )& =x^{T}Wx+\sum _{i=1}^n{\nu }_i(x_i^2-1)\\ & =x^T(W+\mathrm{diag}(\nu ))x-{\mathbf{1}}^T\nu \end{array}$$

对偶函数：

$$\begin{array}{rl}g(\nu )& =\underset{x}{inf}{x}^T(W+\mathrm{diag}(\nu ))x-{\mathbf{1}}^T\nu \\ & =\{\begin{array}{ll}-{\mathbf{1}}^T\nu & W+\mathrm{diag}(\nu )⪰0\\ -\mathrm{\infty }& \text{ otherwise }\end{array}\end{array}$$

为了得到原问题的一个下界，我们可以取一个特殊的对偶变量：

$$\nu =-{\lambda }_{min}(W)\mathbf{1}$$

这时

$$W+\mathrm{diag}(\nu )=W-{\lambda }_{min}(W)I⪰0$$

是对偶可行的。最终我们得到原问题的一个下界：

$$p^{\star }\ge -{\mathbf{1}}^T\nu =n{\lambda }_{min}(W)$$

当然，这个下界也可以将原问题的约束条件放宽成 $\sum _{i=1}^n{x}_i^2=n$ 来得到。

在这里，原问题是一个难解的组合问题，但是对偶问题是一个容易解的SDP。

对偶函数与共轭函数

【重写】

回想一下，$f$ 的共轭函数被定义为：

$$f^{\ast }(y)=\underset{x\in \mathrm{dom}f}{sup}(y^{T}x-f(x))$$

共轭函数与对偶函数具有紧密的关系。考虑以下问题：

$$\begin{array}{ll}\mathrm{minimize}& f_0(x)\\ \text{subject to }& Ax⪯b\\ & Cx=d\end{array}$$

它的对偶函数：

$$\begin{array}{rl}g(\lambda ,\nu )& =\underset{x}{inf}(f_0(x)+{\lambda }^T(Ax-b)+{\nu }^T(Cx-d))\\ & =-b^T\lambda -d^T\nu +\underset{x}{inf}(f_0(x)+{(A^T\lambda +C^T\nu )}^{T}x)\\ & =-b^T\lambda -d^T\nu -\underset{x}{sup}(-{(A^T\lambda +C^{T}v)}^{T}x-f_0(x))\\ & =-b^T\lambda -d^T\nu -f_0^{\ast }(-A^T\lambda -C^T\nu )\end{array}$$

同时 $g$ 的定义域：

$$\mathrm{dom}g=\{(\lambda ,\nu )|-A^T\lambda -C^T\nu \in \mathrm{dom}{f}_0^{\ast }\}$$

一般地，对于某些特殊形式的优化问题，可以通过共轭函数的形式来表示对偶函数。

拉格朗日对偶问题

既然对偶函数的每一个函数值都是原问题的下界，那么是否可以通过计算对偶函数的最大值来逼近原问题的最优值呢？这就导出了拉格朗日对偶问题：

$$\begin{array}{ll}\text{ maximize }& g(\lambda ,\nu )\\ \text{ subject to }& \lambda ⪰0\end{array}$$

其中 $\mathrm{dom}g=\{(\lambda ,\nu )|g(\lambda ,\nu )>-\mathrm{\infty }\}$。

求解拉格朗日对偶问题的好处在于，无论原问题是不是凸问题，对偶问题都是凸优化类问题！

对偶问题的约束条件，往往来源于$\mathrm{dom}g=\{(\lambda ,\nu )|g(\lambda ,\nu )>-\mathrm{\infty }\}$这个定义域的要求！

对偶问题同样会有最优值，我们将$({\lambda }^{\ast },{\nu }^{\ast })$称为对偶变量最优值（dual optimal）或者最优拉格朗日乘子（optimal Lagrange multipliers）。

几类优化问题的对偶问题

以下列举一些常见优化问题的对偶问题的形式

线性规划

考虑不等式形式的线性规划：

$$\begin{array}{ll}\mathrm{minimize}& c^{T}x\\ \text{subject to }& Ax⪯b\end{array}$$

它的对偶函数：

$$g(\lambda )=\underset{x}{inf}L(x,\lambda )=-b^T\lambda +\underset{x}{inf}{(A^T\lambda +c)}^{T}x$$

从而：

$$g(\lambda )=\{\begin{array}{ll}-b^T\lambda & A^T\lambda +c=0\\ -\mathrm{\infty }& \text{ otherwise }\end{array}$$

所以它的对偶问题是：

$$\begin{array}{ll}\mathrm{maximize}& -b^T\lambda \\ \text{subject to }& A^T\lambda +c=0,\lambda ⪰0.\end{array}$$

以上是不等式形式的对偶。接下来考虑标准形式的线性规划：

$$\begin{array}{ll}\mathrm{minimize}& c^{T}x\\ \text{subject to }& Ax=b\\ & x⪰0\end{array}$$

对偶函数：

$$g(\lambda ,\nu )=\{\begin{array}{ll}-b^T\nu & A^T\nu -\lambda +c=0\\ -\mathrm{\infty }& \text{ otherwise }\end{array}$$

对偶问题：

$$\begin{array}{ll}\text{ maximize }& -b^T\nu \\ \text{ subject to }& A^T\nu -\lambda +c=0,\lambda ⪰0\end{array}$$

也可以写成：

$$\begin{array}{ll}\text{ maximize }& b^T\nu \\ \text{ subject to }& A^T\nu +\lambda =c,\lambda ⪰0\end{array}$$

这也是锥形式下线性规划标准形式的对偶。

也可以写成不等式形式：

$$\begin{array}{ll}\text{ maximize }& b^T\nu \\ \text{ subject to }& A^T\nu ⪯c\end{array}$$

线性规划的不等式形式的对偶问题的形式是等式，而线性规划的等式形式的对偶问题的形式可以写成不等式。

等式约束的二次规划

考虑问题：

$$\begin{array}{ll}\mathrm{minimize}& x^{T}x\\ \text{subject to }& Ax=b\end{array}$$

拉格朗日函数：$$L(x,\nu )=x^{T}x+{\nu }^T(Ax-b)$$

$${\mathrm{\nabla }}_{x}L(x,\nu )=2x+A^T\nu =0\Rightarrow x=-(1/2)A^T\nu$$

从而有对偶函数：

$$g(\nu )=L(-(1/2)A^T\nu ,\nu )=-(1/4){\nu }^{T}A{A}^T\nu -b^T\nu$$

对偶问题：

$$\mathrm{maximize}-(1/4){\nu }^{T}A{A}^T\nu -b^T\nu$$

这是一个无约束的凹函数最大化问题！（自然可以转化为无约束的凸优化问题）。从而我们知道，原问题是约束优化问题，对偶问题可能是无约束的问题！

QCQP

考虑：

$$\begin{array}{ll}\mathrm{minimize}& (1/2)x^T{P}_{0}x+q_0^{T}x+r_0\\ \text{subject to }& (1/2)x^T{P}_{i}x+q_i^{T}x+r_i\le 0,i=1,\dots ,m\end{array}$$

拉格朗日函数：

$$L(x,\lambda )=(1/2)x^{T}P(\lambda )x+q(\lambda {)}^{T}x+r(\lambda )$$

其中：

$$P(\lambda )=P_0+\sum _{i=1}^m{\lambda }_i{P}_i,q(\lambda )=q_0+\sum _{i=1}^m{\lambda }_i{q}_i,r(\lambda )=r_0+\sum _{i=1}^m{\lambda }_i{r}_i$$

在 $\lambda ⪰0$ 时，$P(\lambda )$ 是正定的，从而：

$$g(\lambda )=\underset{x}{inf}L(x,\lambda )=-(1/2)q(\lambda {)}^{T}P(\lambda {)}^{-1}q(\lambda )+r(\lambda )$$

所以有对偶问题：

$$\begin{array}{ll}\mathrm{maximize}& -(1/2)q(\lambda {)}^{T}P(\lambda {)}^{-1}q(\lambda )+r(\lambda )\\ \text{subject to }& \lambda ⪰0\end{array}$$

【添加一些问题的对偶】

弱对偶性与强对偶性

记 $d^{\ast }$ 是对偶问题的最优值，通过上面的推证，我们有：

$$d^{\ast }\le p^{\ast }$$

这个性质称为弱对偶性，它甚至不要求原问题是凸的。

弱对偶性可以推广到取值为无穷的情况：

• 如果 $p^{\ast }=-\mathrm{\infty }$，原问题最优值是无界的，则必然有 $d^{\ast }=-\mathrm{\infty }$，也就是对偶问题不可行。
• 如果 $d^{\ast }=+\mathrm{\infty }$，对偶问题最优值无界，也必然成立 $p^{\ast }=+\mathrm{\infty }$，也就是说，原问题不可行。

也可能出现情况：$d^{\ast }=-\mathrm{\infty },p^{\ast }=+\mathrm{\infty }$，即原问题和对偶问题都不可行！

如线性规划的原问题： $$\begin{array}{rl}min& x_1+2x_2\\ \text{ s.t. }& x_1+x_2=1\\ & 2x_1+2x_2=3\end{array}$$ 和对偶问题： $$\begin{array}{rl}max& y_1+3y_2\\ \text{ s.t. }& y_1+2y_2=1\\ & y_1+2y_2=2\end{array}$$ 都不可行！

$p^{\ast }-d^{\ast }$ 称作对偶间隙（optimal duality gap）。如果 $p^{\ast }=d^{\ast }$，我们就称强对偶性成立，这意味着，对偶问题的最优值恰好就是原问题的最优值。因此，如果对偶问题更易求解的话，我们往往能够方便地给原问题提供一个下界。

弱对偶性是一定严格成立的，强对偶性就未必了。

如果原问题是凸的，通常来说强对偶性是会成立的。建立在凸性上的成立强对偶性的条件有很多，我们把这些条件称作：constraint qualifications。

Slater's condition 是强对偶性成立的一个充分条件。如果问题是凸的，并且： $$\mathrm{\exists }\tilde{x}\in \mathcal{D},\mathrm{s}.\mathrm{t}.f_i(\tilde{x})<0,A\tilde{x}=b$$

这样的点有时候叫做严格可行（strictly feasible）。在这个条件成立的同时，对偶可行解（如果有限）是可以取到的。

强对偶性成立的问题

minimax 定理

对于两人零和博弈，可以只使用一个矩阵 $A$ 来表示，用向量 $x,y$ 分别表示两个人的策略，那么 payoff 就是 $\pm y^{T}Ax$，这里说明，强对偶性可以用来证明 minimax 定理的一种特殊情况： $$\underset{x}{max}(\underset{y}{min}{y}^{T}Ax)=\underset{y}{min}(\underset{x}{max}{y}^{T}Ax)$$ 其中 $x,y\ge 0,x^T\mathbf{1}=y^T\mathbf{1}=1$。

在优化问题构建的过程中蕴含了博弈论里的 indifference principle

row player 面临如下的优化问题： $$\begin{array}{cl}min& \underset{i=1,\dots ,n}{max}(A^{T}y{)}_i\\ \text{s.t.}& y\ge 0,y^T\mathbf{1}=1\end{array}$$ 等价于： $$\begin{array}{cl}min& t\\ \text{s.t.}& y\ge 0,y^T\mathbf{1}=1\\ & A^{T}y\le t\mathbf{1}\end{array}$$ 不难写出它的对偶： $$\begin{array}{}\text{(ast)}& \begin{array}{ll}max& \nu \\ \text{ s.t. }& \lambda \ge 0,{\mathbf{1}}^T\lambda =1\\ & A\lambda \ge \nu \mathbf{1}.\end{array}\end{array}$$ column player 面临的优化问题是： $$\begin{array}{cl}max& \underset{i=1,\dots ,m}{min}(Ax{)}_i\\ \text{s.t.}& x\ge 0,x^T\mathbf{1}=1\end{array}$$ 实际上这个问题就是(*)式，根据强对偶性，两个问题的最优值相等。

几何解释

记 $\mathcal{G}=\{(f_1(x),\dots ,f_m(x),h_1(x),\dots ,h_p(x),f_0(x))\in {\mathbf{R}}^m\times {\mathbf{R}}^p\times \mathbf{R}|x\in \mathcal{D}\}$，这是一个把目标函数和所有约束都考虑进来的集合。

原问题的最优解可以很容易用 $\mathcal{G}$ 来表示： $$p^{\star }=inf\{t|(u,v,t)\in \mathcal{G},u⪯0,v=0\}$$ 用 $\mathcal{G}$ 还能来表示对偶函数： $$g(\lambda ,\nu )=inf\{(\lambda ,\nu ,1{)}^T(u,v,t)|(u,v,t)\in \mathcal{G}\}$$ 从而我们可以得到弱对偶性： $$\begin{array}{rl}{p}^{\star }& =inf\{t|(u,v,t)\in \mathcal{G},u⪯0,v=0\}\\ & \ge inf\{(\lambda ,\nu ,1{)}^T(u,v,t)|(u,v,t)\in \mathcal{G},u⪯0,v=0\}\\ & \ge inf\{(\lambda ,\nu ,1{)}^T(u,v,t)|(u,v,t)\in \mathcal{G}\}\\ & =g(\lambda ,\nu )\end{array}$$

鞍点

鞍点这个词，顾名思义，来自马鞍。如上图中标注出的点，它在一个方向上使函数值达到最小，而在另一个方向上使函数达到最大。在光滑的条件下，判断鞍点的一个充分条件是函数在一阶导数为零处（驻点）的Heisen矩阵为不定矩阵。

且先考虑这么一个拉格朗日函数：

$$\begin{array}{rl}\underset{\lambda ⪰0}{sup}L(x,\lambda )& =\underset{\lambda ⪰0}{sup}(f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x))\\ & =\{\begin{array}{ll}{f}_0(x)& f_i(x)\le 0,i=1,\dots ,m\\ +\mathrm{\infty }& \text{ otherwise }\end{array}\end{array}$$

如果原优化问题不可行，那么 $\underset{\lambda ⪰0}{sup}L(x,\lambda )$ 可以取到 $+\mathrm{\infty }$，而如果 $x$ 满足约束条件，就只能等于目标函数。所以：

$$p^{\star }=\underset{x}{inf}\underset{\lambda ⪰0}{sup}L(x,\lambda )$$

而根据对偶问题的定义，又有：

$$d^{\star }=\underset{\lambda ⪰0}{sup}\underset{x}{inf}L(x,\lambda )$$

所以弱对偶性等价于：

$$\underset{\lambda ⪰0}{sup}\underset{x}{inf}L(x,\lambda )\le \underset{x}{inf}\underset{\lambda ⪰0}{sup}L(x,\lambda )$$

强对偶性等价于：

$$\underset{\lambda ⪰0}{sup}\underset{x}{inf}L(x,\lambda )=\underset{x}{inf}\underset{\lambda ⪰0}{sup}L(x,\lambda )$$

事实上， $$\underset{z\in Z}{sup}\underset{w\in W}{inf}f(w,z)\le \underset{w\in W}{inf}\underset{z\in Z}{sup}f(w,z)$$ 总是成立的！这叫做 maxmin-inequality.

称 $\tilde{w}\in W,\tilde{z}\in Z$ 是 $f$ 的鞍点（saddle point），如果

$$f(\tilde{w},z)\le f(\tilde{w},\tilde{z})\le f(w,\tilde{z}),\mathrm{\forall }w\in W,\mathrm{\forall }z\in Z$$

换句话说， $\tilde{w}$ 最小化 $f(w,\tilde{z})$， $\tilde{z}$ 最大化 $f(\tilde{w},z)($ over $z\in Z)$ :

$$f(\tilde{w},\tilde{z})=\underset{w\in W}{inf}f(w,\tilde{z}),f(\tilde{w},\tilde{z})=\underset{z\in Z}{sup}f(\tilde{w},z)$$

所以说，如果 $x^{\ast }$ 和 ${\lambda }^{\ast }$ 分别是原问题和对偶问题的最优点，那么 $(x^{\ast },{\lambda }^{\ast })$ 就是拉格朗日函数的鞍点！反之也是成立的。

Optimality conditions

Complementary slackness

对于任意的问题，如果强对偶性成立，记 $x^{\star }$ 和 $({\lambda }^{\star },{\nu }^{\star })$ 分别是原问题和对偶问题的最优解，那么：

$$\begin{array}{rl}{f}_0\left(x^{\star }\right)& =g({\lambda }^{\star },{\nu }^{\star })\\ & =\underset{x}{inf}(f_0(x)+\sum _{i=1}^m{\lambda }_i^{\star }{f}_i(x)+\sum _{i=1}^p{\nu }_i^{\star }{h}_i(x))\\ & \le f_0\left(x^{\star }\right)+\sum _{i=1}^m{\lambda }_i^{\star }{f}_i\left(x^{\star }\right)+\sum _{i=1}^p{\nu }_i^{\star }{h}_i\left(x^{\star }\right)\\ & \le f_0\left(x^{\star }\right)\end{array}$$

这意味着：

$$\sum _{i=1}^m{\lambda }_i^{\star }{f}_i\left(x^{\star }\right)=0$$

进而有：

$${\lambda }_i^{\star }{f}_i\left(x^{\star }\right)=0,i=1,\dots ,m$$

这就是互补松弛性！(complementary slackness)

如果 ${\lambda }_i^{\ast }>0$，就有 $f_i(x^{\ast })=0$；如果 $f_i(x^{\ast })<0$，那么 ${\lambda }_i^{\ast }=0$。每一个约束都有与它对应的对偶变量（乘子），如果乘子大于0，那么约束必然是紧的 (binding)；如果约束不是紧的 (unbinding)，那么乘子必然为0。

有解 的线性规划必然成立互补松弛定理，它可以看成是强对偶性下的互补松弛的一个特例。

并且，因为线性规划的对偶的对偶就是它本身，这两重对偶的互补松弛性可以揭示线性规划 primal and dual optimality。这是线性规划的 primal-dual method 的思想。

KKT optimality conditions

进一步假设这些函数都是可微的（并没有凸性的假设）。记 $x^{\ast }$ 和 $({\lambda }^{\ast },{\nu }^{\ast })$ 分别是原问题和对偶问题的最优解，且强对偶性成立，因为 $x^{\ast }$ 最小化了 $L(x,{\lambda }^{\ast },{\nu }^{\ast })$，所以： $$\mathrm{\nabla }{f}_0\left(x^{\star }\right)+\sum _{i=1}^m{\lambda }_i^{\star }\mathrm{\nabla }{f}_i\left(x^{\star }\right)+\sum _{i=1}^p{\nu }_i^{\star }\mathrm{\nabla }{h}_i\left(x^{\star }\right)=0$$ 于是，加上互补松弛条件和问题本身的约束，我们有：

$$\begin{array}{rl}{f}_i\left(x^{\star }\right)& \le 0,i=1,\dots ,m\\ h_i\left(x^{\star }\right)& =0,i=1,\dots ,p\\ {\lambda }_i^{\star }& ⪰0,i=1,\dots ,m\\ {\lambda }_i^{\star }{f}_i\left(x^{\star }\right)& =0,i=1,\dots ,m\\ \mathrm{\nabla }{f}_0\left(x^{\star }\right)+\sum _{i=1}^m{\lambda }_i^{\star }\mathrm{\nabla }{f}_i\left(x^{\star }\right)+\sum _{i=1}^p{\nu }_i^{\star }\mathrm{\nabla }{h}_i\left(x^{\star }\right)& =0,\end{array}$$

这就是KKT条件（Karush-Kuhn-Tucker conditions）。总结一下，对任何有着可微目标函数与约束的优化问题，只要强对偶性成立，那么其最优值 $x^{\ast }$ 和对偶最优 $({\lambda }^{\ast },{\nu }^{\ast })$ 就必然成立KKT条件。

在这里，KKT条件的证明，前提是强对偶性，针对的是全局最优点，利用了对偶函数的性质。

简而言之，强对偶性（能取到最优解）$\Rightarrow$ 全局最优点成立KKT条件。注意这里是全局最优而不是局部最优！

强对偶性成立下KKT条件是优化问题最优解的必要条件！

• 例如问题：$$\begin{gathered} minx \\ \text{s.t. }{x}^2\le 0 \end{gathered}$$ 就在最优点（$x=0$）处不成立KKT条件。它的对偶问题是： $max;-\frac{1}{4\lambda }st.\lambda >0$虽然强对偶性还是成立的（$d^=p^=0$），但是对偶问题没有办法取到最优解。

如果这个优化问题还是凸的，那么KKT条件还能提供充分性。

利用KKT条件对最优解的充分性，可以把求凸优化的最优解转化为求满足KKT条件的点。

比如等式约束的二次规划问题可以利用KKT条件求解。对 $$\begin{array}{ll}\mathrm{minimize}& (1/2)x^{T}Px+q^{T}x+r\\ \text{subject to }& Ax=b\end{array}$$ 它的KKT条件是： $$A{x}^{\star }=b,P{x}^{\star }+q+A^T{\nu }^{\star }=0$$ 写成矩阵形式就是： $$\left[\begin{array}{cc}P& A^T\\ A& 0\end{array}\right]\left[\begin{array}{l}{x}^{\star }\\ {\nu }^{\star }\end{array}\right]=\left[\begin{array}{c}-q\\ b\end{array}\right]$$

关于KKT条件对局部最优解的论述，参见：KKT的进一步论述

替代定理（Theorem of alternatives）

在这一部分，将要使用对偶理论来讨论一系列约束的可行性。

约束的可行性，可以用优化的理论进行等价表述：

$$f_i(x)\le 0,i=1,\dots ,m,h_i(x)=0,i=1,\dots ,p$$

这个约束是否可行，可以链接到一个优化问题的最优值上。

$$\begin{array}{}\text{(ast)}& \begin{array}{ll}\mathrm{minimize}& 0\\ \text{subject to }& f_i(x)\le 0,i=1,\dots ,m\\ & h_i(x)=0,i=1,\dots ,p\end{array}\end{array}$$

且：

$$p^{\star }=\{\begin{array}{ll}0& (\ast )\text{ is feasible }\\ \mathrm{\infty }& (\ast )\text{ is infeasible }\end{array}$$

写出这个优化问题的对偶函数：

$$g(\lambda ,\nu )=\underset{x\in \mathcal{D}}{inf}(\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x))$$

注意到 $g(\lambda ,\nu )$ 是齐次函数，即 $g(t\lambda ,t\nu )=tg(\lambda ,\nu ),\mathrm{\forall }t>0$。所以：对偶问题的最优值：

$$d^{\star }=\{\begin{array}{ll}\mathrm{\infty }& \lambda ⪰0,g(\lambda ,\nu )>0\text{ is feasible }\\ 0& \lambda ⪰0,g(\lambda ,\nu )>0\text{ is infeasible. }\end{array}$$

弱对偶性告诉我们，至少成立 $d^{\ast }\le p^{\ast }$，所以，如果 $d^{\ast }=\mathrm{\infty }$，那么必然 $p^{\ast }=\mathrm{\infty }$；如果 $p^{\ast }=0$，那么必然 $d^{\ast }=0$！这说明，这里的原问题和对偶问题，最多只有一个是可行（feasible）的！这叫做weak alternatives。

如果$p^{\ast }=\mathrm{\infty },d^{\ast }=0$，那么意味着都不可行。一个可行能推出另一个不可行，但一个不可行却不能推出另一个可行，所以称作弱 替代（以区别下面的强替代）

回想一下求最大的LP问题的对偶问题没有可行解，那么原问题无上界。

接下来，进一步考虑严格不等式约束的两组条件：

$$\begin{array}{}\text{(1)}& f_i(x)<0,i=1,\dots ,m,h_i(x)=0,i=1,\dots ,p\end{array}$$

$$\begin{array}{}\text{(2)}& \lambda ⪰0,\lambda \ne 0,g(\lambda ,\nu )\ge 0\end{array}$$

容易证明，它们满足弱替代性。

有了弱替代性，自然会想到强替代性，能不能在某种条件下，原问题和对偶问题的可行域有且只有一个可行呢？

弱替代性不要求原约束条件的凸性。为了得到强替代性，凸性，自然是必须的！

考虑一组“凸”的约束条件：

$$\begin{array}{}\text{(3)}& f_i(x)<0,i=1,\dots ,m,Ax=b,\text{let}\mathcal{D}={\cap }_i^m\mathrm{d}\mathrm{o}\mathrm{m}{f}_i\end{array}$$

和它的 alternative：

$$\begin{array}{}\text{(4)}& \lambda ⪰0,\lambda \ne 0,g(\lambda ,\nu )\ge 0\end{array}$$

这里还需要一个条件，就是式(3)的还要成立 $\mathrm{\exists }\tilde{x}\in \mathrm{r}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{t}\mathcal{D},st.A\tilde{x}=b$，在这种条件下，强替代性是成立的！

如果$\mathcal{D}={\mathbf{R}}^n$，那么这个条件就总是成立的。

考虑关于(3)式的优化问题： $$\begin{array}{ll}\mathrm{minimize}& s\\ \text{subject to }& f_i(x)-s\le 0,i=1,\dots ,m\\ & Ax=b\end{array}$$ 如果(3)式的可行域非空，那么上面的优化问题的最优值$p^{\ast }<0$。它的对偶问题是： $$\begin{array}{ll}\mathrm{maximize}& g(\lambda ,\nu )\\ \text{subject to }& \lambda ⪰0,{\mathbf{1}}^T\lambda =1\end{array}$$ Slater's 条件在这里是成立的，所以强对偶性是成立的！由此不难继续推导出强替代性的成立。

另外，还有一种情况也成立强替代性：

这里也需要对第一个约束，成立$\mathrm{\exists }\tilde{x}\in \mathrm{r}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{t}\mathcal{D},st.A\tilde{x}=b$这个条件。

线性关系是最容易导出强替代性的，下面列举一些例子：

例1：Farkas 引理

1. $Ax=b,x\ge 0$
2. $A^{T}y\ge 0,b^{T}y<0$

有且仅有一个可行。可以使用如下的一组对偶

$$(\mathcal{P})\begin{array}{ll}\mathrm{minimize}& c^{T}x\\ \text{subject to }& Ax=b,x\ge 0\end{array}(\mathcal{D})\begin{array}{l}\mathrm{maximize}{b}^{T}y\\ \text{subject to }{A}^{T}y\le c\end{array}$$

例2：Gordan 定理

1. $Ax=0,x\ge 0,x\ne 0$
2. $A^{T}y>0$

有且仅有一个可行。可以使用如下的一组对偶： $$(\mathcal{P})\begin{array}{ll}\mathrm{minimize}& {\mathbf{1}}^{T}x\\ \text{subject to }& Ax=0,x⪰0\end{array}(\mathcal{D})\begin{array}{l}\mathrm{maximize}0\\ \text{subject to }{A}^{T}y⪰\mathbf{1}\end{array}$$ 例3：

1. $Ax\prec b$
2. $y\ne 0,y⪰0,A^{T}y=0,y^{T}b\le 0$

有且仅有一个可行。可以使用如下的一组对偶： $$(\mathcal{P})\begin{array}{ll}\mathrm{minimize}& 0\\ \text{subject to }& Ax\le b\end{array}(\mathcal{D})\begin{array}{l}\mathrm{maximize}-b^{T}y\\ \text{subject to }{A}^{T}y=0,y⪰0\end{array}$$

Generalized inequalities

接下来我们讨论广义不等式下的对偶，这也叫做锥形式的对偶。这种优化问题具有标准形式： $$\begin{array}{ll}\mathrm{minimize}& f_0(x)\\ \text{subject to }& f_i(x){⪯}_{K_i}0,i=1,\dots ,m\\ & h_i(x)=0,i=1,\dots ,p\end{array}$$ 类似地，我们可以定义拉格朗日函数： $$L(x,\lambda ,\nu )=f_0(x)+{\lambda }_1^T{f}_1(x)+\cdots +{\lambda }_m^T{f}_m(x)+{\nu }_1{h}_1(x)+\cdots +{\nu }_p{h}_p(x)$$ 和对偶函数： $$g(\lambda ,\nu )=\underset{x\in \mathcal{D}}{inf}L(x,\lambda ,\nu )=\underset{x\in \mathcal{D}}{inf}(f_0(x)+\sum _{i=1}^m{\lambda }_i^T{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x))$$ 注意，这里的 ${\lambda }_i{⪰}_{K^{\ast }}0$ 在 $K$ 的对偶锥里，根据对偶锥的性质，我们就有： $${\lambda }_i^T{f}_i(x)\le 0$$ **这一点保证了弱对偶性的成立！**因此对偶问题具有如下形式： $$\begin{array}{ll}\mathrm{maximize}& g(\lambda ,\nu )\\ \text{subject to }& {\lambda }_i{⪰}_{K_i^{\ast }}0,i=1,\dots ,m\end{array}$$

强对偶性的Slater's condition可以推广到锥形式的对偶下。即，如果问题是凸的，即 $f_0$ 凸、$f_i$ 关于 $K_i$ 凸，且存在一点 $\tilde{x}$ 严格可行，那么强对偶成立，对偶间隙为0。

锥规划依然成立互补松弛条件、KKT条件、替代定理，在此从略。

minimax theorem

$$\underset{\mathit{z}\in \cap Z_i}{max}{\mathit{x}}^{\mathrm{\prime }}\mathit{z}=\underset{{\mathit{x}}_i,i\in [I]}{min}\{\sum _{i\in [I]}\underset{\mathit{z}\in Z_i}{max}{\mathit{x}}_i^{\mathrm{\prime }}\mathit{z}\mid \sum _{i\in [I]}{\mathit{x}}_i=\mathit{x}\}$$