拉格朗日对偶性在数学优化中扮演着非常重要的角色，本章介绍从优化问题到构造拉格朗日函数，以及其对偶函数的定义，让后分析了其弱对偶性和强对偶性的 Slater 条件，最后着重介绍了 KKT 最优性条件。
拉格朗日对偶函数
问题引入
首先，考虑标准形式的凸最优化问题：
$$ \begin{align}
minimize \quad & f_0(x) \\\
subject to \quad & f_i(x)\le0, \quad i=1,\cdots,m \\\
& h_i(x)=0, \quad i=1,\cdots,p
\end{align} $$
其变量$x\in\mathcal{R}^n$,并且其定义域$\mathcal{D}=\bigcap^m_{i=0}\mathrm{dom} f_i\cap\bigcap^p_{i=1}\mathrm{dom} h_i$是非空的。则其拉格朗日函数为：
$$
L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^m\lambda_i f_i(x)+\sum_{i=1}^p\nu_ih_i(x)
$$
其中$ \lambda_i $被称为与$ f_i(x)\le 0 $相关的拉格朗日乘子，$\nu_i $被称为与$ h_i(x)=0 $相关的拉格朗日乘子，向量$\lambda$和$\nu$被称为对偶变量或拉格朗日乘子向量。
函数定义
有了拉格朗日函数，下面我们定义拉格朗日对偶函数：
$$
g(\lambda,\nu)=\inf_{x\in\mathcal{D}}L(x,\lambda,\nu)=\inf_{x\in\mathcal{D}}\Big(f_0(x)+\sum\limits_{i=1}^m\lambda_i f_i(x)+\sum\limits_{i=1}^p\nu_ih_i(x)\Big)
$$
下面介绍拉格朗日对偶函数的一个重要性质：
拉格朗日对偶函数构成了原凸最优化问题最优值$p^*$的下界，也即：对任意的$\lambda\ge0$和$\nu$，我们有：
$$ g(\lambda,\nu)\le p^* $$
但是当$g(\lambda,\nu)=-\infty$是其意义不大。只有当$\lambda\ge0$且$(\lambda,\nu)\in \mathrm{dom} g$即$g(\lambda,\nu)>-\infty$时，对偶函数才能给出$p^*$的一个非平凡下界，我们称满足$\lambda\ge0$以及$(\lambda,\nu)\in \mathrm{dom} g$的$(\lambda,\nu)$是对偶可行的。
拉格朗日对偶问题
接下来我们思考：从Lagrange函数能够得到的最好下界是什么？也即：
$$ \begin{align}
maximize\quad & g(\lambda,\nu)\\\
subject to\quad & \lambda\ge0
\end{align}$$
上述问题被称为Lagrange对偶问题。前面描述的对偶可行的一组$(\lambda,\nu)$就是对偶问题的一个可行解。如果解$(\lambda^*,\nu^*)$是对偶问题的最优解，则称解$(\lambda^*,\nu^*)$是对偶最优解或者是最优Lagrange乘子
Lagrange对偶问题是一个凸优化问题，因为极大化的目标函数是凹函数，且约束集合是凸集。因此，对偶问题的凸性和原问题是否是凸优化问题无关。
弱对偶性
用$d^*$表示Lagrange对偶问题的最优值，由上面的性质可得下面的不等式：
$$ d^*\le p^* $$
即使原问题不是凸问题上述不等式也成立，这个性质称为弱对偶性。
定义差值$p^*-d^*$是原问题的最优对偶间隙。它给出了原问题最优值以及通过Lagrange对偶函数所能得到的最好（最大）下界之间的差值。最优对偶间隙总是非负的。
但原问题很难求解时，弱对偶不等式可以给出原问题最优值的一个下界，这是因为对偶问题总是凸问题，而且在很多情况下都可以进行有效的求解得到$d^*$。
强对偶性和Slater约束准则
如果：$$d^*=p^*$$ 成立，即最优对偶间隙为零，那么强对偶性成立。
如果原问题是凸问题，可以表述为：
$$ \begin{align}
minimize\quad & f_0(x) \\\
subject to\quad & f_i(x)\le0, \quad i=1,\cdots,m\\\
& Ax=b,
\end{align}$$
使得强对偶性成立的一个简单的约束准则是Slater条件：存在一点$x\in \mathrm{relint} \mathcal{D} $ 使得下式成立：
$$ f_i(x) < 0, \quad i=1,\cdots,m \quad Ax=b.$$ 满足上述条件称为严格可行，这是因为不等式约束严格成立。
若不等式约束函数$ f_i $中有一些是仿射函数时，Slater条件可以进一步改进。如果最前面的$ k $个约束函数$ f_1,\cdots,f_k $是仿射的，则若下列弱化条件成立，强对偶性成立。该条件为：存在一点$ x\in\mathrm{relint} \mathcal{D} $使得：
$$f_i(x)\le0,\quad i=1,\cdots,k,\qquad f_i(x) < 0 \quad i=k+1,\cdots,m,\qquad Ax=b$$
也就是说，仿射不等式不需要严格成立。
若Slater条件满足，不但对于凸问题强对偶性成立，也意味着当$ d^*>-\infty $时对偶问题能够取得最优值，即存在一组对偶可行解$(\lambda^*,\nu^*)$，使得$ g(\lambda^*,\nu^*)=d^*=p^*$。
最优性条件
终止准则
定义原问题和对偶问题目标函数的差值$$f_0(x)-g(\lambda,\nu)$$ 为原问题可行解$ x $和对偶可行解$ (\lambda,\nu) $之间的对偶间隙。一对原对偶问题的可行点$ x,(\lambda,\nu) $将原问题（对偶问题）的最优值限制在一个区间上：$$p^*\in[g(\lambda,\nu),f_0(x)],\qquad d^*\in[g(\lambda,\nu),f_0(x)],$$ 区间的长度即为上面定义的对偶间隙。
上述现象可以用在优化算法中给出非启发式停止准则。某个算法给出一系列原问题可行解$ x^{(k)} $以及对偶问题可行解$ (\lambda,\nu), k=1,2,\cdots, $给定要求的绝对精度$ \epsilon_{abs}>0, $那么停止准则是：$$f_0(x^{(k)})-g(\lambda^{(k)},\nu^{(k)})\le\epsilon_{abs}$$ 保证当算法终止的时候，$x^ {(k)} $是$ \epsilon_{abs}$-次优。（当然，只有在强对偶性成立的条件下，此方法对任意小的$ \epsilon_{abs}$才都可行）
互补松弛性
设原问题和对偶问题的最优值都可以达到且相等（即强对偶性成立）。令$ x^* $是原问题的最优解，$(\lambda^*,\nu^*) $是对偶问题的最优解，这表明：
$$\begin{align}f_0(x^*) &= g(\lambda^*,\nu^*) \\\
&=\inf_x\Big(f_0(x)+\sum_{i=1}^m\lambda_i^* f_i(x)+\sum_{i=1}^p\nu_i^*h_i(x)\Big)\\\
&\le f_0(x^*)+\sum_{i=1}^m\lambda_i^* f_i(x^*)+\sum_{i=1}^p\nu_i^*h_i(x^*)\\\
&\le f_0(x^*)\end{align}$$
由上面的推导可以得出一个重要的结论：
$$ \sum_{i=1}^m\lambda_i^* f_i(x^*)=0 $$
实际上，求和项的每一项都非正，因此有：
$$\lambda^*f_i(x^*)=0,\quad i=1,\cdots,m.$$
上述条件称为互补松弛性，它对任意原问题最优解$ x^* $都成立（当强对偶性成立时）。我们可以将互补松弛条件写成：
$$ \begin{align}
\lambda^* > 0 & \Longrightarrow f_i(x^*) = 0 \\\
f_i(x^*) < 0 & \Longrightarrow \lambda_i^* = 0
\end{align} $$
上式意味着在最优点处，除了第$ i $个约束起了作用的情况，最优Lagrange乘子的第$ i $项都为零。
KKT 最优条件
现在假设函数$ f_0,\cdots,f_m,h_1,\cdots,h_p $可微（定义域开集），但是并不假设这些函数是凸函数。
非凸问题的 KKT 条
和前面一样，令$ x^* $是原问题的最优解，$(\lambda^*,\nu^*) $是对偶问题的最优解，对偶间隙为零。因为$ L(x,\lambda^*,\nu^*) $关于$ x $求极小在$ x^* $处取得最小值，因此函数在$ x $处的导数必须为零，即：
$$
\nabla f_0(x^*)+\sum_{i=1}^m\lambda_i^*\nabla f_i(x)+\sum_{i=1}^p\nu_i^*\nabla h_i(x)=0
$$
因此我们有：
$$\begin{align}
f_i(x^*) &\le0,\quad i=1,\cdots,m \\\
h_i(x^*) &= 0,\quad i=1,\cdots,p \\\
\lambda_i^* &\ge0,\quad i=0,\cdots,m \\\
\lambda_i^*f_i(x^*) &= 0,\quad i=0,\cdots,m \\\
\nabla f_0(x^*)+\sum_{i=1}^m\lambda_i^*\nabla f_i(x)+\sum_{i=1}^p\nu_i^*\nabla h_i(x) &= 0
\end{align}$$
我们称上式为Karush-Kuhn-Tucker（KKT）条件。
总之，对于目标函数和约束函数可微的任意优化问题，如何强对偶性成立，那么任何一对原问题最优解和对偶问题最优解必须满足 KKT 条件。
凸问题的 KKT 条件
当原问题是凸问题时，满足 KKT 条件的点也是原、对偶最优解。也就是说，如何函数$ f_i $是凸函数，$h_i $是仿射函数，$\widetilde{x},\widetilde{\lambda},\widetilde{\nu} $是任意满足 KKT 条件的点，也即：
$$\begin{align}
f_i(\widetilde{x}) &\le 0,\quad i=1,\cdots,m \\\
h_i(\widetilde{x}) &= 0,\quad i=1,\cdots,p \\\
\widetilde{\lambda_i} &\ge 0,\quad i=1,\cdots,m \\\
\widetilde{\lambda_i}f_i(\widetilde{x}) &=0,\quad i=1,\cdots, m \\\
\nabla f_0(\widetilde{x})+\sum_{i=1}^m\widetilde{\lambda_i}\nabla f_i(\widetilde{x})+\sum_{i=1}^p\widetilde{\nu_i}\nabla h_i(\widetilde{x}) &= 0
\end{align} $$
那么$ \widetilde{x} $和$ (\widetilde{\lambda},\widetilde{\nu}) $分别是原问题和对偶问题的最优解，对偶间隙为零。
总之，对目标函数和约束函数可微的任意凸优化问题，任意满足 KKT 条件的点分别是原、对偶问题最优解，对偶间隙为零。
若某个凸优化问题具有可微的目标函数和约束函数，且满足 Slater 条件，那么KKT条件是最优性的充要条件： Slater 条件意味着最优对偶间隙为零且对偶最优解可以达到，因此$ x $是原问题的最优解，当且仅当存在$ (\lambda,\nu) $，二者都满足 KKT 条件。
KKT 条件在优化领域有着重要的作用。在一些特殊的情形下，是可以解析求解 KKT 条件的。更一般的，很多求解凸优化问题的方法可以认为或者理解为求解 KKT 条件的方法。