优化理论及应用精解【11】

凸集

仿射包（Affine Hull）

是凸分析和组合学中的一个重要概念，它指的是由实线性空间中的集合所生成的仿射集。以下是关于仿射包的详细解释：

定义

设A为实线性空间X中的集合，那么包含A的最小仿射集称为A的仿射包。它是所有包含A的仿射集的全体的交集，也是A中的元素的不断用直线连结后的元素全体。A的仿射包通常记为aff A。

数学描述

对于Eⁿ（n维欧几里得空间）中的子集A，A的仿射包Aff A，为A的任意有限多个元素$x_1，x_2，\dots ，x_k$的仿射组合构成的集合。
具体来说:$$AffA={\theta }_1{x}_1+{\theta }_2{x}_2+\dots +{\theta }_k{x}_k|x_1，x_2，\dots ，x_k\in A，{\theta }_1+{\theta }_2+\dots +{\theta }_k=1$$

性质

1. 最小性：仿射包是包含给定集合的最小仿射集。即，如果S是仿射集合且A ⊆ S，那么aff A ⊆ S。
2. 凸性：仿射包是凸集。因为仿射集是凸集的特例，而仿射包作为包含给定集合的最小仿射集，自然也是凸集。
3. 维数：仿射包的维数定义为平行于aff(A)的子空间的维数。这有助于理解仿射包在更高维空间中的“伸展程度”。

示例

• 如果A是二维空间中的两个不共线点，那么aff A就是经过这两点的直线。
• 如果A是三维空间中的三个不共线的点，那么aff A就是经过这三点的平面（如果这些点共面）或者是由这三点确定的三维空间中的唯一平面（如果这些点不共面）。

应用

仿射包在多个领域中有广泛应用，包括但不限于：

• 凸优化：在凸优化问题中，仿射包用于描述和分析凸集和仿射集的性质。
• 机器学习：在基于图像集的人脸识别等应用中，仿射包可以用于对图像进行建模和优化，以提高识别率。

总之，仿射包是理解和分析集合在仿射空间中的几何特性的重要工具，它在数学、工程学和计算机科学等多个领域中都发挥着重要作用。

仿射维数

仿射维数是一个在凸优化、几何学和拓扑学等领域中使用的概念，它指的是仿射包的维数。以下是对仿射维数的详细解释：

定义

• 仿射维数：集合C的仿射维数定义为其仿射包的维数。仿射包是包含集合C的最小仿射集合，即包含集合C中任意点的所有线性组合（包括常数项）的最小集合。仿射包的维数即为仿射维数，它表示了集合C的几何特性，尤其是其在更大空间中的“自由度”或“伸展程度”。

通俗理解

• 可以将仿射维数想象成集合C在仿射空间中“占据”的维度。例如，一个平面正方形在三维空间中，其仿射维数是2维，因为它虽然嵌入在三维空间中，但其所有点的线性组合仍然只在一个二维平面上。

示例

• 单位圆环：考虑二维平面上的单位圆环，其任意点的线性组合（在这个情况下，主要是旋转和平移，但平移不改变仿射维数）都在一个平面上。因此，单位圆环的仿射维数是2维。
• 三角形：在二维平面上，三角形的仿射维数为2，因为它完全位于一个平面上。
• 线段：在二维平面上，线段的仿射维数为1，因为它可以看作是两个点（即线段的两个端点）的所有线性组合（在这个情况下，主要是缩放和平移，但平移不改变仿射维数）的集合，这些线性组合形成了一条直线。

性质

• 仿射维数是一个整数，它表示了集合C的几何复杂度和在仿射空间中的“伸展程度”。
• 对于任何集合C，其仿射维数都不会超过它所处空间的维度。例如，在三维空间中，任何集合的仿射维数都不可能超过3。

应用

• 仿射维数在凸优化、几何学和拓扑学中有着广泛的应用。它帮助数学家和工程师理解和分析集合的几何特性，进而设计出更高效的算法和解决方案。

总的来说，仿射维数是描述集合几何特性的一个重要工具，它为我们提供了一种量化集合在仿射空间中“占据”维度的方式。

集合的相对内部和相对边界

集合的相对内部

定义：

• 相对内部（Relative Interior）是指拓扑线性空间中的集合在相对意义下的内部。具体来说，设A是拓扑线性空间X的子集，A相对于其闭仿射包的内部称为A的相对内部。这个概念在凸集分离定理的叙述中起重要作用。
• 对于凸集C，把C看作它的仿射包的子集时，C的内部称为C的相对内部，记为riC。

通俗理解：

• 可以将集合C比作一幅画，那么C的相对内部就像是这幅画的“画像”部分，即除去边框的内部区域。
• 如果集合C是一个正方形（二维图形）在三维空间中，其仿射包就是对应的二维平面。此时，C的相对内部就是该正方形在平面内的内部，不包括边界上的点。

集合的相对边界

定义：

• 相对边界（Relative Boundary）是指集合C相对于其闭仿射包的边界。具体地，集合C的相对边界可以表示为C的闭包与其仿射包的相对内部的差集，即bd_rC = clC - riC。

通俗理解：

• 继续以正方形在三维空间中的例子，其相对边界就是正方形的四条边。这些边在三维空间中虽然不“真实”存在（因为三维空间中的点不在二维平面上），但从集合的相对意义上看，它们是正方形的边界。
• 简单来说，相对边界就像是“画像”的画框，界定了集合C的相对内部与外部。

性质与定理

关于凸集的相对内部与相对边界，有以下一些重要的性质定理：

• 相对内部和相对边界都是凸集（如果原集合是凸集的话）。
• 相对内部总是开的，而相对边界总是闭的。
• 对于非空凸集C，如果x是C的相对内部点，那么存在以x为球心的开球，使得该开球与C的仿射包的交集完全包含在C中。

这些概念和性质在凸优化、线性规划、以及更广泛的数学领域中都有重要的应用。

凸集与凸组合

凸集

定义

凸集（Convex Set）是在凸组合下闭合的仿射空间的子集。在欧氏空间中，凸集定义为对于集合内的每一对点，连接该对点的直线段上的每个点也都在该集合内。

原理

凸集的概念源于几何学中的凸性，即一个集合如果其内部任意两点之间的连线都在集合内部，则称该集合为凸集。这种性质使得凸集在优化问题中具有许多良好的性质，如凸集上的凸函数最小化问题具有全局最优解。

性质

1. 并集与交集：两个凸集的交集是凸集，但并集不一定是凸集。
2. 仿射变换：凸集在仿射变换下保持不变，即仿射变换后的集合仍然是凸集。
3. 凸组合：凸集内任意两点之间的线段上的点（包括端点）都在该凸集内。
4. 凸包的生成：任意集合的凸包是由该集合中所有点的凸组合生成的最小凸集。

计算

凸集的计算通常涉及到凸包的生成算法，如Graham扫描法、Andrew’s monotone chain algorithm等。这些算法通过找到集合中所有点的凸组合来生成凸包。

例子

• 直线段、平面区域、球体、立方体等都是凸集。
• 在二维空间中，一个圆形区域是凸集，因为圆内任意两点之间的连线都在圆内。

例题

例题：判断集合S={(x,y)|x^2+y2≤1}是否为凸集。

解答：集合S表示的是二维空间中的一个单位圆及其内部区域。对于S中的任意两点P1(x1,y1)和P2(x2,y2)，连接P1和P2的线段上的任意一点P(x,y)可以表示为P=λP1+(1-λ)P2，其中0≤λ≤1。将P1和P2的坐标代入，得到x=λx1+(1-λ)x2和y=λy1+(1-λ)y2。将x和y代入不等式x^2+y2≤1，可以证明不等式成立（利用平方和的性质和λ的取值范围）。因此，集合S是凸集。

凸组合

定义

凸组合是非负线性组合的一种特殊形式，要求系数之和为1。对于向量集合{x_i}，i ∈ {1, 2, …, n}，存在非负实数{λ_i}，i ∈ {1, 2, …, n}，且∑λ_i = 1，则称∑λ_i x_i为{x_i}的凸组合。

原理

凸组合的原理基于凸集的定义。在凸集中，任意两点之间的线段上的点都在集合内，这可以通过凸组合来表示。凸组合是凸集性质在数学上的一种具体表现形式。

性质

1. 非负性：凸组合的系数必须是非负的。
2. 和为1：凸组合的系数之和必须等于1。
3. 凸集内的点：凸集内任意点的凸组合仍然在凸集内。

计算

凸组合的计算通常涉及到给定集合中点的线性组合，其中系数的选择和调整是关键。在实际应用中，凸组合的计算可能涉及到优化问题，如求凸集上的最小点或最大点等。

例子

• 在二维空间中，给定点P1(1,0)和P2(0,1)，则P=0.5P1+0.5P2=(0.5,0.5)是P1和P2的凸组合。

例题

例题：给定三维空间中的三个点A(1,0,0)，B(0,1,0)和C(0,0,1)，求A、B、C的凸组合P=λA+μB+(1-λ-μ)C，其中λ和μ为非负实数且λ+μ≤1。

解答：根据凸组合的定义，我们可以直接写出P的坐标表达式：P=(λ,μ,1-λ-μ)。由于λ和μ的取值范围限制（非负且和为1或小于1），我们可以得到P在由A、B、C确定的三角形区域（包括边界和内部）内。

参考文献

1. 文心一言