坟墓里寂静无比，埋葬你的是你所有没说出口的话

本文由AI整理自凌青老师课程。因看视频太耗时间，故而整理，仅供个人参考。

第一课：引言（一）

核心摘要 (Key Takeaways)

• 凸优化是“简单的优化问题”：课程聚焦于凸优化，因其结构良好、可高效求解，而一般优化问题（非凸）通常难以处理。
• 优化问题的三要素：可行解集合、最优性准则（目标函数）、求解方法；缺一不可。
• 标准优化问题的数学形式：最小化目标函数 $f_0(x)$，满足不等式约束 $f_i(x) \leq b_i$（$i = 1,\dots,M$）。
• 优化无处不在：从日常生活决策、物流调度、通信功率控制到图像去噪、电路设计，均涉及优化建模。
• 课程考核结构：20% 平时成绩（课堂小测验）、80% 期末考试，另设最高10分的可选课程论文（极难获得高分）。

1. 课程介绍与安排

1.1 课程基本信息

• 课程名称：凸优化（原名“最优化理论”，因非凸优化太难，故聚焦于凸优化——即简单的优化问题）。
• 授课时间：第2周至第16周，共60学时；第17周期末考试。
• 助教：王浩、侍卫。
• 联系方式：可通过邮件联系教师或助教。

1.2 考核方式

• 平时成绩（20%）：通过2–3次课堂小测验完成（非课后作业），提前一节课通知。
• 期末考试（80%）。
• 课程论文（额外0–10分，非强制）：
  • 面向研究生，需将自身研究与凸优化结合。
  • 要求使用凸优化方法取得实质性成果。
  • 极难拿高分：去年最高仅3分。

1.3 参考教材

1. 主教材：Convex Optimization by Stephen Boyd（免费电子版可在作者主页下载）。
2. 补充教材（算法方向）：两本由 Bertsekas（巴萨卡斯）所著的优化算法书籍（电子版较难获取）。

建议：无需购买 Boyd 的书，重点掌握基本内容即可。

2. 优化问题的基本定义

2.1 什么是优化？

优化（或称数学规划）是从一个可行解集合中寻找最优元素的过程。

三要素：

1. 可行解集合（Feasible Set）：所有满足约束条件的解构成的集合。
2. 最优性准则：通过目标函数定义“最优”。
3. 求解方法：算法或策略，用于找到最优解。

例子（贾宝玉找老婆）：

• 可行集：大观园中所有适龄女性。
• 最优准则：贾宝玉的喜好（主观目标函数）。
• 求解方法：逐一试探。
• 问题：最优性准则模糊 → 最终出家。说明三要素缺一不可。

2.2 数学形式

任一优化问题可表示为：

• $x \in \mathbb{R}^n$：优化变量（n维向量）。
• $f_0(x)$：目标函数（从 $\mathbb{R}^n \to \mathbb{R}$）。
• $f_i(x) \leq b_i$：不等式约束（共 $M$ 个）。
• 可行集：$\{ x \mid f_i(x) \leq b_i, \, \forall i \}$。
• 最优解：记为 $x^*$，满足对任意可行 $z$，有 $f_0(x^*) \leq f_0(z)$。

注：等式约束 $h(x) = c$ 可等价转化为两个不等式约束：$h(x) \leq c$ 且 $-h(x) \leq -c$。为简化，课程仅讨论不等式形式。

3. 简单示例分析

3.1 一维无约束优化（带界约束）

• 目标函数：$f_0(x)$（如二次函数）。
• 约束：$-A \leq x \leq A$，等价于：
  • $x \leq A$
  • $-x \leq A$

可行集：区间 $[-A, A]$。
最优解：通常为单点（如抛物线顶点），但不一定唯一。

3.2 多最优解情形

• 若目标函数在可行域内有多个极小值点（如双谷函数），则最优解集为多个点的集合。
• 关键结论：
  • 最优解不一定唯一。
  • 唯一最优解的问题通常更简单；多解或连续解集的问题更复杂。

4. 优化的实际应用案例

4.1 日常生活中的优化

• 个人预算分配：在有限工资下，最大化生活满意度（食物、衣物等支出分配）。
• 国家资源分配：在国防、经济建设、对外援助间分配有限财政资源。

共性：在资源约束下，最大化效用或最小化成本。

4.2 数据拟合（最小二乘法）

• 背景：物理实验获得离散数据点 $(x_i, y_i)$，需拟合曲线（如二次函数 $y = ax^2 + bx + c$）。
• 目标：估计参数 $a, b, c$，使测量误差最小。
• 最小二乘准则： $\min_{a,b,c} \sum_{i=1}^N e_i^2 = \sum_{i=1}^N \left( y_i - (a x_i^2 + b x_i + c) \right)^2$
• 约束扩展：若已知 $c > 0$，则增加约束 $c \geq 0$，形成有约束优化问题。

4.3 线性二次调节器（LQR）

• 系统模型（离散线性系统）： $x_{k} = A x_{k-1} + B u_{k}$
  • $x_k$：k时刻系统状态。
  • $u_k$：控制输入。
  • $A, B$：状态转移与输入矩阵。
• 目标函数： $\min_{\{u_k\}} \sum_{k=1}^N \left( x_k^\top Q x_k + u_k^\top R u_k \right)$
  • 第一项：状态偏差惩罚（希望状态接近目标）。
  • 第二项：控制能量惩罚（希望输入不过大）。
• 性质：这是一个标准的凸优化问题，可通过求解 Riccati 方程求解。

4.4 通信中的多用户功率控制

• 场景：多个发射端（TX）与接收端（RX）共存，相互干扰。
• 变量：每个用户 $i$ 的发射功率 $p_i$，满足 $0 \leq p_i \leq b_i$。
• 干扰模型：
  • $\alpha_{ij}$：用户 $j$ 对用户 $i$ 的单位功率干扰。
  • $\delta_i^2$：用户 $i$ 的高斯白噪声方差。
• 信干噪比（SINR）： $\text{SINR}_i = \frac{p_i}{\delta_i^2 + \sum_{j \neq i} \alpha_{ij} p_j}$
• 用户速率：$f_i \propto \log(1 + \text{SINR}_i)$。
• 优化目标（运营商视角）： $\max_{\{p_i\}} \sum_{i=1}^N f_i(p_1, \dots, p_N) \quad \text{s.t.} \quad 0 \leq p_i \leq b_i$
• 挑战：全局流量最大可能导致部分用户速率极低 → 需引入公平性约束（如均衡速率）。

4.5 图像去噪（TV-L2 模型）

• 问题：从带噪图像 $f_0(x,y)$ 恢复干净图像 $f(x,y)$。
• 先验知识：自然图像具有分片光滑性（piecewise smoothness）。
• 全变分（Total Variation, TV）正则项： $\|f\|_{\text{TV}} = \sum_{x,y} \sqrt{ \left( \frac{\partial f}{\partial x} \right)^2 + \left( \frac{\partial f}{\partial y} \right)^2 }$ （离散形式为相邻像素差分的 $\ell_2$ 范数之和）
• 优化模型（TV-L2）： $\min_f \quad \lambda \|f\|_{\text{TV}} + \|f - f_0\|_F^2$
  • 第一项：鼓励分片光滑。
  • 第二项（Frobenius 范数）：保证与观测图像接近。
  • $\lambda > 0$：平衡两项的权重。
• 极端情况分析：
  • 若 $\lambda = 0$ → $f = f_0$（无去噪）。
  • 若无第二项 → $f = 0$（全黑图像，TV 最小）。

4.6 超大规模集成电路（VLSI）设计

• 任务：连接 $N$ 个门电路（$D_1, \dots, D_N$）以实现特定逻辑功能。
• 目标：在满足功能约束下，优化性能指标（如能耗、成本）。
• 数学抽象：
  • 可行连接方案集合：$\{T_1, \dots, T_M\}$。
  • 选择一个方案 $x \in \{T_1, \dots, T_M\}$ 以最小化性能指标 $P(x)$。
• 难点：此类问题通常是 NP-hard（计算复杂度极高），属于难优化问题。

4.7 网络最短路径问题（计算机领域）

• 场景：互联网路由、导航系统。
• 模型：在无向图中，寻找两点间代价最小的路径。
• 本质：一类特殊的组合优化问题，可用图算法（如 Dijkstra）高效求解（属于“简单”优化问题）。

5. 问题难度与课程定位

• 核心观点：凸优化 = 简单优化问题；非凸/组合优化 = 难问题。
• 课程目标：
  • 掌握凸优化的基本理论与建模方法。
  • 学会识别哪些实际问题可转化为凸优化（从而高效求解）。
  • 理解哪些问题本质上是难解的（如 VLSI 设计），避免盲目尝试。

flowchart TD
    A[实际问题] --> B{能否建模为
凸优化问题?}
    B -->|是| C[使用凸优化方法
高效求解]
    B -->|否| D{是否为
组合/NP-hard问题?}
    D -->|是| E[需启发式/近似算法
或问题简化]
    D -->|否| F[可能需非凸优化技术
但无全局最优保证]

flowchart TD
    A[实际问题] --> B{能否建模为
凸优化问题?}
    B -->|是| C[使用凸优化方法
高效求解]
    B -->|否| D{是否为
组合/NP-hard问题?}
    D -->|是| E[需启发式/近似算法
或问题简化]
    D -->|否| F[可能需非凸优化技术
但无全局最优保证]

flowchart TD
    A[实际问题] --> B{能否建模为
凸优化问题?}
    B -->|是| C[使用凸优化方法
高效求解]
    B -->|否| D{是否为
组合/NP-hard问题?}
    D -->|是| E[需启发式/近似算法
或问题简化]
    D -->|否| F[可能需非凸优化技术
但无全局最优保证]

流程图解释：
该流程图描述了面对一个实际优化问题时的决策路径。首先判断其是否可转化为凸优化问题（课程核心）。若可以，则有成熟高效算法；若不能，则进一步判断是否属于组合优化（如 VLSI、旅行商问题），此类问题通常 NP-hard，需特殊处理；否则可能涉及非凸优化，求解困难且无全局最优性保证。本课程重点训练第一步的建模与识别能力。

第二课：引言（二）——优化问题建模与分类

核心摘要 (Key Takeaways)

• 最短路径问题可以建模为一个优化问题，通过引入 0-1 决策变量 $x_{ij}$ 和流量守恒约束，将其形式化为数学规划问题。
• 线性规划是凸优化的特例，其目标函数和约束均为线性，最优解总出现在可行域的顶点或边界上。
• 凸优化是“容易求解”的核心类别：只要问题可建模为凸优化（目标函数凸、可行域凸），就具备良好性质，可用高效算法求解。
• 优化问题有多种分类维度：线性/非线性、凸/非凸、光滑/非光滑、连续/离散、单目标/多目标，其中凸与非凸是最本质的区分。
• 课程目标是教会如何将实际问题转化为“容易的”凸优化问题，并理解其理论基础与求解思路。

一、最短路径问题的优化建模

1.1 问题背景

• 考虑一个无向图 $G = (V, E)$：
  • $V$：顶点集合（每个圆圈代表一个顶点）
  • $E$：边集合（连接两个顶点的线段）
• 每条边 $(i,j) \in E$ 有一个权重 $w_{ij} \geq 0$，表示从顶点 $i$ 到 $j$ 的“代价”（如时间、距离等）。
• 目标：给定起点（源点）$s$ 和终点（汇点）$t$，找到一条从 $s$ 到 $t$ 的路径，使得路径上所有边的权重之和最小。

例子：访问网站时，希望数据包传输路径耗时最短。

1.2 数学建模

引入决策变量：

• $x_{ij} \in \{0, 1\}$：若选择边 $(i,j)$，则 $x_{ij} = 1$；否则为 0。

目标函数

最小化总代价：

约束条件（流量守恒）

为确保解构成一条从 $s$ 到 $t$ 的路径，需满足：

• 起点 $s$：净流出为 1
  

  $$\sum_{j: (s,j) \in E} x_{sj} - \sum_{j: (j,s) \in E} x_{js} = 1$$

• 终点 $t$：净流入为 1（即净流出为 -1）
  

  $$\sum_{j: (t,j) \in E} x_{tj} - \sum_{j: (j,t) \in E} x_{jt} = -1$$

• 中间任意顶点 $i \neq s,t$：流入 = 流出（净流量为 0）
  

  $$\sum_{j: (i,j) \in E} x_{ij} - \sum_{j: (j,i) \in E} x_{ji} = 0$$

关键洞察：原始问题要求 $x_{ij} \in \{0,1\}$（整数规划），但对于最短路径问题，可将约束松弛为 $x_{ij} \geq 0$，问题仍能得到整数最优解。此时问题变为线性规划（Linear Programming, LP），属于“容易求解”的类别。

二、优化问题的分类体系

2.1 线性规划 vs. 非线性规划

• 线性规划（LP）：
  • 目标函数 $f_0(x)$ 和所有约束函数 $f_i(x)$（$i=1,\dots,m$）均为线性函数。
  • 线性函数定义：对任意 $x, y$ 和标量 $\alpha, \beta$，有
    $f_i(\alpha x + \beta y) = \alpha f_i(x) + \beta f_i(y)$
  • 几何性质：可行域是由超平面围成的凸多面体；目标函数等高线为平行超平面。
  • 最优解位置：必定出现在可行域的顶点（极点）或边界上。
  • 经典算法：单纯形法（Simplex Method）。

例子：最短路径问题可转化为 LP。

• 非线性规划（NLP）：
  • 至少有一个函数（目标或约束）是非线性的。
  • 求解难度显著增加，性质复杂。

2.2 凸规划 vs. 非凸规划（课程核心）

• 凸优化问题：

  • 目标函数 $f_0(x)$ 是凸函数
  • 可行域是凸集（即所有约束函数 $f_i(x) \leq 0$ 中的 $f_i$ 为凸函数）
  • 关键性质：局部最优解 = 全局最优解；存在高效算法（如内点法）。
  • 重要结论：所有线性规划都是凸优化问题（因为线性函数既是凸函数也是凹函数）。

• 非凸优化问题：

  • 可能存在多个局部最优解，难以保证找到全局最优。
  • 通常属于“难解”问题（NP-hard）。

直观理解：

• 凸函数：图像呈“碗状”，任意两点连线在函数图像上方。无法找到多个不相邻的“低谷”。
• 非凸函数：可能存在多个孤立的局部最小值点。

课程观点：现代优化理论认为，凸 vs. 非凸才是区分“易”与“难”的本质标准，而非传统的线性 vs. 非线性。

2.3 其他分类维度

（1）光滑 vs. 非光滑

• 光滑优化：目标函数 $f_0(x)$ 处处可微（如二次函数）。
• 非光滑优化：目标函数不可微（如含绝对值、最大值函数）。
• 注意：此分类非本质，难度差异远小于凸/非凸之分。

（2）连续 vs. 离散

• 连续优化：可行域为连续集合（如实数区间、凸多面体）。
• 离散优化：可行域为离散点集（如整数、组合选择）。
  • 例子：集成电路设计、最短路径原始 0-1 模型。
  • 特点：通常为非凸问题，属于“难解”类别。

重要说明：连续问题不一定容易——若非凸，仍难解。

（3）单目标 vs. 多目标优化

• 单目标：仅一个目标函数 $f_0(x)$，标准优化形式。
• 多目标：同时优化多个目标，如 $\min \{f_1(x), f_2(x)\}$。
  • 帕累托最优（Pareto Optimality）：无法在不恶化其他目标的前提下改进任一目标。
  • 帕累托前沿（Pareto Front）：所有帕累托最优解在目标空间中的轨迹。
  • 常用策略：加权求和 $\min \lambda_1 f_1(x) + \lambda_2 f_2(x)$，但不一定能覆盖整个帕累托前沿。

课程范围：仅简要介绍多目标概念，不深入讲解。

三、课程目标与哲学

3.1 核心目标

• 学会将实际问题建模为“容易的”优化问题（尤其是凸优化）。
• 理解：“只要能将问题转化为凸优化，就完成了90%的工作。”
• 掌握：
  1. 建模：如何根据任务构造目标函数与约束；
  2. 分析：理解凸问题的性质（如对偶性、KKT条件）；
  3. 求解：了解基本算法思想（不深入复杂实现）。

3.2 “容易”与“难”的相对性

• 课程假设：目标函数 $f(x)$ 及其导数（一阶、二阶）易于计算。
• 不讨论：目标函数本身难以评估的问题（如需实验测量、模拟耗时）。
• 例子：“找出教室里头发最少的同学”看似简单，实为离散优化 + 目标函数难计算，不属于本课程范畴。

四、优化发展简史（关键人物与贡献）

注：本课程聚焦建模与理论，不深入讲解内点法等复杂算法。

五、总结与展望

• 优化的本质：在约束下寻找最优决策。
• 本课程主线：凸优化——因其具备良好性质，是连接理论与应用的桥梁。
• 学习建议：重点掌握如何识别和构造凸问题，理解“为什么凸问题容易解”。

希尔伯特名言：“只要一个问题能被清晰描述，就等于解决了80%。”
本课程延伸：“只要一个问题能被转化为凸优化，就等于解决了90%。”

第三课：仿射集、凸集与凸包（1）

核心摘要 (Key Takeaways)

• 仿射集（Affine Set） 是指集合中任意两点的整条直线仍包含于该集合；等价地，任意有限个点的仿射组合（系数和为1的线性组合）仍在集合内。
• 线性方程组的解集 $\{x \mid Ax = b\}$ 是仿射集的典型例子；通过平移（减去一个特解 $x_0$），可将其转化为零空间（Null Space），即一个过原点的子空间。
• 仿射包（Affine Hull） 是包含给定集合 $C$ 的最小仿射集，由 $C$ 中所有点的仿射组合构成。
• 仿射集是凸集的推广：所有仿射集都是凸集，但反之不成立（如线段是凸集但不是仿射集）。
• 子空间是过原点的仿射集，具有对任意线性组合封闭的性质（而仿射集仅对仿射组合封闭）。

1. 优化问题的标准形式与术语澄清

1.1 优化问题的一般形式

一个标准的单目标有约束优化问题可表示为：

其中：

• $x \in \mathbb{R}^n$ 是 优化变量
• $f_0(x)$ 是 目标函数
• $f_i(x) \leq b_i$ 是 不等式约束
• “s.t.” 是 “subject to” 的缩写

注：本课程聚焦于此类问题中的易解子类——即凸优化问题。

1.2 “优化” vs “数学规划”

• 历史插曲：二战期间，科学家向军方申请经费时，因“优化”一词被认为“太土”，改称“规划”（如“线性规划”、“非线性规划”），以显得更“酷”。
• 实质等价：“数学规划” = “优化”，二者指同一类问题。

关键区分：问题难易不取决于是否线性，而取决于是否凸——凸规划 = 易解，非凸规划 = 难解。

2. 仿射集（Affine Set）的定义与性质

2.1 直观定义：基于直线

• 直线的参数方程：给定两点 $x_1 \ne x_2 \in \mathbb{R}^n$，连接它们的直线可表示为：

  $$y = \theta x_1 + (1 - \theta) x_2, \quad \theta \in \mathbb{R}$$

  或等价地：

  $$y = x_2 + \theta (x_1 - x_2), \quad \theta \in \mathbb{R}$$

• 线段的参数方程（对比）：

  $$y = \theta x_1 + (1 - \theta) x_2, \quad \theta \in [0, 1]$$

例子（几何可视化）：

• 在二维平面中，两点 $x_1, x_2$ 确定一条无限延伸的直线。
• 两点之间的有限部分称为线段。

2.2 仿射集的正式定义

一个集合 $C \subseteq \mathbb{R}^n$ 是仿射集，当且仅当：

对任意 $x_1, x_2 \in C$ 和任意 $\theta \in \mathbb{R}$，都有

$$\theta x_1 + (1 - \theta) x_2 \in C$$

判断示例：

• 直线：是仿射集 （任意两点连线仍在直线上）
• 线段：不是仿射集 （取端点，其连线超出线段）
• 整个 $\mathbb{R}^2$ 空间：是仿射集
• 正方形区域（含内部）：不是仿射集 （取对角顶点，连线穿出边界）

2.3 仿射组合与广义定义

为处理多个点，引入仿射组合概念：

• 给定 $k$ 个点 $x_1, \dots, x_k \in \mathbb{R}^n$ 和标量 $\theta_1, \dots, \theta_k \in \mathbb{R}$，若满足：

  $$\sum_{i=1}^k \theta_i = 1$$

  则点：

  $$\sum_{i=1}^k \theta_i x_i$$

  称为 $x_1, \dots, x_k$ 的一个仿射组合。

• 仿射集的等价定义：
  集合 $C$ 是仿射集 $\iff$ 对任意 $k \geq 1$，任意 $x_1, \dots, x_k \in C$，其任意仿射组合仍属于 $C$。

证明思路（两定义等价）：

• 从两点定义可归纳推广至 $k$ 点（如三点组合可拆为两次两点组合）。
• 反之，取 $k=2$ 即得原始定义。

3. 仿射集与子空间的关系

3.1 一般仿射集 vs 子空间

• 问题：仿射集仅对仿射组合封闭（系数和为1），但子空间应对任意线性组合封闭。
• 观察：某些特殊仿射集（如过原点的直线）满足更强性质。

反例：不过原点的直线 $L = \{ (1,0) + t(0,1) \mid t \in \mathbb{R} \}$
取 $x_1 = (1,1), x_2 = (1,2) \in L$，则 $x_1 + x_2 = (2,3) \notin L$，故不封闭于任意线性组合。

3.2 从仿射集构造子空间

对任意仿射集 $C$，任取一点 $x_0 \in C$，定义新集合：

则 $V$ 具有以下性质：

1. $V$ 是子空间（即对任意 $\alpha, \beta \in \mathbb{R}$ 和 $v_1, v_2 \in V$，有 $\alpha v_1 + \beta v_2 \in V$）。
2. $V$ 过原点（因 $x_0 - x_0 = 0 \in V$）。
3. $x_0$ 的选择不影响 $V$ 的结构（不同 $x_0$ 生成同一子空间）。

几何意义：将仿射集 $C$ 平移，使其经过原点，得到对应的方向子空间。

4. 仿射集的重要例子：线性方程组的解集

4.1 解集是仿射集

考虑线性方程组：

其中 $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$。其解集：

是一个仿射集。

证明：

任取 $x_1, x_2 \in C$，即 $Ax_1 = b$, $Ax_2 = b$。对任意 $\theta \in \mathbb{R}$，有：

故 $\theta x_1 + (1 - \theta) x_2 \in C$，证毕。

4.2 对应的子空间：零空间（Null Space）

任取特解 $x_0 \in C$（即 $Ax_0 = b$），则平移后的集合：

满足：

即：

这正是矩阵 $A$ 的零空间（Null Space），记作 $\mathcal{N}(A)$。

结论：任何仿射集均可表示为“特解 + 齐次解”，即 $C = x_0 + \mathcal{N}(A)$。

4.3 逆命题成立

任意仿射集都可表示为某个线性方程组的解集。
（证明略，但强调其重要性：仿射集与线性方程组一一对应）

5. 仿射包（Affine Hull）

5.1 动机

给定任意集合 $C$（可能非仿射），如何构造包含 $C$ 的最小仿射集？

5.2 定义

集合 $C$ 的仿射包（Affine Hull），记作 $\text{aff}(C)$，定义为：

即：所有由 $C$ 中点构成的仿射组合的集合。

5.3 性质

• $\text{aff}(C)$ 是包含 $C$ 的最小仿射集。
• 若 $C$ 已是仿射集，则 $\text{aff}(C) = C$。
• 例子：
  • 若 $C$ 是两个不重合点，则 $\text{aff}(C)$ 是穿过这两点的直线。
  • 若 $C$ 是三个不共线点，则 $\text{aff}(C)$ 是它们张成的平面。

6. 课程内容预告与学习资源

6.1 教材结构

本课程主要讲授以下章节（来自指定教材）：

• 第二章：凸集（Convex Sets）
• 第三章：凸函数（Convex Functions）
• 第四章：凸优化问题（Convex Optimization Problems）
• 第五章：对偶理论（Duality）
• 第九、十章（部分）：优化算法（无约束与有约束）

建议：仅打印相关章节，无需整本。

6.2 学习资源

• 教材最新版可在 Stephen Boyd 主页 获取。
• 配套视频与 PPT 亦可在线找到。

总结

本课从直线与线段的几何直观出发，严格定义了仿射集，并通过仿射组合推广至多点情形。核心发现是：线性方程组的解集是仿射集，且可通过平移转化为零空间（子空间）。进一步引入仿射包概念，为任意集合构造最小仿射超集。这些概念是理解凸集（下一课）和凸优化的基石——仿射集是凸集的特例，而凸集允许 $\theta \in [0,1]$（线段封闭），仿射集要求 $\theta \in \mathbb{R}$（直线封闭）。

第四课学习笔记：仿射集 / 凸集 / 凸锥 + 集合 / 组合 / 包（2）

核心摘要 (Key Takeaways)

• 仿射包 是包含给定集合的最小仿射集；凸包 是包含给定集合的最小凸集；凸锥包 是包含给定集合的最小凸锥。
• 仿射集 ⊆ 凸集，但反之不成立；凸锥一定是凸集，但凸集不一定是凸锥。
• 三种组合方式对应三种集合构造：
  • 仿射组合：系数和为1（无符号限制）→ 仿射集
  • 凸组合：系数和为1 且 所有系数 ∈ [0,1] → 凸集
  • 凸锥组合：所有系数 ≥ 0（无和为1要求）→ 凸锥
• 单点集 是仿射集、凸集；仅当该点为原点时，才是凸锥。
• 空集 同时是仿射集、凸集、凸锥——因其“无反例”而满足所有定义。

1. 仿射集与仿射包（Affine Set & Affine Hull）

定义回顾

• 集合 $C$ 是 仿射集，当且仅当对任意 $x_1, x_2 \in C$，其整条直线 $\theta x_1 + (1 - \theta) x_2$（$\theta \in \mathbb{R}$）都属于 $C$。
• 仿射组合：对 $k$ 个点 $x_1, \dots, x_k \in C$，若 $\sum_{i=1}^k \theta_i = 1$（$\theta_i \in \mathbb{R}$），则 $\sum_{i=1}^k \theta_i x_i$ 称为仿射组合。
• 仿射集等价于：任意有限个点的仿射组合仍属于该集合。

仿射包（Affine Hull）

• 给定任意集合 $C$，其仿射包 $\text{aff}(C)$ 是包含 $C$ 的最小仿射集。
• 构造方式：取 $C$ 中任意有限点的所有仿射组合构成的集合。

例子

• 两点集 $\{x_1, x_2\}$：仿射包是连接两点的整条直线。
• 三点不共线集 $\{x_1, x_2, x_3\}$：仿射包是它们张成的二维平面。
• 若 $C$ 本身是仿射集：则 $\text{aff}(C) = C$。

💡 关键理解：仿射包是“用直线和超平面把点撑开到最大仿射结构”。

2. 凸集与凸包（Convex Set & Convex Hull）

定义

• 集合 $C$ 是 凸集，当且仅当对任意 $x_1, x_2 \in C$，其线段 $\theta x_1 + (1 - \theta) x_2$（$\theta \in [0,1]$）都属于 $C$。
• 凸组合：对 $k$ 个点 $x_1, \dots, x_k \in C$，若： $\sum_{i=1}^k \theta_i = 1 \quad \text{且} \quad \theta_i \in [0,1] \quad \forall i$ 则 $\sum_{i=1}^k \theta_i x_i$ 称为凸组合。
• 凸集等价于：任意有限个点的凸组合仍属于该集合。

凸包（Convex Hull）

• 给定任意集合 $C$，其凸包 $\text{conv}(C)$ 是包含 $C$ 的最小凸集。
• 构造方式：取 $C$ 中任意有限点的所有凸组合构成的集合。

例子

• 六边形边界（无内部）：不是凸集（两点连线可能穿出边界）。
• 填充六边形（含内部）：是凸集。
• 正方形去掉两个内点：仍是凸集（只要不破坏“任意两点连线在内”）。
• 正方形去掉两个边界点（如对角）：不是凸集 → 其凸包是完整正方形。
• 离散点集（如教室中的学生）：非凸集；其凸包是最外层点构成的凸多边形（“用绳子绕一圈”）。

✅ 重要关系：所有仿射集都是凸集，因为直线包含线段。

3. 锥与凸锥（Cone & Convex Cone）

锥（Cone）的定义

• 集合 $C$ 是 锥，若对任意 $x \in C$ 和任意 $\theta \geq 0$，都有 $\theta x \in C$。
• 锥必须包含从原点出发的射线（不一定连续）。

例子

• 三条从原点出发的射线：是锥（即使不连续）。
• Y 形结构（交点不在原点）：不是锥（不满足 $\theta x \in C$）。
• 倾斜的冰淇淋形（顶点在原点）：是锥。

凸锥（Convex Cone）的定义

• 集合 $C$ 是 凸锥，若它既是锥又是凸集。
• 等价定义：对任意 $x_1, x_2 \in C$ 和 $\theta_1, \theta_2 \geq 0$，有： $\theta_1 x_1 + \theta_2 x_2 \in C$
• 推广到 $k$ 点：凸锥组合 = $\sum_{i=1}^k \theta_i x_i$，其中 $\theta_i \geq 0$（不要求和为1）。

例子

• 倾斜冰淇淋形（顶点在原点）：是凸锥（任意两点的非负线性组合仍在其中）。
• 过原点的直线：是凸锥（因 $\theta x$ 覆盖正负方向，且满足凸性）。

⚠️ 注意：凸锥必须包含原点（取 $\theta = 0$ 得 $0 \in C$）。

4. 三种组合与三种包的对比

🔁 包的构造逻辑：对集合 $C$，取所有对应组合的点，形成包含 $C$ 的最小结构。

5. 特殊集合的性质分析

单点集 {x}

• 仿射集？ ✅ 是。因任意仿射组合 $\theta x + (1-\theta)x = x \in \{x\}$。
• 凸集？ ✅ 是。线段退化为点。
• 凸锥？
  • 若 $x = 0$（原点）→ ✅ 是凸锥（$\theta \cdot 0 = 0$）。
  • 若 $x \neq 0$ → ❌ 不是锥（因 $0 \notin \{x\}$，除非 $x=0$）。

空集 \emptyset

• 仿射集？ ✅ 是（无反例）。
• 凸集？ ✅ 是。
• 凸锥？ ✅ 是。

🌌 空集是“平凡满足”所有集合定义的特例。

6. 凸锥包（Convex Cone Hull）

• 定义：包含集合 $C$ 的最小凸锥，记为 $\text{cone}(C)$。
• 构造：取 $C$ 中任意有限点的所有凸锥组合（系数 $\geq 0$）。

例子

• 离散点集（不在原点）：凸锥包是从原点出发、穿过这些点的“最小冰淇淋锥”。
• 两点连线过原点：凸锥包是两条射线张成的锥（不是整条直线！除非包含负方向）。
  • 但注意：过原点的直线本身是凸锥（因包含 $\theta x$ 对所有 $\theta \in \mathbb{R}$，而 $\mathbb{R} \supset [0, \infty)$）。

❗ 易错点：两点连线过原点 → 凸锥包是整个直线（因直线满足凸锥定义）。

7. 集合包含关系总结

flowchart LR
    A[仿射集] -->|是特例| B[凸集]
    C[凸锥] -->|是特例| B
    D[空集] --> A
    D --> B
    D --> C
    E[单点集 x=0] --> C
    E --> B
    E --> A

flowchart LR
    A[仿射集] -->|是特例| B[凸集]
    C[凸锥] -->|是特例| B
    D[空集] --> A
    D --> B
    D --> C
    E[单点集 x=0] --> C
    E --> B
    E --> A

flowchart LR
    A[仿射集] -->|是特例| B[凸集]
    C[凸锥] -->|是特例| B
    D[空集] --> A
    D --> B
    D --> C
    E[单点集 x=0] --> C
    E --> B
    E --> A

解释：该流程图展示了集合类别的包含与特例关系。仿射集和凸锥都是凸集的子类；空集和原点单点集具有多重身份。

关键术语强调

• 仿射包（Affine Hull）
• 凸包（Convex Hull）
• 凸锥包（Convex Cone Hull）
• 仿射组合 / 凸组合 / 凸锥组合
• 锥（Cone）必须过原点
• 空集是万能特例

本课核心在于通过组合方式理解集合构造，并掌握“包”的最小包含思想。后续课程将深入具体凸集（如多面体、范数球等）及其性质。

第5课：几种重要的凸集（1）——高质量学习笔记

核心摘要 (Key Takeaways)

• 组合思想是理解九类集合概念的核心：仿射组合、凸组合、凸锥组合分别对应仿射集、凸集、凸锥，以及它们的包（仿射包、凸包、凸锥包）。
• 凸锥的几何本质是“从原点出发的所有非负线性组合构成的集合”，其典型形状如“冰激凌锥”，必须包含原点。
• 超平面与半空间是基础且重要的凸集：超平面是仿射集（当过原点时也是凸锥），半空间总是凸集，但仅当边界过原点时才是凸锥。
• 球与椭球在欧氏空间中均为凸集，其凸性可通过三角不等式严格证明；椭球由对称正定矩阵 $P$ 定义，其形状由 $P$ 的特征值（或奇异值）决定半轴长度。
• 空集和单点集具有特殊性质：空集同时是仿射集、凸集和凸锥；单点集是仿射集和凸集，但仅当该点为原点时才是凸锥。

1. 九个核心概念的统一框架：组合思想

视频强调，理解以下九个概念的关键在于掌握三种组合（combinations）：

1.1 三种组合的定义

设集合 $C \subseteq \mathbb{R}^n$，从中任取 $k$ 个点 $x_1, x_2, \dots, x_k$，并取实数系数 $\theta_1, \theta_2, \dots, \theta_k$，构造点：

根据系数 $\theta_i$ 的约束，该组合有三种类型：

• 仿射组合（Affine Combination）：
  $\sum_{i=1}^k \theta_i = 1$

• 凸组合（Convex Combination）：
  $\sum_{i=1}^k \theta_i = 1$ 且 $\forall i, \theta_i \geq 0$

• 凸锥组合（Conic Combination / Nonnegative Combination）：
  $\forall i, \theta_i \geq 0$（不要求和为1）

关键联系：凸组合 ⊂ 仿射组合 ∩ 凸锥组合；三者通过系数约束相互关联。

1.2 由组合定义的三类集合

• 仿射集（Affine Set）：
  集合中任意有限个点的仿射组合仍在集合内。
  → 几何意义：包含任意两点的整条直线。

• 凸集（Convex Set）：
  集合中任意有限个点的凸组合仍在集合内。
  → 几何意义：包含任意两点的线段。

• 凸锥（Convex Cone）：
  集合中任意有限个点的凸锥组合仍在集合内。
  → 几何意义：从原点出发，沿集合中任意向量方向无限延伸的“锥体”。

1.3 三类“包”（Hull）的定义

即使原集合不满足上述性质，也可通过组合生成最小的包含它的相应集合：

• 仿射包（Affine Hull）：所有仿射组合构成的集合。
• 凸包（Convex Hull）：所有凸组合构成的集合。
• 凸锥包（Conic Hull）：所有凸锥组合构成的集合。

例子：一个不规则点集的凸锥包是包含该点集的“最小冰激凌锥”（即从原点出发，覆盖所有点方向的最小凸锥）。

2. 凸锥的几何解释（修正版）

上节课对凸锥的解释不够准确。正确理解如下：

2.1 二维凸锥的构造（“冰激凌锥”）

• 取两点 $x_1, x_2$（不在原点）。
• 凸锥组合为：$\theta_1 x_1 + \theta_2 x_2$，其中 $\theta_1, \theta_2 \geq 0$。
• $\theta_1 x_1$ 位于从原点出发、经过 $x_1$ 的射线上；$\theta_2 x_2$ 同理。
• 二者之和构成以 $\theta_1 x_1$ 和 $\theta_2 x_2$ 为邻边的平行四边形的对角顶点。
• 当 $\theta_1, \theta_2$ 变化时，该顶点可覆盖整个由 $x_1, x_2$ 张成的锥形区域。

结论：凸锥 = 所有非负线性组合的集合，必须包含原点。

2.2 凸锥包的直观理解

• 给定任意集合 $S$，其凸锥包是包含 $S$ 的最小凸锥（即“最小冰激凌”）。
• 通过从 $S$ 中任取点并做凸锥组合，可“填满”该锥。

3. 特殊集合的性质分析

例子：射线 $x_0 + \theta v$（$\theta \geq 0$）

• 若 $v = 0$，退化为单点 $\{x_0\}$ → 是仿射集。
• 若 $x_0 = 0$，则为 $\{\theta v \mid \theta \geq 0\}$ → 是凸锥。

4. 超平面与半空间

4.1 超平面（Hyperplane）

定义：给定非零向量 $a \in \mathbb{R}^n$ 和标量 $b \in \mathbb{R}$，

• 几何意义：
  • $n=2$：直线
  • $n=3$：平面
  • 一般：$n-1$ 维仿射子空间
• 性质：
  • 总是仿射集（因满足仿射组合封闭）
  • 总是凸集
  • 是凸锥 ⇔ $b = 0$（即过原点，此时为子空间）

4.2 半空间（Halfspace）

由超平面划分空间得到：

• 闭半空间：

  $$\{ x \mid a^\top x \leq b \} \quad \text{或} \quad \{ x \mid a^\top x \geq b \}$$

• 性质：

  • 总是凸集
  • 不是仿射集（两点连线可能跨越边界）
  • 是凸锥 ⇔ $b = 0$（此时关于原点对称）

例子：在 $\mathbb{R}^2$ 中，$a = [1, 0]^\top, b = 1$，则 $x_1 \geq 1$ 是右半平面，为凸集但非仿射集。

5. 球与椭球

5.1 球（Ball）

定义（欧氏空间）：给定中心 $x_c \in \mathbb{R}^n$，半径 $r \geq 0$，

• 性质：
  • 总是凸集
  • 是仿射集 ⇔ $r = 0$（退化为单点）
  • 是凸锥 ⇔ $r = 0$ 且 $x_c = 0$

凸性证明（关键步骤）

任取 $x_1, x_2 \in \mathcal{B}(x_c, r)$，$\theta \in [0,1]$，需证：

证明：

关键工具：三角不等式（$\|a + b\| \leq \|a\| + \|b\|$）是证明凸性的常用技巧。

5.2 椭球（Ellipsoid）

定义：给定中心 $x_c \in \mathbb{R}^n$，对称正定矩阵 $P \in \mathbb{S}^n_{++}$，

其中：

• $\mathbb{S}^n_{++}$：$n \times n$ 对称正定矩阵集合
• 正定 ⇔ 所有特征值 $> 0$
• 半正定（$\mathbb{S}^n_+$）⇔ 特征值 $\geq 0$

与球的关系

• 若 $P = r^2 I$（$I$ 为单位阵），则： $(x - x_c)^\top (r^2 I)^{-1} (x - x_c) = \frac{\|x - x_c\|_2^2}{r^2} \leq 1 \Rightarrow \|x - x_c\|_2 \leq r$ → 椭球退化为球。

几何意义

• $P$ 的特征值决定椭球各方向的半轴长度。
• 特征向量方向即主轴方向。

例子：设 $P = \begin{bmatrix} 4 & 0 \\ 0 & 1 \end{bmatrix}$，则 $P^{-1} = \begin{bmatrix} 1/4 & 0 \\ 0 & 1 \end{bmatrix}$，椭球为：

$$> \frac{x_1^2}{4} + x_2^2 \leq 1 >$$

→ 半长轴为 2（沿 $x_1$），半短轴为 1（沿 $x_2$）。

• 性质：椭球总是凸集（因是仿射变换下的球，而凸性在仿射变换下保持）。

6. 补充：特征值 vs 奇异值

• 特征值（Eigenvalues）：仅对方阵定义，满足 $A v = \lambda v$。
• 奇异值（Singular Values）：对任意矩阵 $A \in \mathbb{R}^{m \times n}$，定义为 $\sqrt{\text{eigenvalues of } A^\top A}$。
  • $A^\top A$ 对称半正定 ⇒ 特征值 $\geq 0$ ⇒ 奇异值实数且 $\geq 0$。
• 特殊情况：若 $A$ 对称正定，则奇异值 = 特征值的绝对值 = 特征值（因特征值 > 0）。

此知识用于理解 $P$ 的几何意义，但非本课核心。

总结提醒

• 核心思想：所有凸集概念源于组合方式。
• 证明凸性：优先尝试三角不等式。
• 凸锥必须含原点：这是判断的关键。
• 超平面/半空间/球/椭球是后续优化问题中最常用的凸集模型。

教师忠告：“除非你100%聪明，否则必须付出120%的努力。” —— 凸锥虽小，细节决定成败。

第6课：几种重要的凸集（2）——学习笔记

核心摘要 (Key Takeaways)

• 多面体是由有限个半空间（线性不等式）和超平面（线性等式）的交集构成的集合，一定是凸集，但不一定有界。
• 单纯形是由 $k+1$ 个满足特定线性无关条件的点所构成的凸包，在 $\mathbb{R}^n$ 中最多包含 $n+1$ 个顶点；例如：线段（1维）、三角形（2维）、四面体（3维）。
• 任意单纯形都是多面体，可通过构造线性不等式与等式系统严格证明。
• 对称半正定矩阵集合 $\mathbb{S}^n_+$ 是一个凸锥（从而也是凸集），而对称正定矩阵集合 $\mathbb{S}^n_{++}$ 是凸集但不是凸锥（因其不包含零矩阵）。
• 在高维抽象空间（如矩阵空间）中，需依赖逻辑推理而非几何直觉来判断凸性。

1. 多面体（Polyhedron）

定义

一个多面体是一个集合：

• 由 $m$ 个线性不等式（定义半空间）和 $p$ 个线性等式（定义超平面）共同约束。
• 即：多面体 = 若干半空间 ∩ 若干超平面。

性质

• 一定是凸集：任取 $x_1, x_2 \in \mathcal{P}$，对任意 $\theta \in [0,1]$，有 $\theta x_1 + (1-\theta)x_2 \in \mathcal{P}$。
  原因：线性不等式与等式在凸组合下保持封闭。
• 不一定有界：
  • 例子：仅含一个不等式约束 $x_1 \geq 0$ 的集合 $\{x \in \mathbb{R}^n \mid x_1 \geq 0\}$ 是一个无界多面体。
• 有界多面体：若在每个坐标轴方向上取值均有界（即体积有限），则称为有界多面体（也称多胞形，polytope）。

2. 单纯形（Simplex）

定义

给定 $k+1$ 个点 $v_0, v_1, \dots, v_k \in \mathbb{R}^n$，若向量组 $\{v_1 - v_0, v_2 - v_0, \dots, v_k - v_0\}$ 线性无关，则这些点的凸包构成一个 $k$-维单纯形：

几何直观与例子

• 1维单纯形（$k=1$）：两个点 $v_0, v_1$ → 线段。
  • 条件：$v_1 - v_0 \neq 0$（自动线性无关）。
• 2维单纯形（$k=2$）：三个不共线点 → 实心三角形（含内部）。
  • 条件：$v_1 - v_0$ 与 $v_2 - v_0$ 线性无关（即不共线）。
• 3维单纯形（$k=3$）：四个不共面点 → 四面体。
• 关键限制：在 $\mathbb{R}^n$ 中，单纯形最多有 $n+1$ 个顶点（因最多有 $n$ 个线性无关向量）。
  • 例子：在 $\mathbb{R}^2$ 中，不存在四边形是单纯形，因为无法找到4个点使得3个差向量线性无关。

💡 注意：单纯形法（Simplex Method）中的“单纯形”与此几何概念相关，但不等同。

3. 单纯形一定是多面体（证明概要）

目标

证明：任意单纯形可表示为多面体形式（即满足有限个线性等式与不等式）。

证明思路（构造法）

1. 设单纯形由 $v_0, \dots, v_k$ 生成，且 $\{v_i - v_0\}_{i=1}^k$ 线性无关。
2. 任一点 $x$ 在单纯形中可写为： $x = \sum_{i=0}^k \lambda_i v_i,\quad \lambda_i \geq 0,\ \sum \lambda_i = 1$
3. 令 $y = [\lambda_1, \dots, \lambda_k]^\top$，则 $x = v_0 + B y$，其中 $B = [v_1 - v_0, \dots, v_k - v_0] \in \mathbb{R}^{n \times k}$。
4. 由于 $B$ 列满秩（秩为 $k$），存在可逆矩阵 $A$ 使得： $A B = \begin{bmatrix} I_k \\ 0 \end{bmatrix}$
5. 左乘 $A$ 得： $A(x - v_0) = \begin{bmatrix} y \\ 0 \end{bmatrix} \Rightarrow \begin{cases} A_1(x - v_0) = y \\ A_2(x - v_0) = 0 \end{cases}$
6. 利用 $y \geq 0$ 且 $\mathbf{1}^\top y \leq 1$（因 $\lambda_0 = 1 - \sum_{i=1}^k \lambda_i \geq 0$），得到： $\begin{aligned} A_1(x - v_0) &\geq 0 \\ \mathbf{1}^\top A_1(x - v_0) &\leq 1 \\ A_2(x - v_0) &= 0 \end{aligned}$ 这正是线性不等式 + 线性等式的形式。

✅ 结论：单纯形可表示为多面体，故单纯形 ⊆ 多面体。

4. 矩阵空间中的凸集

常用符号

• $\mathbb{S}^n$：所有 $n \times n$ 对称矩阵集合，即 $X = X^\top$。
• $\mathbb{S}^n_+$：所有 $n \times n$ 对称半正定矩阵集合，即 $X \succeq 0$（所有特征值 $\geq 0$）。
• $\mathbb{S}^n_{++}$：所有 $n \times n$ 对称正定矩阵集合，即 $X \succ 0$（所有特征值 $> 0$）。

⚠️ 重要区别：

• $X \geq 0$：通常指元素非负（逐元素）。
• $X \succeq 0$：指半正定（特征值非负）。
  视频中为书写简便，用 $X \geq 0$ 表示半正定，但强调其含义为 $\succeq 0$。

凸性分析

(1) \mathbb{S}^n_+：是凸锥（从而是凸集）

• 证明：任取 $A, B \in \mathbb{S}^n_+$，$\theta_1, \theta_2 \geq 0$，需证 $\theta_1 A + \theta_2 B \in \mathbb{S}^n_+$。
  • 对称性：显然成立。
  • 半正定性：对任意 $x \in \mathbb{R}^n$， $x^\top (\theta_1 A + \theta_2 B) x = \theta_1 x^\top A x + \theta_2 x^\top B x \geq 0 + 0 = 0$ 因 $x^\top A x \geq 0$，$x^\top B x \geq 0$（半正定定义）。

(2) \mathbb{S}^n_{++}：是凸集，但不是凸锥

• 是凸集：对 $\theta \in [0,1]$，若 $A, B \succ 0$，则 $x^\top (\theta A + (1-\theta) B) x = \theta x^\top A x + (1-\theta) x^\top B x > 0 \quad (\forall x \neq 0)$ 故 $\theta A + (1-\theta) B \succ 0$。
• 不是凸锥：因凸锥要求对任意 $\theta_1, \theta_2 \geq 0$ 封闭，但若取 $\theta_1 = 0$，则 $\theta_1 A + \theta_2 B = \theta_2 B$，当 $\theta_2 > 0$ 时仍正定；问题在于零矩阵不在其中。
  • 关键反例：凸锥必须包含原点（取 $\theta_1 = \theta_2 = 0$），但 $0 \notin \mathbb{S}^n_{++}$（零矩阵非正定）。