对偶性 (最佳化)

在最优化理论中的对偶（duality）或对偶性原则（duality principle）是指最佳化问题可以用两种观点来看待的理论，两种观点分别是“原始问题”（primal problem）及“对偶问题”（dual problem）。对偶问题的解提供了原始问题（假设是最小化问题）的下限，不过一般而言，原始问题和对偶问题的最佳解不相同。两个最佳解的差距为对偶间隙。若是凸优化问题，对偶间隙也称为是卡鲁什-库恩-塔克条件。

## 对偶问题

一般而言“对偶问题”是指“拉格朗日对偶问题”（Lagrangian dual problem），不过也有其他的对偶问题，例如Wolfe对偶问题和Fenchel对偶定理。拉格朗日对偶问题是指在最小化问题上加上拉格朗日乘数，也就是在目标函数上加上对应限制条件的非负拉格朗日乘数，再求解可将原目标函数最小的原始变数值。此解会得到以拉格朗日乘数的函数表示的原始变数，称为是“对偶变数”（dual variables），因此，新的问题就是要衍生对偶变数的限制下（包括非负的限制条件），找到可以使目标函数最大化的对偶变数。

一般而言，给定二个对偶对的分隔局部凸空间 $\left(X,X^*\right)$及$\left(Y,Y^*\right)$，以及函数$f: X \to \mathbb{R} \cup \{+\infty\}$，可以定义原始问题为找到$\hat{x}$使得$f(\hat{x}) = \inf_{x \in X} f(x). \,$ 换句话说，若$\hat{x}$存在，$f(\hat{x})$是函数$f$的最小极值（minimum），也可以得到函数的最大下界（infimum）。

若有限制条件，可以整合到函数$f$中，方式是令$f = f + I_\text{constraints}$，其中$I_{\mathrm{constraints}}$是在$X$上的适当函数，在限制条件上有最小值0，可以证明$\inf_{x \in X} \tilde{f}(x) = \inf_{x \ \mathrm{constrained}} f(x)$。后者的条件很明显，但不一定很方便可以符合示性函数（也就是说，满足限制条件的$x$，$I_{\mathrm{constraints}}(x) = 0$，在其他情形，$I_{\mathrm{constraints}}(x) = \infty$）。因此可以将$\tilde{f}$延伸为扰动函数$F: X \times Y \to \mathbb{R} \cup \{+\infty\}$使得$F(x,0) = \tilde{f}(x)$。

对偶间隙就是不等式

$$\sup_{y^* \in Y^*} -F^*(0,y^*) \le \inf_{x \in X} F(x,0), \,$$

左侧和右侧的差。

其中$F^*$是二个变数的凸共轭，而$\sup$是上确界

## 线性规划

线性规划问题是指损失函数和约束都是线性关系的最优化问题。原始问题中，目标函数是n个变数的线性组合，问题有m个约束，每一个都有上限，上限由n个变数的线性组合表示。其目的是要在满足限制条件的情形下，最大化目标函数的值。其解是由n个值表示的向量，可以让目标函数有最大值。

在对偶问题中，目标函数是m个值的线性组合，这些是原始问题中m个限制条件的上下限。有n个对偶限制条件，每一个的下限都是由m个对偶变数的线性组合所表示。

### 原始问题和对偶问题的关系

针对线性的最佳化问题，在原始问题中每一个符合限制条件的次佳点，都有一个方向（或方向的子空间），可以往目标函数增加的方向移动。若往这类的方向移动，称为除去候选解和一个或多个限制之间的松弛量（slack）。候选解中不可行的值即为超过一个或多个限制的值。

在对偶问题中，会将对偶向量和限制条件相乘，这些限制条件会决定原始问题中限制条件的位置。在对偶问题中变动对偶向量类似在原始问题中调整上限。要找到最小的上限。也就是说，要将对偶向量最小化，以移除限制的候选位置和实际最佳解之间的松弛量（slack）。对偶向量中的不可行值是指哪些太低的值。这会让候选解的一个或多个限制条件落在排除实际最佳解的位置。

在线性规划中探讨对偶性的方程式中，会对上述直觉有型式化的叙述。

## 非线性规划

非线性规划中的限制条件不一定是线性的，不过许多线性规划的原则还是适用。

为了确保可以简单的识别非线性规划中的全域最大值，问题一般会要求函数要是凸函数，而且有紧致的lower level sets。

由此可以看出卡鲁什-库恩-塔克条件的重要性。卡鲁什-库恩-塔克条件可以提供非线性规划问题中识别局部最佳值的必要条件。也有一些额外的必要条件（约束规范，constraint qualifications）可以用来判断可能有“最佳解”（是局部最佳解，但不一定是全域最佳解）的方式。

### 强拉格朗日原则：拉格朗日对偶

考虑以下形式的非线性规划：

$$\begin{align} \text{minimize } &f_0(x) \\ \text{subject to } &f_i(x) \leq 0,\ i \in \left \{1,\ldots,m \right \} \\ <pre> &h_i(x) = 0,\ i \in \left \{1,\ldots,p \right \} </pre> \end{align}$$

其定义域$\mathcal{D} \subset \mathbb{R}^n$有非空的内部。其拉格朗日函数$\Lambda: \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}$定义为

$$\Lambda(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x).$$

向量$\lambda$和$\nu$是有关此问题的“对偶变数”（dual variables）或拉格朗日乘数向量（Lagrange multiplier vectors）。拉格朗日对偶函数（Lagrange dual function）$g:\mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}$定义如下

$$g(\lambda,\nu) = \inf_{x\in\mathcal{D}} \Lambda(x,\lambda,\nu) = \inf_{x\in\mathcal{D}} \left ( f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \right ).$$

对偶函数g是凹函数，就算初始问题不是凸也会如此，因为是仿射函数的点状最大下界。对偶函数提供初始问题最佳值$p^*$的下界：针对任意$\lambda \geq 0$及任意$\nu$，可以得到$g(\lambda,\nu) \leq p^*$。

若满足约束规范（例如斯莱特条件），且原问题是凸，则可以得到强对偶$d^* = \max_{\lambda \ge 0, \nu} g(\lambda,\nu) = \inf f_0 = p^*$。

### 凸问题

针对有不等式限制的凸最小化问题

$$\begin{align} &\underset{x}{\operatorname{minimize}}& & f(x) \\ &\operatorname{subject\;to} & &g_i(x) \leq 0, \quad i = 1,\ldots,m \end{align}$$

拉格朗日对偶问题为

$$\begin{align} &\underset{u}{\operatorname{maximize}}& & \inf_x \left(f(x) + \sum_{j=1}^m u_j g_j(x)\right) \\ &\operatorname{subject\;to} & &u_i \geq 0, \quad i = 1,\ldots,m \end{align}$$

其中目标函数是拉格朗日对偶函数。假设函数$f$ and $g_1, \ldots, g_m$ 连续可微，最大下界出现在梯度等于零的位置。问题

$$\begin{align} &\underset{x, u}{\operatorname{maximize}}& & f(x) + \sum_{j=1}^m u_j g_j(x) \\ &\operatorname{subject\;to} & & \nabla f(x) + \sum_{j=1}^m u_j \, \nabla g_j(x) = 0 \\ &&&u_i \geq 0, \quad i = 1,\ldots,m \end{align}$$

称为Wolfe对偶问题。此问题用计算的方式处理可能会很困难，因为目标函数在联合变数$(u,x)$上不是凹。而且，一般而言，等式的限制条件$\nabla f(x) + \sum_{j=1}^m u_j \, \nabla g_j(x)$也是非线性的，因此Wolfe对偶问题一般而言会不会是凸最佳化问题。不论如何，弱对偶会成立。

## 历史

依照乔治·伯纳德·丹齐格所述，在丹齐格提出了线性规划问题后，约翰·冯·诺伊曼就提出了线性规划的对偶性定理的猜想。冯·诺伊曼注意到他使用了来自其博弈论中的资讯，并且猜想两人零和的矩阵博弈和线性规划等效。严谨的证明最早是由阿尔伯特·塔克和其团队发表（丹齐格在Nering和塔克1993年著作中的前言）

## 参考资料

### 论文

- Duality in Linear Programming Gary D. Knott