11. 凸优化与几何问题

# 几何问题

# 凸集的投影与距离

1. 投影的定义

   点 $x$ 在集合 $C$ 上的投影定义为：

   $$P_C(x) = \arg\min_{z \in C} \|x - z\|$$

   即 $C$ 中与 $x$ 距离最近的点。

   凸优化形式

   假设 $C$ 具有形式：

   $$C = \{x \mid Ax = b, \ f_i(x) \leq 0, \ i = 1, \ldots, m\}$$

   其中 $f_i: \mathbb{R}^n \to \mathbb{R}$ 是凸函数，则投影问题可以表述为凸规划问题：

   $$\begin{align*} P_C(x) = \arg\min \quad & \|x - z\| \\ \text{s.t.} \quad & Az = b \\ & f_i(z) \leq 0, \quad i = 1, \ldots, m \end{align*}$$

2. 集合之间的距离

   距离的定义

   两个集合 $C$ 和 $\tilde{C}$ 之间的距离定义为：

   $$\text{dist}(C, \tilde{C}) = \min_{z \in C, \tilde{z} \in \tilde{C}} \|z - \tilde{z}\|$$

   凸优化形式

   假设集合 $C$ 和 $\tilde{C}$ 都是凸集，且具有形式：

   $$\begin{gathered} C = \{x \mid Ax = b, \ f_i(x) \leq 0, \ i = 1, \ldots, m\} \\ \tilde{C} = \{z \mid \tilde{A}z = \tilde{b}, \ \tilde{f}_i(z) \leq 0, \ i = 1, \ldots, \tilde{m}\} \end{gathered}$$

   其中 $f_i, \tilde{f}_i: \mathbb{R}^n \to \mathbb{R}$ 是凸函数，则距离计算是一个凸规划问题：

   $$\begin{align*} \min \quad & \|z - \tilde{z}\| \\ \text{s.t.} \quad & Az = b \\ & \tilde{A}\tilde{z} = \tilde{b} \\ & f_i(z) \leq 0, \quad i = 1, \ldots, m \\ & \tilde{f}_i(\tilde{z}) \leq 0, \quad i = 1, \ldots, \tilde{m} \end{align*}$$

3. 例子：单位立方体中两条直线的最小距离

   问题：在单位立方体中，两条粗黑直线之间的最小欧几里得距离是多少？

   答案：$1/\sqrt{3}$

   这是一个典型的凸优化问题，可以通过求解两个凸集（直线）之间的距离得到。

4. Fermat 点问题（Fermat Point Problem）

   问题描述

   Fermat 点（也称为 Torricelli 点或 Fermat-Torricelli 点）是三角形中使得到三个顶点距离之和最小的点。这个问题最初由 Fermat 在给 Evangelista Torricelli 的私人信件中提出，由 Torricelli 解决。

   优化方法

   可以使用优化方法（特别是拉格朗日乘数法）来求解。设三角形内一点到三个顶点的距离分别为 $x, y, z$，它们之间的夹角为 $\alpha, \beta$，则 $x$ 和 $z$ 之间的夹角为 $(2\pi - \alpha - \beta)$。

   使用拉格朗日乘数法，构造拉格朗日函数：

   $$\begin{aligned} L &= x + y + z + \lambda_1(x^2 + y^2 - 2xy\cos(\alpha) - a^2) \\ &\quad + \lambda_2(y^2 + z^2 - 2yz\cos(\beta) - b^2) \\ &\quad + \lambda_3(z^2 + x^2 - 2zx\cos(\alpha + \beta) - c^2) \end{aligned}$$

   其中 $a, b, c$ 是三角形的边长。

   通过求解偏导数并消除拉格朗日乘数，可以得到 $\sin(\alpha) = \sin(\beta)$ 和 $\sin(\alpha + \beta) = -\sin(\beta)$，从而得到 $\alpha = \beta = 120°$。

   几何性质

   • 如果三角形的所有内角都小于 $120°$，则 Fermat 点位于三角形内部
   • Fermat 点到三个顶点的连线之间的夹角都是 $120°$
   • 如果三角形有一个内角大于等于 $120°$，则 Fermat 点位于该角的顶点

# 多面体的相交与包含

1. 多面体的相交检查

   问题：给定两个多面体

   $$\begin{gathered} P_1 = \{x \mid a_i^T x \leq b_i, \ i = 1, \ldots, m\} = \{x \mid Ax \leq b\} \\ P_2 = \{x \mid f_i^T x \leq g_i, \ i = 1, \ldots, l\} = \{x \mid Fx \leq g\} \end{gathered}$$

   检查问题 $P_1 \cap P_2 = \emptyset$？可以通过求解可行性问题：

   $$Ax \leq b, \quad Fx \leq g$$

   如果该可行性问题有解，则 $P_1 \cap P_2 \neq \emptyset$；否则 $P_1 \cap P_2 = \emptyset$。

2. 多面体的包含检查

   问题：检查 $P_1 \subseteq P_2$？

   对于 $k = 1, \ldots, l$，需要检查：

   $$\sup \{f_k^T x \mid Ax \leq b\} \leq g_k$$

   这可以通过求解一系列线性规划问题：

   $$\begin{align*} \text{maximize} \quad & f_k^T x \\ \text{s.t.} \quad & Ax \leq b \end{align*}$$

   如果对于所有 $k = 1, \ldots, l$，都有 $\sup \{f_k^T x \mid Ax \leq b\} \leq g_k$，则 $P_1 \subseteq P_2$。

3. 凸包表示

   如果多面体用凸包表示：

   $$P_1 = \text{Co}\{v_1, \ldots, v_K\}$$

   其中 $v_1, \ldots, v_K$ 是顶点，则包含检查可以转化为检查所有顶点是否在 $P_2$ 内。

# 多面体的一些定理

多面体理论中有许多重要定理，包括：

1. Krein-Milman 定理：紧凸集是其极点的凸包
2. Carathéodory 定理：$\mathbb{R}^n$ 中任意点的凸组合可以用最多 $n+1$ 个点的凸组合表示
3. Helly 定理：关于凸集交集的定理
4. Radon 定理：关于点集分离的定理

这些定理在凸分析和优化理论中具有重要地位。

# 椭球问题

椭球问题涉及椭球的计算和优化，包括：

1. 最小包围椭球（Minimum Enclosing Ellipsoid）

   给定一组点，找到包含所有点的最小体积椭球。

2. 最大内接椭球（Maximum Inscribed Ellipsoid）

   给定一个多面体，找到其内部的最大体积椭球。

3. Chebyshev 中心（Chebyshev Center）

   在多面体内找到最大半径的球心，使得该球完全包含在多面体内。

这些问题都可以表述为凸优化问题（通常是半正定规划问题）。

# 切平面法与中心问题

1. 切平面法（Cutting Plane Method）

   切平面法是一种求解凸优化问题的迭代方法：

   • 在每次迭代中，添加一个切平面（分离超平面）来切割可行域
   • 逐步缩小可行域，逼近最优解
   • 适用于线性规划和某些凸优化问题

2. 中心问题（Center Problems）

   Chebyshev 中心

   在多面体 $P = \{x \mid Ax \leq b\}$ 内找到最大半径的球心：

   $$\begin{align*} \max \quad & r \\ \text{s.t.} \quad & B(x_c, r) \subseteq P \end{align*}$$

   其中 $B(x_c, r)$ 是以 $x_c$ 为圆心、$r$ 为半径的球。

   这可以转化为线性规划问题。

# 角度问题

角度问题涉及几何中的角度计算和优化，可能包括：

• 多面体顶点角度的计算
• 最优角度配置问题
• 角度约束的优化问题

# 谜题

几何谜题（Puzzles）是一类有趣的几何问题，可能包括：

• 多边形凸化问题（Erdős-Nagy 定理）
• 几何拼图问题
• 其他组合几何问题

这些谜题通常可以转化为优化问题，并具有重要的理论意义。

# Rupert's Problem

Rupert's Problem 是一个经典的几何问题，涉及：

• 一个多面体是否可以通过一个更小的"洞"（hole）穿过
• 具体来说，是否存在一个比给定多面体小的多面体，可以通过旋转和移动穿过原多面体上的一个洞

这个问题在几何和优化中具有重要地位，可以表述为约束优化问题。

# 选址优化

选址优化（Location Optimization）是一类重要的几何优化问题，涉及在给定约束下选择最优位置。

1. 问题形式

   一般形式

   给定 $N$ 个点，坐标为 $x_i \in \mathbb{R}^2$（或 $\mathbb{R}^3$）：

   • 某些位置 $x_i$ 是给定的（固定点）
   • 其他 $x_i$ 是变量（自由点）
   • 对于每对点，有一个代价函数 $f_{ij}(x_i, x_j)$

   优化问题：

   $$\min \quad \sum_{i \neq j} f_{ij}(x_i, x_j)$$

   变量是自由点的位置。

   解释：

   • 点代表工厂/仓库，$f_{ij}(x_i, x_j)$ 是设施 $i$ 和 $j$ 之间的运输成本
   • 点代表集成电路上的单元，$f_{ij}(x_i, x_j)$ 表示连线长度

2. $\ell_1$ 范数情况

   对于 $\ell_1$ 范数：

   $$\sum_{i=1}^k [|u - u_i| + |v - v_i|]$$

   最优点是固定点的中位数（median）。这可以通过中位数方法求解。

3. 例子：最小化连接长度

   问题：最小化 $\sum_{(i,j) \in \mathcal{A}} h(\|x_i - x_j\|_2)$，其中：

   • 有 6 个自由点
   • 27 条连接
   • $h(z)$ 是距离的函数

   不同代价函数的最优布局：

   • $h(z) = z$（线性）：最小化总距离
   • $h(z) = z^2$（二次）：最小化总距离的平方
   • $h(z) = z^4$（四次）：更强调长距离连接的惩罚

   连接长度分布：

   不同代价函数会导致不同的连接长度分布 $\|x_i - x_j\|_2$：

   • 线性代价倾向于均匀分布
   • 二次代价倾向于中等长度连接
   • 四次代价倾向于短距离连接（避免长距离）

4. 求解方法

   • 凸优化：当 $f_{ij}$ 是凸函数时，可以使用凸优化方法
   • 梯度下降：对于可微的代价函数
   • 启发式方法：对于大规模问题
   • 几何方法：对于特殊形式的代价函数（如 $\ell_1$ 范数）

5. 应用

   • 设施选址：工厂、仓库、服务中心的位置选择
   • 电路布局：集成电路中单元的放置
   • 网络设计：通信网络节点的位置优化
   • 城市规划：公共设施的位置选择