11. 凸优化与几何问题

# 几何问题

# 凸集的投影与距离

投影的定义

点 $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*}$
集合之间的距离

距离的定义

两个集合 $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*}$
例子：单位立方体中两条直线的最小距离

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

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

这是一个典型的凸优化问题，可以通过求解两个凸集（直线）之间的距离得到。
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 点位于该角的顶点

# 多面体的相交与包含

多面体的相交检查

问题：给定两个多面体

$\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$ 。
多面体的包含检查

问题：检查 $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$ 。
凸包表示

如果多面体用凸包表示：

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

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

# 多面体的一些定理

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

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

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

# 椭球问题

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

最小包围椭球（Minimum Enclosing Ellipsoid）

给定一组点，找到包含所有点的最小体积椭球。
最大内接椭球（Maximum Inscribed Ellipsoid）

给定一个多面体，找到其内部的最大体积椭球。
Chebyshev 中心（Chebyshev Center）

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

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

# 切平面法与中心问题

切平面法（Cutting Plane Method）

切平面法是一种求解凸优化问题的迭代方法：
- 在每次迭代中，添加一个切平面（分离超平面）来切割可行域
- 逐步缩小可行域，逼近最优解
- 适用于线性规划和某些凸优化问题
中心问题（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）是一类重要的几何优化问题，涉及在给定约束下选择最优位置。

问题形式

一般形式

给定 $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)$ 表示连线长度
$\ell_1$ 范数情况

对于 $\ell_1$ 范数：

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

最优点是固定点的中位数（median）。这可以通过中位数方法求解。
例子：最小化连接长度

问题：最小化 $\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$ ：
- 线性代价倾向于均匀分布
- 二次代价倾向于中等长度连接
- 四次代价倾向于短距离连接（避免长距离）
求解方法
- 凸优化：当 $f_{ij}$ 是凸函数时，可以使用凸优化方法
- 梯度下降：对于可微的代价函数
- 启发式方法：对于大规模问题
- 几何方法：对于特殊形式的代价函数（如 $\ell_1$ 范数）
应用
- 设施选址：工厂、仓库、服务中心的位置选择
- 电路布局：集成电路中单元的放置
- 网络设计：通信网络节点的位置优化
- 城市规划：公共设施的位置选择