跳转至

对偶锥与广义不等式

在了解了锥后,我们对锥做更进一步的讨论。

正常锥#

正常锥(proper cone)

一个锥K \subseteq \mathbb{R}^n被称作一个正常锥,当:

  • K是凸集
  • K闭合:包括他的边界
  • K是实锥(solid):包括非空内部(interior)
  • K是尖锥(pointed):不包括线(line)
正定锥是一个正常锥吗

是的

正常锥

  • 非负象限
K = \mathbb{R}^n_+
  • 半正定锥
K = \mathbb{S}^n_+
  • [0, 1]上的非负多项式
K = \{x \in \mathbb{R}^n \mid \sum_{i=1}^n x_nt^{n-1} \text{for} t \in [0, 1\}
正常锥的对偶锥的对偶锥是他本身吗

是的

广义不等式#

广义不等式(generalised inequality)

一个由正常锥K定义的广义不等式满足:

x \preceq_K y \quad \Longleftrightarrow \quad y - k \in K
x \prec_K y \quad \Longleftrightarrow \quad y - k \in int(K)

广义不等式是非线性的

我们可以有x \preceq_K yy \preceq_K x同时成立

但是其他属性都很相似,如x \preceq_K y, u \preceq_K v \quad \Rightarrow x + u \preceq_K y + v

广义不等式

  • 分量不等式(K = \mathbb{R}^n_+
x \preceq_{\mathbb{R}^n_+} y \quad \Longleftrightarrow \quad \forall i, x_i \leq y_i
  • 矩阵不等式(K = \mathbb{S}^n_+
X \preceq_{\mathbb{S}^n_+} Y \quad \Longleftrightarrow \quad Y - X \text{半正定}

对偶锥#

对偶锥

一个锥K的对偶锥是

K^\star = \{y \mid \forall x \in K, y^Tx \geq 0\}

对偶锥

  • K = \mathbb{R}^n_+: K^\star = \mathbb{R}^n_+
  • K = \mathbb{S}^n_+: K^\star = \mathbb{S}^n_+
  • K = \{(x, t) \mid \Vert x \Vert_2 \leq t\}: K^\star = \{(x, t) \mid \Vert x \Vert_2 \leq t\}
  • K = \{(x, t) \mid \Vert x \Vert_1 \leq t\}: K^\star = \{(x, t) \mid \Vert x \Vert_\inf \leq t\}

其中,前三个锥的对偶锥与其本身一致,我们将其称为自对偶锥(self-dual cone)。

对偶正常锥

正常锥的对偶锥也正常,因此可以定义广义不等式:

y \preceq_{K^\star} 0, \quad \Longleftrightarrow \quad \forall x \succeq_K 0, y^Tx \geq 0

对偶不等的最小与极小#

对偶不等的最小

x是集合S的最小元,当且仅当对于所有\lambda \succ_{K^\star} 0x唯一最小化S\lambda^Tz

\forall y \in S, \ x \preceq_K y

对偶不等的极小

  • 对于某些\lambda \succ_{K^\star} 0,如果x最小化S上的\lambda^Tz,那么x是集合S的一个极小元。

  • 如果x是集合S的极小元,那么存在一个不为零的\lambda \succ_{K^\star} 0使得x最小化S\lambda^Tz

\forall y \in S, \ y \preceq_K x \Rightarrow y = x

-\lambda定义了支持超平面。

一个集合必定有最小元吗

不是


最后更新: 2021-05-06 19:36:11

评论