线性规划的对偶问题——由拉格朗日对偶问题导出

news/2024/6/30 23:01:05

线性规划的对偶问题可由拉格朗日函数导出，这不仅提供了另一种理解问题的视角，还揭示了原问题与对偶问题之间深刻的关系。通过构造拉格朗日函数，原问题的约束条件被整合到目标函数中，使得我们能够在拉格朗日乘子的空间中寻求最优解。通过拉格朗日函数，可以将原始线性规划问题的最优解与对偶问题的最优解联系起来，揭示了两者在解空间和目标值上的对称关系。具体而言，原始问题的约束条件在对偶问题中表现为目标函数的约束，反之亦然。这种对称关系使得对偶问题不仅是原问题的一个镜像，更是在解的性质和目标函数上表现出一致性。

一、线性规划的最优解存在理论

线性规划问题通常表示为：

\[\begin{align} \max \quad & c^T x \\ \text{s.t.} \quad & Ax \leq b \\ & x \geq 0 \end{align} \]

其中：

$x \in \mathbb{R}^n$ 是决策变量向量，
$c \in \mathbb{R}^n$是目标函数的系数向量，
$A \in \mathbb{R}^{m \times n}$是约束矩阵，
$ b \in \mathbb{R}^m$ 是约束向量。

2.1 可行域的存在性

假设可行域是非空的，即存在一个$x \geq 0$使得$Ax \leq b$。如果没有可行解，那么问题无解，无法进行生产计划。在实际生产计划问题中，生产数量$x$通常是有限的，因为企业的生产能力和资源是有限的。因此，假设可行域是有界的，即存在一个正数$M$，使得所有可行解$x$ 满足$| x| \leq M $。

2.2最优解的存在性

线性规划问题的目标函数$c^T x$是一个线性函数，在线性规划的可行域上是连续的。线性约束$Ax \leq b$和$x \geq 0$定义的可行域是一个凸集。根据线性规划的最优解存在性定理，一个在线性约束定义的有界可行域上的连续线性目标函数必有最优解。因此，对于生产计划问题，我们可以断言其必有最优解。

二、导出线性规划的对偶问题

2.1拉格朗日对偶问题

考虑一个一般形式的非线性规划问题(目标函数最小化)：

\[\begin{align} \min \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \leq 0, \quad i = 1, \ldots, m \\ & h_j(x) = 0, \quad j = 1, \ldots, p \end{align} \]

其中，$f(x)$ 是目标函数，$g_i(x) \leq 0$是不等式约束，$h_j(x) = 0$是等式约束。

拉格朗日函数
为了将约束条件整合到目标函数中，我们构造拉格朗日函数：

\[L(x, \lambda, \nu) = f(x) + \sum_{i=1}^{m} \lambda_i g_i(x) + \sum_{j=1}^{p} \nu_j h_j(x) \]

其中，$\lambda_i \geq 0$是与不等式约束$g_i(x) \leq 0$相关的拉格朗日乘子，$\nu_j$是与等式约束$h_j(x) = 0$相关的拉格朗日乘子。

拉格朗日对偶函数$g(\lambda, \mu)$定义为：

\[g(\lambda, \mu) = \inf_{x \in \mathbb{R}^n} L(x, \lambda, \mu) \]

对偶函数$g(\lambda, \mu)$是通过在所有$x$上求拉格朗日函数的下界得到的，即：

\[g(\lambda, \mu) = \inf_{x \in \mathbb{R}^n} \left[ f(x) + \sum_{i=1}^{m} \lambda_i g_i(x) + \sum_{j=1}^{p} \mu_j h_j(x) \right] \]

拉格朗日对偶问题是最大化拉格朗日对偶函数

\[g(\lambda, \mu)：\max_{\lambda \geq 0, \mu \geq 0} g(\lambda, \mu) \]

即：

\[\max_{\lambda \geq 0, \mu \geq 0} \left\{ \inf_{x \in \mathbb{R}^n} \left[ f(x) + \sum_{i=1}^{m} \lambda_i g_i(x) + \sum_{j=1}^{p} \mu_j h_j(x) \right] \right\} \]

2.2线性规划的对偶函数

设线性规划为

\[\begin{align} \min_{x \in \mathbb{R}^n} \quad c^T x\\ Ax \geq b \\ x \geq 0 \end{align} \]

其中$c = [c_1, c_2, \ldots, c_n]$ 是目标函数的系数向量，$x = [x_1, x_2, \ldots, x_n]$是决策变量向量；$A$是约束条件的系数矩阵，$b = [b_1, b_2, \ldots, b_m]$ 是约束条件的右侧常数向量。这里假设$A$ 是一个 $m \times n$矩阵。

线性规划问题的拉格朗日函数

\[L(x, \lambda, \mu) = c^T x + \lambda^T (b - Ax) - \mu^T x \]

其中$\lambda = [\lambda_1, \lambda_2, \ldots, \lambda_m]$是不等式约束$Ax \geq b$的拉格朗日乘子向量，$\mu = [\mu_1, \mu_2, \ldots, \mu_n]$是非负性约束$x \geq 0$的拉格朗日乘子向量。

拉格朗日对偶函数
拉格朗日对偶函数$g(\lambda, \mu)$定义为原始问题的最优值的下界，即：

\[g(\lambda, \mu) = \inf_{x \geq 0} L(x, \lambda, \mu) \]

根据拉格朗日函数的定义：

\[L(x, \lambda, \mu) = c^T x + \lambda^T (b - Ax) - \mu^T x \]

要最小化$$L(x, \lambda, \mu)$$，需要考虑非负性约束$x \geq 0$。

拉格朗日对偶问题
拉格朗日对偶问题是最大化拉格朗日对偶函数$g(\lambda, \mu)$，即：

\[\max_{\lambda \geq 0, \mu \geq 0} \quad g(\lambda, \mu) \]

换句话说，拉格朗日对偶问题可以表示为：

\[\max_{\lambda \geq 0, \mu \geq 0} \left\{ \inf_{x \geq 0} [c^T x + \lambda^T (b - Ax) - \mu^T x] \right\} \]

2.3 线性规划的对偶问题

根据前面的推导，拉格朗日对偶函数$g(\lambda, \mu)$的表达式是：

\[g(\lambda, \mu) = \begin{cases} b^T \lambda & \text{if } A^T \lambda + \mu = c, \\-\infty & \text{otherwise}. \end{cases}\]

将上述对偶函数转换为线性规划的标准矩阵形式，我们可以按照以下步骤进行：

引入新的变量和约束
引入变量$\lambda \in \mathbb{R}^m$ 和$\mu \in \mathbb{R}^n$，并考虑以下约束条件：

\[A^T \lambda + \mu = c \]

其中$\lambda \geq 0$ 和$\mu \geq 0$。

目标函数最大化$b^T \lambda$。

\[\max_{\lambda \geq 0, \mu \geq 0} \quad b^T \lambda \]

约束条件
除了上面引入的等式约束$A^T \lambda + \mu = c$，还要满足$\lambda \geq 0$和$\mu \geq 0$。

综合以上步骤，线性规划的对偶问题可以写为：

\[\begin{align} \max_{\lambda, \mu} \quad b^T \lambda\\ A^T \lambda + \mu = c \\ \lambda \geq 0 \quad \mu \geq 0 \end{align}\]

这个形式清晰地显示了对偶函数在给定约束条件下的定义和有效性。

2.4 满足强对偶定理

拉格朗日函数的最小化
要最小化拉格朗日函数$L(x, \lambda)$，我们对$x$求偏导并令其等于零：

\[\nabla_x L(x, \lambda) = c - A^T \lambda = 0 \]

从而得到最优解 $x^*(\lambda)$：

\[x^*(\lambda) = A^T \lambda \]

替换到拉格朗日函数
将最优解$x^*(\lambda)$带入拉格朗日函数：

\[g(\lambda) = L(x^*(\lambda), \lambda) = c^T x^*(\lambda) - \lambda^T (A x^*(\lambda) - b)\\ g(\lambda) = c^T A^T \lambda - \lambda^T (AA^T \lambda - Ab)\\ g(\lambda) = \lambda^T (AA^T \lambda) - b^T A^T \lambda\]

对偶问题的最大化
我们希望最大化$g(\lambda)$：

\[\max_{\lambda \geq 0} \quad g(\lambda) = \max_{\lambda \geq 0} \left\{ \lambda^T (AA^T \lambda) - b^T A^T \lambda \right\} \]

这个最大化问题可以通过线性规划的方法求解，它给出了原始线性规划问题的最优解。因此，强对偶定理得证。

总结

通过拉格朗日函数导出的对偶问题，不仅为我们提供了理解和求解线性规划问题的新工具，还揭示了原问题与对偶问题之间深刻而优雅的数学关系。具体而言，拉格朗日对偶理论使得原问题的约束条件被整合到目标函数中，从而在拉格朗日乘子的空间中寻求最优解。这种对称性和互补性在优化理论和实际应用中具有重要的意义和广泛的应用价值。例如，在经济学、工程学和管理科学中，对偶问题常被用于资源分配、成本控制和生产调度等领域，提供了理论基础和实用方法。
这种对偶关系在优化理论中起着重要作用。首先，它帮助我们理解最优性条件，证明最优解的存在性和唯一性。这是通过分析原问题和对偶问题的解空间和目标函数之间的对称关系实现的。在进行大规模问题求解时，对偶问题的引入和分析常常能显著简化计算过程，提高求解效率。例如，在一些复杂的优化问题中，对偶问题的解可以为原问题的解提供界限，从而缩小搜索空间，提升求解速度。这种方法不仅有助于找到最优解，还能为实际应用中的复杂决策问题提供有效的解决方案。