择一定理

通过对偶函数建立弱择一性

对约束系统的定义如下

$$\begin{array}{rl}{f}_i(x)& ⩽0,i=1,\cdots ,m\\ h_i(x)& =0,i=1,\cdots ,p\end{array}$$

考虑不等式和等式约束的系统的可行性，即求解如下优化问题

$$\begin{array}{rl}\mathrm{minimize}& 0\\ \mathrm{subject}\mathrm{to}& f_i(x)⩽0,i=1,\cdots ,m\\ & h_i(x)=0,i=1,\cdots ,p\end{array}$$

此问题的最优值显然只有两种情况：

• $p^{\star }=0$：约束是可行的。
• $p^{\star }=\mathrm{\infty }$：约束是不可行的。

对偶函数

$$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))$$

同理，对偶问题的最优值同样也只有两种情况：

• $d^{\star }=\mathrm{\infty }$：$\lambda ⪰0,g(\lambda ,\nu )>0$ 可行。
• $d^{\star }=0$：$\lambda ⪰0,g(\lambda ,\nu )>0$ 不可行。

也就是说，原问题和对偶问题关于约束是否可行的情况正好相反。事实上，可以将不等式

$$\begin{array}{rl}\lambda & ⪰0\\ g(\lambda ,\nu )& >0\end{array}$$

看作是系统不可行的证明或认证。

如果两个不等式（等式）系统至多有一个可行，则称之为弱择一的。无论不等式是否是凸的，上述结论都成立；此外，择一不等式系统总是凸的。

严格不等式

同样可以分析具有严格不等式系统的可行性，我们得到择一不等式系统如下

$$\begin{array}{rl}\lambda & ⪰0\\ \lambda & \ne 0\\ g(\lambda ,\nu )& ⩾0\end{array}$$

强择一

当原不等式系统是凸的，即函数 $f_i$ 是凸函数，$h_i$ 是仿射函数，且某些类型的约束准则成立是，那么上述描述的弱择一的两个系统是强择一的，即恰有一个系统可行。换而言之，两个不等式系统中的任意一个可行，当且仅当另一个不可行。

不等式系统可以描述为

$$\begin{array}{rl}{f}_i(x)& ⩽0,i=1,\cdots ,m\\ Ax& =b\end{array}$$

严格不等式

严格不等式系统的强择一还需要满足：存在一点 $x\in \mathrm{relint}\mathcal{D}$ 使得 $Ax=b$。

我们可以通过考虑相关的优化问题得到上述结论，即

$$\begin{array}{rl}\mathrm{minimize}& s\\ \mathrm{subject}\mathrm{to}& f_i(x)-s⩽0,i=1,\cdots ,m\\ & Ax=b\end{array}$$

优化变量为 $x,s$，定义域为 $\mathcal{D}\times \mathbf{R}$。当且仅当严格不等式系统有解时，上述优化问题的最优值 $p^{\star }<0$。

其对偶函数为

$$\underset{x\in \mathcal{D},s}{inf}(s+\sum _{i=1}^m{\lambda }_i(f_i(x)-s)+{\nu }^{\mathrm{\top }}(Ax-b))=\{\begin{array}{ll}g(\lambda ,\nu )& {\mathbf{1}}^{\mathrm{\top }}\lambda =1\\ -\mathrm{\infty }& \text{otherwise}\end{array}$$

因此其对偶问题可以描述为

$$\begin{array}{rl}\mathrm{maximize}& g(\lambda ,\nu )\\ \mathrm{subject}\mathrm{to}& \lambda ⪰0,{\mathbf{1}}^{\mathrm{\top }}\lambda =1\end{array}$$

该问题满足 Slater 条件，即 $d^{\star }=p^{\star }$。

非严格不等式

下面考虑非严格不等式系统

$$\begin{array}{rl}{f}_i(x)& ⩽0,i=1,\cdots ,m\\ Ax& =b\end{array}$$

以及其择一系统

$$\begin{array}{rl}\lambda & ⪰0\\ g(\lambda ,\nu )& >0\end{array}$$

强择一成立的条件和严格不等式系统类似。

举例

线性不等式

考虑具有线性不等式 $Ax⪯b$ 的系统。它的对偶函数为

$$g(\lambda )=\underset{x}{inf}{\lambda }^{\mathrm{\top }}(Ax-b)=\{\begin{array}{ll}-b^{\mathrm{\top }}\lambda & A^{\mathrm{\top }}\lambda =0\\ -\mathrm{\infty }& \text{otherwise}\end{array}$$

因此，其择一不等式系统为

$$\begin{array}{rl}\lambda & ⪰0\\ A^{\mathrm{\top }}\lambda & =0\\ b^{\mathrm{\top }}\lambda & <0\end{array}$$

这两个系统是强择一的。

Farkas 引理

Farkas 引理描述了一对强择一系统，它们是由严格和非严格线性不等式组成的混合系统。不等式系统

$$\begin{array}{rl}Ax& ⪯0\\ c^{\mathrm{\top }}x& <0\end{array}$$

其中 $A\in {\mathbf{R}}^{m\times n},c\in {\mathbf{R}}^n$，以及不等式系统

$$\begin{array}{rl}{A}^{\mathrm{\top }}y+c& =0\\ y& ⪰0\end{array}$$

是强择一的。