解大规模部分可分无约束极小化问题的并行分块松弛方法

刘亚云

（重庆师范大学 数学学院，重庆401331）

对于并行优化算法，大致可以分为两类：一类是原问题没有分解为一系列小规模的子问题，而是使用并行搜索方向的并行优化算法［1］或使用并行梯度计算的并行优化算法［2］；另一类是针对一般函数或可分函数，把原问题分解为子问题的基础上提出的并行优化算法［3－9］.笔者提出的方法主要是依据基于区域分解方法的优化方法，此类方法被应用在计算机技术方面［10－13］.通过分解变量来加速含有部分可分函数的极小化，这一思想也在一致优化中体现［14］.在一致优化中，全局变量来保证分解的一致性，在笔者提出的方法中，只通过邻接子向量［10－13］（“interface”subvectors即两个邻近的子向量的公共部分）来保证分解的一致性.在一致优化中，子函数必须是凸函数，而笔者提出的算法中可以适用于部分可分函数是凸函数或非凸函数的情形.

1 部分可分无约束极小化问题

考虑如下极小化问题

其中Fi（x）：Rni→R （i＝1，2，...，N ），此时存在正整数ni，使得是连续可微函数.在某种程度上，函数（）F x部分可分即：只包含x的多维子向量；Fi，Fji≠（）j共有x的某些部分.对于子向量，适合于文献［15］的记法.为了充分理解和解决问题（1），引入以下记号：

·子向量x［i］的邻接指标集：事实上，

·邻接子向量［10－13］：x［ij］，x［ji］∈Rmij，（i，j）∈I

其中，x［ij］＝x［i］∩x［j］表示x［i］中x［i］，x［j］共有部分；x［ji］＝x［j］∩x［i］表 示x［j］中x［i］，x［j］共有部分.

例1 在文献［16］中，一个著名的部分可分函数Rosenbrock测试函数：

则函数F1（x）和F2（x）共有x2，即对邻接子向量x［12］，x［21］有x［12］＝x［21］＝x2，阻碍了函数F （x）完全可分.向量x的子向量是x［1］＝ （x1，x2）T∈R2，x［2］＝ （x2，x3）T∈R2.

2 并行分块松弛方法（PBR）

笔者提出的新的并行分块松弛方法是依据有约束的极小化问题而得出的并行方法.首先，引入合适的辅助未知变量使无约束极小化问题转化为含有全部可分函数的线性约束极小化问题；其次，依据增广拉格朗日方法［17］便可得到并行分块松弛方法（PBR），其中算法的一致性由拉格朗日乘子来保证.此并行算法中的每一次迭代，都并行解决只含有未知量x的子变量的非耦合无约束极小化子问题，随着精确的辅助未知变量被更新，拉格朗日乘子随之更新.最终得出解决含有部分可分函数的大规模无约束极小化问题的更优方法——即并行分块松弛方法.

2.1 问题构想

为了简便，记：

为了解决含有部分可分函数的无约束极小化问题，在引入邻接子向量之后，无约束极小化问题（1）可以表述为如下约束优化问题：

类比在区域分解方法［18］中的三项表达式，引入辅助未知变量则线性约束极小化问题（2）～（3）变为：

关于（4）～（5）给出拉格朗日函数L：X×Z→R.

其中r＞0是罚参数，‖·‖是欧几里得范数.在此易证Lr的鞍点就是L的鞍点，反之也成立；且易验证

2.2 具体算法陈述

并行分块松弛算法（PBR）.以下是具体的算法步骤.

初始步：选取初始λ0，z－1，r＞0，设迭代计数k：＝0，当k≥0，假设zk，λk已知.

第一步：分块松弛

当l＝0时，xk，0←xk－1，zk，0←zk－1；当l＝1，2，...，p 时，假设xk，l－1，zk，l－1.已知并行解决［19－21］：

第三步：更新拉格朗日乘子

第四步：终止步

注1 为了并行解决无约束优化子问题，使用文献［19－21］中给出的L－BFGS方法解决，使用L－BFGS中的终止准则：

3 数据实验结果及评价

在数据实验的呈现中，使用以下记号：

N表示分解子问题的个数；

PZ表示并行分块松弛算法中的迭代次数；

QN表示解决子问题时L－BFGS算法中的拟牛顿迭代次数；

下面选取如下一个部分可分的凸的三对角二次函数［22］进行验证：

虽然PBR算法对任意的罚参数r＞0都收敛，但是迭代次数（结果也就是CPU运行时间）依赖于罚参数r的选取.对于此测试函数，图1、2显示，当罚参数足够大时，CPU运行时间的变化区别并不大.所以在以下的数据试验中，选取r＝450.

图1 n＝5×104，N＝4对于不同的罚参数r的CPU运行时间

图2 n＝5×104，N＝16对于不同的罚参数r的CPU运行时间

在表1中结果显示了标准化速度，算法PBR在很大程度上节省了计算时间.为了研究规模化的速度，改变子问题的个数从1到256，同时保持局部子问题的规模是ni＝104，全局问题的规模从104变化到256×104.在表2中，结果显示，当子问题的个数变为256个时，CPU运行时间只增加了约50%，这表明算法PBR对于凸二次函数的适用性很强.因此PBR在解决大规模无约束极小化问题时能节省大量的运算时间，为解决大规模无约束极小化问题提出了一种全新的算法及思想.

表1 测试函数的标准速度，r＝450

表2 测试函数的规模化速度，r＝450

4 结论

针对解决部分可分的大规模无约束极小化问题，笔者所呈现的并行分块松弛方法具有很强的实施性和灵活性.通过分析目标函数的结构来降低原始问题的复杂性，因此可以有效地解决大规模部分可分无约束优化问题.但是并行分块松弛方法的缺点是在具体的算法迭代过程中罚参数r是凭借经验来选择的，而不是随着调解程序自动的更新，这是以后研究中所继续需要努力的方向.

［1］Phua P K H，Fan Parallel.algorithms for large scale nonlinear optimization.Int.Trans［J］.Oper.Res.，1998，5：67－77.

［2］Koko J，Moukrim.Parallel implementation of a generalized conjugate gradient algorithm［A］.Informatica，1998，9：437－448.

［3］Bouaricha A，MoréJ.Impact of partial separability on large－scale optimization［J］.Comput.Optim.Appl.，1997，7：27－40.

［4］Fukushima.Parallel variable transformation in unconstrained optimization［J］.SIAM J.Optim.，1998，8：658－672.

［5］Kibardin V.Decomposition into functions in minimization problem［J］.Autom.Remote Control，1980，40，1311－1323.

［6］Liu C S，Tseng S.Parallel synchronous and asynchronous space－decomposition algorithms for large－scale minimizations problems［H］.Comput.Optim.Appl.，2000，17，85－107.

［7］Mangasarian.Parallel gradient distribution in unconstrained optimization［J］.SIAM J.Control Optim.，1995，5：1916－1925.

［8］林梦雄.非线性约束最优化并行算法综述［J］.数值计算与计算机应用，1993，3：48－57.

［9］郑芳英.优化问题的若干并行算法研究［D］.山东青岛：山东科技大学，2004.

［10］Fortin M，Glowinski.Augmented Lagrangian Methods：Application to the Numerical Solution of Boundary－Value Problems［R］.North－Holland，Amsterdam，1983.

［11］Glowinski R，Le Tallec.Augmented Lagrangian and Operator－Splitting Methods in Nonlinear Mechanics［P］.Studies in Applied Mathematics.SIAM，Philadelphia，1989.

［12］Gunzburger M，Heinkenschloss M，Lee H K.Solution of elliptic partial differential equations by an optimization－based domain decomposition method［J］.Appl.Math.Comput.，2000，113：111－139.

［13］Gunzburger M D，Peterson J，Kwon.An optimization based domain decomposition method for partial differential equations［J］.Comput.Math.Appl.，1999，37（10）：77－93.

［14］Boyd S，Parikh N，Chu E，et al.Distributed optimization and statistical learning via alternating direction method of multipliers［J］.Found.Trends Mach.Learn.，2011，3：1－122.

［15］Nocedal J，Wright.Numerical Optimization［M］.Berlin：Springer，2006.

［16］Conn A R，Gould N I M，Toint.Testing a class of methods for solving minimization problems with simple bounds on variables［J］.Math.Comput.，1988，50：399－430.

［17］Hestenes M R.Multiplier and gradient method［J］.Journal on Optimization Theory and Applications，1969，4：303－320.

［18］Quarteroni A，Valli.Domain Decomposition Methods for Partial Differential Equations［A］.London：Oxford University Press，1999.

［19］龚纯，王正林.精通 MATLAB最优化计算［M］.北京：电子工业出版社，2009.

［20］Byrd，R.H.，Lu，P.，Nodedal.A limited memory algorithm for bound constrained optimization［J］.SIAM J.Sci.Comput.，1995，16（5）：1190－1208.

［21］Zhu，C.，Byrd，R.H.，Lu，P.，Nocedal.L－BFGS－B：a limited memory code for solving bound constrained optimization problems［A］.Technical report NAM－11，EECS Department，Northwestern University 1994.

［22］Buckley，A.，Lenir.QN－link variable storage conjugate gradients［J］.Math.Program.，1983，27：155－175.