拉格朗日对偶与KKT条件

优化问题

\[ \begin{align} \text{minimize }& f_0(x) \\ \text{subject to }&f_i(x) \le 0, i=1:m\\ & h_i(x) = 0, i=1:p \end{align}\\ D_{f} = \bigcap_{i=0}^m\text{dom}f_i\cap \bigcap_{i=0}^m\text{dom}h_i \]

拉格朗日表达式

\[ L(x, \lambda, v) = f_0(x) + \sum_{i=1}^m\lambda_if_i(x) + \sum_{i=1}^pv_ih(i)\\ \text{dom }L = D \times R^m \times R^p\\ \]

\[ \begin{align} \text{For any } &\lambda\succeq 0,\forall \tilde x \in D\\ L(\tilde x, \lambda, v) &= f_0(\tilde x) + \sum_{i=1}^m\lambda_if_i(\tilde x) + \sum_{i=1}^pv_ih_i(\tilde x)\\ &\le f_0(\tilde x) \end{align} \]

对偶方程

\[ \begin{align} g(\lambda, v)& = \inf_{x\in D} L(x, \lambda, v) \\ &= \inf_{x\in D}[f_0(x)+\sum_i\lambda_if_i(x)+\sum_iv_ih_i(x))] \end{align} \]

\(g(\lambda, v)\)是concave的，假设原来优化问题的最优值为 \(p^*\)，则对于任意\(\lambda \succeq 0, g(\lambda, v) \le p^*\)

那么对偶问题描述为 \[ \text{maximize } g(\lambda, v)\\ \text{subject to } \lambda \ge 0 \] 假设对偶问题的最优值为\(d^*\)，那么弱对偶条件\(d^* \le p^*\)总是成立，无论原优化问题是否为凸 而当原问题是凸时，一般情况下强对偶条件\(d^* = p^*\) 成立 也就是对偶问题至少可以求得原问题的一个下界，而这个 \(\text{gap} = p^* - d^*\) 当问题是凸时为0，即凸问题的解与对偶问题的解相同

KKT 条件

记\(x^*, (\lambda^*, v^*)\) 为各自问题的最优点，在强对偶条件成立（不论原问题是否为凸）的情况下

KKT条件成立（必要条件） \[ f_i(x^*) \le 0, i=1:m\\ h_i(x^*) = 0, i=1:p\\ \lambda_i^* \ge 0, i=1:m\\ \lambda^*_if_i(x^*) = 0, i=1:m\\ \nabla f_0(x^*)+\sum_{i=1}^{m}\lambda^*_i\nabla f_i(x^*)+\sum_{i=1}^pv^*_i\nabla h_i(x^*)=\mathbf{0} \] 即\(f_0\)的梯度是\(f_i和h_i\)的线性组合

\(F(x)\)表示点\(x\)的所有可行方向的集合，\(x\)的可行方向是指\(x\)加上一个高阶小量仍然在可行域\(D_f\) 中

对于函数\(f\)在\(x\)点的梯度方向可以将空间分成三部分，梯度分量为正的\(N_f^+\)，梯度分量为负的\(N_f^-\)，梯度分量为0的\(T_f\)

各个约束的可行方向总结如下

\(x^*\)是极值点，让目标函数减小的方向不能在\(F(x^*)\) 中，因此\(-\nabla f(x^*) \bot F(x^*)\)

\[ F(x^*) = \left( \cap_iT_{h_i} \right)\cap\left( \cap_i (T_{f_i} \cup N_{f_i}^-) \right)\cap\left( \cap_k R^n \right)\\ -\nabla f \subset R^n-F(x^*)=\left( \cup_i N_{h_i} \right)\cup\left( \cup_i N_{f_i}^+ \right) \] 上式即证明了\(f_0\)的梯度是\(f_i和h_i\)的线性组合

参考资料

zhihu: 非线性优化中的KKT条件该如何理解？

Convex Optimization Boyd.