凸优化学习笔记：Duality 对偶问题
拉格朗日对偶函数
$$\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条件是强对偶性成立的一个必要条件。