凸集基础概念与优化应用解析

1. 凸集基础概念与定义

在优化问题中，凸集是最基础也是最重要的概念之一。简单来说，凸集就是"没有凹陷"的集合。想象一个橡皮球，无论怎么挤压变形，只要不出现凹陷，它就是一个凸集；而如果出现凹陷，比如一个甜甜圈，就不是凸集。

数学上的严格定义是：对于集合C⊂ℝⁿ，如果对于任意两点x,y∈C，连接这两点的线段上的所有点都在C内，那么C就是凸集。用公式表示为：
∀x,y∈C, θ∈[0,1], 有(1-θ)x + θy ∈ C

这个定义看似简单，但蕴含着深刻的几何意义。它保证了在凸集内任意两点间的"过渡"都是平滑的，没有突变或间断。这个性质在优化问题中至关重要，因为它确保了如果我们沿着两点间的连线搜索，不会突然"掉出"可行域。

注意：凸集的定义中θ的范围是闭区间[0,1]，这意味着包含端点。这一点在实际应用中非常重要，特别是在处理边界情况时。

2. 常见凸集类型与应用实例

2.1 线性子空间与仿射集

线性子空间是最简单的凸集例子。它满足加法和数乘封闭性：x,y∈S ⇒ ax+by∈S, ∀a,b∈ℝ。几何上，线性子空间必须经过原点，如直线、平面等。

仿射集则是线性子空间的平移。形式上，S = T + v₀，其中T是线性子空间，v₀是固定向量。在实际应用中，仿射集经常出现在线性方程组的解空间中。

工程应用实例：在电路设计中，基尔霍夫定律形成的约束条件就定义了一个仿射集。电压和电流的关系通过线性方程描述，其解空间就是一个仿射集。

2.2 线性不等式定义的集合

形如{x | Ax ≤ b}的集合是凸集。这个性质非常重要，因为大多数工程优化问题都可以表示为线性不等式约束。

证明思路：取x,y满足Ax≤b，Ay≤b。对于它们的凸组合z=(1-θ)x+θy，有：
Az = A[(1-θ)x + θy] = (1-θ)Ax + θAy ≤ (1-θ)b + θb = b

实际应用：在资源分配问题中，资源限制通常表示为线性不等式，如CPU、内存等资源的分配上限。

2.3 范数球与椭球

范数球Bᵣ = {x | ||x|| ≤ r}是凸集，其中||·||可以是任意范数。特别地：

• l₂范数：标准的欧几里得球
• l₁范数：菱形（在2D中是旋转45度的正方形）
• l∞范数：轴对齐的盒子

椭球是范数球的