知识点：对偶理论

提供下界: 对偶问题的解可以为原始问题的解提供一个质量保证。
算法设计: 许多算法（如对偶上升法、ADMM）通过求解对偶问题或同时求解原问题和对偶问题来解决原始问题。
简化问题: 有时对偶问题比原始问题更容易求解。

知识点概述

对偶理论是优化理论的支柱之一。它为每个优化问题（称为原始问题）关联一个对偶问题。对偶问题的最优值给出了原始问题最优值的一个下界（弱对偶性），在凸优化中，这个界通常是紧的（强对偶性），这为求解和分析问题提供了强大的工具。

拉格朗日函数: 对于一个约束问题 $min f (x)$ s.t. $c_{i} (x) \leq 0, h_{j} (x) = 0$ ，其拉格朗日函数为 $L (x, λ, ν) = f (x) + \sum λ_{i} c_{i} (x) + \sum ν_{j} h_{j} (x)$ ，其中 $λ_{i} \geq 0, ν_{j}$ 是拉格朗日乘子。
对偶函数: 对偶函数 $g (λ, ν)$ 定义为拉格朗日函数关于 $x$ 的最小值： $g (λ, ν) = in f_{x} L (x, λ, ν)$ 。无论原始问题是否为凸，对偶函数总是一个凹函数。
对偶问题: 对偶问题就是最大化对偶函数： $max_{λ \geq 0, ν} g (λ, ν)$ 。
弱对偶性: 对偶问题的最优值 $d^{*}$ 总是小于或等于原始问题的最优值 $p^{*}$ ，即 $d^{*} \leq p^{*}$ 。这个性质永远成立。
强对偶性: 当 $d^{*} = p^{*}$ 时，称强对偶性成立。此时，原始问题和对偶问题的解可以通过KKT条件关联起来。
Slater条件: 对于凸优化问题，如果存在一个严格满足所有不等式约束的可行点，那么强对偶性成立。这是保证强对偶性最常用的条件。