拉格朗日对偶性

在求解约束最优化问题中，可以利用拉格朗日对偶性将原始问题转化为对偶问题来解决。

对于原始问题： f(x),ci(x),hj(x)f(x), c_i(x), h_j(x) 是定义在 Rn\textbf{R}^n 上的连续可微函数。考虑最优化问题

min⁡x∈Rnf(x)s.t.ci(x)≤0,i=1,2,⋯ ,khj(x)=0j=1,2,3,⋯ ,l\begin{align*} \min_{x \in \textbf{R}^n} \quad& f(x) \\ s.t. \quad & c_i(x) \leq 0, \quad i = 1, 2, \cdots,k \\ & h_j(x) = 0 \quad j = 1, 2, 3, \cdots, l \end{align*}

这个就是最优化的原始问题，为了解决这个问题，我们引入拉格朗日函数：

L(x,α,β)=f(x)+∑i=1kαici(x)+∑j=1lβjhj(x)L(x, \alpha, \beta) = f(x) + \sum_{i = 1}^k \alpha_ic_i(x) + \sum_{j = 1}^l\beta_jh_j(x)

其中 αi≥0\alpha_i \geq 0

考虑关于 xx 的函数 θP(x)=max⁡α,β:αi≥0L(x,α,β)\theta_P(x) = \max_{\alpha, \beta: \alpha_i\geq 0} L(x, \alpha, \beta)

对于不符合不等式约束的 xx ，取对应的 αi→+∞\alpha_i \to +\infty 那么 θP\theta_P的取值就趋于 +∞+\infty。同样的，对于不满足等式约束的 xx 可以通过对应的 βj\beta_j 的取值，使 θP\theta_P 的取值趋于 +∞+\infty。

因此可以得到：

θP(x)={f(x)x满足约束条件+∞else\theta_P(x) = \begin{cases} f(x) \quad x 满足约束条件\\ +\infty \quad \text{else} \end{cases}

因此原始问题与 min⁡xθP(x)\min_x \theta_P(x) 是等价的

对偶问题

定义：

θD(α,β)=min⁡xL(x,α,β)\theta_D(\alpha, \beta) = \min_x L(x, \alpha, \beta)

L(x,α,β)L(x, \alpha, \beta) 关于 α\alpha 或 β\beta是一个仿射函数，而 L(x,α,β)L(x, \alpha, \beta) 就可以看作一个函数集，而仿射函数集的下确界就是一个凹函数，

问题：

max⁡θD(α,β)s.t.αi≥0\begin{align*} \max \quad &\theta_D(\alpha, \beta)\\ s.t. \quad &\alpha_i \geq0 \end{align*}

称之为原始问题的对偶问题，实际上可以转化为一个凸优化问题

对偶问题解的联系

定义原始问题与对偶问题的最优值

p∗=min⁡xθP(x),d∗=max⁡α,β:αi≥0θD(α,β)p^* = \min_x\theta_P(x), d^* = \max_{\alpha, \beta: \alpha_i \geq0}\theta_D(\alpha, \beta)

弱对偶性：当二者都存在时 d∗≤p∗d^* \leq p^*

强对偶性：若 x∗,α∗,β∗x^{*}, \alpha^{*}, \beta^{*} 分别是原始问题与对偶问题的可行解且 p∗=d∗p^{*} = d^{*}时， 那么我们的得到的结果就是最优解

定理：若 f(x)f(x) 与 ci(x)c_i(x) 均为凸函数，且 hj(x)h_j(x) 均为仿射函数（即线性的等式约束），那么对偶问题与原始问题的最优值是一致的，并且最优解是等价的。

KKT条件：若 f(x)f(x) 与 ci(x)c_i(x) 均为凸函数，且 hj(x)h_j(x) 均为仿射函数（即线性的等式约束），那么 x∗,α∗,β∗x^{*}, \alpha^{*}, \beta^{*} 分别是原始问题与对偶问题最优解的充分必要条件是：

∇xL(x∗,α∗,β∗)=0αi∗ci(x∗)=0ci(x∗)≤0αi∗≥0hj(x∗)=0\begin{align*} \nabla_x L(x^{*}, \alpha^{*}, \beta^{*}) = 0\\ \alpha_i^{*}c_i(x^{*}) = 0\\ c_i(x^{*}) \leq0\\ \alpha_i^{*} \geq0\\ h_j(x^{*}) = 0 \end{align*}