一、对偶锥

1. 定义

令$K$为一个锥，集合：

称为$K$的对偶锥。$K^*$是一个锥，并且它总是凸的，即使$K$不是凸锥。

2. 例子

1. 子空间：子空间$V \subseteq \mathbb{R}^n$的对偶锥是其正交补$V^{\bot} = \{y|y^Tv=0, \forall v \in V\}$

2. 非负象限：锥$\mathbb{R}^n_+$的对偶是它本身：

   $$y^Tx \geq 0, \forall x \succeq 0 \Leftrightarrow y \succeq 0$$

   我们称这种锥自对偶。

3. 正交锥：在$n \times n$对称矩阵的集合$S^n$上，我们使用其标准内积$\textbf{tr}(XY) = \sum^{n}_{i,j=1}X_{ij}Y_{ij}$。半正定锥$S^n_+$是自对偶的，即对于任意的$X, Y \in S^n$，

   $$\textbf{tr}(XY) \geq 0, \forall X \succeq 0 \Leftrightarrow Y\succeq 0$$

4. 范数锥的对偶：令$\|\cdot\|$为定义在$\mathbb{R}^n$上的范数。与之相关的锥$K=\{(x,t) \in R^{n+1} |\|x\| \leq t\}$的对偶锥由其对偶范数定义，

   $$K^*=\{(u, v) \in \mathbb{R}^{n+1} | \|u\|_* \leq v\},$$

   这里的对偶范数由$\|u\|_* = \textbf{sup}\{u^Tx | \|x\| \leq 1\}$给出。

   对于范数锥的一般定义有：$K^*=\{(u,v)|(u,v)^T(x, t) \geq 0, \forall (x, t) \in K\}$，且$K=\{(x,t)|\|x\|\leq t\}$

   1. 证$\Rightarrow$，假设$(u, v) \in K^*$

      先得出$v \geq 0$。若$v < 0$，对于任意固定非零$x$可取$t \rightarrow +\infty$，（满足$t \geq \|x\|$），则$u^Tx + vt \rightarrow - \infty$,与对偶性矛盾，故$v \geq 0$

      对任意$x$，取$t = \|x\|$可得

      $$u^Tx+v\|x\| \geq 0, \forall x \in \mathbb{R}^n$$

      把$x$换成$-x$得

      $$-u^Tx + v\|x\| \geq 0, \forall x$$

      因此对任意$x$

      $$|u^Tx| \leq v \|x\|.$$

      两边对单位向量取上确界，得到

      $$\textbf{sup}_{\|x\|\leq 1}|u^Tx| \leq v.$$

      因为单位球关于原点对称，$\textbf{sup}_{\|x\| \leq 1}u^Tx = \textbf{sup}_{\|x\|\leq 1}|u^Tx|$.定义对偶函数为$\|u\|_* = \textbf{sup}_{\|x\|\leq 1} u^Tx$，于是得到$\|u\|_* \leq v$.由此$(u, v)$满足$\|u\|_* \leq v$。

3. 规范化：

对于$\forall x \in \mathbb{R}^n$：$|u^Tx| \leq v\|x\|$，证等价于$\textbf{sup}_{\|x\| \leq 1}|u^Tx| \leq v$.

令任意$x \neq 0$，定义：

$$y=\frac{x}{\|x\|},$$

于是$\|y\| = 1$.

代入$|u^Tx| \leq v\|x\|$：

$$|u^T(\|x\|y)| \leq v\|x\| \Rightarrow \|x\||u^Ty| \leq v\|x\|.$$

|x| > 0时，两边同时除以$\|x\|$，得到：

$$\|u^Ty\| \leq v, \forall y \text{满足} \|y\| = 1.$$

因此：

$$\textbf{sup}_{\|y\| = 1}|u^Ty| \leq v.$$

由于$\|x\| \leq 1$时，$|u^Tx| \leq \textbf{sup}_{\|y\|=1}|u^Ty|$，可直接写成：

$$\textbf{sup}_{\|x\| \leq 1}|u^Tx| \leq v.$$

该操作利用了范数的齐次性，把不等式缩放到单位球上取上确界，是分析线性函数与范数关系的标准套路。

4.性质

• $K^*$是闭凸锥
• $K_1 \subseteq K_2$可导出$K^*_2 \subseteq K^*_1$
• 如果$K$有非空内部，那么$K^*$是尖的
• 如果$K$的闭包是尖的，那么$K^*$有非空内部
• $K^{**}$是$K$的凸包的闭包。（因此，如果$K$是凸和闭的，则$K^{**} = K$）

这些性质表明如果$K$是一个正常锥，那么它的对偶$K^*$也是，进一步地，有$K^{**} = K$

二、广义不等式的对偶

我们称广义不等式$\preceq_{K^*}$为广义不等式$\preceq_K$的对偶。

关于广义不等式及其对偶有一些重要的性质：

性质

• $x \preceq_K y$当且仅当对于任意$\lambda \succeq_{K^*} 0$有$\lambda^T x \leq \lambda^T y$
• $x \prec_K y$当且仅当对于任意 $\lambda \succeq_{K^*} 0$ 和 $\lambda \neq 0$，有 $\lambda^T x < \lambda^T y$

因为$K = K^{**}$，与$\preceq_{K^*}$相关的对偶广义不等式为$\preceq_K$，因此也有：

三、对偶不等式定义的最小元和极小元

最小元

关于$\preceq_K$的最小元：元素$x \in S$是集合$S$最小元当且仅当对于所有$\lambda \succ_{K^*} 0$，$x$是在$S$上极小化$\lambda^Tz$的唯一最优解。

从几何上看，这意味着$\forall \lambda \succ_{K^*}0$，超平面

是在$x$处对$S$的一个严格支撑超平面。

极小元

关于$\preceq_K$的极小元：当对于某个$\lambda \succ_{K^*} 0$，$x$在$S$上极小化$\lambda^Tz$，元素$x \in S$是集合$S$极小元（逆命题不一定成立）.

当集合$S$为凸集时，对于任意极小元$x$，存在非零$\lambda \succ_{K^*} 0$，使得$x$在$S$上极小化$\lambda^Tz$.