本系列笔记(更新中): https://blog.csdn.net/qq_21149391/category_11891398.html
0. Preliminaries
1) 直线与线段
-
x
1
,
x
2
∈
R
n
x_1, x_2 in mathbb{R}^n
x1?,x2?∈Rn 为两个不重叠的点, 所有满足下式的点构成一条穿过
x
1
,
x
2
x_1, x_2
x1?,x2? 的直线 (line):
y
=
θ
x
1
+
(
1
?
θ
)
x
2
y= heta x_1 +(1- heta)x_2
y=θx1?+(1?θ)x2?
其中,θ
∈
R
heta in mathbb{R}
θ∈R 为任意实数.
-
当上式中的
θ
∈
[
0
,
1
]
hetain[0, 1]
θ∈[0,1]时, 所有满足上式的点构成一条在
x
1
,
x
2
x_1, x_2
x1?,x2? 中间的线段 (line segment).
2) 正定与半正定矩阵
- 正定矩阵 positive definite matrix：
矩阵P
P
P 是正定的 iif 对任意非零向量
x
x
x 有
x
T
P
x
>
0
x^T P x > 0
xTPx>0. 用符号表示为
P
?
0
P succ 0
P?0.
- 半正定矩阵 positive semi-definite matrix：
矩阵P
P
P 是正定的 iif 对任意非零向量
x
x
x 有
x
T
P
x
≥
0
x^T P x geq 0
xTPx≥0. 用符号表示为
P
?
0
P succeq 0
P?0.
iif 是 if and only if 的缩写. 意思为 “当且仅当”, 可用符号 “
?
Leftrightarrow
?” 表示.
3) 奇异矩阵与非奇异矩阵
- 奇异矩阵 singular matrix 是不可逆的方阵.
- 非奇异矩阵 nonsingular matrix 是可逆的方阵.
4) 向量的范数 (norm)
对于任意
x
,
y
∈
R
n
,
t
∈
R
x, yinmathbb{R}^n, tin mathbb{R}
x,y∈Rn,t∈R, 向量的范数
∣
∣
?
∣
∣
||cdot||
∣∣?∣∣ 是满足下面三个条件的距离公式:
-
∣
∣
x
∣
∣
≥
0
||x||geq 0
∣∣x∣∣≥0;
∣
∣
x
∣
∣
=
0
?
x
=
0
||x||= 0 Leftrightarrow x=0
∣∣x∣∣=0?x=0
-
∣
∣
t
x
∣
∣
=
∣
t
∣
∣
∣
x
∣
∣
||tx||=|t| ||x||
∣∣tx∣∣=∣t∣∣∣x∣∣
- Triangle inequality:
∣
∣
x
+
y
∣
∣
≤
∣
∣
x
∣
∣
+
∣
∣
y
∣
∣
||x+y|| leq ||x||+||y||
∣∣x+y∣∣≤∣∣x∣∣+∣∣y∣∣
常用范数:
-
?
1
ell_1
?1? norm:
∣
∣
x
∣
∣
1
=
∑
i
=
1
n
∣
x
i
∣
||x||_1=sum_{i=1}^n |x_i|
∣∣x∣∣1?=∑i=1n?∣xi?∣, 每个元素的绝对值之和
-
?
2
ell_2
?2? norm:
∣
∣
x
∣
∣
2
=
(
∑
i
=
1
n
∣
x
i
∣
2
)
1
/
2
||x||_2=(sum_{i=1}^n |x_i|^2)^{1/2}
∣∣x∣∣2?=(∑i=1n?∣xi?∣2)1/2, 每个元素的2次方之和再开根号
-
?
p
ell_p
?p? norm:
∣
∣
x
∣
∣
p
=
(
∑
i
=
1
n
∣
x
i
∣
p
)
1
/
p
||x||_p=(sum_{i=1}^n |x_i|^p)^{1/p}
∣∣x∣∣p?=(∑i=1n?∣xi?∣p)1/p, 每个元素的p次方之和再开p次根号.
p
p
p 为正整数
-
?
∞
ell_infty
?∞? norm:
∣
∣
x
∣
∣
∞
=
max
?
i
=
1
,
.
.
.
,
n
{
∣
x
i
∣
}
||x||_infty=max_{i=1,...,n}{|x_i|}
∣∣x∣∣∞?=maxi=1,...,n?{∣xi?∣}, 绝对值最大的元素
1. Affine set 仿射集
1) Affine set (仿射集) 的定义:
x
1
,
x
2
x_1, x_2
x1?,x2? 为集合
C
?
R
n
Csubseteq mathbb{R}^n
C?Rn 内的任意两点，若穿过
x
1
,
x
2
x_1,x_2
x1?,x2? 的直线仍在
C
C
C 内，那么
C
C
C 为 affine set.
一些 affine set 的例子:
- 一条直线 line
- 一个平面 plane
- 一个三维空间
- 线性方程
{
x
∣
A
x
=
b
}
{x|Ax=b}
{x∣Ax=b} 的解集
证明：
令x
1
,
x
2
x_1,x_2
x1?,x2? 为上述解集内的两个点, 有
A
x
1
=
b
,
A
x
2
=
b
Ax_1=b, Ax_2=b
Ax1?=b,Ax2?=b. 对于任意
θ
heta
θ, 可以算出:
A
[
θ
x
1
+
(
1
?
θ
)
x
2
]
=
θ
A
x
1
+
(
1
?
θ
)
A
x
2
=
θ
b
+
(
1
?
θ
)
=
b
A[ heta x_1 +(1- heta)x_2]= heta A x_1 + (1- heta) A x_2= heta b+(1- heta)=b
A[θx1?+(1?θ)x2?]=θAx1?+(1?θ)Ax2?=θb+(1?θ)=b
所以点θ
x
1
+
(
1
?
θ
)
x
2
heta x_1 +(1- heta)x_2
θx1?+(1?θ)x2? 仍在解集内.
下面第四节的开头有 affine set, convex set, convex cone 的一些例子.
2) Affine combination (仿射组合) 的定义
x
1
,
.
.
.
,
x
k
x_1,...,x_k
x1?,...,xk? 的 affine combination 是
θ
1
x
1
+
.
.
.
+
θ
k
x
k
heta_1 x_1+...+ heta_k x_k
θ1?x1?+...+θk?xk?，其中
θ
1
+
.
.
.
+
θ
k
=
1
heta_1+...+ heta_k =1
θ1?+...+θk?=1.
- an affine set contains every affine combination of its points.
3) 扩展:
若
C
C
C 为 affine set 且
x
0
∈
C
x_0in C
x0?∈C，那么
V
=
C
?
x
0
=
{
x
?
x
0
∣
x
∈
C
}
V=C-x_0={x-x_0|xin C}
V=C?x0?={x?x0?∣x∈C}称为与
C
C
C相关的子空间 subspace. (相当于平移)
对
V
V
V 的分析：
V
=
{
x
?
x
0
∣
x
∈
C
}
????????
?
x
0
∈
C
=
{
x
?
x
0
∣
A
x
=
b
}
=
{
x
?
x
0
∣
A
x
=
A
x
0
}
=
{
x
?
x
0
∣
A
(
x
?
x
0
)
=
0
}
=
{
y
∣
A
y
=
0
}
egin{align} V&={x-x_0|xin C} ;;;; forall x_0in C \ &={x-x_0|Ax=b}\ &={x-x_0|Ax=Ax_0}\ &={x-x_0|A(x-x_0)=0}\ &={y|Ay=0} end{align}
V?={x?x0?∣x∈C}?x0?∈C={x?x0?∣Ax=b}={x?x0?∣Ax=Ax0?}={x?x0?∣A(x?x0?)=0}={y∣Ay=0}??
V
V
V 为
A
A
A 的 null space.
4) Affine hull (仿射包) 的定义:
C
∈
R
n
C in mathbb{R}^n
C∈Rn为任意集合，
C
C
C 中的点所构成的全部 affine combinations 的集合称为
C
C
C 的 affine hull，记为
aff
C
extbf{aff } C
aff C：
aff
C
=
{
θ
1
x
1
+
.
.
.
+
θ
k
x
k
∣
x
1
,
.
.
.
,
x
k
∈
C
,
θ
1
+
.
.
.
+
θ
k
=
1
}
extbf{aff } C={ heta_1 x_1+...+ heta_k x_k | x_1,...,x_kin C, heta_1+...+ heta_k=1}
aff C={θ1?x1?+...+θk?xk?∣x1?,...,xk?∈C,θ1?+...+θk?=1}
可以看出，集合
C
C
C 的 affine hull 是包含
C
C
C 的最小 affine set.
即, 若
S
S
S 是任意 affine set 且
C
?
S
Csubseteq S
C?S，那么
aff
C
?
S
extbf{aff } C subseteq S
aff C?S.
2. Convex sets 凸集
Convex sets 的相关概念定义与 Affine sets 的定义相似, 可以结合起来记.
1) Convex sets 的定义
定义1：
x
1
,
x
2
x_1, x_2
x1?,x2? 为集合
C
?
R
n
Csubseteq mathbb{R}^n
C?Rn 内的任意两点，若线段
x
1
x
2
x_1 x_2
x1?x2?仍在
C
C
C 内，那么
C
C
C 为 convex set.
定义2：
x
1
,
x
2
x_1, x_2
x1?,x2? 为集合
C
?
R
n
Csubseteq mathbb{R}^n
C?Rn 内的任意两点，
θ
∈
[
0
,
1
]
hetain [0,1]
θ∈[0,1]，若
θ
x
1
+
(
1
?
θ
)
x
2
∈
C
heta x_1+(1- heta)x_2in C
θx1?+(1?θ)x2?∈C，那么
C
C
C 为 convex set.
- 从定义我们就能推出, 所有的 affine set 都是 convex set.
图1. 左：六边形，包括边，是凸集；中：非凸集合；右：正方形， 不包含边上的某些点，非凸（如果不含的点只在四个角上，为凸集）。
2) Convex combination (凸组合) 的定义
x
1
,
.
.
.
,
x
k
x_1,...,x_k
x1?,...,xk? 的 convex combination 是
θ
1
x
1
+
.
.
.
+
θ
k
x
k
heta_1 x_1+...+ heta_k x_k
θ1?x1?+...+θk?xk?，其中
θ
1
+
.
.
.
+
θ
k
=
1
heta_1+...+ heta_k =1
θ1?+...+θk?=1，并且
θ
i
∈
[
0
,
1
]
heta_i in [0,1]
θi?∈[0,1]，
i
=
1
,
.
.
.
,
k
i=1,...,k
i=1,...,k.
与前面的 affine combination 区别为
θ
heta
θ 的约束.
- a set is convex iif it contains every convex combination of its points.
3) Convex hull (凸包) 的定义
C
∈
R
n
C in mathbb{R}^n
C∈Rn为任意集合，
C
C
C 中的点所构成的全部 convex combinations 的集合称为
C
C
C 的 convex hull，记为
conv
C
extbf{conv } C
conv C：
conv
C
=
{
θ
1
x
1
+
.
.
.
+
θ
k
x
k
∣
x
i
∈
C
,
θ
i
∈
[
0
,
1
]
,
i
=
1
,
.
.
.
,
k
,
θ
1
+
.
.
.
+
θ
k
=
1
}
extbf{conv } C={ heta_1 x_1+...+ heta_k x_k|x_iin C, heta_iin[0,1], i=1,...,k, heta_1+...+ heta_k=1}
conv C={θ1?x1?+...+θk?xk?∣xi?∈C,θi?∈[0,1],i=1,...,k,θ1?+...+θk?=1}
集合
C
C
C 的 convex hull 是包含
C
C
C 的最小 convex set.
即, 若
B
B
B 是任意 convex set 且
C
?
B
C subseteq B
C?B，那么
conv
C
?
B
extbf{conv } C subseteq B
conv C?B.
图2.
R
2
mathbb{R}^2
R2中的两个凸包，左图中的集合（15个点构成的集合）的凸包是一个五边形（阴影部分）；右图阴影部分为图1中间的图形的凸包。
3. Convex cone 凸锥
1) Convex cones (凸锥) 的定义
- 如果对于任意
x
∈
C
xin C
x∈C，
θ
≥
0
heta geq 0
θ≥0，有
θ
x
∈
C
heta x in C
θx∈C, 那么集合
C
C
C 被称为 cone 或 nonnegative homogeneous.
- 如果集合
C
C
C 既是 cone 又是 convex set, 那么
C
C
C 为 convex cone.
- 如果集合
C
C
C 为 convex cone, 那么对于任意
x
1
,
x
2
∈
C
x_1,x_2in C
x1?,x2?∈C 和任意
θ
1
,
θ
2
≥
0
heta_1, heta_2 geq 0
θ1?,θ2?≥0，有
θ
1
x
1
+
θ
2
x
2
∈
C
heta_1 x_1+ heta_2x_2 in C
θ1?x1?+θ2?x2?∈C。
图3. 凸锥在几何上可以描述为：顶点为0且边缘穿过
x
1
x_1
x1?和
x
2
x_2
x2?的二维饼图
2）Conic combination (锥组合) 的定义
x
1
,
.
.
.
,
x
k
x_1,...,x_k
x1?,...,xk? 的 conic combination (或称为 nonnegative linear combination) 是
θ
1
x
1
+
.
.
.
+
θ
k
x
k
heta_1 x_1+...+ heta_k x_k
θ1?x1?+...+θk?xk?，其中
θ
1
,
.
.
.
,
θ
k
≥
0
heta_1,..., heta_k geq 0
θ1?,...,θk?≥0.
- 若
x
i
x_i
xi? 在 convex cone
C
C
C 中，那么
x
i
x_i
xi? 的任意 conic combination 仍在
C
C
C内.
- a set is a convex cone iif it contains all conic combinations of its elements.
3）Conic hull (锥包) 的定义
C
∈
R
n
C in mathbb{R}^n
C∈Rn为任意集合，
C
C
C 中的点所构成的全部 conic combinations 的集合称为
C
C
C 的 conic hull：
{
θ
1
x
1
+
.
.
.
+
θ
k
x
k
∣
x
i
∈
C
,
θ
i
≥
0
,
i
=
1
,
.
.
.
,
k
}
{ heta_1x_1+...+ heta_kx_k|x_iin C, heta_igeq 0, i=1,...,k}
{θ1?x1?+...+θk?xk?∣xi?∈C,θi?≥0,i=1,...,k}
- 集合
C
C
C 的 conic hull 是包含
C
C
C 的最小 convex cone.
图4. 图2中的两个集合的锥包（阴影部分）；如果集合为两个点，且两点连线通过0点，它的锥包为一条通过这两点，顶点为0的射线
4. 一些重要的例子
- 仿射集都是凸集。
- 所有的空集
?
varnothing
?，所有只包含一个点的集合
{
x
0
}
{x_0}
{x0?}，和整个
R
n
mathbb{R}^n
Rn空间都是
R
n
mathbb{R}^n
Rn 的仿射子集。
- 所有的直线都是仿射集，如果直线通过 0 点，那么它是一个凸锥。
- 所有的线段都是凸集，但不是仿射集。
- 一条射线，形式为
{
x
0
+
θ
v
∣
θ
≥
0
}
{x_0 + θv | θ geq 0}
{x0?+θv∣θ≥0}，其中
v
≠
0
v
eq 0v=0，是凸集，但不是仿射集。 如果
x
0
=
0
x_0=0
x0?=0，则它是凸锥。
- 所有的子空间都是仿射集，并且是凸锥。
4.1 Hyperplanes 超平面
定义：超平面是一个形式为
{
x
∣
a
T
x
=
b
}
{x|a^Tx=b}
{x∣aTx=b} 的集合，其中
a
∈
R
n
,
a
≠
0
,
b
∈
R
ain mathbb{R}^n, a
eq 0, bin mathbb{R}
a∈Rn,a=0,b∈R。
- 超平面是线性方程的非零解集
- 向量
a
a
a 是超平面的 normal vector (法向量) , 常数
b
b
b 决定了超平面与原点的偏移量.
- 超平面也可表示为
{
x
∣
a
T
(
x
?
x
0
)
=
0
}
{x|a^T(x-x_0)=0}
{x∣aT(x?x0?)=0}，其中
x
0
x_0
x0? 是超平面中的任意一点
- 也可表示为
{
x
∣
a
T
(
x
?
x
0
)
=
0
}
=
x
0
+
a
⊥
{x|a^T(x-x_0)=0}=x_0+a^perp
{x∣aT(x?x0?)=0}=x0?+a⊥，其中
a
⊥
a^perp
a⊥ 表示
a
a
a 的正交补集.
图5.
R
2
mathbb{R}^2
R2中的超平面，法向量为
a
a
a，点
x
0
x_0
x0?在超平面内。在超平面中的任意一点
x
x
x，
x
?
x
0
x-x_0
x?x0?（图中加粗的向量）与
a
a
a正交。
4.2 Halfspaces 半空间
上述的超平面能够将
R
n
mathbb{R}^n
Rn 划分成两个 halfspaces，halfspace 是一个形式为
{
x
∣
a
T
x
≤
b
}
{x|a^Tx leq b}
{x∣aTx≤b} 的集合，其中
a
≠
0
a
eq 0
a=0，是一个线性不等式的非零解集.
A halfspace is a convex set，not a affine set:
图6. 超平面
a
T
x
=
b
a^Tx=b
aTx=b 将
R
n
mathbb{R}^n
Rn划分成两个半空间。由
a
T
x
≥
b
a^T x geq b
aTx≥b 确定的半空间(未加阴影)是沿
a
a
a方向延伸的。 由
a
T
x
≤
b
a^T x leq b
aTx≤b 确定的半空间(阴影部分)在
?
a
-a
?a方向上延伸的。向量
a
a
a是这个半空间的外法线。
Halfspace 也可表示为
{
x
∣
a
T
(
x
?
x
0
)
≤
0
}
{x|a^T(x-x_0)leq0}
{x∣aT(x?x0?)≤0}，其中
x
0
x_0
x0?是对应的超平面上的任意点，即满足
a
T
x
0
=
b
a^T x_0 = b
aTx0?=b。
对此的几何解释为：Halfspace 由
x
0
x_0
x0?和任何与向量
a
a
a(
a
a
a为向外的法向量)成钝角或直角的向量组成。如图7。
图7. 由
a
T
(
x
?
x
0
)
≤
0
a^T(x-x_0)leq0
aT(x?x0?)≤0定义的半空间（阴影部分）：向量
x
1
?
x
0
x_1 - x_0
x1??x0?与
a
a
a成锐角，因此
x
1
x_1
x1?不在半空间中。 向量
x
2
?
x
0
x_2 - x_0
x2??x0? 与
a
a
a 成钝角，在半空间中。
集合
{
x
∣
a
T
x
<
b
}
{x|a^Tx <b}
{x∣aTx<b}称为开半空间(open halfspace)。
4.3 Euclidean Balls 欧式球
在
R
n
mathbb{R}^n
Rn 空间中的 Euclidean balls (或简称为 balls) 的形式为：
B
(
x
c
,
r
)
=
{
x
∣
??
∣
∣
x
?
x
c
∣
∣
2
≤
r
}
=
{
x
∣
??
(
x
?
x
c
)
T
(
x
?
x
c
)
≤
r
2
}
B(x_c,r)={x|; ||x-x_c||_2 leq r}={x|; (x-x_c)^T(x-x_c)leq r^2}
B(xc?,r)={x∣∣∣x?xc?∣∣2?≤r}={x∣(x?xc?)T(x?xc?)≤r2}
其中
r
>
0
r>0
r>0，
∣
∣
?
∣
∣
2
||cdot||_2
∣∣?∣∣2? 为
?
2
ell_2
?2? norm，
x
c
x_c
xc? 是球的中心，标量
r
r
r 为半径.
- 若上述公式内的 “
≤
leq
≤” 换为成 “
=
=
=”, 那么它表示球的表面 (sphere, 球面)
-
B
(
x
c
,
r
)
B(x_c,r)
B(xc?,r) 由距中心
x
c
x_c
xc? 小于等于
r
r
r 的所有点组成，即球面 + 球的内部.
- 球的另一种表示形式为：
B
(
x
c
,
r
)
=
{
x
c
+
r
u
∣
??∣
∣
u
∣
∣
2
≤
1
}
B(x_c,r)={x_c + ru|; ||u||_2 leq 1}
B(xc?,r)={xc?+ru∣∣∣u∣∣2?≤1}
- 球是 convex set，证明：
球内任取两点x
1
,
x
2
x_1, x_2
x1?,x2?，有
∣
∣
x
1
?
x
c
∣
∣
2
≤
r
||x_1-x_c||_2 leq r
∣∣x1??xc?∣∣2?≤r 和
∣
∣
x
2
?
x
c
∣
∣
2
≤
r
||x_2-x_c||_2 leq r
∣∣x2??xc?∣∣2?≤r，
令θ
∈
[
0
,
1
]
heta in [0,1]
θ∈[0,1]，则根据 convex set 的定义，需证明线段
θ
x
1
+
(
1
?
θ
)
x
2
heta x_1 + (1- heta) x_2
θx1?+(1?θ)x2? 是否在球内：
∣
∣
θ
x
1
+
(
1
?
θ
)
x
2
?
x
c
∣
∣
2
=
∣
∣
θ
(
x
1
?
x
c
)
+
(
1
?
θ
)
(
x
2
?
x
c
)
∣
∣
2
≤
θ
∣
∣
x
1
?
x
c
∣
∣
2
+
(
1
?
θ
)
∣
∣
x
2
?
x
c
∣
∣
2
≤
r
egin{align} & || heta x_1 + (1- heta) x_2 - x_c||_2 \ =&|| heta(x_1-x_c) + (1- heta) (x_2-x_c)||_2 \ leq & heta||x_1-x_c||_2 + (1- heta) ||x_2-x_c||_2\ leq &r end{align}
=≤≤?∣∣θx1?+(1?θ)x2??xc?∣∣2?∣∣θ(x1??xc?)+(1?θ)(x2??xc?)∣∣2?θ∣∣x1??xc?∣∣2?+(1?θ)∣∣x2??xc?∣∣2?r??
4.4 Ellipsoids 椭球
椭球也属于 convex set，其形式为：
ε
=
{
x
∣
(
x
?
x
c
)
T
P
?
1
(
x
?
x
c
)
≤
1
}
varepsilon = {x|(x-x_c)^T P^{-1}(x-x_c)leq 1}
ε={x∣(x?xc?)TP?1(x?xc?)≤1}
其中
P
P
P 为对称且正定的矩阵.
- 同样的，
x
c
∈
R
n
x_cin mathbb{R}^n
xc?∈Rn 为椭球的中心，
P
P
P 决定了椭球在每个方向上从
x
c
x_c
xc? 延伸多远，
ε
varepsilon
ε 的半轴长度由
P
P
P的特征值
λ
i
sqrt{lambda_i}
λi?
- 当
P
=
r
2
I
P=r^2 I
P=r2I 时，上述公式的椭球就是球。
图8. 二维空间中的椭球（也是椭圆），
x
c
x_c
xc?为中心，两个线段为半轴。
4.5 Norm Balls 范数球
当将欧氏球公式中的二范数（
∣
∣
?
∣
∣
2
||cdot||_2
∣∣?∣∣2?）换成
R
n
mathbb{R}^n
Rn上的任意范数（
∣
∣
?
∣
∣
||cdot||
∣∣?∣∣），此时的集合称为 Norm Balls：
B
(
x
c
,
r
)
=
{
x
∣
??
∣
∣
x
?
x
c
∣
∣
≤
r
}
B(x_c,r)={x|; ||x-x_c||leq r}
B(xc?,r)={x∣∣∣x?xc?∣∣≤r}
当球的中心为圆点时, 不同范数球在二维空间中的形状如下图:
- 当范数为
?
1
ell_1
?1? norm 时, 此时的球的边界对应于图中红色正方形
- 当范数为
?
2
ell_2
?2? norm 时, 此时的球的边界对应于图中黄色圆形, 最普遍的球
- 当范数为
?
∞
ell_infty
?∞? norm 时, 此时的球的边界对应于图中蓝色正方形
- 当范数为
?
p
ell_p
?p? norm 且
p
>
2
p > 2
p>2 时, 此时的球的边界在黄线与蓝线之间
4.6 Norm Cones 范数锥
范数锥的公式为：
C
=
{
(
x
,
t
)
∣
??
∣
∣
x
∣
∣
≤
t
}
C={(x,t)|; ||x||leq t}
C={(x,t)∣∣∣x∣∣≤t}
其中，
x
∈
R
n
xin mathbb{R}^n
x∈Rn，
t
∈
R
t inmathbb{R}
t∈R.
- 注意, 集合
C
?
R
n
+
1
C subseteq mathbb{R}^{n+1}
C?Rn+1 中的元素是
(
x
,
t
)
(x,t)
(x,t), 是由一个 n 维向量和一个标量组成的对儿.
- 范数为
?
2
ell_2
?2? 的范数锥称为二阶锥 second-order cone, 如下图.
图9.
R
2
mathbb{R}^2
R2中的 second-order cone 二阶锥的边界。
4.7 Polyhedra 多面体
定义：多面体为有限个线性等式和不等式的解集：
P
=
{
x
∣
A
x
?
b
,
C
x
=
d
}
mathcal{P}={x|A x preceq b, C x = d }
P={x∣Ax?b,Cx=d}
- 此处的符号
?
preceq
? 用于向量之间的关系, 与正定/半正定符号不同, 表示:
x
?
y
?
x
i
≤
y
i
x preceq y Leftrightarrow x_i leq y_i
x?y?xi?≤yi?
- 若令
A
=
[
a
1
T
.
.
.
a
m
T
]
,
C
=
[
c
1
T
.
.
.
c
p
T
]
A=egin{bmatrix} a_1^T\ ...\ a_m^T\ end{bmatrix}, C=egin{bmatrix} c_1^T\ ...\ c_p^T\ end{bmatrix}
A=
a
i
T
x
≤
b
i
,
c
j
T
x
=
d
j
????
for
????i
=
1
,
.
.
.
,
m
;
????j
=
1
,
.
.
.
,
p
a_i^T xleq b_i, c_j^T x=d_j;; ext{for } ;; i = 1,...,m;;; j=1,...,p
aiT?x≤bi?,cjT?x=dj?for i=1,...,m;j=1,...,p
- 根据上式可看出，多面体是
m
m
m 个半空间和
p
p
p 个超平面的 交集，其中
m
,
n
m,n
m,n 为非无穷的正数。
- 仿射集（直线、子空间、超平面）、射线、线段、半空间都是多面体，多面体是凸集。
4.8 Simplexes 单纯形
1）定义
在
R
n
mathbb{R}^n
Rn 空间中选取
k
+
1
k+1
k+1 个仿射独立 (affinely independent) 的点，即
v
1
?
v
0
,
.
.
.
,
v
k
?
v
0
v_1 - v_0,...,v_k-v_0
v1??v0?,...,vk??v0? 是线性无关的，则与上述点相关的单纯形为：
C
=
conv
{
v
0
,
.
.
.
,
v
k
}
=
{
θ
0
x
0
+
.
.
.
+
θ
k
x
k
∣
θ
?
0
,
1
T
θ
=
1
}
C= extbf{conv } {v_0,...,v_k}={ heta_0 x_0+...+ heta_k x_k| hetasucceq 0,mathbf{1}^T heta = 1}
C=conv {v0?,...,vk?}={θ0?x0?+...+θk?xk?∣θ?0,1Tθ=1}
其中
conv
extbf{conv }
conv 表示凸包，
1
mathbf{1}
1 表示所有元素均为
1
1
1 的向量. 该单纯形的仿射维数为
k
k
k，称为
k
k
k维单纯形.
图10.
R
2
mathbb{R}^2
R2空间中，左：
k
=
1
k=1
k=1，选取两个点得到的单纯形为一个线段；中：
k
=
2
k=2
k=2，选三个点，相关的单纯形为一个三角形（包括边和阴影部分）；右：
k
=
3
k=3
k=3，选取四个点，但是在二维空间中无法找到三个线性无关的向量（图中的任一向量可由另两个向量的线性组合得到），故在二维空间中，无法找到四个或以上的点来构成一个单纯形。
如图1，同样的可以得出：一维空间中的单纯形是线段；二维空间中的单纯形是三角形；三维空间中的单纯形为四面体。
2）证明：单纯形是多面体的一种
C
∈
R
n
Cinmathbb{R}^n
C∈Rn为单纯形，则根据单纯形的定义可得：
x
∈
C
?
x
=
θ
0
v
0
+
.
.
.
+
θ
k
v
k
,
1
T
θ
=
1
,
θ
?
0
,
v
1
?
v
0
,
.
.
.
,
v
k
?
v
0
线性无关
(1)
xin CLeftrightarrow x= heta_0 v_0 + ...+ heta_k v_k,mathbf{1}^T heta = 1, hetasucceq 0,v_1 - v_0,...,v_k-v_0线性无关 ag{1}
x∈C?x=θ0?v0?+...+θk?vk?,1Tθ=1,θ?0,v1??v0?,...,vk??v0?线性无关(1)
为方便表示，我们定义
y
y
y 和
B
B
B：
y
=
[
θ
1
,
.
.
.
,
θ
k
]
T
,
????
y
?
0
,
????
1
T
y
≤
1
y=[ heta_1,..., heta_k]^T, ;; ysucceq 0, ;; mathbf{1}^T y leq 1
y=[θ1?,...,θk?]T,y?0,1Ty≤1
B
=
[
v
1
?
v
0
.
.
.
v
k
?
v
0
]
∈
R
n
×
k
B=egin{bmatrix} v_1-v_0 & ... & v_k-v_0 end{bmatrix}in mathbb{R}^{n imes k}
B=[v1??v0??...?vk??v0??]∈Rn×k
则公式（1）可以表示为：
x
∈
C
?
x
=
v
0
+
B
y
(2)
xin C Leftrightarrow x=v_0 + By ag{2}
x∈C?x=v0?+By(2)
v
0
,
.
.
.
,
v
k
v_0, ..., v_k
v0?,...,vk?为仿射独立的，即
v
1
?
v
0
,
.
.
.
,
v
k
?
v
0
v_1-v_0,...,v_k-v_0
v1??v0?,...,vk??v0?为线性无关的，可得
r
a
n
k
(
B
)
=
k
{
m rank}(B)=k
rank(B)=k，
(
k
≤
n
)
(kleq n)
(k≤n)，因此存在一个非奇异矩阵
A
=
[
A
1
A
2
]
∈
R
n
×
n
A=egin{bmatrix}A_1 \A_2end{bmatrix}inmathbb{R}^{n imes n}
A=[A1?A2??]∈Rn×n使得
A
B
=
[
A
1
A
2
]
B
=
[
I
0
]
,
??
(
I
∈
R
k
×
k
)
AB=egin{bmatrix}A_1 \A_2end{bmatrix} B=egin{bmatrix}I\0end{bmatrix},;(Iin mathbb{R}^{k imes k})
AB=[A1?A2??]B=[I0?],(I∈Rk×k)
对公式（2）左乘一个矩阵
A
A
A：
A
x
=
A
v
0
+
A
B
y
[
A
1
A
2
]
x
=
[
A
1
A
2
]
v
0
+
[
I
0
]
y
egin{aligned} Ax &= Av_0 + ABy\ egin{bmatrix}A_1 \A_2end{bmatrix}x &=egin{bmatrix}A_1 \A_2end{bmatrix}v_0+egin{bmatrix}I\0end{bmatrix}y end{aligned}
Ax[A1?A2??]x?=Av0?+ABy=[A1?A2??]v0?+[I0?]y?
即
{
A
1
x
=
A
1
v
0
+
y
A
2
x
=
A
2
v
0
left{egin{matrix} A_1 x=A_1 v_0 + y\ A_2 x=A_2 v_0 end{matrix}
ight.
{A1?x=A1?v0?+yA2?x=A2?v0??
因此
x
∈
C
xin C
x∈C 当且仅当
A
2
x
=
A
2
v
0
A_2 x= A_2 v_0
A2?x=A2?v0?且向量
y
=
A
1
x
?
A
1
v
0
y=A_1x - A_1 v_0
y=A1?x?A1?v0?满足
y
?
0
,
??
1
T
y
≤
1
ysucceq 0, ; mathbf{1}^T y leq 1
y?0,1Ty≤1。换句话说，
x
∈
C
xin C
x∈C 当且仅当:
A
2
x
=
A
2
v
0
,
??????
A
1
x
?
A
1
v
0
,
??????
1
T
A
1
x
≤
1
+
1
T
A
1
v
0
A_2 x = A_2 v_0, ;;; A_1 x succeq A_1 v_0, ;;; mathbf{1}^TA_1x leq 1+ mathbf{1}^T A_1 v_0
A2?x=A2?v0?,A1?x?A1?v0?,1TA1?x≤1+1TA1?v0?
即单纯形为两个不等式和一个等式描述的集合，这也就是多面体的定义。
4.9 The Positive Semidefinite Cone 半正定锥
1) 定义
-
S
n
extbf{S}^n
Sn 为全部对称矩阵的集合
:S
n
=
{
X
∈
R
n
×
n
∣
X
=
X
T
}
mathbf{S}^n = {Xin mathbb{R}^{n imes n}|X=X^T}
Sn={X∈Rn×n∣X=XT}
这是一个维度为n
(
n
+
1
)
/
2
n(n + 1)/2
n(n+1)/2 的向量空间。
是凸锥，所以也是凸集。 -
S
+
n
mathbf{S}^n_+
S+n? 为半正定锥, 是全部对称且半正定的矩阵的集合
:S
+
n
=
{
X
∈
S
n
∣
X
?
0
}
mathbf{S}^n_+ = {Xin extbf{S}^n|Xsucceq 0}
S+n?={X∈Sn∣X?0}
是凸锥，所以也是凸集。 -
S
+
+
n
mathbf{S}^n_{++}
S++n? 为全部对称且正定的矩阵的集合
:S
+
+
n
=
{
X
∈
S
n
∣
X
?
0
}
mathbf{S}^n_{++} = {Xin mathbf{S}^n|Xsucc 0}
S++n?={X∈Sn∣X?0}
是凸集，不是凸锥。
2）证明：
S
+
n
mathbf{S}^n_+
S+n?是凸锥
即（根据凸锥的定义）任取
θ
1
,
θ
2
≥
0
heta_1, heta_2 geq 0
θ1?,θ2?≥0，
A
,
B
∈
S
+
n
A, B in mathbf{S}^n_+
A,B∈S+n?，证明
θ
1
A
+
θ
2
B
∈
S
+
n
heta_1 A+ heta_2 Bin mathbf{S}^n_+
θ1?A+θ2?B∈S+n?。
根据半正定矩阵的性质有：
?
x
∈
R
n
,
??
x
T
A
x
≥
0
,
??
x
T
B
x
≥
0
forall xin mathbb{R}^n,; x^T A x geq 0,; x^T B x geq 0
?x∈Rn,xTAx≥0,xTBx≥0
因此：
x
T
(
θ
1
A
+
θ
2
B
)
x
=
??
θ
1
x
T
A
x
+
θ
2
x
T
B
x
≥
??
0
egin{aligned} &x^T( heta_1 A+ heta_2 B)x\ =&; heta_1x^T A x + heta_2 x^T B x\ geq & ; 0 end{aligned}
=≥?xT(θ1?A+θ2?B)xθ1?xTAx+θ2?xTBx0?
即
θ
1
A
+
θ
2
B
∈
S
+
n
heta_1 A+ heta_2 Bin extbf{S}^n_+
θ1?A+θ2?B∈S+n?，证明完毕。
3）不同空间中的特征
n=1：即一维空间中，
S
1
=
R
extbf{S}^1 = extbf{R}
S1=R（实数集）；
S
+
1
=
R
+
extbf{S}^1_+ = extbf{R}_+
S+1?=R+?（非负实数集）；
S
+
+
1
=
R
+
+
extbf{S}^1_{++} = extbf{R}_{++}
S++1?=R++?（正实数集)。
n=2：即二维空间中，如图2，我们有：
X
=
[
x
y
y
z
]
∈
S
+
2
?
x
≥
0
,
z
≥
0
,
x
z
≥
y
2
X = egin{bmatrix}x & y\ y & zend{bmatrix}in extbf{S}^2_+ Leftrightarrow x geq 0, z geq 0, xz geq y^2
X=[xy?yz?]∈S+2??x≥0,z≥0,xz≥y2
图11. 二维空间中半正定锥的边界，在
R
3
mathbb{R}^3
R3中绘制为
(
x
,
y
,
z
)
(x, y, z)
(x,y,z)。