几种combination

linear combination

x=∑jλjxj 其中 xj∈Rn,λ∈R

affine combination

x=∑jλjxj,∑jλj=1 其中 xj∈Rn,λ∈R

dimension

集合S的dimension，是affinely independent points的最大个数再减去1。 如果集合 S={x∈Rn:Ax=b} 非空，那么 dim(S)=n−rank(A)

包含集合S的minimal affine space叫做affine hull，并表示为 aff(S)

证明一个非空集合的维度是k：

证明 dim(S)≤k ，找到 Ax=b ，满足 S⊂{x∈Rn:Ax=b} 并且 rank(A)=n−k 证明 dim(S)≥k ，集合S中存在k+1个affinely independent points；或者对于S中的任意一个点x， αx=β ，都是 Ax=b 的linear combination。

convex combination

x=∑jλjxj,∑jλj=1,λj≥0 其中 xj∈Rn,λ∈R

convex set

如果一个集合 C⊂Rn ，包含了所有C中节点的convex combination，那么C是convex set。 等价的，可以说 λx+(1−λ)y∈C, where t∈[0,1],∀x,y∈C

convex hull

一个集合S的convex hull，是保护S的minimal convex set，标记为 conv(S)

conic combination

x=∑jλjxj,λj≥0 其中 xj∈Rn,λ∈R

各类cone和space

cone

集合C是cone，如果 0∈C ，并且对于任意的 x∈C∖{0} 和 λ≥0 ， λx 属于C 从几何考虑，对于C中的任意一个点，C包含了从原点出发沿着x方向的射线

convex cone

如果一个cone C包含了任意 包含在C内的vector conic combination，那么C就是convex cone

这里可以简单的举一个例子。在二维空间上，任意一个扇形（及其夹边中间的部分）都是cone。如果一个扇形超过了180度的内角，那么不是convex；反之如果是180度以内，那么就是convex cone。

cone of a set

给定一个非空集合S，那么S的cone，标记为cone(S)，是最小的包含S的convex cone

Ray

给定一个cone C和一个向量，沿着cone内某一个向量的射线就是ray

Polyhedron

集合 P⊂Rn 是polyhedron，当存在正整数m和矩阵 A∈Rm×n ，满足 P={x∈Rn:Ax≤b}

因此可以认为polyhedron是finite半平面/polyhedra的交集

Polyhedral cone

集合C是polyhedral cone，当C是可数的半平面交集，并且原点在边界上

Polytope

Q是polytope，当Q是可数的vectors的convex hull

Recession cone

给定一个非空的polyhedron P，那么P的recession cone就是 rec(P)={r∈Rn:x+λr∈P,∀x∈P,∀λ∈R+}

Lineality Space

集合P的lineality space是集合 lin(P)={r∈Rn:x+λr∈P,∀x∈P,∀λ∈R}

所以有如下的性质：

让P = {x∈Rn,Ax≤b}=conv(v1,...,vp)+cone(r1,...,rq) 是非空的polyhedron，那么有 rec(P)={r∈Rn,Ar≤0}=cone(r1,...,rq) lin(P)={r∈Rn,Ar=0}

Valid Inequality

对于一个集合 P⊂Rn ，valid inequality就是对于P中的任何一个点 x , 都有cx≤δ

Face

一个polyhedron P的face有如下的形式 F=P⋂{x∈Rn:cx=δ} ，其中 xc≤δ 是P的valid inequality。

根据定义，不难发现 ∅ 和 P <script type="math/tex" id="MathJax-Element-3410">P</script>是trivial的face。

polyhedron P的maximal proper faces叫做facets。minimal faces不包含其他face，也是affine subspace。

Edge

维度为1的face就是P的edge。 如果这个edge没有vertex，那么就是P的minimal face。 如果这个edge有两个vertices，那么这个edge就是这两个vertices中间的线段。 如果这个edge只有一个vertex，那么是一条射线。

Extreme ray

一个pointed polyhedral cone C的extreme ray是C的edge。 一个pointed polyhedral P的extreme ray是 P的recession cone的extreme rays。