拉格朗日对偶之学习 | Peter’s Secluded Realm

封面图片credit: From UC Denver Math Department

承接上一篇文章。这篇文章依然将重心放在拉格朗日方法上，按照之前所述，上一篇文章的拉格朗日乘子法即为本系列的敲门砖，本篇文章将进一步的探讨复杂情况下的优化。

注意：阅读本文需要基本微积分知识，本P将会略去所有微积分基础的解释。又及该篇文章的主要集中点在用途上，所以将会略去数理证明内容。

0x00 背景

从本篇开始，我们将进一步地探究优化问题，那么什么是优化问题呢？这篇博文^1里面说：

最优化理论是研究函数在给定一组约束条件下的最小值(或者最大值)的数学问题. 一般而言, 一个最优化问题具有如下的基本形式:

为了解释什么是对偶问题，我们引入最简单的线性规划优化问题进行解释。

即每一个线性规划问题（称为原始问题）有一个与它对应的对偶线性规划问题（称为对偶问题）。1928年美籍匈牙利数学家 J.von.诺伊曼在研究对策论发现线性规划与对策论之间存在着密切的联系。两零和对策可表达成线性规划的原始问题和对偶问题。

这篇^2文章给出了一个很好的解释例子：

问题1：

某工厂有两种原料A、B，而且能用其生产两种产品：

1、生产第一种产品需要2个A和4个B，能够获利6；

2、生产第二种产品需要3个A和2个B，能够获利4；

此时共有100个A和120个B，问该工厂最多获利多少？

问题2：

工厂除了拿原料生产成产品卖掉这条出路外，还有一种方法是直接将原料卖掉。当然，无论选择哪种方式，都要实现利益最大化。重复一下条件：

某工厂有两种原料A、B，而且能用其生产两种产品：

1、生产第一种产品需要2个A和4个B，能够获利6；

2、生产第二种产品需要3个A和2个B，能够获利4；

此时共有100个A和120个B，那么最低可以接受多少的A、B的原料价格呢？

上述两种问题实际上即为一种对偶问题。我们可以很方便的列出解决的表达式：

对问题1：

对问题2：

很明显地，这两个问题是相互关联的。具体修改方法是：将目标变量与优化变量对调，再把符号更改一遍即为线性规划原问题的对偶问题。

说了那么多，什么是拉格朗日优化问题呢。从昨天的投资问题我们可以看到，在优化上我们并不能指望约束是刚好为一个等式。所以拉格朗日优化问题的一般形式长下面这样：

假设是定义在R^n上的连续可微函数，考虑约束最优化问题：

现在如果不考虑约束条件，原始问题就是：

因为其连续可微，那么利用高中知识就可以解答：求导数-等于0-代回去，非常之简单。可是实际偏偏有约束条件，拉格朗日函数做的事情就是通过数学方式把约束条件去掉。于是乎我们请出广义拉格朗日函数（generalized Lagrange function）:

其中，，是拉格朗日乘子，特别地，要求

现在，如果把看作是关于的函数，要求其最大值，即

注意，我们把看作是关于的函数。然后我们不管通过了何种优化方法总之就是优化完了，让取到了一个让取得最大值的数，而且在这个过程中把看作常量的话，那么显然就变成了只与相关的函数了。我们定义这个函数为：

里面的还是熟悉的配方：

下面通过是否满足约束条件两方面来分析这个函数:

考虑某个违反了原始的约束（忘了的请滑到最前面看约束是什么），即或者，那么：

注意，这个式子我们已经确定好了作为最大化参数，我们只是来找对应的的。但很不幸的是，在这个假设下我们让违反了约束，在的情况下，对应之就可以让整个函数要多大取多大（记住我们要优化的函数是求最大值，所以当然要多大取多大）；同理，时，我们同样可以很容易取一个使得。那么简直是一场灾难：求一个有约束函数的最大值已经够麻烦的了，现在倒好，直接引入了两个巨大的函数让变化后的函数变成无穷大了，那么这个变化后的函数不能拿来做事情，也没有意义了。

所以反过来，考虑某个遵守原始的约束，则。为什么呢？因为我们已经确定好了作为最大化参数。剩下的就是待优化的常量（注意这个函数变量里面没有），常量的最大值当然就是常量。

推了这么久，我们可以得出：

可以发现这个加了一大堆的函数居然和原函数等价了！那么解决这个加了东西的函数的优化也就是解决原来函数的优化，前提是满足约束条件：

所以说，我们定义拉格朗日函数原始问题的最优解：

现在是时候总结了，也就是说，拉格朗日通过提出了这么一种方法，把原来有拘束的问题变成了无拘束问题，从而将原来的问题简单化。虽然加了很多东西，但是后期的数学计算会告诉我们问题确实得到了简化。

0x01 定义

铺垫了这么久，那么什么是对偶问题呢？

定义关于的函数：

注意，这个函数等式右边是关于的函数的最小化，确定以后，最小值就只与有关，所以是一个关于的函数。

我们考虑最大化式子并且展开它：

是不是很熟悉？我们写出来了原始问题的对偶问题！原始的问题是：

对偶问题和原问题在形式上是很对称的，只不过原始问题是先固定中的，优化出参数，再优化，而对偶问题是先固定，优化出最优，然后再确定参数。

定义对偶问题的最优值：

0x02 性质

定理：若原始问题与对偶问题都有最优值，则：

证明见这里^3 。

那么，生活中的规划问题一般都是非线性的，那么什么样子的条件才能使用拉格朗日优化对偶方法呢？这时我们要请出KKT条件：

KKT最优化条件是Karush(1939)以及Kuhn和Tucker(195)先后独立发表[^4]出来的。其第一项是说最优点必须满足所有等式及不等式限制条件, 也就是说最优点必须是一个可行解, 这一点自然是毋庸置疑的; 第二项表明在最优点, 必须是和的线性組合, 和都叫作拉格朗日乘子；所不同的是不等式限制条件有方向性, 所以每一个都必须大于或等于零, 而等式限制条件没有方向性，所以没有符号的限制, 其符号要视等式限制条件的写法而定。