凸优化学习笔记：Duality 对偶问题

2024年07月29日 1.5k 字大概 8 分钟

拉格朗日对偶函数

\begin{align}minimize\ &f_0(x)\\ subject\ to\ &f_i(x)\le 0,i=1,...,m\\ &h_i(x)=0,i=1,...,p\end{align}

假设最优值为 $p^*$
Lagrangian duality是将约束通过加权合并到目标函数中， $L:R^n\times R^m\times R^p\to R$ 。

L(x,\lambda,\nu)=f_0(x)+\Sigma_{i=1}^m\lambda_if_i(x)+\Sigma_{i=1}^p\nu_ih_i(x)

其中 $\lambda_i,\nu_i$ 为拉格朗日乘数。
拉格朗日对偶函数为

g(\lambda,\nu)=inf\ L(x,\lambda,\nu)=inf\ (f_0(x)+\Sigma_{i=1}^m\lambda_if_i(x)+\Sigma_{i=1}^p\nu_ih_i(x))

是凹的，与原问题的凹凸性无关。

最优值的下界

假设在 $x^*$ 处取的最优值 $f_0(x)=p^*$ ，此时由于 $\lambda\succeq 0$ ，

\Sigma_{i=1}^m\lambda_if_i(x)

小于0，虽然

\nu

的符号不确定，但是

h_i=0

，因此有

L(x,\lambda,\nu)=f_0(x)+\Sigma_{i=1}^m\lambda_if_i(x)+\Sigma_{i=1}^p\nu_ih_i(x)\le f_0(x)

g(\lambda,\nu)\le L(x,\lambda,\nu)\le f_0(x)

该式对任意x成立，因此有 $g(\lambda,\nu)\le p^*$
g能给出下界。

拉格朗日对偶问题

对任意对 $(\lambda,\nu)$ ，拉格朗日对偶函数都能给出一个最优值的下界。但最优的下界是什么？

\begin{align} maximize\ &g(\lambda,\nu)\\ subject\ to\ &\lambda\succeq0 \end{align}

该问题称为原问题的拉格朗日对偶问题。原问题则称为primal problem。
dual feasible意为 $\lambda\succeq 0,g(\lambda,\nu)>-\infty$
该问题的最优解 $\lambda^*,\nu^*$ 被称为dual optimal或optimal Lagrange multipliers。该问题是凸问题，与原问题的凹凸性无关。

p^*-d^*

被称为duality gap

例：QCQP的拉格朗日对偶

\begin{align}minimize\ &(1/2)x^TP_0x+q_0^Tx+r_0\\ subject\ to\ &(1/2)x^TP_ix+q_i^Tx+r_i\le0,i=1,...,m \\&P_0\in S_{++}^n, P_i\in S_{+}^n \end{align}

其拉格朗日函数为

\begin{align}L(x,\lambda)= &(1/2)x^TP_0x+q_0^Tx+r_0+\Sigma_{i=1}^m(\lambda_i/2)x^TP_ix+\lambda_iq_i^Tx+\lambda_ir_i\\ =&(1/2)x^TP(\lambda)x+q(\lambda)^Tx+r(\lambda)\\ P(\lambda)=&P_0+\Sigma_{i=1}^m\lambda_iP_i,\\ q(\lambda)=&q_0+\Sigma_{i=1}^m\lambda_iq_i,\\ r(\lambda)=&r_0+\Sigma_{i=1}^m\lambda_ir_i. \end{align}

其取最值处应有

\begin{align}\nabla L=&0\\ =&P(\lambda)x+q(\lambda)^T\\ x =& -P^{-1}(\lambda)q(\lambda)^T \\ L(-P^{-1}(\lambda)q(\lambda)^T,\lambda)=& -(1/2)q(\lambda)^TP(\lambda)^{-1}q(\lambda)+r(\lambda) \end{align}

\begin{align}g(\lambda)=&{\inf}\ L(x,\lambda)\\ =&-(1/2)q(\lambda)^TP(\lambda)^{-1}q(\lambda)+r(\lambda) \end{align}

KKT优化条件

假定函数 $f_0,...,f_m,h_1,...,h_p$ 可微。
假设 $x^*$ 和 $(\lambda^*,\nu^*)$ 分别是primal和对偶问题的最优解，且duality gap为0

由于 $x^*$ 为 $L(x,\lambda^*,\nu^*)$ 的极值点，该处梯度应为0。

\nabla f_0(x^*)+\Sigma_{i=1}^m\lambda_i^*\nabla f_i(x^*)+\Sigma_{i=1}^pv_i^*\nabla h_i(x^*)=0

Karush-Kuhn-Tucker（KKT）条件即为

\begin{align} f_i(x^*)\le 0\\ h_i(x^*)=0\\ \lambda_i^*\ge 0\\ \lambda_i^*f_i(x^*)=0\\ \nabla f_0(x^*)+\Sigma_{i=1}^m\lambda_i^*\nabla f_i(x^*)+\Sigma_{i=1}^pv_i^*\nabla h_i(x^*)=0 \end{align}

在凸优化中，如果原问题和对偶问题都具有凸形式，那么它们的最优值是相等的。这意味着原问题的最优解和对偶问题的最优解是一致的。
在任何满足以下条件的凸优化问题中：

目标函数和约束函数都是可微的。
强对偶性成立，即原问题和对偶问题的最优值相等。

对于这样的问题，原问题的最优解和对偶问题的最优解必须满足KKT条件。这意味着，如果一个点是原问题的最优解，那么它必须满足KKT条件；同样，如果一个点是对偶问题的最优解，它也必须满足KKT条件。

简而言之，KKT条件是强对偶性成立的一个必要条件。

其他参考资料

一个非常好的KKT解读