note-math

[affine_space]

Example 三维中的二维子空间 的参数化

[affine_combination]

[affine_coordinate] 点 中的 可以认为是基于点 的一种坐标. 称为仿射坐标. alias 重心坐标 [barycentric_coordinate]

Example [center_of_affine_point_set] 仿射组合 的中点/重心的仿射坐标是

[affine_independent]

[affine_map_point_ver] alias [simplicial_map] 仿射映射 := 取另一个仿射空间的点 作为顶点的映射到达点 , 其它非顶点的情况是

仿射映射 <==> 对于两个仿射空间选择原点后的两个线性空间, 线性映射 + 平移

注意, 线性映射和平移并不交换. 例子: 的

• 先旋转 度之后是 , 再平移 之后是
• 先平移 之后是 , 再旋转 度之后是

[convex_hull] := 的仿射组合 再额外限制

[simplex] := 由仿射无关的点构成的 convex hull

[extreme_point_of_convex_hull]

Prop extreme-point 已经生成原来的 convex hull, 且是最少生成

Proof 在 和 中不断剔除多余的点. extreme-point 属于 convex hull 且无法由别的点生成, 只能由自己生成, 所以是生成 convex hull 必须的

Prop 定义域在 值域在 的仿射函数 的最值可以在 extreme-point 处取得

Proof

设有限维实仿射空间 , 及其向量空间

Def := interval of := 由 生成的 convex hull

Def := open interval := 生成的 convex hull, 且额外地,

Def [convex] convex set :=

Prop convex set 的交集 convex

以下参考 ref-34

Def [core] 类似于拓扑内部.

Prop [finite_intersect_preserve_core] . Proof 显然. 用

Def [linearly_accessible] 类似于拓扑闭包.

Prop

let convex

Prop let . then . 推论是

Proof

Prop [core_open_interval_core] let , let . then

Proof

Prop convex ==> convex

Proof 由前面的命题得到

Prop convex ==> convex

Proof

Def [boundary]

仿射映射不保持边界. 简单的反例是, 四面体映射到 矩形, 按照顶点对应生成仿射映射

Prop 设 , 则 在 时

Proof 否则, 如果存在 使得 , 则 导出矛盾

Prop convex & ==>

Proof

Prop convex & ==>

Proof

注意: 有可能在 里 但在 的一个仿射子空间 里面

Prop convex & ==>

Proof

Prop [finite_intersect_preserve_convex_closed]

Proof 易知

Def convex open , convex closed

可以对一般集合定义 convex hull

Def

Proof (of convex)

如果 convex 则 . 特别地, 对一般的 , 有

Def := 包含 的仿射子空间的最小维数

Prop [full_dim_iff_core_nonempty]

Proof core nonempty <==> 可以展开 个线性无关方向

Prop

Proof 点数 时, 仿射相关, 有多余的点

Prop [convex_of_union] 设 convex 则

Proof

Prop 设 convex 且 . 则存在 convex 且 (即 集合互补) 且

Proof

设 convex 且是集合互补. 设

Prop

Proof

Prop

Prop

Proof 如果 or 则显然. 假设 . 定义 . 取 的上确界 即可得到

Prop 如果 , 则 是超平面

Proof

Prop [hyperplane_separation] 超平面分离定理. 设 convex 且 , 则存在超平面 分离

注意: 分离是 , 而不是严格分离

Prop 分离

Def [support_hyperplane] 支撑超平面, 在超平面 的一边且

Prop 如果 and 则 (即 ) Proof 不可能是 , 且

Prop let , let , 则存在支撑超平面 且

Proof 对 用超平面分离定理, 因为 . 于是 . 取 , 于是 , 通过反证可得 , 于是

Prop . Proof 反证法, 取 , 利用 的定义和分离超平面的定义, 导出矛盾

Prop 仿射子空间 且 且 , let . 则存在 的支撑超平面 且

Proof 设 . 设 . . 如果 , 取 . 则 展开 的一维补空间. 但是有以下矛盾

• 的一维补空间不会

以下参考 ref-35

Def [order_of_boundary] 的所有支撑超平面的交集 是一个仿射子空间, order 定义为其维数

Def [vertex] 顶点 := order 边界点

Prop [bd_convex_hull_core] let . if , then

Prop [bd_convex_hull_bd] let . if , then

Proof convex and so . if not then , hence , contradict to

上面的两个命题可以推广到 (假设 已经是 的极点)

Prop [support_hyperplane_at_core_of_convex_bd_subset] 设 convex, 设 张开仿射子空间 , 则任何包含 ( 里的 core) 的支撑超平面 都有 , 从而

Proof

Prop

是可能的. 考虑 立方 . 考虑 . 考虑 . 则

Prop 如果存在 使得 (这种性质称为 是暴露面) 则 从而

Prop 向量空间超平面与线性函数的对偶. 向量空间超平面 <==> 存在线性函数 使得

由于 , 的对偶空间 中的 子空间 对应 的 子空间

Prop 向量子空间与线性函数子空间的对偶. 的 维向量子空间 <==> 的 维向量子空间 . 直接的联系方式是

Proof 选取 的一个基 . 则 的基 对应

Prop . Proof

Prop 超平面 对应的线性函数 在 中展开 维子空间 <==> 是 的 维子空间

Prop is vertex <==> 存在超平面 , 对应的线性函数 线性无关, 是 的基,

Prop , 则 , 从而

Prop

Proof 设 , 则 从而

Prop

Def 子空间的加法

Prop 子空间交集的维数

Proof

Prop 仿射超平面 的两边是

Prop (同理 )

以下处理两种多面体描述的等价

• 有限点的 convex hull
• 有界的超平面包围

假设 已经是极点. 假设 已经展开 , 否则, 在它们展开的维数更低的仿射子空间里讨论

Prop 对每个不包含原点的超平面 , 存在唯一的 使得

Proof 向量空间超平面对应 中 展开的一维空间

等价的方程是 , 其中

[pole] 在一个坐标系中, 可以表示为 , 对应

[polar_hyperplane] 反之, 在一个坐标系中, 可以给出超平面

有以下一一对应

• 不包含原点的仿射超平面

Prop

Proof

[polar_dual] let .

Prop

Proof

Prop 如果对每个 存在超平面 有半严格分离 , 则 从而

Proof

Prop 如果

• convex
• (convex closed)

则对每个 都有超平面半严格分离

Proof

Prop 如果 则

Proof

Prop 满足

• convex
• (convex closed)

Proof

Prop

Proof

Prop

Proof

Prop 满足

• convex
• (convex closed)

Proof

• . , 取 足够小
• let .
  
  即
  这是关于 的 值连续函数, 令 得到 从而

let convex, ,

Prop 设 . 则 是 的支撑超平面, support 的点包括 , 它是 的 support 在 的支撑超平面 的 polar-dual

Proof

Prop 这是所有可能的 的支撑超平面

Proof

Def 有限点 convex hull 生成的多面体叫做 V 多面体 (Vertex). 有界超平面包围生成的多面体叫做 H 多面体 (Hyperplane)

Prop H 多面体 满足

• convex
• (convex closed)

Proof 每个 满足以上两个条件, 有限交集也满足以上两个条件

类似于 V 多面体的极点, H 多面体也有极超平面. 对于 如果 则 是多余的, 可去除.

[extreme_hyperplane] Def 极超平面 := 无法包含其它超平面包围区域

Prop 极超平面已经生成原来的 H 多面体, 且是最少生成

Proof 类似极点, 不断剔除多余的超平面

设 H 多面体 有 . 假设 已经都是极超平面

Def [facet]

Prop facet 是 维的 H 多面体

Proof

Prop (从而 H 多面体的 facet 都是支撑超平面)

Proof

Def 递归地定义 的 face 为 的 face 的 facet

Prop 递归地, face 都来自某些 facet ( face) 的交集

Def Two -faces are adjacent if their intersection is a -face

Prop 设 . 则 的所有支撑超平面的交集等于包含 的所有 facet 的交集. Proof facet 展开极超平面, 所以如果支撑超平面不是 facet 展开, 则是多余的

Def [extreme_point] 一般 convex set 的极点定义为 且 convex

Prop 且 convex ==> . Proof ==> 不是 convex

Prop 是极点 <==>

Prop 是极点 <==>

Prop 顶点 ==> 极点 (一般 convex set )

Proof

Prop 对于 H 多面体 , 如果 , 则 在某个 face 的 core

Proof

Prop face 数量有限. 特别地, face, 即, 顶点的数量有限

Prop 对于 H 多面体, 顶点就是极点

Proof

一般情况下, 极点无法蕴含顶点. 考虑 抛物线 . 在 处的支撑超平面只有 , 所以 , 但是 是极点

Prop 对于 V 多面体 有

Proof

我们已经假设过 是 维区域, 但如果是 维区域, 则 可能不是有界的

Def [bounded] 有界 := 每个直线与 交集是有界区间

Prop 交集有界区间的端点在

Prop 如果有界且 (convex closed) 则直线与 交集是有界闭区间

以下假设 有界且 convex closed

Prop

Proof 取 , 取包含 的直线, 与 相交得到闭区间, 且端点在

Prop 的仿射子空间 是 convex closed 的. Proof 维数 已经证明了. 维数 的是 个 convex closed 的交集, 从而根据 finite_intersect_preserve_convex_closed, 也是 convex closed

Prop 如果存在 的仿射子空间 使得 则 和 里的 都是相同的, 从而

Proof 显然 里的 蕴含 里的 . 反之, 设 属于 的 , 则存在 使得 , 从而由于 是 convex closed 的, , 从而 属于 里的

Prop 如果 则 在 和 里 convex 都是相同的

Prop 和 里的 都是相同的, 从而

Prop 设 是支撑超平面, 则

Proof

Prop 存在极点, 即, , 且

Proof

Prop 有界 H 多面体 ==> V 多面体

Proof

Prop 维有界 H 多面体 ==> 维 V 多面体

Prop 设 是 V 多面体, 则 有界

Proof

Prop 在 维的空间中, 如果 是不经过原点的

1. 线段
2. 射线
3. 直线

则 polar-dual 是

1. 两个不经过原点超平面包围
2. 一个不经过原点的超平面和一个经过原点的超平面包围
3. 退化到 维

Proof

Prop 设 是 维 V 多面体, 以 的某点为原点建立坐标系, 则

1. polar-dual 有界, 从而 是有界 H 多面体
2. 包含原点, 从而根据 full_dim_iff_core_nonempty, 是 维的

Proof

Prop 维 V 多面体 ==> 维有界 H 多面体

Proof 是 维 V 多面体 ==> 以 的某点作为原点建立坐标系, 是 维有界 H 多面体且 包含原点 ==> 是 维 V 多面体 ==> 是 维有界 H 多面体

Prop 维 V 多面体 <==> 维有界 H 多面体

Prop 设 是有界多面体, 设 是仿射函数, 则 是有界多面体. Proof 用 V 多面体

和 多面体的情况类似, 值仿射函数的最值可以在极点取到, 根据

更一般地, 连续的 convex 函数 () 的最大值或者连续的 concave 函数 ( 是 convex 函数) 的最小值可以在极点取到

[convex_hull_decomposition] convex hull 可以用这种方式分解到 simplex

• simplex 的顶点属于 convex hull 的顶点
• simplex 内部不相交
• simplex 的并集是 convex hull

分解方式非唯一

Example

的 个点

的 个点

根据上图, 直观上可以这样证明 convex hull 分解为 simplex

对维数归纳. 取一个顶点

将边界面 (facet) 分类为

• 包含
• 不包含

可以分解为由 和不包含 的边界面 形成的锥

每个 是低一维的 convex hull, 可以分解为 维 simplex

这些 simplex 和 组成 维 simplex

convex hull 分解为这些 simplex

Prop [opposite_facet] 设 是 维有界 H 多面体, 是 的极点. 对任意 , 从 出发经过 的射线 与 相交于唯一一点 使得 . 则 必然落在某个不包含 的 facet 上.

Proof

Prop [simplex_vertex_core_ray_to_facet_core] 设 是一个由仿射无关的极点生成的 simplex, 是其不包含 的 facet. 若 , 则从 出发穿过 的射线 () 与 所在超平面的唯一交点 必定满足 .

Proof

Prop [convex_hull_decomposition_to_simplices] convex hull 可以分解为 simplex, 满足:

1. simplex 的顶点属于 convex hull 的顶点;
2. simplex 的内部 () 互不相交;
3. simplex 的并集是该 convex hull;
4. (单纯复形相交性质) 任意两个 simplex , 其交集 要么为空, 要么是 的一个公共 face.

Proof

convex hull 的交集是 convex hull. 用 H 多面体容易证明这一点

Example

Prop convex hull 的减集可能不是 convex hull. 但 (直观上) 仍然可以分解到 convex hull

Proof (from LLM)

Prop simplex 的减集可以分解为 simplex

Prop 设 具有正定向基 . 对于 simplex , 其任一 维 face 上由相交的两个 维 facet 诱导出的两个定向 是严格相反的 (即边界的边界为零).

Proof