对应 note 2_cvx.pdf。这是整门课的"语言基础"——不掌握这一章，后面所有内容都没法读。

0. 一句话理解这一章

凸性是优化的"友好"性质。我们要学会两件事：(1) 判定一个集合 / 一个函数是否是凸的；(2) 用凸性的"几何化"刻画（梯度不等式、Hessian、次梯度、共轭函数）来推后面的最优性条件和算法。

1. 知识地图

            凸集
            ├── 基本定义（仿射 / 凸 / 锥）
            ├── 标准凸集：超平面、半空间、多面体、球、椭球、范数球、SOC、PSD 锥
            ├── 凸性保持运算：交、仿射映射、透视、线性分式
            └── 几何结果：分离/支撑超平面、Carathéodory、极点、相对内点

            凸函数
            ├── 三个等价定义：(凸性) ↔ epi(f) 凸 ↔ Jensen 不等式
            ├── 三个判定层次：定义 / 一阶 / 二阶 / 沿直线限制
            ├── 凸性保持运算：非负组合、点态 sup、仿射复合、单调复合、最小化、透视
            ├── 共轭函数 f*(y) = sup_x (y^T x − f(x))
            └── 次梯度 ∂f(x)（不可微情形）

---

2. 凸集

2.1 三个核心定义（一定要背熟）

• 仿射集：$\mathrm{\forall }x,y\in S,\alpha \in \mathbb{R},\alpha x+(1-\alpha )y\in S$。"穿过两点的整条直线都在集合里"。
• 凸集：把上面 $\alpha \in \mathbb{R}$ 改成 $\alpha \in [0,1]$，"两点之间的线段都在集合里"。
• 凸锥：凸 + 锥（$x\in K,\alpha \ge 0\Rightarrow \alpha x\in K$）。

区别记忆：仿射 ⇒ 凸 ⇒ "锥要再加齐次"。

2.2 一定要会"看见就认识"的标准凸集

集合	形式
超平面	$\{x:a^{T}x=b\}$
半空间	$\{x:a^{T}x\le b\}$
多面体	$\{x:Ax\le b,Cx=d\}$
欧氏球	$\{x:|x-\overline{x}{|}_2\le r\}$
椭球	$\{x:(x-\overline{x}{)}^{T}Q(x-\overline{x})\le 1,Q⪰0\}$
二阶锥（SOC, Lorentz / 冰激凌锥）	$\{(x,t):|x{|}_2\le t\}$
半正定锥	${\mathcal{S}}_{+}^n=\{X:X⪰0\}$
范数球 / 范数锥	$\{x:|x|\le r\}$ / $\{(x,t):|x|\le t\}$

只要能把目标集合"组合"成上面这些标准凸集的交、仿射像、原像，它就是凸的。

2.3 凸性保持的四大运算（最常用）

1. 交：任意多个凸集的交还是凸集。这是判凸的"万能武器"——多面体就是半空间和超平面的交。
2. 仿射映射 $f(x)=Ax+b$：凸集的像和原像都是凸集。
   • 椭球是球的仿射像；线性矩阵不等式（LMI）的解集是 PSD 锥的原像。
3. 透视函数 $P(x,t)=x/t,t>0$：凸集的像和原像都是凸集。
4. 线性分式 $f(x)=\frac{Qx+u}{c^{T}x+d}$（$c^{T}x+d>0$）：=透视∘仿射，故保凸。

2.4 必须熟悉的几个几何定理（可作为论证工具）

• 分离超平面定理：两个不相交的凸集 $C,D$，存在 $a\ne 0,b$ 使 $a^{T}x\le b$ 在 $C$、$\ge b$ 在 $D$。
• 支撑超平面定理：凸集的每个边界点都有支撑超平面。
• Carathéodory：${\mathbb{R}}^n$ 中凸包里的点至多由 $n+1$ 个原集合点的凸组合表出。
• 极点 / Minkowski：紧凸集 = 它的极点的凸包。

这些几何结果在本科生考试里通常作为"理论叙述题"出现，证明往往不要求自己写，但结论必须能用得很顺（推广到对偶证明等）。

2.5 作业题型对照（凸集判定）

以下"考点"列出题目要用的工具，不给答案。

作业	题面	考点
A1.1(a)	极集 $S^{\circ }=\{x:x^{T}y\le 1,\mathrm{\forall }y\in S\}$	把 $S^{\circ }$ 看成关于 $y$ 索引的半空间的交 → 交是凸的
A1.1(b)	ε-邻域 $C_{ϵ}$	$C_{ϵ}=C+B(0,ϵ)$：用 Minkowski 和保凸性，或者写成 $\underset{y}{inf}|x-y|\le ϵ$（凸函数的下水平集）
A1.2(a)	$N_C(x)=\{g:g^T(y-x)\le 0,\mathrm{\forall }y\in C\}$ 是凸锥	同样是"半空间的交"，再验证锥性（齐次）
A1.2(b)	给定多面体，证 $\sum {\lambda }_i{a}_i\in N_C(x)$	把内积 $g^T(y-x)$ 拆成 $\sum {\lambda }_i{a}_i^T(y-x)$，再用 $a_i^{T}y\le b_i=a_i^{T}x$
A1.3	回收锥 $\text{rec}(C)$	hint 说"把 $x+\alpha ({\lambda }_1{d}_1+{\lambda }_2{d}_2)$ 写成两点的中点"——典型的"用凸性凑两点"
A1.4	Minkowski 差 $C\sim D$	$(C\sim D)$ 可写成无限多个平移凸集的交 $\bigcap _{d\in D}(C-d)$

复习要点：A1 全是"判定集合凸性"的题；几乎每道都能通过"先把它写成半空间/凸集的交（或仿射原像）"来解决，不要试图直接用定义"取两点+插值"硬算（除非题目就是 hint 这么暗示的）。

---

3. 凸函数

3.1 三个等价定义（这是凸函数最核心的工具，背熟）

设 $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\mathrm{\infty }\}$。下列等价：

1. $\text{dom}(f)$ 凸 且 $f(\alpha x+(1-\alpha )y)\le \alpha f(x)+(1-\alpha )f(y)$。
2. $\text{epi}(f)=\{(x,t):f(x)\le t\}$ 是凸集（Prop 2.2）。
3. Jensen 不等式：$f(\sum {\alpha }_i{x}_i)\le \sum {\alpha }_{i}f(x_i)$（${\alpha }_i\ge 0,\sum {\alpha }_i=1$）。

严格凸：把 $\le$ 换成 $<$，且 $\alpha \in (0,1),x\ne y$。

强凸：$f-\frac{\mu }{2}\parallel x{\parallel }^2$ 凸（更强，第六章用）。

3.2 一阶条件（可微情形）⭐

$$f\text{ 凸}⟺f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x),\mathrm{\forall }x,y\in \text{dom}(f).$$

几何含义：$f$ 处处被它的切超平面"托底"。这个不等式在第 4、5、6 章被反复引用。

严格凸把 $\ge$ 改成 $>$（且 $x\ne y$）。

3.3 二阶条件（二次连续可微情形）⭐⭐

$$f\text{ 凸}⟺{\mathrm{\nabla }}^{2}f(x)⪰0,\mathrm{\forall }x\in \text{dom}(f).$$

注意"反向"不成立：${\mathrm{\nabla }}^{2}f\succ 0$ ⇒ 严格凸，但严格凸 不一定 ${\mathrm{\nabla }}^{2}f\succ 0$（反例 $f(x)=x^4$）。

还要小心：定理 2.11 要求 dom(f) 是开集，否则 Hessian 计算可能出错（讲义最后那个 $f(x,y)=x^2-y^2,\text{dom}=\mathbb{R}\times \{0\}$ 的例子）。

3.4 凸性保持的运算（判凸题最常用）⭐

Theorem 2.7（要会熟练运用每一条）：

运算	形式	凸性条件
非负组合	$\sum {\alpha }_i{f}_i,{\alpha }_i\ge 0$	每个 $f_i$ 凸
积分形式	${\int }_{A}w(y)f(x,y)dy$	$f(\cdot ,y)$ 凸，$w\ge 0$
点态上确界	$\underset{i\in I}{sup}{f}_i$	每个 $f_i$ 凸
仿射复合	$f(x)=g(Ax+b)$	$g$ 凸
单调复合（标量）	$f(x)=h(g(x))$	$h$ 凸非降 + $g$ 凸；或 $h$ 凸非升 + $g$ 凹
单调复合（向量）	$h(g_1,\dots ,g_k)$	每个分量按上述规则
部分最小化	$g(x)=\underset{y}{inf}f(x,y)$	$f$ 在 $(x,y)$ 上联合凸
透视	$g(x,t)=tf(x/t)$	$f$ 凸
沿直线限制	${\tilde{f}}_{x_0,h}(t)=f(x_0+th)$	$f$ 凸 ⇔ 任意直线上凸

"沿直线限制" 是判凸的降维利器：把 $f:{\mathbb{R}}^n\to \mathbb{R}$ 的凸性化简到 $\tilde{f}:\mathbb{R}\to \mathbb{R}$，然后只用单变量微积分检查。

3.5 必须熟悉的标准凸函数

• 仿射函数：既凸又凹。
• 二次型 $\frac{1}{2}{x}^{T}Qx,Q⪰0$：凸。
• 范数 $\parallel x\parallel$：凸（三角不等式 + 齐次性）。
• 范数的 $p$ 次方 $\parallel x{\parallel }^p,p\ge 1$：凸。
• log-sum-exp $f(x)=\log \sum e^{x_i}$：凸（用 Cauchy-Schwarz 算 Hessian，例 4）。
• 几何均值 $(\prod x_i{)}^{1/n}$：在正象限上凹（例 5）。
• $-\log detX$ 在 ${\mathcal{S}}_{++}^n$ 上：凸（例 6）。
• 二次分式 $x^T{Y}^{-1}x,Y\succ 0$：凸（用 Schur 补，例 1）。

这些是建模和判凸题的"零件库"，看到要立刻反应。

3.6 共轭函数 $f^{\ast }(y)=\underset{x}{sup}(y^{T}x-f(x))$ ⭐

性质：

• $f^{\ast }$ 总是凸（任意 $f$ 都行，因为是仿射的点态 sup）。
• 当 $f$ 凸闭时，$f^{\ast \ast }=f$（双共轭定理）。
• 典型计算：
  • $f(x)=-\log x$（$x>0$）：$f^{\ast }(y)=-1-\log (-y),y<0$。
  • $f(x)=\frac{1}{2}{x}^{T}Qx,Q\succ 0$：$f^{\ast }(y)=\frac{1}{2}{y}^T{Q}^{-1}y$。
  • $f(x)=\parallel x\parallel$：$f^{\ast }(y)=I_{B^{\ast }}(y)$（对偶范数球的指示函数）。

在第 5 章，Fenchel 对偶就是写共轭。LASSO 的对偶推导也要靠它。

3.7 次梯度（不可微情形）

$$s\in \partial f(x)⟺f(y)\ge f(x)+s^T(y-x),\mathrm{\forall }y.$$

• 可微 ⇒ $\partial f(x)=\{\mathrm{\nabla }f(x)\}$。
• $\partial \parallel x{\parallel }_2$ 的例子：$x\ne 0$ 时 $\partial \parallel x{\parallel }_2=\{x/\parallel x\parallel \}$；$x=0$ 时 $\partial \parallel 0{\parallel }_2=B(0,1)$。
• 加法：$\partial (f_1+f_2)=\partial f_1+\partial f_2$（在某 $x_0$ 处 $f_1$ 连续）。
• 方向导数与次梯度：$f^{\prime }(x;d)=\underset{s\in \partial f(x)}{max}{s}^{T}d$。

---

4. 作业题型对照（凸函数判定 + 综合）

作业	题面	考点
A2.1	凸 + 严格凸 → 严格凸	直接用定义 + 严格不等式相加
A2.2	$e^{x+y}+x^2+2xy+3y^2$ 严格凸吗？	拆成 $e^{x+y}$（沿直线复合 → 凸但不是严格凸沿 $(1,-1)$ 方向）+ $(x+y{)}^2+2y^2$；用"凸+严格凸=严格凸"（A2.1 的结论）作为思路
A2.3	$f(x)=|x{|}_2^4$ 凸	用复合："$g(z)=z^4$ 在 $z\ge 0$ 上凸非减" + "$|x{|}_2$ 凸非负"；或者 $|x{|}_2^4=(|x{|}_2^2{)}^2$ 是凸非减 $\circ$ 凸非负
A2.4(a)	$|x{|}_p^p/t^{p-1}$ 凸	透视函数：先证 $|x{|}_p^p$ 凸，再写成它的透视；或者算 Hessian + Schur 补
A2.4(b)	$|Ax+b{|}_2^2/(c^{T}x+d)$	思路同上，先证 $|y{|}^2$ 凸，再透视，再仿射复合；或直接 Schur 补
A2.5	凸可微 ⇒ $\mathrm{\nabla }f$ 单调	把一阶条件 $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)$ 写两遍交换 $x,y$ 相加
A3.1	给反例：(i) $f$ 不凸但限制在 $C$ 上凸；(ii) 都不凸但限制在 $C$ 上凸	找局部凸的简单函数，例如取 $f(x)=-x^2$ 在某些限制集合上
A3.2	$f$ 严格凸 ⇔ $f$ 在 int dom $f$ 上严格凸	用相对内点性质 + 闭包
A3.3	"三段斜率"特征	凸的等价定义：见 epi 视角；严格分析割线斜率单调
A3.4	$f(x)={\int }_0^{|x|}\psi (t)dt,\psi$ 连续递增	(i) $g(z)={\int }_0^z\psi$ 凸（一阶导数递增）+ $|x|$ 凸；(ii) $\psi$ 严格递增 ⇒ 严格凸

复习要点：A2/A3 的判凸题，尽量先用"运算保凸法则"而不是直接算 Hessian——后者在矩阵情形下经常很难。

---

5. 核心证明思路总结（"招式手册"）

招式 1：判集合 $S$ 凸 → "把 $S$ 写成已知凸集的交 / 仿射像 / 透视像"

模板：

$S=\bigcap _i\{x:g_i(x)\le 0\}$，每个 $\{g_i\le 0\}$ 是某凸函数 $g_i$ 的下水平集（凸函数的下水平集是凸的），故 $S$ 凸。

招式 2：判函数 $f$ 凸 → "运算保凸 → 沿直线限制 → 二阶 Hessian"

优先级：

1. 先看能不能用运算保凸"组合"出来。
2. 不行就"沿直线限制"降到 1 维，再用 $g^{″}(t)\ge 0$。
3. 再不行就直接算 Hessian + Schur 补。

招式 3：用一阶条件 $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)$ "正反"使用

• 正向：知道凸 → 用不等式（A2.5、第 4 章 KKT 充分性、第 6 章收敛性）。
• 反向：要证"凸 ⇒ 某性质"时，把 $x,y$ 互换写两遍相加，能消掉 $f(x),f(y)$ 留下梯度的双线性式。

招式 4：Schur 补——"分式塞进 PSD 约束"

$$\left(\begin{array}{cc}Y& x\\ x^T& r\end{array}\right)⪰0,Y\succ 0⟺r\ge x^T{Y}^{-1}x.$$

这条贯穿 Ch2 例 1 → Ch3 SOCP 建模 → Ch5/A6 SDP 建模。一定要熟到秒答。

招式 5：透视降维

把 $g(x,t)=tf(x/t)$ 这种"分母里有变量"的函数视作 $f$ 的透视（$t>0$），从而由 $f$ 凸推出 $g$ 凸。

---

6. 自检清单（学完这一章你应该能 5 分钟内回答）

• [ ] 仿射 / 凸 / 锥的定义？三者层级关系？
• [ ] 不假思索写出 5 个标准凸集的形式（半空间、椭球、SOC、PSD、多面体）？
• [ ] 不假思索写出 5 条凸函数运算法则？
• [ ] $f$ 凸的一阶条件、二阶条件分别是什么？严格凸 vs 强凸的区别？
• [ ] $\log \sum e^{x_i}$、$-\log detX$、$x^T{Y}^{-1}x$ 的凸性怎么证？
• [ ] 共轭函数定义？$\frac{1}{2}{x}^{T}Qx$ 的共轭？$-\log x$ 的共轭？
• [ ] $\parallel x{\parallel }_2$ 在 $0$ 处的次梯度是什么？

7. 常见陷阱

1. "严格凸 ⇒ Hessian 严格正定"是错的（$x^4$ 反例）。
2. $f$ 凸 ≠ epi(f) 凸：要求 dom(f) 也凸，定义 2.1 第 2 条已经包含。
3. 二阶条件要求 dom(f) 开——否则 Hessian 计算会失误。
4. 次梯度可能为空：在 dom 的边界上（讲义里给了反例 $-\sqrt{1-\parallel x{\parallel }^2}$）。
5. 下水平集凸 ≠ 函数凸：那叫 quasi-convex（拟凸）；典型反例 $x\mapsto x^3$。
6. 共轭函数 $f^{\ast }$ 不依赖 $f$ 是否凸——任意 $f$ 的共轭都凸（因为是仿射的 sup）；这一点在 A5.2 是直接被考的。

---

8. 接下来怎么学

学完本章，你应当：

1. 不看书做完 A1, A2, A3（重做 ≠ 抄答案）如果还卡，回来重读 §2.4 和 §3.4。
2. 把"凸性保持运算"那张表（§3.4）打印出来贴在桌上。
3. 进入 3_凸优化问题。