拉格朗日乘子与KTT条件
用简易的语言介绍两者的原理以及证明，本人非科班出身，有误请指正，联系方式：Zero@OSAI.Club
1.原始问题
假设\(f(x)\),\(c_i(x)\),\(h_j(x)\)是定义在\(R^n\)上的连续可微函数（为什么要求连续可微呢，后面再做解释），\(f(x)\)为我们优化的目标函数，\(c_i(x)\),\(h_j(x)\)，为约束条件。
\[\min_{x \in R^n }f(x) \\ s.t.c_i(x) \le 0,i = 1,2,...,k\\ h_j(x) = 0,j = 1,2,...,l\]称为约束最优化问题的原始问题。
先不考虑约束条件，原始问题就是： \(\min_{x \in R^n }f(x) \\\)
因为假设其连续可微，利用高中的知识，对\(f(x)\)求导数，然后令导数为0，即可解出。
但是在不考虑约束条件的情况下，然后事实并没有那么简单，考虑了约束条件后我们就感觉很难了（WFT？？！！）
这是时候就要引入我们的今天的主角拉格朗日乘子，一种神奇伟大的参数。
\(x = (x^{(1)},x^{(2)},...,x^{(n)})^T \in R^n\)，其中\(\alpha_i,\beta_j\)是拉格朗日乘子并且\(\alpha_i \ge 0\)
现在，如果把\(L(x,\alpha,\beta)\)看作是关于\((\alpha,_i\beta_j)\)的函数，求其最大值：
\(\max_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta)\) 也就是说，现在我们的目的就是去优化一个与\(\alpha_i(\alpha \ge 0),\beta_i\)变量有关的函数\(L(x,\alpha,\beta)\)（在这里我们把\(x\)作为常量）使其值最大。在我们确当了\(\alpha_i,\beta_j\)后，\(\max_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta)\)就是一个只跟\(x\)有关的函数了，我们定义函数：
\[\theta_p(x) = \max_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta)\]其中:
\[L(x,\alpha,\beta)=f(x)+\sum^k_{i =1}a_ic_i(x)+\sum^l_{j=1} \beta_jh_j(x)\]下面我们从是否满足约束条件来分析这个函数：
-
当不满足某个约束条件时，即\(c_i(x) > 0\)或者\(h_j(x) \ne 0\),那么
\(\theta_p(x) = \max_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta)=\max_{\alpha,\beta:\alpha_i \ge 0}( f(x)+\sum^k_{i =1}a_ic_i(x)+\sum^l_{j=1} \beta_jh_j(x) )= + \infty\) 分析：
1.若\(c_i(x) > 0，h_j(x) = 0\)，要使\(L(x,\alpha,\beta)\)最大，则\(\alpha_i \to +\infty\)
2·若\(c_i(x) \le 0，h_j(x) \ne 0\)，要使\(L(x,\alpha,\beta)\)最大，则取\(\beta_j\)使得\(\beta_jh_j(x) \to +\infty\)
综上两种情况\(\theta_p = + \infty\)。
-
当满足所有约束条件时，即\(c_i(x) \le 0, h_j(x) = 0\)
\(\theta_p(x) = \max_{\alpha,\beta:\alpha_i \ge 0} L(x,\alpha,\beta)= \max_{\alpha,\beta:\alpha_i \ge 0} f(x) = f(x)\) 分析：
1.\(c_i(x) \le 0\)并且\(\alpha_i \ge 0\),要使\(L(x,\alpha,\beta)\)最大，则\(\alpha_i = 0\)
2.\(h_j(x) = 0\)
综上两种情况\(\theta_p = \max_{\alpha,\beta:\alpha_i \ge 0} f(x) = f(x)\)。
因此，
\[\theta_p(x) =\begin{cases}+ \infty&\text 其他 \\f(x) &\text 满足约束条件 \end{cases}\]那么在满足约束条件的情况下：
即\(\min_{x}\theta_p(x)\)与原始优化问题等价，所以我们常用\(\min_{x}\theta_p(x)\)代表原始问题，下标\(p\)表示原始问题，定义原始问题的最优解：\(p ^* = \min\theta_p(x)\)
通过拉格朗日乘子重新定义一个无约束问题，这个无约束问题等价于原来的约束优化问题，从而将约束问题无约束化！
2.对偶问题
定义关于\(\alpha,\beta\)的函数：
\[\theta_D(\alpha,\beta) = \min_{x}L(x,\alpha,\beta)\]等式右边是关于\(x\)的函数的
最小化，\(x\)确定以后，最小值就只与\(\alpha,\beta\)有关，所以是一个关于\(\alpha,\beta\)的函数.
假设我们极大化\(\theta_D(\alpha,\beta) = \min_xL(x,\alpha,\beta)\),即：
\[\max_{\alpha,\beta:\alpha_i\ge0}\theta_D(\alpha,\beta) = \max_{\alpha,\beta:\alpha_i\ge0}\min_{x}L(x,\alpha,\beta)\]这样我们就得出了我们原始问题的对偶问题。
原始问题的表达式： \(\min_{x}\theta_p(x) = \min_x\max_{\alpha,\beta:\alpha_i \ge 0}L(x,\alpha,\beta)\)
我们可以看到我们的对偶问题与我们的原始问题在形式上是相互对称的，也就是说
对偶问题先固定的是\(L(x,\alpha,\beta)\)中的\(\alpha,\beta\),优化出最佳\(x\)，然后再确定\(\alpha,\beta\);而我们的原始问题刚好相反，是先固定\(L(x,\alpha,\beta)\)中的\(x\),优化出最佳的\(\alpha,\beta\)。
现在，定义对偶问题的最优解： \(d^* = \max_{\alpha,\beta:\alpha_i\ge0}\theta_D(\alpha,\beta)\)
3. 原始问题与对偶问题的关系
定理：若原始问题与对偶问题都有最优值，则 \(d^* =\max_{\alpha,\beta:\alpha_i\ge0}\min_{x}L(x,\alpha,\beta) \le \min_x\max_{\alpha,\beta:\alpha_i \ge 0}L(x,\alpha,\beta) = p^*\)
为什么会有这个不等式，现在我们一步一步来证明它。
证明：对任意的\(\alpha,\beta和x\),有
\[\theta_D(\alpha,\beta) = \min_xL(x,\alpha,\beta) \le L(x,\alpha,\beta) \le \min_{\alpha,\beta:\alpha_i \ge 0}L(x,\alpha,\beta) = \theta_P(x)\]即：
\[\theta_D(\alpha,\beta) \le \theta_P(x)\]由于原始问题与对偶问题都有最优值，所以 \(\max_{\alpha,\beta:\alpha_i \ge 0}\theta_D \le \min_x\theta_P(x)\)
即： \(d^* = \max_{\alpha,\beta:\alpha_i\ge0}\min_xL(x,\alpha,\beta) \le \min_x\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) =p^*\)
也就是说原始问题的最优值不小于对偶问题的最优值，但是我们要通过对偶问题来求解原始问题，就必须使得原始问题的最优值与对偶问题的最优值相等。
于是可以得出下面的推论：
推论：设\(x^*和\alpha^*,\beta^*\)分别是原始问题和对偶问题的可行解，如果\(p^*=d^*\)，那么\(x^*和\alpha^*,\beta^*\)分别是原始问题和对偶问题的最优解。但是到底满足什么样的条件才能使的\(p^*=d^*\)呢，这就是下面要阐述的 KKT 条件。
4. KKT 条件
定理：对于原始问题和对偶问题，假设\(f(x)\)函数和\(c_i(x)\)是凸函数，\(h_j(x)\)是仿射函数（即由一阶多项式构成的函数，\(f(x)=Ax + b\), \(A\)是矩阵，\(x，b\)是向量）；并且假设不等式约束\(c_i(x)\)是严格可行的，即存在\(x\)，对不等式\(c_i(x) < 0\)恒成立，则\(x^*\)和\(\alpha^*,\beta^*\)分别是原始问题和对偶问题的最优解的充分必要条件是\(x^*\)和\(\alpha^*,\beta^*\)
满足下面的Karush-Kuhn-Tucker(KKT)条件：
\[0 \in\partial f(x^*)+\sum^k_{i =1}a_i \partial c_i(x^*)+\sum^l_{j=1} \beta_j \partial h_j(x^*) \quad \Rightarrow \quad Stationarity\\ \alpha^*_i \cdot c_i(x^*) = 0,(i=1,2,...,k) \quad \Rightarrow \quad Complementary \,Slackness\\ c_i(x^*) \le 0,h_j(x^*) \ne0,(i=1,2,...,k;j=1,2,...,l)\quad \Rightarrow \quad Primal \,Feasibility\\ \alpha_i^* \ge0,(i=1,2,...,k)\quad \Rightarrow \quad Dual \,Feasibility\]综上所述，对于具有强对偶性的优化问题，且该优化问题存在至少一个可行解，那么下列问题等价:
\(x^{\star}, \alpha^{\star}和\beta^{\star}是原问题和对偶问题的最优解（solution）\Leftrightarrow x^{\star}, u^{\star}和v^{\star}满足KKT条件\)。
KKT条件证明
(1) 必要性（Necessity）：
如果\(x^{\star}, \alpha^{\star}和\beta^{\star}\)是原问题和对偶问题的最优解，且对偶问题保持强对偶性，即对偶间隙为0，那么:
\[\begin{equation} \begin{split} f(x^{\star}) & = g(\alpha^{\star}, \beta^{\star}) \\ & = \min \limits_{x} L(x,\alpha^{\star},\beta^{\star}) \\ & = \min_x f(x) + \sum_i^k \alpha^*_ic_i(x^*)+ \sum_j^l \beta^*_j h_j(x^*) \\ & \leq f(x) + \sum_i^k \alpha^*_ic_i(x^*)+ \sum_j^l \beta^*_j h_j(x)\\ & \leq f(x^{\star}) \end{split} \end{equation}\]第一个不等式成立的原因是，假设原问题可行解域为\(C\)，那么\(\min \limits_{x \in C} L(x,\alpha,\beta) = L(x^{\star},\alpha,\beta) \geq \min \limits_{x} L(x,\alpha,\beta)\)。
根据上面的推导，由于不等式前后均为\(f(x^*)\)，所有不等号实际上都是等号。
对于第一个不等式，等号成立代表\(x^*\)是\(\min_x f(x)+\sum^k_{i}\alpha^*_ic_i(x^*) + \sum^l_j\beta^*_jh_j(x^*)\)的最优解，因此，0必然是\(\min_x f(x)+\sum^k_{i}\alpha^*_ic_i(x) + \sum^l_j\beta^*_jh_j(x)\)的次梯度，既证stationarity条件。
对于第二个不等式，等号成立代表\(\alpha_i \cdot c_i(x^*) = 0\)，既证complementary slackness条件。
对于primal feasibility和dual feasibility，它们是原问题和对偶问题的约束，满足条件。
综上所述，KKT条件必要性证明完毕，如果\(x^*,\alpha^*\)和\(\beta^*\)是原问题和对偶问题的最优解（solution），同时对偶间隙为0，那么\(x^*,\alpha^*\)和\(\beta^*\)满足KKT条件。
（2）充分性（Sufficiency）：
如果存在\(x^*,\alpha^*\)和\(\beta^*\)满足KKT条件，那么：
\[\begin{equation} \begin{split} f(x^{\star}) & = g(\alpha^{\star}, \beta^{\star}) \\ & = \min \limits_{x} L(x,\alpha^{\star},\beta^{\star}) \\ & = \min_x f(x) + \sum_i^k \alpha^*_ic_i(x^*)+ \sum_j^l \beta^*_j h_j(x^*) \\ & = f(x) + \sum_i^k \alpha^*_ic_i(x^*)+ \sum_j^l \beta^*_j h_j(x)\\ & =f(x^{\star}) \end{split} \end{equation}\]第一和第二个等式是由定义获得，第三个等式是根据KKT条件中的stationarity条件，即0是函数\(L(x,\alpha,\beta)\)的次梯度，因此等式必然成立，最后等式是根据KKT条件中得slackness条件获得。因此\(g^{\star} = f^{\star}\)，，该解使得对偶间隙为0，分别为原问题和对偶问题的最优解。
综上所述，既证如果和满足KKT条件，那么和是原问题和对偶问题的solution。