跳转至

拉格朗日松弛

这节我们要来介绍一个重要的优化技术: 拉格朗日松弛(Lagrangian Relaxation), 简单来说, 这是一种解决复杂线性规划问题的方法. 当一个优化问题包含很多的约束条件, 导致求解困难的时候, 拉格朗日松弛会将其中一些棘手的约束条件"松弛"掉, 通过引入拉格朗日乘子(Lagrange Multipliers), 将这些约束整合到目标函数中, 从而得到一个更容易求解的优化问题.

拉格朗日松弛介绍

带约束的生成树问题

目标是在图\(G\)中找到一个生成树\(T\), 使其总成本\(\sum_{e\in T} c_e\)最小. 约束是这个生成树的总收益值\(\sum_{e\in T} b_e\)必须不低于一个门槛\(B\). (\(c_e\)代表图中的某一条边\(e\)的成本, \(c\)是将每一条边映射到一个成本值的函数; \(b_e\)代表图中的某一条边的收益, \(b\)是将每一条边映射到一个收益值的函数).

拉格朗日松弛

现在, 我们把这个刚性的约束拿掉, 转而将其变为一个惩罚项放到目标函数中. 惩罚项\(\lambda\)是一个我们自己选择的非负数, 它被称为拉格朗日乘子. 代表了对不满足收益要求的惩罚力度, 惩罚项表示为\(\lambda (B-\sum_{e\in T} b_e)\). \((B-\sum_{e\in T}b_e)\)衡量了当前找到的树\(T\)的总收益离目标\(B\)还差多少. 如果收益不达标, 那么就会是一个正数, 整个惩罚项就会增加成本, 相当于对这个不好的结果进行惩罚; 如果收益达标, 那么惩罚项就是一个负数, 整个惩罚项就会降低总成本, 相当于对这个好的解进行奖励. 这个新的目标是在所有可能的生成树\(T\)中, 寻找一个能使得成本+惩罚这个综合值最小的数. 这个新的目标函数可以表示为:

\(t(\lambda)=\min_{T\in \mathcal{T}} \sum_{e\in T}c_e + \lambda(B-\sum_{e\in T} b_e)\).

对于这个目标函数, 我们有一些重要的观察:

  1. 设\(z\)是原始问题的最优值, \(T^*\)是原始问题的最优解, 我们有\(t(\lambda)\leq \sum_{e\in T^*} c_e + \lambda(B-\sum_{e\in T^*} b_e)\leq \sum_{e\in T^*}c_e\), 第一个不等式非常明显, 我们来看第二个不等式. 根据IP.1的约束条件, 我们有\(\sum_{e\in T^*}\geq B\), 所以\(B-\sum_{e\in T^*}b_e\)必然小于等于\(0\), 而\(\lambda\geq 0\), 所以后面惩罚项的结果一定是一个非正数, 所以整一个式子一定小于它的第一项, 即\(\sum_{e\in T^*} c_e = z\).
  2. 我们可以在多项式时间内计算出\(t(\lambda)\)的值. 之所以能够做到这一点, 是因为我们可以把一个看起来很复杂的优化问题, 转化为一个我们已经直到如何快速解决的经典问题-最小生成树问题. 以下是具体的解决步骤: 首先, 对\(t(\lambda)\)的公式进行变形, 得到\(t(\lambda)=\min_{T\in \mathcal{T}} \sum_{e\in T}(c_e - \lambda b_e) + \lambda B\), \(\lambda B\)是一个常数. 现在问题变成了在图\(G\)中寻找一个生成树\(T\), 使得\(\sum_{e\in T}(c_e - \lambda b_e)\)最小. 我们给图中的每一条边\(e\)定义一个新的权重, 这个新权重的值是\(ce-\lambda b_e\), 然后, 我们需要在这个新的权重图上, 找到一个生成树\(T\), 使得这个数的所有边的新权重之和最小. 这就是一个经典的最小生成树问题, 我们可以使用Kruskal算法或者Prim算法在多项式时间内解决它.
  3. \(t(\lambda)\)的几个重要的数学性质: 分段线性, 连续和凹函数. 首先, 我们来看为什么\(t(\lambda)\)的背后是一堆直线, 在\(t(\lambda)\)的表达式中, 我们把\(\lambda\)当作变量, 那么其余的都是常数, 这个表达式可以变为一个关于\(\lambda\)的线性函数, 由于图中存在许多不同的生成树\(T(T_1, T_2, ...)\), 每一棵树都对应着这样一条关于\(\lambda\)的直线, 因此, 我们实际上拥有一个由大量直线组成的直线集合, 图中的细线就代表了这些直线的一部分. 然后, 我们再来看为什么\(t(\lambda)\)是这些直线的下包路线(lower envelope), 其中的\(\min\)是关键, 它的意思是: 对于任何一个给定的\(\lambda\)值, 我们需要在所有直线上(也就是对应所有可能的树\(T\))找到在那个\(\lambda\)处的函数值, 然后取其中最小的一个作为\(t(\lambda)\)的值. 这就就是了为啥是连续的, 并且是凹函数.

那么第三个性质有什么作用呢? 这很重要, 我们根据第一个性质已经知道了\(t(\lambda)\leq z\), 即\(t(\lambda)\)是我们想求的真实最优成本\(z\)的一个下界. 为了让这个下界尽可能地接近真实的\(z\), 我们需要找到能让\(t(\lambda)\)最大的那个\(\lambda\)值, 换句话说, 我们的目标是求解\(\max t(\lambda)\). \(t(\lambda)\)的凹函数性质在这里就派上了大用场. 凹函数只有一个全局最大值, 没有其他局部的小山峰来迷惑我们. 我们可以通过高效的算法来快速定位这个最高点.

而这个最大值, 就是我们通过拉格朗日松弛这种方法所能得到的, 对于原问题最优解\(z\)的最紧密, 最有效(strongest)的下界.

无约束优化

在前面的介绍中, 我们提到拉格朗日松弛的目标是通过松弛掉一些约束条件, 将问题转化为一个更容易求解的形式. 我们要求解的就是无约束优化问题. 我们可以用求解无约束优化问题的各种经典方法, 来求解拉格朗日松弛后的优化问题, 其中的一个基本算法是最速上升法.

它的核心思想如下: 目标是找到一个连续, 可微, 凹函数\(f\)的最大值. 从一个任意的点\(x(0)\)开始, 根据以下的规则重复更新当前点\(x(k+1)=x(k)+\alpha(k)\times f'(x(k))\), 简单来说, 就是从一个点出发, 不断地朝着函数增长最快的方向移动一小步, 从而逼近函数的最高点, \(\alpha(k)\)决定的是步长, 控制每一步沿着梯度方向前进的距离.

定理9.1说明了最快速上升法是收敛于最大值的. 随着迭代次数的增多, \(x(k)\)会越来越接近那个使\(f(x)\)最大的点.

定理的关键在于对步长\(\alpha(k)\)的选择, 为了保证收敛, 步长需要满足以下两个条件 \(\lim \alpha(k)=0\), 步长最终寻妖趋近于0, 这好比登山, 越接近山顶, 步子迈的越小, \(\sum \alpha(i)=\infty\), 保证了不论离山顶有多远, 都有足够的燃料爬到终点, 不会半途而废.

我们给出了一种符合上述条件的步长设置方法, \(\alpha(k)=\rho \beta^k\), 这是一个按照几何级数递减的步长序列.

另外, 最快速上升法的一个巨大优势是它可以轻松地从一维函数推广到多变量函数, 这种情况下, 更新规则中的导数\(f'(x)\)被梯度\(\nabla f(x)\)所取代.

但是, 我们发现, 这个方法有一个前提条件是前面的\(t(\lambda)\)不满足的, 那就是它要求函数是可微的, 而\(t(\lambda)\)是一个分段函数. 那么我们如何用这种方法处理不可微函数呢? 为了处理不可微的情况, 算法需要做一个小小的修改, 将梯度替换为次梯度. 对于一个凹函数\(f\), 向量\(s\)称为函数\(f\)在\(x\)点的次梯度, 前提是对于定义域中所有的\(y\), 下式都成立: \(\(f(y) \leq f(x) + s \cdot (y - x)\)\)

只要我们沿着次梯度的方向去更新解 \((x(k+1) = x(k) + α(k) * s(k))\), Theorem 9.1的收敛性就得到了保证.

拉格朗日松弛在旅行商问题中的应用

旅行商问题

我们来回顾一下旅行商问题. 目标是\(\min \sum_{e\in E}w_ex_e\). 最小化所选路径的总权重, \(w_e\)是边\(e\)的权重, \(x_e\)是一个决策变量. 约束包含两部分, 一个是度约束, 意味着对于每个城市, 必须有且仅有两条边与之相连, 另一个是子路径消除约束, 防止旅行商在一些城市构成的环路之中徘徊, 而不是访问所有的城市.

为了使问题更容易被拉格朗日松弛求解, 我们要对模型(IP.2)进行变换, 得到等价的模型(IP.3). 怎么转换呢?

首先, 我们要消除冗余约束, 子集\(S\)的边界和补集的边界是一样的(同一组边), \(2^n-2\)个约束实际上只有\((2^n-2)/2\)个独立约束. 所以, 我们可以得到\(\sum_{e\in \delta(S)}x_e = \sum_{e\in \delta(V/\ S)}x_e\). 这里要注意一下\(\delta()\)这个的含义, \(\delta(S)\)被定义为所有连接\(S\)内部和\(S\)外部的边, \(\delta(u)\)表示所有直接连接到城市\(u\)的边的集合.

其次, 子环消除约束\(\sum_{e\in \delta(S)}x_e\geq 2\). 可以转化为\(\sum_{e\in E(S)} x_e\leq |S|-1\). 这之所以成立, 是由于度数约束, 我们可以通过一个逻辑推导来理解, 把子集\(S\)中所有城市的度数加起来, 由于度数约束, 总和应该是\(2\times |S|\). 这个总和由两部分组成, 第一个是每一条内部边\(e\in E(S)\)都会被计算两次(因为它的两个端点都在\(S\)内). 第二个是每一条跨界边\(e\in \delta(S)\)都只会被计算一次(因为它只有一个端点在\(S\)内), 因此, 我们可以得到一个恒等式\(2\times |S|=2\times E(S)+\delta(S)\), 对这个等式进行移项, 可以发现左右两边的表达式可以互相推导, 从而证明它们是等价的.

另外, 同样是由于度数约束, 我们可以得到\(\sum_{e\in E(V-v)} x_e = |V| -2\). 这是因为, 一个完整的旅行路线总共有\(|V|\)条边, 任意一个城市\(v\)都必须连接着正好\(2\)条边. 我们可以把整个陆星路线上的所有路(总共\(|V|\)条)分为两类: 第一类是连接到我们关注的那个特定你城市\(v\)的路; 第二类是跟城市\(v\)完全无关的路, 第一类的数量正好是2条, 那么, 第二类的数量就是\(|V|-2\)条.

根据以上的三点, 我们可以得到(IP.3). 注意, 此时问题的难度还是没有改变的, 我们只是对模型进行了等价的变换. 为了能够实际进行计算, 我们选择放弃寻找精确解, 而是求解和它一个相关但是简单得多得近似问题, (IP.3)改变了, 我们选择移除除了\(v\)之外的所有度约束, 并将它们放入到目标函数中, 得到\(t(\lambda) = \sum_{e\in E}w_ex_e + \sum_{u\in V}\lambda_u (2-\sum_{e\in \delta(u)}x_e)\). 保留的度约束告诉我们, 对于这个特殊的节点\(v\), 与它相连的边的总数必须是2. 子环消除约束和基数约束告诉我们, 应该在\(V-v\)上面选择一个生成树, \(\sum_{e\in E(S)}x_e\leq |S|-1\)告诉我们在\(V-v\)这个子图中, 不允许形成任何的小圈; \(\sum_{e\in E(V-v)} x_e = |V|-2\)告诉我们, 在\(V-v\)这个子图中, 必须选择不多不少, 正好\(|V|-2\)条边, 这就强制算法必须在\(V-v\)上面构建一个连通的生成树.

为什么要这样做呢? 因为得到这个生成树是有成熟的算法的, 把这个生成树的两端连起来之后就变成了一个环, 这就是一个可行的旅行路线, 这个树被称为1-树.

设\(\mathcal{R}\)是一个巨大的集合, 它包含了所有符合1-树结构的可能性. 那么\(t(\lambda)\)定义为\(t(\lambda) = \min_{R\in \mathcal{R}} \sum_{e\in R} w_e + \sum_{u\in V} \lambda_u (2-\deg_R(u))\).

对于\(t(\lambda)\), 有几下的几点重要观察:

  1. 设原始旅行商问题的最优值是\(z\), 那么观察4说明, 这个\(t(\lambda)\)的结果一定小于等于\(z\). 这个和前面拉格朗日松弛的第一个观察的证明是差不多的.
  2. 通过一个聪明的数学恒等式变换, 可以把原来那个复杂的最小化问题, 变为一个我们早就已经知道如何快速解决的, 标准的最小生成树的问题, 可以在多项式时间内求解. 仿照前面的, 我们可以将\(t(\lambda)\)改写为\(t(\lambda) = (\min_{R\in \mathcal{R}} \sum_{(u, v)\in R} (w_{uv}-\lambda_u-\lambda_v)) + 2\sum_{u\in V}\lambda_u\). 对于第一项, 我们可以定义一个新的权重\(w'_{uv} = w_{uv} - \lambda_u - \lambda_v\). 我们称之为修改后的边权, 然后, 在这个修改了权重的新图上, 找到一个权重最小的1-树, 最后, 检查所有连接到\(v\)的边, 然后选择其中权重最小的两条边加入到这个1-树中, 这样就得到了最终的结果.
  3. \(t(\lambda)\)的数学性质: 分段线性, 连续和凹函数. 这个和前面的拉格朗日松弛的第三个观察是一样的道理. 然后求解的算法就是前面说的次梯度算法.

拉格朗日松弛的数学基础

拉格朗日松弛提供的下界怎么样呢? 我们在算\(\max_{\lambda} t(\lambda)\)的时候在优化什么东西呢. 在这一小节中, 我们要看一下拉格朗日松弛的数学基础.

设\(z\)为以下整数线性规划的的最优值. 我们的目标是最小化\(cx\), 需要同时满足两个条件, 一个是\(Ax\geq b\), 我们称之为复杂约束, 另一个是\(Dx\geq d\), 我们能称之为简单约束, \(x\)必须是整数.

经过拉格朗日松弛, 我们把复杂约束\(Ax\geq b\)从约束条件中拿掉, 然后把它加入到目标函数中, 并给他一个惩罚项\(\lambda\times (b-Ax)\). 这里的\(\lambda\)是一个非负的乘子向量, 可以理解为对不满足原约束\(Ax\geq b\)的惩罚力度. 新的目标函数变味了\(cx+\lambda\times (b-Ax)\), 此时, 问题就简化为了只需要满足简单约束\(Dx\geq d\), 并且\(x\)是整数的条件下, 最小化新的目标函数. \(t(\lambda)\)被定义为\(t(\lambda) = \min cx + \lambda \times (b - Ax)\).

我们通过尝试所有可能的\(\lambda\)得到的下界\(t\), 其实等价于求解另一个新的优化问题, 这个新问题是: 目标是最小化\(cx\), 约束是\(Ax\geq b\), \(x\in CH(L)\), 这里的\(CH(L)\)是一个关键的概念, 它代表集合\(L\)的凸包. 想象以下, 把所有在\(L\)里面的整数点都画出来, 然后用一根橡皮经把最外围的点都圈起来, 这个橡皮筋圈住的区域(包括内部)就是\(CH(L)\), 它是一个比\(L\)更大的连续区域. 所以, 这个定理的本质上实在说, 最大化\(t(\lambda)\)等价于原问题的整数可行域的凸包上, 求解一个连续线性规划问题的最优值.

在一个更大的可行域(\(CH(L)\))里寻找最小值, 得到的结果\(t\)自然不会超过(即小于或等于)在一个更小的, 离散的点集\(L\)里找到的最小值\(z\). 这为我们提供了一个坚实的理论基础, 证明了拉格朗日松弛确实能为我们找到一个有效的下界. \(t\)和\(z\)之间的差距\((z - t)\), 被称为对偶间隙(duality gap). 这个间隙越小, 我们通过拉格朗日松弛得到的下界质量就越高.

如果描述\(L\)的"简单"约束\(Dx ≥ d\)本身就是一个"整"的多面体(即去掉整数要求后, 所有顶点坐标仍然是整数), 那么 \(CH(L)\) 就和这个多面体完全一样. 在这种情况下, 拉格朗日松弛能给出的最好下界\(t\), 就等于我们对整个原始问题进行拉格朗日松弛所得到的最优值.

对于该定理的证明可见Page6.