Optimization Algorithms - Dual Algorithms & ALM & ADMM & BCD

本文是《最优化算法》课程的学习笔记，内容主要包括对偶算法和增广Lagrange乘子法。

对偶算法

对于复合优化问题，许多实际问题的原始问题有时候比较难以处理，这时候一个非常重要的技巧是考虑它的对偶问题。这里将介绍两种算法：一种是把前面提到的算法应用到对偶问题上，例如对偶近似点梯度法；另一种是同时把原始问题和对偶问题结合起来考虑，例如原始–对偶混合梯度类的算法。我们将看到这两种算法的思想将极大地丰富求解问题的手段。

对偶邻近点下降法

尽管一般对偶问题具有比原始问题更简单的形式，但有时候对偶问题仍然难以求解，例如在一些情况下对偶函数可能不可微，或者定义域可能非平凡等。为了克服这些问题，可以尝试以下方法：

对原始函数添加较小的强凸项，将对偶函数光滑化；
使用要求较低的次梯度法求解，但其速度较慢，且步长选择困难；
如果对偶函数可微，则可以使用梯度法；
使用邻近点下降法(PPA)求解对偶问题；
…

本节我们介绍最后一种方法，即对偶邻近点下降法。该方法适用于对偶函数可被分裂成两项，且其中一项是梯度Lipschitz连续函数，另一项是易于计算其邻近点映射的函数的情况。确切地说，设都是闭凸函数，现在考虑以下形式的优化问题：

其中是某一矩阵。对于该问题而言，即使具有简单的近似点映射，变换后的函数可能仍然不具有易于计算的近似点映射。为了解决这个问题，我们引入辅助变量，于是问题(P)可以转化为以下形式：

考虑上述问题的Lagrange函数：

于是使用Lagrange函数可以将原问题(P)转化为以下等价形式

交换最小化和最大化的顺序，我们可以得到以下对偶问题：

注意到内层的最小化问题可以使用共轭函数来简化，即

其中

分别是函数和的共轭函数。于是对偶问题(D)可以进一步简化为

回忆共轭函数的性质可由原函数导出，即以下定理成立。

定理设是适当且闭的强凸函数，强凸参数为，则其共轭函数在全空间上有定义，并且是梯度-Lipschitz连续的可微函数。

因此当原问题(P)中的目标函数满足定理中的条件时，对偶问题(D)中的目标函数也具有较好的性质，因此可以使用各种梯度方法来求解。下面我们分不同的约束种类来介绍如何使用对偶邻近点下降法求解凸约束问题。

等式约束 考虑以下带有等式约束的凸优化问题：

该问题的Lagrange函数为

注意到

于是对偶问题为

现在可以使用次梯度算法来计算这一对偶问题的解，即令

其中是在点处的次梯度，这是因为根据对共轭函数性质的分析可知以下一般性的事实成立：

另一方面，根据次梯度的计算法则可知是在处的次梯度。当计算很容易时，上述算法可以高效地由当前的计算出下一个迭代点。

目标函数可分 考虑如下形式的凸优化问题：

该问题的Lagrange函数为

其中。原问题的对偶问题为

经过直接计算可知

因此对偶问题可以简化为

该对偶问题可使用与之前类似的次梯度算法来求解。使用，我们有

由于是唯一的约束，因此求解原问题的对偶邻近点下降法可以写成以下形式：

下面我们要求目标函数具有更好的光滑性，此时可以使用梯度法来代替次梯度法求解对偶问题。

注意到为了在对偶问题上使用近似点梯度法，函数需要满足”可微函数+凸函数”的复合形式，其中是闭的强凸函数，或的邻近点算子容易计算。在这些条件下，我们可以证明是梯度-Lipschitz连续的，即

一般地，对于本节开头的问题

在其对偶问题上应用近似点梯度法的更新格式形如

需要注意由于对偶问题是一个极大化问题，因此邻近算子内部应当取上升方向。当进一步引入辅助变量之后，上述更新格式可以写成

Remark. 如果可分，则的计算可以分为多个独立的问题分别求解；另外，更新格式中的步长可以使用常数或由回溯线搜索等方法来选择；以及也可使用加速近似点梯度法，如FISTA等来加速收敛。

一般约束 最后我们考察使用对偶邻近点下降法求解一般约束问题：

首先我们通过引入示性函数将其变形为以下等价形式

该问题的Lagrange函数为

重复之前的分析可得

于是对偶问题为

上式中第一项相对容易得到次梯度，第二项容易计算邻近点算子，因此可以使用对偶邻近点下降法来求解对偶问题。具体地，针对第一项我们有

而第二项中的示性函数的共轭函数为的支撑函数，即

其中的近似点映射为

即集合的投影算子，根据Moreau分解可知

再由邻近算子的性质可得

因此对偶邻近点下降法的更新格式为

整理上式可得

其中是迭代步长。

原始-对偶混合算法

令是适当的闭凸函数，是某一矩阵，考虑以下形式的优化问题：

根据之前的分析，通过引入Lagrange函数，上述问题可以转化为以下min-max形式(鞍点问题)：

又由于具有自共轭性，即

所以原问题也等价于下述形式的min-max问题：

这一形式相较而言更加紧凑，且优化变量不包含辅助变量。

如果Hessian矩阵不定，即同时具有正负特征值，则称满足的点为一个鞍点(saddle point)。当原问题是凸问题，且强对偶性成立时，根据我们上面的分析可见求解的最小值等价于寻找的鞍点。然而，通常来说鞍点问题是难以直接求解的，我们需要使用一些迭代方法来寻找鞍点，最常使用的迭代方法是原始-对偶混合梯度法(Primal-Dual Hybrid Gradient, PDHG)。

PDHG的核心思想在于分别对两类变量使用近似点梯度法来进行迭代。具体地，我们使用下述更新格式来迭代求解中的鞍点问题：

即

其中分别是原始变量和对偶变量的更新步长。该方法在第一步固定原始变量针对对偶变量做(近似点)梯度上升，在第二步固定更新后的对偶变量针对原始变量做(近似点)梯度下降。不难发现，原始变量和对偶变量的更新顺序是无关紧要的，若先更新原始变量，其等价于在另一初值下先更新对偶变量。

需要注意的是，PDHG的收敛性需要比较强的条件，依赖于原始问题和对偶问题的强对偶性，在一些情形下未必收敛。

另外一种常用的求解鞍点问题的方法是Chambolle-Pock算法，相比原始的PDHG，Chambolle-Pock算法在每次迭代中添加了一次外推以加速收敛。具体地，Chambolle-Pock算法的迭代格式为

收敛性

下面我们简要说明Chambolle-Pock算法的收敛性。记

设分别为变量和的取值空间，如果点满足

则称为的一个鞍点。

对任意子集，定义部分原始-对偶间隙为

不难验证，如果鞍点，则

且在处取等号，即

反之，可以证明如果点满足，则是的一个鞍点。

在以上分析的基础上，我们有以下收敛性定理。

Convergence of Chambolle-Pock Algorithm

设

是闭凸函数，且问题

存在鞍点。若在Chambolle-Pock算法中使用常数步长

，且

，则算法输出的迭代点

满足以下性质：

令常数，则有上界，且对于任意都有其中是的一个鞍点。
记，，则对任意都有并且序列的聚点为问题的一个鞍点。
存在的一个鞍点，使得

增广Lagrange乘子法

增广Lagrange乘子法是一种用于求解一般的带有等式约束与不等约束的优化问题的迭代方法。它的核心思想是通过构造增广Lagrange函数，将原问题转化为一个更易求解的形式，并通过迭代更新乘子和变量来逼近原问题的最优解。不过当可行域直接由凸集给定时，不易显式给出迭代格式，因此这一方法通常仅适合可行域由经典的等式与不等式约束给出的问题。

考虑如下形式的等式约束问题

当不具有较好的性质，问题的可行域可能并不规则，此时难以使用次梯度或近似点梯度法等方法直接求解，此时求解这一问题的经典方法之一是传统的二次罚函数法，即求解对应的最小化罚函数问题

然而这种方法的缺点在于罚函数的参数必须趋于无限大才能保证最小化罚函数的解落在原问题的可行域内，这是因为上述罚函数的稳定点满足

对比原问题的KKT条件
$，$
为使两者的解尽量一致，需要各项的系数相近，即

为保证，罚因子必须迅速膨胀到无穷大，这使得难以数值求解这一子问题。为了解决这一问题，增广Lagrange乘子法(Alternating Direction Method of Multipliers, ADMM)引入增广Lagrange函数，可以使用有限的罚因子逼近最优解，从而避免了上述必须使罚因子迅速增大的数值困难。

增广Lagrange法的每步都需要构造增广Lagrange函数。根据不同的约束, 增广Lagrange函数的形式也不同, 因此我们下面分别论述。

不同约束

等式约束 对于本节开头的等式约束问题，定义其Lagrange函数为

即在Lagrange函数的基础上添加了一个等式约束对应的二次罚项。根据以上定义，在第步迭代中，给定罚因子和乘子，则的最小值点应满足梯度条件

回忆这一问题的KKT条件，与应满足稳定性条件

对比上述梯度条件，为了保证两式在最优解处的一致性，我们要求各项的系数相近，于是对充分大的应当有

这等价于要求

根据上述要求，自然的改进想法是

通过合理更新乘子，控制而不仅仅是增大来使接近；
基于上一条，我们可以使用与的差值来更新乘子，使其接近，即令

根据上述讨论，增广Lagrange乘子法的基本流程见下图所示：

在每次迭代确定时，应考虑如下两点：

不应增长过快。这是因为一方面随着罚因子的增大，关于的Hessian矩阵的条件数将增大，使得求解的子问题变得困难；另一方面，罚因子与接近时，可以作为求解的初始点以加速收敛。
不应增长过慢，否则算法整体的收敛速度将因惩罚不足而变慢。

因此在实际中, 我们应该控制的增长维持在一个合理的速度区间内。一个简单的方法是维持算法流程中的参数, 不过近年来也有学者设计了更合理的自适应方法。

一般约束 考虑一般形式的约束优化问题

对于上述问题，我们首先针对不等约束引入松弛变量，将原问题写为下面的等价形式

保留其中的非负约束，可以构造以下Lagrange函数

而原问题中等式约束的二次罚函数为

于是可以定义增广Lagrange函数为

其中对应的。

与前述等式约束类似，增广Lagrange乘子法进行第次迭代时，需在给定乘子以及罚因子的前提下求解以下最小化问题

以得到与。求解这一问题最常用的方法是消元法，即将变量消去，求解只与相关的子问题：首先我们固定，子问题退化为仅与相关的最小化问题

由于上述目标函数是关于的二次函数，因此可以直接求解其最小值点，直接计算可知满足非负约束的最优解为

现在将上述重新代回增广Lagrange函数中，得到

当都是连续可微函数时，是关于的连续可微函数，因此子问题等价于下述仅与相关的最小化问题

上述问题可以使用梯度类方法来求解。

下面我们需要更新乘子。同样与前述等式约束类似，一般约束问题的最优解与乘子应满足KKT条件中的稳定性条件：

而子问题的最优解应满足梯度条件

这等价于

与之前的KKT条件对比，令各项系数相同可得以下乘子更新格式

综上，ALM的迭代格式为

其中罚因子需事先指定。

不等约束的凸优化问题 考虑以下仅含不等约束的凸优化问题

根据之前的分析可得其增广Lagrange函数为

现在任给一列单调递增的罚因子和一个初始乘子，则这一问题的增广Lagrange乘子法的迭代格式为

定义其中的，由于的最小值点的显式表示通常未知，一般需要使用迭代法得到一个近似解，为了保证收敛性和求解精度，我们要求该近似解需要至少满足某一不精确条件，例如

然而由于一般未知，难以直接验证上式成立。不过如果是-强凸函数，则

故此时只需验证下式以保证非精确条件成立：

下面我们不加证明地给出增广Lagrange乘子法的收敛性定理。

Convergence of ALM (Convex Problem)

设与为使用ALM求解上述不等约束的凸优化问题生成的迭代点序列，满足不精确条件。如果问题满足Slater约束品性，则序列是有界序列，且收敛到对偶问题的某一最优解。

进一步地，如果存在某一使得下水平集是非空有界集，则序列也是有界的，且其所有的聚点都是问题的最优解。

与邻近点下降法的关系

现在我们回过头来再次考虑下述形式的复合优化问题

其中和都是适当的闭凸函数，是某一矩阵。根据之前的分析，该问题的Lagrange对偶函数为

对偶问题为

下面我们说明使用近似点梯度法求解对偶问题等价于使用增广Lagrange乘子法求解原问题。

回忆使用近似点梯度法求解对偶问题的迭代格式为

上式等价于

其中

我们下面说明上式给出的正是增广Lagrange乘子法中子问题的最小值点，于是近似点算法的迭代格式对应增广Lagrange乘子法中的乘子更新。

首先将改写成以下形式

接着对约束引入Lagrange乘子，则上述问题的Lagrange函数为

于是根据增广Lagrange乘子法理论，最优点所要满足的稳定性条件为

现在消去可得。另一方面，根据Fenchel对偶可知

带入约束中可得

上式即的最优性条件，即就是近似点梯度法给出的下一次迭代点。

另一方面，如果，则直接选取与即可重新得到增广Lagrange乘子法的乘子更新格式。

综上所述，使用近似点梯度法求解对偶问题等价于使用增广Lagrange乘子法求解原问题。

交替方向乘子法

交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)是增广Lagrange乘子法的一种变体，主要用于求解大规模的凸优化问题。ADMM的核心思想是将一个复杂的优化问题分解为多个简单的子问题，通过交替地求解这些子问题来逐步逼近原问题的最优解。

现在考虑如下问题：

其中都是适当闭凸函数，但可以并不光滑，和是给定矩阵，是给定向量。这一问题的主要特征是目标函数可被分为彼此分离的两块，但是变量被线性约束结合在一起。许多常见的无约束与有约束优化问题都可以转化为上述形式。例如：

可被分为两块的无约束问题，它可被转化为
带线性变换的无约束优化问题，它可被转化为
凸集上的约束优化问题，，这一问题可被转化为
全局一致性问题可被转化为

对于标准形式的问题，我们可以构造增广Lagrange函数

经典的增广Lagrange乘子法需要在每次迭代中求解以下最小化问题

之后在对乘子做如下更新

其中是更新步长。这一算法的瓶颈在于每次需要求解的通常是一个联合优化问题，该问题一般难以直接求解。

为了解决上述问题，ADMM将分解为两个简单的子问题，分别针对和进行迭代，在针对一个变量进行优化时先固定另一个变量为上一步迭代点。具体地，ADMM的迭代格式为

其中为更新步长，通常令。上述更新格式可以自然地推广到多块变量的情况。

现在考察ADMM的收敛性，当是闭凸函数时，由于的约束为线性约束，当Slater条件成立时，我们可以使用凸优化问题的KKT条件来作为ADMM的收敛性判断准则。具体地，问题的Lagrange函数为

根据最优性条件，是的最优解当且仅当满足以下KKT条件：

其中前两个条件为对偶可行性条件，第三个条件为原始可行性条件。

注意到根据，的更新格式等价于

根据次梯度的最优性条件，是上述问题的最优解当且仅当

而由的乘子更新格式可知

因此时有

类似地，的更新格式等价于

同样根据次梯度的最优性条件，是上述问题的最优解当且仅当

依然在中取，则

对比KKT条件可知，只需检测多出来的是否足够小即可验证对偶可行性条件是否满足，即对偶可行性大小由

刻画。

综上，当更新取到精确解，且更新步长为时，判断ADMM是否收敛只需检测下面的两个残差是否足够小，即
$对偶可行性条件原始可行性条件$

分块坐标下降法

现在我们考虑如下形式的问题：

其中是问题的可行域，自变量被拆分成个变量块，其中每个变量块。要求是关于的可微函数，每个都关于是适当且闭的凸函数，但是并不一定可微。

该问题目标函数的性质依赖于与每个的性质，并与变量的分块有关。通常情况下，对于所有变量块不可分，但是当单独考虑某一变量块而固定其他变量块时，的结构可能会变得简单，而又只与相关，因此在中天然可分，需要解决的关键难点在于怎样利用分块结构来处理不可分的函数。

在使用分块坐标下降法(Block Coordinate Descent, BCD)求解上述问题时，需要首先按照的次序，在固定其他个变量块的前提下，按照顺序关于变量块极小化。在完成一块变量的更新后，BCD立刻使用更新值代替之前的，然后继续下一个变量块的更新，即在每次优化一个变量块时，其他变量块的值都使用最新得到的值。

为了说明BCD的具体更新格式，我们定义以下变量划分之后的第个优化空间

并定义辅助函数

则BCD的第次迭代中，关于变量块的更新格式为以下三种方式之一：

交替极小化方法：

该格式严格保证了整个迭代过程的目标函数值是下降的，然而由于的形式复杂，子问题求解难度较大。在收敛性方面，该格式在强凸问题上可保证目标函数收敛到极小值，但在非光滑或非凸问题上不一定收敛。
交替近似极小化方法：

该格式不保证迭代过程目标函数的单调性，但可以改善收敛性结果。使用这一格式可使得算法收敛性在函数为非严格凸时有所改善。
交替近似线性极小化方法：

其中常采用外推定义

这里是外推的权重，是外推点处的梯度。在该式中取权重即可得到不带外推的更新格式，此时该更新格式等价于进行一次近似点梯度法的更新。一般地，使用外推可以一定程度上加快分块坐标下降法的收敛速度。

该格式本质上基于目标函数的一阶泰勒展开近似，在一些测试问题上有更好的表现，可能的原因是使用一阶近似可以避开一些局部极小值点。此外，这一格式的计算量很小，比较容易实现．而且收敛条件很弱，对于非凸或非光滑（可分时）问题均可收敛。

一般地，分块坐标下降法的基本流程如下所示：

分块坐标下降法的迭代流程

References

最优化讲义，陈士祥
最优化与建模，文再文