首页 » 学习 » 对偶锥(dual cone)与广义不等式(generalized inequality)

对偶锥(dual cone)与广义不等式(generalized inequality)

  1. 真锥
  2. 广义不等式
  3. 分割超平面定理
  4. 支撑超平面
  5. 对偶锥和对偶广义不等式
  6. 最小和极小元素
  7. 参考

1 真锥(proper cone)

K\subseteq R^n如果满足以下几个条件则可以被称为真锥

  • K是凸的
  • K是闭合的(closed)
  • K是solid,也就是内部不是空的。
  • K是尖的,也就是内部不含有直线,x\in K,-x\in K\Longrightarrow x=0

2 广义不等式(generalized inequality)

广义不等式是一种偏序(不必要保证所有对象都具有可比较性),可以使用真锥来进行定义:
x\preceq _K y \iff y-x\in K
类似的还有严格偏序
x\prec _K y \iff y-x\in \mathbf{int}K

广义不等式的性质:

  • 可加性:如果x\preceq_Ky,u\preceq_Kv,那么有x+u\preceq_Ky+v
  • 传递性:如果x\preceq_Ky,y\preceq_Kz,那么有x\preceq_Kz
  • 可以进行非负的缩放:如果x\preceq_Ky,\alpha\geqslant0,那么有 \alpha x\preceq_K\alpha y
  • 自反性:x\preceq_Kx
  • 不对称性:如果x\preceq_Ky,y\preceq_Kx,那么x=y
  • 可以进行极限运算:如果x_i\preceq_Ky_i,i=1,2,\ldots,当i趋近于无穷时x_i\rightarrow x,y_i\rightarrow y,那么有x\preceq_Ky

3 分割超平面定理(separating hyperplane theorem)

分割超平面定理:设有两个非空不相交的两个凸集C、D,那么存在一个a\ne0和b,使所有C内的点满足a^Tx\leqslant b,使D内点满足a^Tx\geqslant b

4 支撑超平面(support hyperplane)

x_0是集合C边缘(boundary)上一点(x_0\in \mathbf{bd}C)。如果有非零的a对集合C内任意一点x都满足a^Tx\leqslant a^Tx_0,那么称超平面\{x\mid a^Tx=a^Tx_0\}支撑超平面

支撑超平面定理(supporting hyperplane therorem)任意一个非空凸集的边缘上任意一点上都存在一个支撑超平面。

5 对偶锥(dual cone)和对偶广义不等式(dual generalized inequality)

设K为一锥,那么称 K^*=\{y\mid x^Ty \geqslant 0,\forall x\in K\}称为K的对偶锥。即使K不是凸的,K的对偶锥K^*仍是凸的。

锥K的对偶锥K^*具有以下性质:

  • 始终是闭的(closed)、凸的。
  • K_1\subseteq K_2\implies K_1^*\subseteq K_2^*
  • 如果K内部非空,那么K^*是尖的(pointed)。
  • 如果K是尖的,那么K^*内部是非空的。
  • K^{**}是K的凸包。如果K是凸和闭的,那么K^{**}=K

真锥的对偶锥仍是真锥,所以我们用真锥K定义了广义不等式\preceq _K,我也可以同样用K^*定义对偶广义不等式x\preceq_{K^*}y \iff y-x \in K^*。对偶广义不等式满足性质 x\preceq_K y \iff \lambda^Tx\leqslant\lambda^Ty,\forall\lambda\succeq_{K^*}0。使用对偶广义不等式的好处是在将一个偏序问题转换为满足一个偏序条件的全序问题。

6 最小(minimun)和极小(minimal)元素

任意两个标量都是可以比较大小的,但是并不是所有矢量都能比较,例如不能比较[1,2]^T,[2,1]^T。如果一个元素比集合内任何一个元素都小,那么称该元素为最小元素。即如果集合S内一元素x满足S\subseteq x+K,那么该元素x为集合S的最小元素,其中K为真锥。利用对偶广义不等式可以得到如果x是集合S的一个最小元素,对任意\lambda \succ _{K^*}0,超平面\{z\mid\lambda^T(z-x)=0\}都是S的严格支撑平面(strict supporting hyperplane)。

极小元素是指所有能比较的元素中最小的元素。即如果集合S内一点x如果满足(x-K)\cap S=\{x\},那么称x为S的极小元素,其中K为真锥。

7 参考

标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注