4. 对偶理论

# 线性规划的对偶理论

1. 标准形式的线性规划问题（原问题 Primal Problem）

   $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \succeq 0 \end{align*}$$

   其中 $A \in \mathbb{R}^{m \times n}$，$b \in \mathbb{R}^m$，$c \in \mathbb{R}^n$，$x \in \mathbb{R}^n$。

2. 对偶问题的构造

   对于标准形式的线性规划问题，其对偶问题（Dual Problem）为：

   $$\begin{align*} \max_{\lambda, \nu} \quad & b^T \nu \\ \text{s.t.} \quad & A^T \nu + \lambda = c \\ & \lambda \succeq 0 \end{align*}$$

   其中 $\nu \in \mathbb{R}^m$ 是对应等式约束 $Ax = b$ 的拉格朗日乘子，$\lambda \in \mathbb{R}^n$ 是对应非负约束 $x \succeq 0$ 的拉格朗日乘子。

   通过消去 $\lambda$，对偶问题可等价地写为：

   $$\begin{align*} \max_{\nu} \quad & b^T \nu \\ \text{s.t.} \quad & A^T \nu \preceq c \end{align*}$$

3. 一般形式的线性规划对偶

   对于更一般的线性规划问题：

   $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & Gx \preceq h \\ & Ax = b \end{align*}$$

   其对偶问题为：

   $$\begin{align*} \max_{\lambda, \nu} \quad & -h^T \lambda + b^T \nu \\ \text{s.t.} \quad & G^T \lambda + A^T \nu + c = 0 \\ & \lambda \succeq 0 \end{align*}$$

   或等价地：

   $$\begin{align*} \max_{\lambda, \nu} \quad & -h^T \lambda + b^T \nu \\ \text{s.t.} \quad & G^T \lambda + A^T \nu = -c \\ & \lambda \succeq 0 \end{align*}$$

4. 弱对偶定理（Weak Duality Theorem）

   设 $x$ 是原问题的可行解，$(\lambda, \nu)$ 是对偶问题的可行解，则

   $$c^T x \geq b^T \nu$$

   即原问题的最优值 $p^*$ 和对偶问题的最优值 $d^*$ 满足：

   $$p^* \geq d^*$$

   证明：由于 $x$ 和 $(\lambda, \nu)$ 分别是原问题和对偶问题的可行解，有：

   • $Ax = b$，$x \succeq 0$
   • $A^T \nu + \lambda = c$，$\lambda \succeq 0$

   因此：

   $$c^T x = (A^T \nu + \lambda)^T x = \nu^T A x + \lambda^T x = \nu^T b + \lambda^T x \geq \nu^T b = b^T \nu$$

   其中不等式成立是因为 $\lambda \succeq 0$ 且 $x \succeq 0$，所以 $\lambda^T x \geq 0$。

5. 强对偶定理（Strong Duality Theorem）

   对于线性规划问题，如果原问题和对偶问题都有可行解，则强对偶成立：

   $$p^* = d^*$$

   即原问题和对偶问题的最优值相等。

   注意：

   • 线性规划问题满足强对偶性（只要原问题和对偶问题都有可行解）
   • 这与一般凸优化问题不同，一般凸优化问题需要满足 Slater 条件才能保证强对偶

6. 互补松弛条件（Complementary Slackness）

   设 $x^*$ 是原问题的最优解，$(\lambda^*, \nu^*)$ 是对偶问题的最优解，则互补松弛条件成立：

   $$\lambda_i^* x_i^* = 0, \quad i = 1, \ldots, n$$

   即对于每个 $i$，要么 $\lambda_i^* = 0$，要么 $x_i^* = 0$（或两者同时为 0）。

   对于一般形式的线性规划，互补松弛条件为：

   $$\lambda_i^* (Gx^* - h)_i = 0, \quad i = 1, \ldots, m$$

   即对于每个不等式约束，要么拉格朗日乘子为 0，要么约束在最优解处是紧的（等号成立）。

7. 对偶问题的几何解释

   • 对偶问题可以理解为在原问题的约束下，寻找目标函数的下界
   • 对偶变量的值反映了原问题约束的"价格"或"影子价格"（shadow price）
   • 对偶问题的最优解提供了原问题最优值的下界

8. 对偶问题的对偶

   线性规划的对偶问题的对偶是原问题本身，即对偶关系是对称的。

9. 对偶单纯形法（Dual Simplex Method）

   • 对偶单纯形法是在对偶可行性的基础上，通过迭代逐步达到原问题可行性的方法
   • 当原问题不可行但对偶问题可行时，可以使用对偶单纯形法
   • 对偶单纯形法在灵敏度分析中特别有用

10. 对偶性的应用

    • 灵敏度分析：对偶变量可以用于分析约束右端项变化对目标函数值的影响
    • 下界估计：对偶问题的最优值提供了原问题最优值的下界
    • 算法设计：对偶理论为设计高效的线性规划算法提供了理论基础
    • 经济解释：对偶变量可以解释为资源的边际价值或影子价格

11. 原问题与对偶问题的共可行性关系定理

    对于标准形式的线性规划问题（LPP），原问题和对偶问题之间的共可行性关系可以确定如下：

    原问题 \ 对偶问题	不可行（Infeasible）	最优（Optimal）	无界（Unbounded）
    不可行（Infeasible）	√	×	√
    最优（Optimal）	×	√	×
    无界（Unbounded）	√	×	×

    定理说明：

    • 当原问题不可行时，对偶问题可能不可行，也可能无界，但不可能有最优解
    • 当原问题最优时，对偶问题也一定最优（强对偶性），且最优值相等
    • 当原问题无界时，对偶问题一定不可行
    • 对称地，当对偶问题无界时，原问题一定不可行
    • 原问题和对偶问题不可能同时无界
    • 原问题和对偶问题可能同时不可行

# 定义和例子

1. 标准形式的优化问题（原问题 Primal Problem）

   $$\begin{align*} \min_x \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq 0,\quad i=1,\dots, m \\ & h_j(x) = 0,\quad j=1,\dots, p \end{align*}$$

   其中 $f_0: \mathbb{R}^n \to \mathbb{R}$ 是目标函数，$f_i: \mathbb{R}^n \to \mathbb{R}$ 是不等式约束函数，$h_j: \mathbb{R}^n \to \mathbb{R}$ 是等式约束函数。

2. 拉格朗日函数 (Lagrangian Function)

   对于标准形式的优化问题，其拉格朗日函数定义为：

   $$L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x)$$

   其中：

   • $\lambda = [\lambda_1, \ldots, \lambda_m]^T \in \mathbb{R}^m$ 是不等式约束的拉格朗日乘子（对偶变量）
   • $\nu = [\nu_1, \ldots, \nu_p]^T \in \mathbb{R}^p$ 是等式约束的拉格朗日乘子（对偶变量）
   • 拉格朗日函数将约束优化问题转化为无约束优化问题

3. 对偶函数 (Dual Function)

   对偶函数定义为拉格朗日函数关于原变量 $x$ 的下确界：

   $$g(\lambda, \nu) = \inf_{x \in \mathcal{D}} L(x, \lambda, \nu) = \inf_{x \in \mathcal{D}} \left[ f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x) \right]$$

   其中 $\mathcal{D} = \bigcap_{i=0}^m \text{dom}\ f_i \cap \bigcap_{j=1}^p \text{dom}\ h_j$ 是问题的定义域。

   对偶函数的性质：

   • 对偶函数是凹函数（无论原问题是否为凸问题）
   • 对偶函数提供了原问题最优值的下界：$g(\lambda, \nu) \leq p^*$，其中 $p^*$ 是原问题的最优值
   • 对偶函数可能取值为 $-\infty$（当拉格朗日函数无下界时）

4. 对偶问题 (Dual Problem)

   对偶问题定义为最大化对偶函数：

   $$\begin{align*} \max_{\lambda, \nu} \quad & g(\lambda, \nu) \\ \text{s.t.} \quad & \lambda \succeq 0 \end{align*}$$

   其中 $\lambda \succeq 0$ 表示 $\lambda_i \geq 0$ 对所有 $i=1,\ldots, m$ 成立。

   对偶问题的性质：

   • 对偶问题总是凸优化问题（因为对偶函数是凹函数，且约束 $\lambda \succeq 0$ 是凸集）
   • 对偶问题的最优值记为 $d^*$
   • 即使原问题不是凸的，对偶问题也是凸的

5. 弱对偶定理 (Weak Duality Theorem)

   设 $x$ 是原问题的可行解，$(\lambda, \nu)$ 是对偶问题的可行解（即 $\lambda \succeq 0$），则

   $$f_0(x) \geq g(\lambda, \nu)$$

   即原问题的最优值 $p^*$ 和对偶问题的最优值 $d^*$ 满足：

   $$p^* \geq d^*$$

   证明：由于 $x$ 是原问题的可行解，有 $f_i(x) \leq 0$ 和 $h_j(x) = 0$。又因为 $\lambda \succeq 0$，所以：

   $$\begin{align*} g(\lambda, \nu) &= \inf_{z \in \mathcal{D}} L(z, \lambda, \nu) \\ &\leq L(x, \lambda, \nu) \\ &= f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x) \\ &\leq f_0(x) \end{align*}$$

   其中最后一个不等式成立是因为 $\lambda_i \geq 0$ 且 $f_i(x) \leq 0$，所以 $\lambda_i f_i(x) \leq 0$，以及 $h_j(x) = 0$。

   对偶间隙 (Dual Gap)：$p^* - d^* \geq 0$ 称为对偶间隙。当 $p^* = d^*$ 时，称为强对偶（strong duality）。

6. 例子：线性规划的对偶

   考虑线性规划问题：

   $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \succeq 0 \end{align*}$$

   拉格朗日函数：

   $$L(x, \lambda, \nu) = c^T x - \lambda^T x + \nu^T (Ax - b) = (c - \lambda + A^T \nu)^T x - \nu^T b$$

   对偶函数：

   $$g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu) = \begin{cases} -\nu^T b & \text{如果 } c - \lambda + A^T \nu = 0 \\ -\infty & \text{否则} \end{cases}$$

   对偶问题：

   $$\begin{align*} \max_{\lambda, \nu} \quad & -\nu^T b \\ \text{s.t.} \quad & c - \lambda + A^T \nu = 0 \\ & \lambda \succeq 0 \end{align*}$$

   通过消去 $\lambda$，等价地写为：

   $$\begin{align*} \max_{\nu} \quad & b^T \nu \\ \text{s.t.} \quad & A^T \nu \preceq c \end{align*}$$

7. 例子：二次规划的对偶

   考虑二次规划问题：

   $$\begin{align*} \min_x \quad & \frac{1}{2} x^T P x + q^T x + r \\ \text{s.t.} \quad & Ax = b \\ & x \succeq 0 \end{align*}$$

   其中 $P \succeq 0$。

   拉格朗日函数：

   $$L(x, \lambda, \nu) = \frac{1}{2} x^T P x + q^T x + r - \lambda^T x + \nu^T (Ax - b)$$

   对偶函数：对 $x$ 求导并令其为零：

   $$\nabla_x L = Px + q - \lambda + A^T \nu = 0$$

   如果 $P \succ 0$（正定），则 $x = P^{-1}(\lambda - A^T \nu - q)$，代入拉格朗日函数可得对偶函数。

   如果 $P$ 只是半正定，需要额外的条件保证对偶函数有限。

8. 例子：最小范数问题

   考虑问题：

   $$\begin{align*} \min_x \quad & \|x\| \\ \text{s.t.} \quad & Ax = b \end{align*}$$

   拉格朗日函数：

   $$L(x, \nu) = \|x\| + \nu^T (Ax - b)$$

   对偶函数：

   $$g(\nu) = \inf_{x} [\|x\| + \nu^T (Ax - b)] = \inf_{x} [\|x\| + \nu^T A x] - \nu^T b$$

   利用共轭函数的性质，可以证明：

   $$g(\nu) = \begin{cases} -\nu^T b & \text{如果 } \|A^T \nu\|_* \leq 1 \\ -\infty & \text{否则} \end{cases}$$

   其中 $\|\cdot\|_*$ 是对偶范数。

9. 对偶问题的几何解释

   • 对偶函数 $g(\lambda, \nu)$ 可以理解为：对于给定的对偶变量 $(\lambda, \nu)$，在原问题的约束下，拉格朗日函数的最小值
   • 对偶问题是在所有可能的对偶变量中，寻找使得这个最小值最大的对偶变量
   • 对偶问题的最优值 $d^*$ 提供了原问题最优值 $p^*$ 的下界
   • 对偶变量 $\lambda_i$ 可以解释为第 $i$ 个不等式约束的"价格"或"影子价格"

10. 对偶问题的优势

    • 对偶问题总是凸优化问题（即使原问题不是凸的）
    • 对偶问题的变量维度通常小于原问题的变量维度
    • 对偶问题可以提供原问题最优值的下界
    • 对偶问题在算法设计中非常有用（如对偶上升法、增广拉格朗日法等）

# Slater 条件

1. 强对偶 (Strong Duality)

   对于优化问题，如果原问题的最优值 $p^*$ 和对偶问题的最优值 $d^*$ 相等，即

   $$p^* = d^*$$

   则称强对偶成立。

   强对偶的重要性：

   • 强对偶成立时，对偶间隙为零，对偶问题的最优值等于原问题的最优值
   • 强对偶为求解原问题提供了另一种途径：可以通过求解对偶问题来获得原问题的最优值
   • 强对偶成立时，原问题和对偶问题的最优解之间存在特定的关系（KKT条件）

2. Slater 条件 (Slater's Condition)

   对于标准形式的凸优化问题：

   $$\begin{align*} \min_x \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq 0,\quad i=1,\dots, m \\ & Ax = b \end{align*}$$

   其中 $f_0, f_1, \ldots, f_m$ 是凸函数，$A \in \mathbb{R}^{p \times n}$，$b \in \mathbb{R}^p$。

   Slater 条件：如果存在点 $x \in \text{relint}\ \mathcal{D}$（$\mathcal{D}$ 的相对内部）使得

   $$f_i(x) < 0,\quad i=1,\ldots, m, \quad Ax = b$$

   则称问题满足 Slater 条件（或 Slater 约束品性）。

   说明：

   • $\text{relint}\ \mathcal{D}$ 表示定义域 $\mathcal{D}$ 的相对内部
   • 对于不等式约束，要求严格小于 0（严格可行）
   • 对于等式约束，要求严格等于（必须满足）
   • 这样的点 $x$ 称为严格可行点（strictly feasible point）或Slater 点

3. 强对偶定理 (Strong Duality Theorem)

   对于凸优化问题，如果满足 Slater 条件，则强对偶成立：

   $$p^* = d^*$$

   定理表述：

   • 设原问题是凸优化问题（$f_0, f_i$ 是凸函数，$h_j$ 是仿射函数）
   • 如果存在严格可行点（Slater 条件满足）
   • 且原问题的最优值 $p^*$ 有限（$p^* > -\infty$）
   • 则强对偶成立：$p^* = d^*$

   注意：

   • Slater 条件是强对偶成立的充分条件，但不是必要条件
   • 即使不满足 Slater 条件，强对偶也可能成立
   • 对于线性规划，只要原问题和对偶问题都有可行解，强对偶就成立（不需要 Slater 条件）

4. 相对内部 Slater 条件 (Relative Interior Slater Condition)

   对于某些问题，标准的 Slater 条件可能过于严格。相对内部 Slater 条件是更弱的条件：

   如果存在点 $x \in \text{relint}\ \mathcal{D}$ 使得

   $$f_i(x) < 0,\quad i \in I, \quad Ax = b$$

   其中 $I$ 是某些不等式约束的索引集合，则称问题满足相对内部 Slater 条件。

   应用场景：

   • 当某些不等式约束是仿射函数时，可以放宽要求
   • 对于仿射不等式约束 $f_i(x) = a_i^T x - b_i \leq 0$，只需要 $f_i(x) \leq 0$（不需要严格小于）

5. Slater 条件的几何解释

   • Slater 条件要求可行域有"内部点"（在相对内部意义下）
   • 如果可行域是"薄的"（如只有边界点），可能不满足 Slater 条件
   • Slater 条件保证了可行域有足够的"厚度"，使得对偶问题能够达到原问题的最优值

6. 例子：满足 Slater 条件的问题

   考虑二次规划问题：

   $$\begin{align*} \min_x \quad & \frac{1}{2} x^T P x + q^T x \\ \text{s.t.} \quad & Ax = b \\ & x \succeq 0 \end{align*}$$

   其中 $P \succeq 0$。

   如果存在 $x > 0$（所有分量严格大于 0）且 $Ax = b$，则满足 Slater 条件。

7. 例子：不满足 Slater 条件的问题

   考虑问题：

   $$\begin{align*} \min_x \quad & x_1 \\ \text{s.t.} \quad & x_1^2 + x_2^2 \leq 1 \\ & x_1 + x_2 = 1 \end{align*}$$

   可行域是单位圆与直线 $x_1 + x_2 = 1$ 的交集，只有一个点 $(1, 0)$（或 $(0, 1)$），没有严格可行点，因此不满足 Slater 条件。

   但在这个例子中，强对偶仍然可能成立（需要具体分析）。

8. Slater 条件与约束品性的关系

   • Slater 条件是一种约束品性（constraint qualification）
   • 约束品性用于保证最优解满足 KKT 条件
   • Slater 条件不仅保证 KKT 条件成立，还保证强对偶成立
   • 对于凸优化问题，Slater 条件比一般的约束品性（如 LICQ）更强

9. 强对偶不成立的情况

   即使原问题是凸优化问题，如果：

   • 不满足 Slater 条件
   • 且可行域是"退化的"（如只有边界点）

   则可能出现对偶间隙（duality gap）：$p^* > d^*$。

   例子：考虑问题

   $$\begin{align*} \min_{x, y} \quad & e^{-x} \\ \text{s.t.} \quad & \sqrt{x^2 + y^2} \leq y \end{align*}$$

   该问题的可行域只有一个点 $(0, 0)$，不满足 Slater 条件，可能存在对偶间隙。

10. 线性规划的特殊性

    对于线性规划问题，强对偶的条件更宽松：

    • 只要原问题和对偶问题都有可行解，强对偶就成立
    • 不需要 Slater 条件（因为线性约束总是可以找到严格可行点，除非问题不可行）
    • 这是线性规划的一个重要性质

11. 强对偶的应用

    • 对偶方法：当强对偶成立时，可以通过求解对偶问题来求解原问题
    • 最优性验证：如果找到原问题可行解 $x$ 和对偶问题可行解 $(\lambda, \nu)$ 使得 $f_0(x) = g(\lambda, \nu)$，则 $x$ 是原问题的最优解
    • 下界估计：即使强对偶不成立，对偶问题的最优值 $d^*$ 仍然提供原问题最优值的下界

# KKT 条件

1. KKT 条件与对偶性的关系

   对于标准形式的优化问题：

   $$\begin{align*} \min_x \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq 0,\quad i=1,\dots, m \\ & h_j(x) = 0,\quad j=1,\dots, p \end{align*}$$

   其拉格朗日函数为：

   $$L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x)$$

   KKT 条件包括：

   • 稳定性条件（Stationarity）：$\nabla_x L(x^*, \lambda^*, \nu^*) = 0$
   • 原问题可行性（Primal Feasibility）：$f_i(x^*) \leq 0, h_j(x^*) = 0$
   • 对偶可行性（Dual Feasibility）：$\lambda_i^* \geq 0$
   • 互补松弛（Complementary Slackness）：$\lambda_i^* f_i(x^*) = 0$

   KKT 条件将原问题的最优性与对偶问题的最优性联系起来。

2. KKT 条件与强对偶的关系

   定理：设 $x^*$ 是原问题的可行解，$(\lambda^*, \nu^*)$ 是对偶问题的可行解。如果满足：

   • 互补松弛条件：$\lambda_i^* f_i(x^*) = 0$ 对所有 $i$ 成立
   • 稳定性条件：$\nabla_x L(x^*, \lambda^*, \nu^*) = 0$

   则 $x^*$ 和 $(\lambda^*, \nu^*)$ 分别是原问题和对偶问题的最优解，且强对偶成立：$p^* = d^* = f_0(x^*) = g(\lambda^*, \nu^*)$。

   证明思路：

   • 由稳定性条件，$x^*$ 是拉格朗日函数 $L(x, \lambda^*, \nu^*)$ 的极小值点
   • 因此 $g(\lambda^*, \nu^*) = L(x^*, \lambda^*, \nu^*)$
   • 由互补松弛条件和可行性条件，$L(x^*, \lambda^*, \nu^*) = f_0(x^*)$
   • 因此 $f_0(x^*) = g(\lambda^*, \nu^*)$，即强对偶成立

3. 凸优化问题中 KKT 条件的充要性

   对于凸优化问题（$f_0, f_i$ 是凸函数，$h_j$ 是仿射函数），如果满足 Slater 条件，则：

   KKT 条件是充要条件：

   • 充分性：如果 $x^*$ 和 $(\lambda^*, \nu^*)$ 满足 KKT 条件，则 $x^*$ 是原问题的最优解，$(\lambda^*, \nu^*)$ 是对偶问题的最优解，且强对偶成立
   • 必要性：如果 $x^*$ 是原问题的最优解，且满足 Slater 条件，则存在 $(\lambda^*, \nu^*)$ 使得 KKT 条件成立

   证明充分性：

   • 设 $x^*$ 和 $(\lambda^*, \nu^*)$ 满足 KKT 条件
   • 由于 $x^*$ 是可行解，$f_0(x^*) \geq p^*$
   • 由于稳定性条件，$x^*$ 是 $L(x, \lambda^*, \nu^*)$ 的极小值点
   • 因此 $g(\lambda^*, \nu^*) = L(x^*, \lambda^*, \nu^*) = f_0(x^*)$（由互补松弛条件）
   • 所以 $f_0(x^*) = g(\lambda^*, \nu^*) \leq d^* \leq p^* \leq f_0(x^*)$
   • 因此 $p^* = d^* = f_0(x^*)$，即 $x^*$ 是最优解且强对偶成立

4. 通过 KKT 条件验证最优性

   当强对偶成立时，可以通过以下方法验证最优性：

   方法：如果找到 $x^*$ 和 $(\lambda^*, \nu^*)$ 使得：

   • $x^*$ 是原问题的可行解
   • $(\lambda^*, \nu^*)$ 是对偶问题的可行解
   • $f_0(x^*) = g(\lambda^*, \nu^*)$（或等价地，满足互补松弛条件和稳定性条件）

   则 $x^*$ 是原问题的最优解，$(\lambda^*, \nu^*)$ 是对偶问题的最优解。

   应用：这是验证最优性的重要方法，特别是在对偶方法中。

5. KKT 条件与对偶问题的关系

   对偶问题可以写为：

   $$\begin{align*} \max_{\lambda, \nu} \quad & g(\lambda, \nu) \\ \text{s.t.} \quad & \lambda \succeq 0 \end{align*}$$

   其中 $g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)$。

   KKT 条件的对偶解释：

   • 稳定性条件 $\nabla_x L(x^*, \lambda^*, \nu^*) = 0$ 意味着 $x^*$ 是 $L(x, \lambda^*, \nu^*)$ 的极小值点
   • 因此 $g(\lambda^*, \nu^*) = L(x^*, \lambda^*, \nu^*)$
   • 互补松弛条件 $\lambda_i^* f_i(x^*) = 0$ 意味着 $L(x^*, \lambda^*, \nu^*) = f_0(x^*)$
   • 因此 $f_0(x^*) = g(\lambda^*, \nu^*)$，即原问题和对偶问题的最优值相等

6. 例子：线性规划的 KKT 条件

   考虑线性规划问题：

   $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & Ax = b \\ & x \succeq 0 \end{align*}$$

   拉格朗日函数：$L(x, \lambda, \nu) = c^T x - \lambda^T x + \nu^T (Ax - b)$

   KKT 条件：

   • 稳定性：$\nabla_x L = c - \lambda + A^T \nu = 0$
   • 原问题可行性：$Ax = b, x \succeq 0$
   • 对偶可行性：$\lambda \succeq 0$
   • 互补松弛：$\lambda_i x_i = 0$ 对所有 $i$

   这些条件等价于线性规划的最优性条件。

7. 例子：二次规划的 KKT 条件

   考虑二次规划问题：

   $$\begin{align*} \min_x \quad & \frac{1}{2} x^T P x + q^T x \\ \text{s.t.} \quad & Ax = b \\ & x \succeq 0 \end{align*}$$

   其中 $P \succeq 0$。

   拉格朗日函数：$L(x, \lambda, \nu) = \frac{1}{2} x^T P x + q^T x - \lambda^T x + \nu^T (Ax - b)$

   KKT 条件：

   • 稳定性：$\nabla_x L = Px + q - \lambda + A^T \nu = 0$
   • 原问题可行性：$Ax = b, x \succeq 0$
   • 对偶可行性：$\lambda \succeq 0$
   • 互补松弛：$\lambda_i x_i = 0$ 对所有 $i$

   如果 $P \succ 0$ 且满足 Slater 条件，则 KKT 条件是充要条件。

8. KKT 条件与对偶间隙

   如果 $x^*$ 和 $(\lambda^*, \nu^*)$ 满足 KKT 条件，则：

   $$p^* = d^* = f_0(x^*) = g(\lambda^*, \nu^*)$$

   即对偶间隙为零。

   反之，如果存在对偶间隙（$p^* > d^*$），则不存在同时满足 KKT 条件的 $x^*$ 和 $(\lambda^*, \nu^*)$。

9. KKT 条件在算法中的应用

   • 对偶上升法：通过求解对偶问题，然后利用 KKT 条件恢复原问题的最优解
   • 增广拉格朗日法：通过修改拉格朗日函数，使得 KKT 条件更容易满足
   • 内点法：通过修改互补松弛条件（如 $\lambda_i f_i(x) = \mu$，其中 $\mu > 0$），逐步逼近 KKT 条件
   • 原始-对偶方法：同时求解原问题和对偶问题，利用 KKT 条件作为最优性判据

10. KKT 条件的几何解释

    • 稳定性条件：目标函数梯度与约束函数梯度的线性组合为零，意味着在最优解处，目标函数的梯度位于约束函数梯度张成的空间中
    • 互补松弛条件：如果约束不起作用（$f_i(x^*) < 0$），则对应的拉格朗日乘子为零（$\lambda_i^* = 0$）；如果约束起作用（$f_i(x^*) = 0$），则拉格朗日乘子可能非零
    • 对偶可行性条件：拉格朗日乘子非负，反映了不等式约束的方向性

11. KKT 条件与 Fritz John 条件的关系

    • Fritz John 条件是更一般的条件，允许目标函数梯度前的系数 $\lambda_0 \geq 0$
    • 当 $\lambda_0 > 0$ 时，Fritz John 条件等价于 KKT 条件（可归一化使 $\lambda_0 = 1$）
    • 当 $\lambda_0 = 0$ 时，称为异常情况，此时目标函数梯度不参与条件，通常意味着约束品性不满足

12. KKT 条件总结

    对于凸优化问题，在 Slater 条件下：

    • KKT 条件是充要条件
    • 满足 KKT 条件的解是全局最优解
    • KKT 条件保证了强对偶成立
    • KKT 条件提供了原问题和对偶问题之间的桥梁

# 灵敏度与择一理论

1. 灵敏度分析 (Sensitivity Analysis)

   灵敏度分析研究优化问题参数变化对最优解和最优值的影响。对于优化问题：

   $$\begin{align*} \min_x \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq u_i,\quad i=1,\dots, m \\ & h_j(x) = v_j,\quad j=1,\dots, p \end{align*}$$

   其中 $u = [u_1, \ldots, u_m]^T$ 和 $v = [v_1, \ldots, v_p]^T$ 是参数。

   最优值函数定义为：

   $$p^*(u, v) = \inf\{f_0(x) \mid f_i(x) \leq u_i, h_j(x) = v_j\}$$

2. 对偶变量与灵敏度

   对于凸优化问题，如果满足 Slater 条件且强对偶成立，则对偶变量 $\lambda^*$ 和 $\nu^*$ 提供了最优值函数关于参数的灵敏度信息：

   定理：设 $p^*(u, v)$ 在 $(0, 0)$ 处可微，且强对偶成立，则

   $$\lambda_i^* = -\frac{\partial p^*}{\partial u_i}(0, 0), \quad \nu_j^* = -\frac{\partial p^*}{\partial v_j}(0, 0)$$

   解释：

   • $\lambda_i^*$ 表示第 $i$ 个不等式约束右端项 $u_i$ 增加一个单位时，最优值的减少量（负号表示增加约束会使最优值增大或不变）
   • $\nu_j^*$ 表示第 $j$ 个等式约束右端项 $v_j$ 变化对最优值的影响
   • 对偶变量也称为影子价格（shadow price）或边际值（marginal value）

3. 局部灵敏度分析

   在最优解 $x^*$ 和对偶最优解 $(\lambda^*, \nu^*)$ 附近，如果约束品性满足，则：

   $$p^*(u, v) \approx p^*(0, 0) - \sum_{i=1}^m \lambda_i^* u_i - \sum_{j=1}^p \nu_j^* v_j$$

   这提供了参数小扰动时最优值的近似变化。

4. 择一理论 (Alternative Theorems)

   择一理论（也称为 Farkas 引理或择一定理）研究两个系统是否至少有一个有解的问题。

   Farkas 引理 (Farkas' Lemma)：

   设 $A \in \mathbb{R}^{m \times n}$，$b \in \mathbb{R}^m$，则以下两个系统有且仅有一个有解：

   系统 1：$Ax = b, x \succeq 0$

   系统 2：$A^T y \succeq 0, b^T y < 0$

   几何解释：

   • 系统 1 有解意味着 $b$ 属于 $A$ 的列向量生成的锥
   • 系统 2 有解意味着存在超平面将 $b$ 与该锥分离

5. 择一理论的推广：Gordan 定理

   Gordan 定理：

   设 $A \in \mathbb{R}^{m \times n}$，则以下两个系统有且仅有一个有解：

   系统 1：$Ax = 0, x \succ 0$（存在严格正解）

   系统 2：$A^T y \succeq 0, A^T y \neq 0$

   即要么存在严格正的解，要么存在非零的非负解。

6. 择一理论与对偶性的关系

   择一理论可以用于证明对偶性结果。例如，可以用 Farkas 引理证明线性规划的强对偶性。

   应用：择一理论可以用于：

   • 判断优化问题的可行性
   • 证明对偶性定理
   • 分析约束系统的相容性

7. 例子：线性规划的灵敏度分析

   考虑线性规划问题：

   $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & Ax = b + \delta b \\ & x \succeq 0 \end{align*}$$

   如果原问题和对偶问题都有最优解，则对小的 $\delta b$，最优值的变化为：

   $$p^*(b + \delta b) \approx p^*(b) + \nu^{*T} \delta b$$

   其中 $\nu^*$ 是对偶问题的最优解。

8. 择一理论的应用：可行性判断

   择一理论可以用于判断优化问题的可行性：

   • 如果原问题不可行，则对偶问题无界或不可行
   • 如果对偶问题不可行，则原问题无界或不可行
   • 这提供了判断问题可行性的另一种方法

9. 强择一理论 (Strong Alternative)

   对于更一般的系统，有强择一理论：

   设 $f_i: \mathbb{R}^n \to \mathbb{R}$ 是凸函数，$h_j: \mathbb{R}^n \to \mathbb{R}$ 是仿射函数，则以下两个系统有且仅有一个有解（在 Slater 条件下）：

   系统 1：$f_i(x) < 0, i=1,\ldots, m; h_j(x) = 0, j=1,\ldots, p$

   系统 2：存在 $\lambda \succeq 0, \nu$（不全为零）使得

   $$\sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x) \geq 0, \quad \forall x$$

10. 灵敏度分析的局限性

    • 灵敏度分析基于局部线性近似，只适用于参数的小扰动
    • 当参数变化较大时，最优解的结构可能发生变化（如起作用约束集合改变）
    • 需要重新求解优化问题以获得准确结果

# 广义不等式约束问题

1. 广义不等式约束的优化问题

   考虑带有广义不等式约束的优化问题：

   $$\begin{align*} \min_x \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \preceq_{\mathcal{K}_i} 0,\quad i=1,\dots, m \\ & h_j(x) = 0,\quad j=1,\dots, p \end{align*}$$

   其中 $\preceq_{\mathcal{K}_i}$ 是由正常锥（proper cone）$\mathcal{K}_i$ 诱导的广义不等式。

2. 拉格朗日函数（广义不等式情况）

   对于广义不等式约束问题，拉格朗日函数定义为：

   $$L(x, \lambda_1, \ldots, \lambda_m, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i^T f_i(x) + \sum_{j=1}^p \nu_j h_j(x)$$

   其中：

   • $\lambda_i \in \mathcal{K}_i^*$ 是对应第 $i$ 个广义不等式约束的对偶变量
   • $\mathcal{K}_i^*$ 是 $\mathcal{K}_i$ 的对偶锥（dual cone）
   • $\nu_j$ 是等式约束的拉格朗日乘子

3. 对偶锥 (Dual Cone)

   对于锥 $\mathcal{K} \subseteq \mathbb{R}^n$，其对偶锥定义为：

   $$\mathcal{K}^* = \{y \in \mathbb{R}^n \mid y^T x \geq 0, \forall x \in \mathcal{K}\}$$

   性质：

   • 如果 $\mathcal{K}$ 是正常锥，则 $\mathcal{K}^*$ 也是正常锥
   • $(\mathcal{K}^*)^* = \mathcal{K}$（对偶锥的对偶是原锥）
   • 如果 $\mathcal{K}$ 是闭凸锥，则 $\mathcal{K}^{**} = \mathcal{K}$

4. 对偶函数（广义不等式情况）

   对偶函数定义为：

   $$g(\lambda_1, \ldots, \lambda_m, \nu) = \inf_{x \in \mathcal{D}} L(x, \lambda_1, \ldots, \lambda_m, \nu)$$

   其中 $\lambda_i \in \mathcal{K}_i^*$。

5. 对偶问题（广义不等式情况）

   对偶问题为：

   $$\begin{align*} \max_{\lambda_1, \ldots, \lambda_m, \nu} \quad & g(\lambda_1, \ldots, \lambda_m, \nu) \\ \text{s.t.} \quad & \lambda_i \succeq_{\mathcal{K}_i^*} 0,\quad i=1,\ldots, m \end{align*}$$

   其中 $\lambda_i \succeq_{\mathcal{K}_i^*} 0$ 表示 $\lambda_i \in \mathcal{K}_i^*$。

6. 弱对偶定理（广义不等式情况）

   设 $x$ 是原问题的可行解，$(\lambda_1, \ldots, \lambda_m, \nu)$ 是对偶问题的可行解，则

   $$f_0(x) \geq g(\lambda_1, \ldots, \lambda_m, \nu)$$

   即 $p^* \geq d^*$。

7. 强对偶定理（广义不等式情况）

   对于凸优化问题（$f_0, f_i$ 是凸函数，$h_j$ 是仿射函数），如果满足 Slater 条件，则强对偶成立：$p^* = d^*$。

   Slater 条件（广义不等式情况）：存在 $x \in \text{relint}\ \mathcal{D}$ 使得

   $$f_i(x) \prec_{\mathcal{K}_i} 0,\quad i=1,\ldots, m; \quad h_j(x) = 0,\quad j=1,\ldots, p$$

8. KKT 条件（广义不等式情况）

   对于凸优化问题，在 Slater 条件下，KKT 条件是充要条件：

   • 稳定性条件：$\nabla_x L(x^*, \lambda_1^*, \ldots, \lambda_m^*, \nu^*) = 0$
   • 原问题可行性：$f_i(x^*) \preceq_{\mathcal{K}_i} 0, h_j(x^*) = 0$
   • 对偶可行性：$\lambda_i^* \succeq_{\mathcal{K}_i^*} 0$
   • 互补松弛：$\lambda_i^{*T} f_i(x^*) = 0$

9. 例子：半正定规划 (SDP) 的对偶

   考虑半正定规划问题：

   $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & F(x) = F_0 + \sum_{i=1}^n x_i F_i \preceq 0 \\ & Ax = b \end{align*}$$

   其中 $F_i \in S^k$（$k \times k$ 对称矩阵），$\preceq$ 表示半正定矩阵的 Löwner 偏序。

   对偶问题：

   $$\begin{align*} \max_{Z, \nu} \quad & -\text{tr}(F_0 Z) + b^T \nu \\ \text{s.t.} \quad & \text{tr}(F_i Z) + (A^T \nu)_i + c_i = 0,\quad i=1,\ldots, n \\ & Z \succeq 0 \end{align*}$$

   其中 $Z \in S^k$ 是对偶变量，对应半正定约束。

10. 例子：二阶锥规划 (SOCP) 的对偶

    考虑二阶锥规划问题：

    $$\begin{align*} \min_x \quad & c^T x \\ \text{s.t.} \quad & \|A_i x + b_i\|_2 \leq c_i^T x + d_i,\quad i=1,\ldots, m \\ & Fx = g \end{align*}$$

    其中约束 $\|A_i x + b_i\|_2 \leq c_i^T x + d_i$ 是二阶锥约束（Lorentz 锥约束）。

    对偶问题也涉及二阶锥约束，对偶变量属于对偶的二阶锥。

11. 广义不等式的对偶锥

    常见锥的对偶锥：

    • 非负象限：$(\mathbb{R}_+^n)^* = \mathbb{R}_+^n$（自对偶）
    • 半正定锥：$(S_+^n)^* = S_+^n$（自对偶）
    • 二阶锥：Lorentz 锥也是自对偶的
    • 一般锥：需要根据定义计算

12. 广义不等式约束问题的优势

    • 可以统一处理多种类型的约束（线性、二次、半正定等）
    • 对偶理论在广义不等式情况下仍然成立
    • 为设计统一的算法提供了理论基础

# 对偶问题和问题变形

1. 对偶问题的构造方法

   对于标准形式的优化问题，对偶问题的构造步骤：

   • 写出拉格朗日函数
   • 求对偶函数（关于原变量的下确界）
   • 最大化对偶函数，约束为对偶可行性

2. 等价问题的对偶

   如果两个优化问题是等价的（有相同的最优值），它们的对偶问题也等价。

   例子：以下两个问题等价：

   $$\min_x f_0(x) \text{ s.t. } f_i(x) \leq 0$$

   和

   $$\min_{x, t} t \text{ s.t. } f_0(x) \leq t, f_i(x) \leq 0$$

   它们的对偶问题也等价。

3. 问题变形：引入松弛变量

   可以通过引入松弛变量将不等式约束转化为等式约束：

   $$f_i(x) \leq 0 \quad \Leftrightarrow \quad f_i(x) + s_i = 0, s_i \geq 0$$

   这种变形不改变问题的对偶（对偶变量对应关系可能改变）。

4. 问题变形：消除等式约束

   如果等式约束是 $Ax = b$，可以通过参数化可行域来消除：

   $$\{x \mid Ax = b\} = \{Fz + x_0 \mid z \in \mathbb{R}^k\}$$

   其中 $F$ 的列向量张成 $A$ 的零空间，$x_0$ 是 $Ax = b$ 的一个特解。

   消除等式约束后，对偶问题中不再有对应的对偶变量。

5. 问题变形：引入上境图形式

   将问题转化为上境图形式（epigraph form）：

   $$\begin{align*} \min_{x, t} \quad & t \\ \text{s.t.} \quad & f_0(x) \leq t \\ & f_i(x) \leq 0,\quad i=1,\ldots, m \\ & h_j(x) = 0,\quad j=1,\ldots, p \end{align*}$$

   这种形式有时便于分析对偶。

6. 对偶问题的对偶

   对于凸优化问题，对偶问题的对偶是原问题（在适当条件下）。

   定理：如果原问题是凸优化问题且满足 Slater 条件，则对偶问题的对偶是原问题。

7. 问题变形：最小化最大值

   考虑问题：

   $$\min_x \max_{i=1,\ldots, m} f_i(x)$$

   可以等价地写为：

   $$\begin{align*} \min_{x, t} \quad & t \\ \text{s.t.} \quad & f_i(x) \leq t,\quad i=1,\ldots, m \end{align*}$$

   然后可以构造对偶问题。

8. 问题变形：最小化上确界

   考虑问题：

   $$\min_x \sup_{y \in \mathcal{Y}} f(x, y)$$

   可以等价地写为：

   $$\begin{align*} \min_{x, t} \quad & t \\ \text{s.t.} \quad & f(x, y) \leq t,\quad \forall y \in \mathcal{Y} \end{align*}$$

   如果 $\mathcal{Y}$ 是有限集，这是标准的优化问题；如果是无限集，需要其他方法。

9. 对偶问题的简化

   有时可以通过消去变量来简化对偶问题：

   • 如果对偶函数关于某些变量是线性的，可以通过约束条件消去这些变量
   • 如果某些约束是等式约束，可以代入消去

10. 例子：最小范数问题的变形

    原问题：

    $$\min_x \|x\| \text{ s.t. } Ax = b$$

    上境图形式：

    $$\begin{align*} \min_{x, t} \quad & t \\ \text{s.t.} \quad & \|x\| \leq t \\ & Ax = b \end{align*}$$

    两种形式的对偶问题等价。

11. 问题变形：分式规划

    考虑分式规划问题：

    $$\min_x \frac{f_0(x)}{g_0(x)} \text{ s.t. } f_i(x) \leq 0$$

    其中 $g_0(x) > 0$。

    可以通过变量替换 $y = x/g_0(x), t = 1/g_0(x)$ 转化为等价的凸问题（如果 $f_0, g_0$ 满足某些条件）。

12. 对偶问题的计算

    计算对偶问题的步骤：

    • 写出拉格朗日函数
    • 求对偶函数（可能需要求解一个优化子问题）
    • 确定对偶函数的定义域
    • 写出对偶问题（最大化对偶函数，约束为对偶可行性）

    注意：对偶函数的计算可能很困难，特别是当需要求解非平凡的优化子问题时。

13. 对偶问题的优势

    • 对偶问题总是凸优化问题（即使原问题不是凸的）
    • 对偶问题的变量维度通常小于原问题
    • 对偶问题可以提供原问题最优值的下界
    • 对偶问题在算法设计中非常有用

14. 问题变形总结

    常见的问题变形包括：

    • 引入松弛变量
    • 消除等式约束
    • 上境图形式
    • 最小化最大值/上确界
    • 变量替换

    这些变形可以简化问题或使其更适合某些算法，但需要确保变形后的对偶与原问题的对偶一致或等价。