优化中的对偶性理论

在优化问题中，对偶是一种重要的概念。对偶问题是原问题的等价形式，通过将原问题转化为对偶问题，我们可以更好地了解原问题的性质，从而更好地解决它。

首先介绍拉格朗日函数。在优化问题中，该函数是一种特殊的函数形式，用于将带有约束条件的优化问题转化为不带约束条件的优化问题。具体而言，对于一个带有约束条件的优化问题：

\begin{aligned} \min_{x} \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq 0, \quad i=1,2,\ldots,m \\ & h_j(x) = 0, \quad j=1,2,\ldots,p \end{aligned} \tag1其中， f(x) 是定义域为 D 目标函数， g_i(x) \leq 0 和 h_j(x) = 0 是约束条件。为了将这个问题转化为不带约束条件的问题，可以定义拉格朗日函数：

L(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^n \mu_j h_j(x) \tag2

其中， \lambda_i 是与不等式相关的拉格朗日乘子， \mu_j 是与等式相关拉格朗日乘子，用于将约束条件引入到目标函数中。

然后，可以定义拉格朗日对偶函数：

g(\lambda, \mu) = \inf_{x} L(x, \lambda, \mu) \tag3该函数的值表示在给定拉格朗日乘子 \lambda 和 \mu 的情况下，通过遍历 x ，找到拉个朗日函数 L(x, \lambda, \mu) 的下界。

拉格朗日对偶函数具有以下性质：

性质(1) -- 拉格朗日对偶函数一定是凹的。

性质(2) -- \forall \lambda \ge 0, \forall \mu ，有 g(\lambda,\mu) \le p^* ， p^* 是原问题的最优解， g(\lambda,v) 是对偶函数的函数值，对偶函数构成了原问题最优解的下界。

最后，定义拉格朗日对偶问题，形式如下：

\begin{aligned} \text{max} \quad & g(\lambda, \mu) \\ \text{s.t.} \quad & \lambda_i \geq 0, \quad i = 1, 2, \ldots, m \end{aligned} \tag4

对该问题的求解，可以得到Dual问题的对偶最优解或者说最优的拉格朗日乘子 (\lambda^*, \mu^*) 。以上形式可以看出拉格朗日对偶问题是一个凸问题，因为更具前述的性质(2)，极大化的 g(\lambda,v) 是一个凹函数，因此这个问题实际上是凸的。

总结，通过上述方式将问题进行等价变换然后求解的过程被称为拉格朗日对偶性。

例1：举一个二次规划问题，显然这是一个凸问题。 \begin{aligned} \min_{x} \quad & x^Tx \\ \text{s.t.} \quad & Ax=b \quad \end{aligned} \tag5

例2：举一个带整数约束的二次规划问题，这是一个非凸问题。

\begin{aligned} \min_{x} \quad & x^Twx \\ \text{s.t.} \quad & x_i=\{-1,+1\} \quad \end{aligned} \tag 6

该问题完全是一个非凸问题，约束为二进制约束。首先我们把其约束做一个等价变换 x_i^2-1=0 。

首先定义对偶间隙是指原问题的目标函数最优值 $p^$ 与对偶问题目标函数的最优值 $d^$ 之间的差距，即 $p^-d^$。

定义强对偶： d^* = p^*，即对偶间隙为0 。

定义弱对偶： d^* \le p^*，即存在一定的对偶间隙。

由对偶函数的性质（1）可以看出，任何一个对偶函数都是弱对偶函数，那什么条件下满足强对偶？

Slater's Condition（是一个充分条件）：对于一个标准形式的凸问题，定义域为 D ，当 \exists x \in RelintD ，使 f_i(x)f_i(x)>0 ，使得 \lambda_j=0,j\not = i ，以及让 \lambda_i 趋于无穷大，则 \sum_{i=1}^m \lambda_i f_i(x) 会无穷大，得出 \underset{\lambda \ge 0}{\text{sup}}\, L(x, \lambda, \mu)=\infty 。② 反过来，如果x可行，则有 f_i(x)\le0,i=1,...,m ， \lambda 的最优选择为 \lambda=0 ，同时 h_i(x)\not=0 ，因此得到 underset{\lambda \ge 0}{\text{sup}}\, L(x, \lambda, \mu)= f_0(x) 。 在上面分析中，等式约束和等式约束的对偶变量实际没有起任何作用，因此上式可简化为： \begin{aligned} \underset{\lambda \ge 0}{\text{sup}} \, L(x, \lambda) =& \underset{\lambda \ge 0}{\text{sup}} \,(f(x) + \sum_{i=1}^m \lambda_i f_i(x)) \\=&\begin{cases} f_0(x), & \text{if $f_i(x)\le0,i=1,...,m$} \\ \infty, & \text{ otherwise} \\ \end{cases} \end{aligned}

鞍点定理：若 (x^*,\lambda^*) 为 L(x,\lambda) 的鞍点 \Leftrightarrow 该问题强对偶存在，且 (x^*,\lambda^*) 为Primal与Dual的最优解。

待述

Karush-Kuhn-Tucker（KKT）条件：若点 (\tilde{x},\tilde{\lambda}) 满足以下条件：

（1）原问题可行性（Primal Feasibility Condition） f_i(x) \le 0 ， g_i(x)=0 。

（2）对偶可行性 （Dual Feasibility Condition） \lambda_i \ge 0,\,i=1,...,m

（3）互补松弛条件（Complementary Slackness Condition） \lambda_i^*f_i(x^*)=0 ， i=1,…,m。

（4）稳定性或梯度条件（Stationary Condition） \nabla f(x^\star) + \sum_{i=1}^m \lambda_i^* \nabla g_i(x^\star) + \sum_{j=1}^n \mu_j^* \nabla h_j(x^\star) = 0

则该点是满足该问题局部最优解的一个必要条件。

性质(3) -- 若原问题是凸问题，各个函数可微，对偶间隙为零，则KKT条件为一个充要条件。

证明：必要性在推到KKT条件时已经证明，充分性证明如下：已知有一个凸问题，存在点 (\tilde{x},\tilde{\lambda}) 满足KKT条件。证明思路：若要证明 (\tilde{x},\tilde{\lambda},\tilde{v}) 为原问题和对偶问题的最优解，则只要证明 g(\tilde{\lambda},\tilde{v}) = f_0(\tilde{x})，原因为如果左边取极大，右边取极小，则该点就变成了一个鞍点，利用鞍点定理可推得 (x^*,\lambda^*) 为Primal与Dual的最优解。

对于一般的优化问题（不一定凸），若拉格朗日函数有鞍点 此点Primal和Dual都是最优点，对偶间隙为零。

例1：举一个只带等式约束得二次规划问题： \begin{aligned} \min_{x} \quad & \frac{1}{2}x^TPx+qx+r \\ \text{s.t.} &\ Ax=b \end{aligned} \tag0

写出KKT条件：

Ax^=b, \nabla f(x^\star)=0\Leftrightarrow \begin{cases} px+q+A^Tv=0 & \\ Ax^ =0& \\ \end{cases} \tag 0

把上式写成矩阵形式：

\begin{bmatrix} p & A^T \\ A & 0 \\ \end{bmatrix} \begin{bmatrix} x^* \\ v^* \end{bmatrix}=\begin{bmatrix} -q \\ b \end{bmatrix} \tag 0 求原问题的最优解转换成了求一个线性方程组，不仅能得到Prime的最优解，同时得到对偶问题的最优解。