对应 note 5_dual.pdf。这是整门课最高频被考的章节，几乎所有期中/期末必考"写对偶"。

0. 一句话理解这一章

每一个原问题 (P) 都对应一个"对偶问题" (D)，对偶恒为凸；弱对偶 $d^{\ast }\le p^{\ast }$ 永远成立；在凸 + Slater 下强对偶 $d^{\ast }=p^{\ast }$ 成立，且 (KKT 条件 ⇔ Lagrangian 鞍点)。

1. 知识地图

            原问题 (P) min f0  s.t. g_i ≤ 0, h_j = 0, x ∈ X
                              ↓
            构造 Lagrangian L(x, λ, ν) = f0 + λ^T g + ν^T h
                              ↓
            对偶函数 θ(λ, ν) = inf_x L(x, λ, ν)
                              ↓
            对偶问题 (D) max θ(λ, ν)  s.t. λ ≥ 0
                              │
                  弱对偶 (恒成立)：sup θ ≤ inf f0
                              │
                  强对偶（凸 + Slater）：sup θ = inf f0
                              │
                  鞍点 / KKT：等价刻画

            扩展到广义不等式 g(x) ⪯_K 0
                              ↓
                  K* (对偶锥), 强对偶在 strict feasibility 下成立

            两类标准 CLP：
              - SOCP（K = SOC，自对偶）
              - SDP （K = PSD 锥，自对偶）

            应用：
              - SDP relaxation of QCQP（rank-1 松弛）
              - 鲁棒优化（用 LP/CLP 强对偶把"对所有 a"转为"存在某 λ"）

2. Lagrangian 与对偶问题（核心定义）

$$L(x,\lambda ,\nu )=f_0(x)+\sum _i{\lambda }_i{g}_i(x)+\sum _j{\nu }_j{h}_j(x).$$

关键观察（识别公式 (2)）：

$$\underset{\lambda \ge 0,\nu }{sup}L(x,\lambda ,\nu )=\{\begin{array}{ll}{f}_0(x)& \text{若 }g(x)\le 0,h(x)=0\\ +\mathrm{\infty }& \text{otherwise}\end{array}$$

这步把"约束"用"$sup$ 后变成 +∞"的方式植入了无约束的极值问题——这是对偶整套理论的"灵魂技巧"。

由此：

• 原问题 $p^{\ast }=\underset{x}{inf}\underset{\lambda \ge 0,\nu }{sup}L(x,\lambda ,\nu )$。
• 对偶函数 $\theta (\lambda ,\nu )=\underset{x}{inf}L(x,\lambda ,\nu )$。
• 对偶问题 $d^{\ast }=\underset{\lambda \ge 0,\nu }{sup}\theta (\lambda ,\nu )$（注意 $\nu$ 无符号约束）。

弱对偶（Theorem 1.1，恒成立！）⭐

$$\theta (\overline{\lambda },\overline{\nu })\le f_0(\overline{x}),\mathrm{\forall }\text{原可行 }\overline{x},\mathrm{\forall }\text{对偶可行 }(\overline{\lambda },\overline{\nu }).$$

进而 $d^{\ast }\le p^{\ast }$。对偶差距 $p^{\ast }-d^{\ast }\ge 0$。

对偶问题永远是凸的 ⭐⭐

$\theta (\lambda ,\nu )$ 是仿射函数族 $L(x,\cdot ,\cdot )$ 关于 $(\lambda ,\nu )$ 的点态下确界 → 凹。$(D)$ 是 max 凹 = 凸优化。

重要意义：哪怕原问题非凸，对偶都是凸的。这是 SDP relaxation 与 robust counterpart 等技巧的根源。A5.2 直接考这个事实。

例：弱对偶严格 $d^{\ast }<p^{\ast }$ 的反例（Example 1.2）

$min-x$ s.t. $x\le 1,x\in \{0,2\}$。$p^{\ast }=0$ 但 $d^{\ast }=-1$。问题在于 $X=\{0,2\}$ 不凸（书里把 $X$ 当作"特殊集合"独立处理，所以本身不是 KKT 的标准框架）。

3. 鞍点 ⇔ KKT ⇔ 强对偶

鞍点定义（Definition 1.3）

$(\overline{x},\overline{\lambda },\overline{\nu })$ 是 Lagrangian 的鞍点，若：

• $\overline{x}\in X$，$\overline{\lambda }\ge 0$；
• 对所有 $x\in X,(\lambda ,\nu )\in {\mathbb{R}}_{+}^m\times {\mathbb{R}}^p$：$L(\overline{x},\lambda ,\nu )\le L(\overline{x},\overline{\lambda },\overline{\nu })\le L(x,\overline{\lambda },\overline{\nu })$。

直观：固定 $(\overline{\lambda },\overline{\nu })$，$\overline{x}$ 极小化 $L$；固定 $\overline{x}$，$(\overline{\lambda },\overline{\nu })$ 极大化 $L$。

三个等价命题（Theorem 1.4 + Theorem 1.5）⭐⭐⭐

[Theorem 1.4]：

$(\overline{x},\overline{\lambda },\overline{\nu })$ 是 $L$ 的鞍点 ⇔ $p^{\ast }=d^{\ast }$ 且 $\overline{x},(\overline{\lambda },\overline{\nu })$ 分别是 (P), (D) 的最优解。

[Theorem 1.5] 鞍点最优性条件：

$(\overline{x},\overline{\lambda },\overline{\nu })$ 是鞍点 ⇔ 满足

1. (原始可行) $\overline{x}\in X,g(\overline{x})\le 0,h(\overline{x})=0$；
2. (Lagrangian 最优) $\overline{\lambda }\ge 0$ 且 $\overline{x}=\arg \underset{x\in X}{min}L(x,\overline{\lambda },\overline{\nu })$；
3. (互补松弛) ${\overline{\lambda }}^{T}g(\overline{x})=0$。

在 $X$ 开凸 + $f_0,g_i$ 凸可微 + $h_j$ 仿射的情形下，条件 (b) 等价于"梯度方程"，鞍点条件就是 KKT 条件。

强对偶（Corollary 1.6 / 1.7）⭐

凸优化问题 + Slater ⇒ $d^{\ast }=p^{\ast }$ 且对偶达到最优。仿射约束直接 ok（Cor 1.7）。

总结：在凸问题下，下面 5 件事互相等价（重要！）

1. $(\overline{x},\overline{\lambda },\overline{\nu })$ 满足 KKT 条件。
2. $(\overline{x},\overline{\lambda },\overline{\nu })$ 是 Lagrangian 的鞍点。
3. $\overline{x}$ 是 (P) 的最优解，$(\overline{\lambda },\overline{\nu })$ 是 (D) 的最优解，且 $p^{\ast }=d^{\ast }$。
4. $(\overline{\lambda },\overline{\nu })$ 让 $\theta (\overline{\lambda },\overline{\nu })=f_0(\overline{x})$。
5. $\overline{x}$ 让 $\underset{\lambda \ge 0,\nu }{sup}L(\overline{x},\lambda ,\nu )=\underset{x}{inf}sup\cdots =supinf\dots$。

4. 写对偶的"标准三步法" ⭐⭐⭐

任意原问题，写对偶就这三步：

第 1 步：写 $L(x,\lambda ,\nu )$。 第 2 步：对 $x$ 求 $inf$，得 $\theta (\lambda ,\nu )$。常用工具：

• 二次型：$\underset{x}{inf}\frac{1}{2}{x}^{T}Qx+b^{T}x=-\frac{1}{2}{b}^T{Q}^{-1}b$（$Q\succ 0$），最优 $x=-Q^{-1}b$。
• 共轭函数：$\underset{x}{inf}f(x)-y^{T}x=-f^{\ast }(y)$。这是 Fenchel 对偶的根。
• 看到 $\underset{x}{inf}{c}^{T}x+(\dots )$ 中关于 $x$ 的线性项：若系数不为 0 则 $inf=-\mathrm{\infty }$；为 0 则余项就是答案。这是处理 LP/SOCP/SDP 对偶的基本套路。 第 3 步：把"$inf=-\mathrm{\infty }$ 的情形"对应的条件写成对偶约束，剩下的写成对偶目标。

5. 经典对偶推导（全部要会复现）

5.1 LP 的对偶 → LP

原 $min{c}^{T}x$ s.t. $Ax=b,x\ge 0$。

$L=c^{T}x+{\nu }^T(b-Ax)-{\lambda }^{T}x$。$\underset{x}{inf}=\{\begin{array}{ll}{\nu }^{T}b& \text{若 }c-A^T\nu -\lambda =0，\mathrm{即}c-A^T\nu =\lambda \ge 0\\ -\mathrm{\infty }& \text{otherwise}\end{array}$

对偶：$max{b}^T\nu$ s.t. $A^T\nu \le c$。

5.2 凸 QP（Example 1.8.2）

原 $min\frac{1}{2}{x}^{T}Qx+c^{T}x$ s.t. $Ax\le b$，$Q\succ 0$。

$L=\frac{1}{2}{x}^{T}Qx+c^{T}x+v^T(Ax-b)$；对 $x$ 求 $inf$：$x^{\ast }=-Q^{-1}(c+A^{T}v)$。

代回得 $\theta (v)=-\frac{1}{2}{v}^{T}A{Q}^{-1}{A}^{T}v-(A{Q}^{-1}c+b{)}^{T}v-\frac{1}{2}{c}^T{Q}^{-1}c$。

对偶：$min\frac{1}{2}{v}^{T}A{Q}^{-1}{A}^{T}v+(A{Q}^{-1}c+b{)}^{T}v$ s.t. $v\ge 0$。对偶仍是 QP。

5.3 QCQP 的对偶 → SDP（Example 1.8.3）⭐

用 Lemma 1.9（$x^{T}Ax+2b^{T}x+c\ge 0\mathrm{\forall }x⟺\left(\begin{array}{cc}A& b\\ b^T& c\end{array}\right)⪰0$），把对偶函数中"对所有 $x$ 成立的二次不等式"用 PSD 约束写出来，最终得 SDP (12)。

这条推导是 SDP 与 QCQP 关系的根本。

5.4 SDP 的对偶 → SDP（Example 1.8.1）

原 $minC\bullet Z$ s.t. $A_j\bullet Z=b_j,Z⪰0$。

$L=C\bullet Z+\sum {\nu }_j(b_j-A_j\bullet Z)$。$\underset{Z⪰0}{inf}(C-\sum {\nu }_j{A}_j)\bullet Z=\{\begin{array}{l}-\mathrm{\infty },\mathrm{若}C-\sum {\nu }_j{A}_j⪰̸0(\mathrm{取}\mathrm{负}\mathrm{方}\mathrm{向}\mathrm{特}\mathrm{征}\mathrm{向}\mathrm{量}\mathrm{构}\mathrm{造}\mathrm{的}Z\mathrm{让}\mathrm{目}\mathrm{标}\to -\infty )\\ 0,otherwis(\mathrm{取}Z=0)\end{array}$

对偶：$max{b}^T\nu$ s.t. $C-\sum {\nu }_j{A}_j⪰0$。

5.5 Fenchel 对偶（Example 1.8.4）⭐

$min{f}_1(Ax)+f_2(x)$ → 引入 $y=Ax$ → 对偶为：

$$-min{f}_1^{\ast }(w)+f_2^{\ast }(-A^{T}w).$$

LASSO 的对偶：$min\frac{1}{2}\parallel Ax-b{\parallel }^2+\lambda \parallel x{\parallel }_1$。

取 $f_1(y)=\frac{1}{2}\parallel y-b{\parallel }^2$，$f_1^{\ast }(w)=\frac{1}{2}\parallel w{\parallel }^2+b^{T}w$；$f_2(x)=\lambda \parallel x{\parallel }_1$，$f_2^{\ast }(z)=\{\begin{array}{ll}0,& \parallel z{\parallel }_{\mathrm{\infty }}\le \lambda \\ +\mathrm{\infty },& \text{else}\end{array}$（即 $L_{\mathrm{\infty }}$ 球的指示函数）。最终对偶：$max-\frac{1}{2}\parallel w{\parallel }^2+b^{T}w$ s.t. $\parallel A^{T}w{\parallel }_{\mathrm{\infty }}\le \lambda$。

讲义最后那个 Exercise 说"写下 LASSO 对偶"——直接背这个结论就行。

6. 广义不等式与 CLP

6.1 Proper cone 与对偶锥

Proper cone $K$：凸 + 闭 + solid（实心，有内点）+ pointed（不含直线）。对偶锥：

$$K^{\ast }=\{y:x^{T}y\ge 0,\mathrm{\forall }x\in K\}.$$

广义不等式：$x{⪰}_{K}y⟺x-y\in K$。性质完全类比标量不等式（详见讲义 §2.1）。

自对偶锥（重要）：

• ${\mathbb{R}}_{+}^n$（非负象限）= 自对偶。
• SOC $Q=\{(x,t):\parallel x\parallel \le t\}$ = 自对偶。
• PSD 锥 ${\mathcal{S}}_{+}^n$ = 自对偶（在 Frobenius 内积下）。

6.2 广义 KKT + 对偶

把 ${\lambda }^{T}g$ 换成 $\lambda \bullet g$（即 $⟨\lambda ,g⟩$），把 $\lambda \ge 0$ 换成 $\lambda {⪰}_{K^{\ast }}0$，其余完全一样。

强对偶在"广义 Slater"（存在 $g_i(x){\prec }_{K_i}0$）下成立。

6.3 CLP 的强对偶（Theorem 2.3）⭐

注意 LP 与 CLP 强对偶的差别：

• LP 强对偶：只要 (P) 有最优解（有界 + 可行），就保证强对偶（Theorem 2.1）。
• CLP 强对偶需要"严格可行"（即 $\overline{x}{\succ }_{K}0$）才能保证 $p^{\ast }=d^{\ast }$（Theorem 2.3）。

这是为什么 SDP / SOCP 也可能有 duality gap（讲义 Example 2.4, 2.5）！比 LP 严格。

6.4 SDP relaxation of QCQP（核心案例）

把 QCQP 的 $x{x}^T$ 换成 $X⪰0$ 并加 rank-1 约束 → 丢掉 rank → 得 SDP relaxation (18)。

重要事实：

• relaxation 的对偶 = 原 QCQP 的对偶（讲义在 §2.3.1 末尾给出）。
• 当 $b_i=0$（齐次）时，存在解 $X^{\ast }$ 满足 $r(r+1)/2\le m$（Pataki 定理），$m\le 2$ 时 SDR 紧 ($r\le 1$)。
• 非齐次 $m\le 1$ + Slater 时紧——S-lemma。

6.5 鲁棒优化的对偶推导（§3）

思路：把"对所有 $a\in \mathcal{U}$ 成立"的内部 max 用 LP/CLP 强对偶转成 min，然后这个 min 与外面的 min 合并。

多面体不确定 ${\mathcal{U}}_i=\{a:D_{i}a\le e_i\}$：

$$max{a}_i^{T}x\text{s.t.}{D}_{i}a\le e_i\stackrel{\text{LP 对偶}}{\to }\underset{\lambda }{min}{e}_i^T\lambda \text{s.t.}{D}_i^T\lambda =x,\lambda \ge 0.$$

得到一个 LP 的鲁棒对应。其它锥不确定集合可类似处理。

7. 作业题型对照（A5 + A6 + hw07）

作业	题面	考点
A5.1	$min{x}_1^2+0.5x_2^2+x_1{x}_2-2x_1-3x_2$ s.t. $x_1+x_2\le 2$	写 L，对 $x$ 求 inf 得 $\theta (\lambda )$（QP 对偶）；解 ${\lambda }^{\ast }$，再代回得原 $x^{\ast }$。典型 5.2 例的练手
A5.2	$min{c}^{T}x$ s.t. $f(x)\le 0$（$c\ne 0$），用 $f^{\ast }$ 表对偶；解释为何凸	写 $L=c^{T}x+\lambda f(x)$；$\underset{x}{inf}[c^{T}x+\lambda f(x)]=-\lambda \underset{x}{sup}[(-c/\lambda {)}^{T}x-f(x)]=-\lambda f^{\ast }(-c/\lambda )$（$\lambda >0$）；对偶 $max-\lambda f^{\ast }(-c/\lambda )$ s.t. $\lambda \ge 0$。为何凸：对偶函数是仿射的 inf，恒凹
A5.3	$min|x-a{|}^2$ s.t. $e^{T}x=\mu$	(a) 写 L，对 $x$ 求 inf 得显式 $\theta (\nu )$（一个关于 $\nu$ 的二次）；强对偶用 Slater（仿射约束自动）；(b) 用 ${\nu }^{\ast }$ 反解 $x^{\ast }$
A5.4(a)	minmax 写成 LP	引入 $t$：$mint$ s.t. $a_k+a_{2k}+a_{3k}\le t\mathrm{\forall }k$，加上 simplex 约束
A5.4(b)	给出 $V^{\ast }$ 与对应 $(\lambda ,\mu )$	hint 已经说"考虑它与对偶问题的关系"——所以 $\lambda ,\mu$ 就是对偶变量，要解对偶 LP
A6.2	proper cone：$x{\succ }_{K}0⟺\mathrm{\exists }t>0,x{⪰}_{K}ty$	用 int(K) 与 K 的关系；$y{\succ }_{K}0$ 给出"邻域"，small $t$ 一定能让 $x-ty\in$ int(K)
A6.3	$min(Ax+b{)}^{T}F(x{)}^{-1}(Ax+b)$ s.t. $F(x)\succ 0$	用 Schur 补 + 引入 $t$：$mint$ s.t. $\left(\begin{array}{cc}F(x)& Ax+b\\ (Ax+b{)}^T& t\end{array}\right)⪰0$。直接 SDP
A6.4(a)	$max\text{tr}(AX)$ s.t. $\text{tr}(X)=r,0⪯X⪯I$ 的最优值 = top-r 特征值之和	用谱分解 $A=\sum {\lambda }_i{v}_i{v}_i^T$；最优 $X^{\ast }=\sum _{i\le r}{v}_i{v}_i^T$；可以验证 KKT
A6.4(b)	$f(A)=\sum _{i\le r}{\lambda }_i(A)$ 凸	用 (a) 的"逐点最大化"表示：$f(A)$ 是关于 $A$ 的线性函数族 $A\mapsto \text{tr}(AX)$ 的点态最大值——凸
A6.4(c)	$minf(A(x))$ → SDP	把 (a) 的 SDP 嵌入：$mint$ s.t. $\text{tr}(A(x)X)=t$ 化为约束... 实际写法：$mint$ s.t. $\mathrm{\exists }X:\text{tr}(A(x)X)\ge \text{tr}(\dots )$。需要写出"max 内嵌"的等价 SDP，即用 (a) 的对偶
hw07.4(a)(b)(c)	Backtracking 步长下界	用 $\frac{M}{2}{t}^2|\mathrm{\Delta }x{|}^2\le \frac{1-\alpha }{??}t\mathrm{\nabla }{f}^T\mathrm{\Delta }x$ 等。这部分本质上要用 Quadratic upper bound (Lemma 1.2)——属于第 6 章内容，但 hw07 把它放进来
hw07.5	SOCP 对偶（两种推导）	(a) 引入 $y_i=A_{i}x+b_i,t_i=c_i^{T}x+d_i$，写 L，求 inf 得 $\theta$，约束变成 $|u_i|\le v_i$（SOC 自对偶）；(b) 把 SOCP 写成 conic 形式，用 conic 对偶

复习要点：A5、A6 的所有题（除了 A6.2）几乎都是"写对偶"的不同变种。写对偶三步法（§4）必须熟练到秒答。

---

8. 解题"招式手册"

招式 1：写对偶的三步法

(1) 写 $L$。(2) 对 $x$ 求 $inf$。(3) 把"$inf=-\mathrm{\infty }$ 的情形"对应的"$x$ 系数 = 0"那部分作为对偶约束。

招式 2：识别"对偶函数"的关键结构

$x$ 的项	对偶里如何出现
$\frac{1}{2}{x}^{T}Qx+b^{T}x$，$Q\succ 0$	二次：$-\frac{1}{2}{b}^T{Q}^{-1}b$
$c^{T}x$	线性，$inf$ 不是 -∞ ⇔ 系数 = 0 → 对偶等式约束
$\lambda$ 系数关于 $x$ 是仿射的	用 LP 对偶或共轭函数
$(\dots )\bullet X$ ($X⪰0$)	对偶 PSD 约束（系数矩阵 $⪰0$）
$f(x)$ 是任意凸	用共轭 $f^{\ast }$

招式 3：用强对偶求解原问题（A5.1, A5.3 套路）

1. 写对偶问题（往往维度更低）。
2. 求对偶最优 $({\lambda }^{\ast },{\nu }^{\ast })$。
3. 由 KKT 条件中"$\overline{x}=\arg \underset{x}{min}L(x,{\lambda }^{\ast },{\nu }^{\ast })$" 反解原最优 $\overline{x}$。

招式 4：用对偶证下界 / 上界

A5.4(b) 是经典套路：要证 $V\ge V^{\ast }$，用对偶可行点构造。

招式 5：把"内部最大化"用 LP/CLP 强对偶转换

鲁棒优化（§3）核心招式。出现 "$\underset{a\in \mathcal{U}}{sup}{a}^{T}x\le b$" → 对偶把 $sup$ 转 $inf$ → 与外层合并。

招式 6：识别"PSD 内积" 与 "锥内积" 的区别

$A\bullet B=\text{tr}(A^{T}B)=\sum _{ij}{A}_{ij}{B}_{ij}$。SDP 写对偶时全部用这个内积。

---

9. 自检清单

• [ ] Lagrangian 与对偶函数 / 对偶问题的定义？
• [ ] 弱对偶 / 强对偶 / Slater 三个层次的区别？
• [ ] 鞍点 ⇔ KKT ⇔ 强对偶的等价链？
• [ ] LP / QP / QCQP / SDP 的对偶推导？
• [ ] Fenchel 对偶 $min{f}_1(Ax)+f_2(x)$ 的形式？
• [ ] 共轭 $f^{\ast }$ 在对偶推导中的作用？
• [ ] proper cone、对偶锥、自对偶锥的例子？
• [ ] CLP 强对偶比 LP 强对偶要严格的"严格可行"条件？
• [ ] SDR：QCQP 怎么松弛到 SDP？什么时候紧（$m\le 1,2$）？
• [ ] LASSO 对偶？

10. 常见陷阱

1. 对偶 $\nu$ 的符号：等式约束的乘子 没有符号约束！只有不等式 $g\le 0$ 的乘子 $\lambda \ge 0$。
2. 对偶变量与原始约束的对应：写 $L=f_0+{\lambda }^T(\text{Ax-b ≤ 0})+{\nu }^T(\text{Cx-d=0})$，$\lambda$ 对应不等式。
3. $\underset{x}{inf}[\dots c^{T}x\dots ]$：若 $c\ne 0$ 则 $=-\mathrm{\infty }$；这给出对偶约束 $c=0$。容易写漏。
4. CLP 强对偶不能只看可行：必须严格可行（$\overline{x}{\succ }_{K}0$）才行。
5. LASSO 等 ℓ1 问题：$f^{\ast }$ 是对偶范数球的指示函数。常考。
6. SDR 的 duality gap：QCQP 的 SDR 在某些情形（$m\le 2$ 齐次或 $m\le 1$ + Slater 非齐次）下紧，否则有 gap。
7. A5.2 的"为什么对偶恒凸"：因为 $\theta (\lambda )$ 是仿射函数 $\lambda \mapsto L(x,\lambda )$ 的点态 inf，所以恒凹；对偶 max 凹 = 凸优化。
8. 互补松弛 ${\overline{\lambda }}^{T}g(\overline{x})=0$：在多个约束并存时，每个 ${\overline{\lambda }}_i{g}_i(\overline{x})=0$ 都成立（强化版）。

---

11. 接下来怎么学

1. 默写 §4 的"写对偶三步法"。
2. 把 §5 的 5 个经典对偶（LP / QP / QCQP→SDP / SDP / Fenchel）推导亲手做一遍。
3. 完成 A5 全部 + A6.2/3/4 + hw07.5。
4. 进入 6_梯度下降与牛顿法，从"对偶 / 解析"过渡到"算法 / 数值"。