求解非凸优化问题的近似交替方向乘子法①

谭秋芬， 罗洪林

重庆师范大学 数学科学学院， 重庆 401331

本文考虑以下线性约束优化问题

minf(x)+g(y)

s． t．Ax+By=b，x∈P

(1)

P={x∈Rn1|li≤xi≤ui，i=1，2，…，n1}

当问题(1)的目标函数是凸可分时， 交替方向乘子法(ADMM)是解决这类问题较为有效的方法[5-8]． 若目标函数非凸， 则通过一些假设条件， ADMM仍然可以保持较好的适用性[9-14]． 其中， 文献[10-11]针对非凸问题提出了Bregman ADMM并证明了其收敛性， 该算法在分别求解子问题时， 在原本的增广拉格朗日函数上增加了一个Bregman距离函数， 通过将非凸子问题进行一个凸化处理来简化原来的子问题， 进而对其进行求解． 文献[13]提出了非凸Proximal ADMM， 该算法在子问题中引入了近端项， 将子问题进行凸化处理， 进而使用ADMM进行求解， 而文献[15]在处理非凸问题上考虑的是近似二次项， 近似二次项在保证问题凸化的同时还能使得迭代点不会偏离稳定点太多， 这为凸化处理提供了更好的方向．

当考虑问题(1)中的有界约束时， 使用ADMM直接解决是比较困难的． 幸运的是， 文献[15]在处理有界多面体上的非凸优化问题时引入了梯度投影算法， 对含有有界约束的单块优化问题进行了求解并取得了较好的结果． 受以上文献启发， 在借鉴梯度投影和交替方向乘子法(ADMM)两种经典方法思想的基础上， 本文针对具有可分结构的非凸优化问题提出了一种新的近似交替方向乘子法(P-ADMM)， 基于ADMM的框架在解决有界多面体上的非凸子问题时， 采用梯度投影， 以此简化非凸子问题的求解， 降低运算成本， 并且通过引入一个“平滑的”(即指数加权)原始迭代序列， 并在每次迭代时， 向增广拉格朗日函数中增加一个以平滑的原始迭代为中心的近似二次项， 使所得到的近似增广拉格朗日函数在每次迭代时被不精确地最小化， 在保证算法的收敛性的同时也能够提升算法的收敛速度． 该算法可有效应用于求解一类非凸的船舶分布式能源管理问题．

1 预备知识

1.1 论文的符号定义

1) Rn1为n1维欧氏空间， Rn2为n2维欧氏空间．

2) Rm×n1是m×n1维实矩阵空间， Rm×n2是m×n2维实矩阵空间．

1.2 稳定解集合

原问题(1)的KKT条件如下

∇f(x*)+ATλ*-μ*+ν*=0

∇g(y*)+BTλ*=0

Ax*+By*=b

μ*0，ν*0

1.3 基本假设

(I)BBTμ0I， 其中μ0>0， 即B是列满秩的．

(II)f(x)是可微的， 且满足Lipschitz可微条件

‖∇f(x1)-∇f(x2)‖≤L1‖x1-x2‖，L1>0， ∀x1，x2∈P

则可得， 存在γ<0， 使得

〈∇f(x1)-∇f(x2)，x1-x2〉≥γ‖x1-x2‖2

(III)g(y)是强凸的， 强凸系数为m， 即

(IV)g(y)是可微的， 且满足Lipschitz可微条件

‖∇g(y1)-∇g(y2)‖≤L2‖y1-y2‖，L2>0， ∀y1，y2∈Rn2

(VI) 函数g(y)是强制的， 即

1.4 一种近似的ADMM

接下来介绍近似的交替方向乘子法(P-ADMM)， 问题(1)的增广拉格朗日函数为

其中常数α>0． 经典的ADMM算法处理以下两个子问题： 对于固定的y，λ， 在有界约束P上极小化L(x，y，λ)； 对于固定的x，λ， 极小化L(x，y，λ)． 最后， 利用原始残差Ax+By=b更新乘子λ． 由于有界约束的特殊性， 在求解有界非凸子问题上采用梯度投影， 且考虑到f(x)是非凸的， 通过引入一个指数平均(或平滑)方案来生成一个额外的序列{zt}， 并在增广的拉格朗日函数中插入一个额外的以zt为中心的二次近似项， 在保证非凸子问题凸化的同时也能够使得原始迭代点xt不会偏离稳定迭代点太多．

表1 近似交替方向乘子法

注1该算法与传统的ADMM相比的优势在于， 传统的ADMM处理有界约束上的非凸子问题是十分困难的， 一方面是子问题的非凸性， 另一方面则是有界约束的限制， 而采用梯度投影、 引入近似二次项则可以简化子问题的求解， 很好地处理了非凸性和有界约束， 使得算法更加简便， 降低了运算成本．

注2与文献[15]算法相比， P-ADMM是投影算法和ADMM的结合， 主要用于解决有界约束上的可分离的非凸优化问题， 而文献[15]中的算法主要用于解决有界约束上的单块非凸优化模型， 是本文模型的一种特殊情况， 因此P-ADMM的应用性更加广泛．

注3与文献[16]中算法APGMM相比， P-ADMM在解决有界约束上的非凸子问题时不是直接采用的梯度投影， 而是在原本的增广拉格朗日函数上引入了近似二次项， 近似二次项的引入在保证非凸子问题凸化的同时也加快了算法收敛的速度(见数值实验)．

2 收敛性分析

为了更加方便分析P-ADMM的收敛性， 首先给出一些关键的引理．

引理1若假设(I)，(IV)成立， 那么可得

证首先， 通过假设(I)可得

(2)

利用算法关于y在t+1步迭代式的一阶最优性条件可得

∇g(yt+1)+〈B，λt〉+α〈B，Axt+1+Byt+1-b〉=0

再通过算法关于λ在t+1步的迭代式可得∇g(yt+1)=-〈B，λt+1〉， 同理可得

∇g(yt)=-〈B，λt〉

通过假设(IV)可知， 函数g(x)是梯度Lipschitz连续的， 则

‖∇g(yt+1)-∇g(yt)‖=‖BT(λt+1-λt)‖≤L2‖yt+1-yt‖

(3)

引理2若假设(II)成立， 且p+γ>0， 令函数

则下列结论成立：

1) 函数K(x，y，z，λ)关于x是强凸的， 且强凸系数为γk=p+γ， 即

〈∇Kx(x1，y，z，λ)-∇Kx(x2，y，z，λ)，x1-x2〉≥(p+γ)‖x1-x2‖2

其中σ1为矩阵A的最大奇异值．

证对函数K(x，y，z，λ)关于x求梯度， 则

∇Kx(x，y，z，λ)=∇f(x)+ATλ+αAT(Ax+By-b)+p(x-z)

由假设(Ⅱ)知

同理可得

则引理2成立．

接下来， 构造辅助函数

M(xt，yt，yt-1，zt，λt)-M(xt+1，yt+1，yt，zt+1，λt+1)≥

证由算法关于x在t+1步的迭代式及投影定理， 可得

〈xt-c∇xK(xt，yt，zt，λt)-xt+1，xt-xt+1〉≤0

则有

(4)

通过引理2的结论1)， 利用函数K(x，y，z，λ)关于x的凸性， 有

K(xt，yt，zt，λt)-K(xt+1，yt，zt，λt)≥〈∇xK(xt+1，yt，zt，λt)，xt-xt+1〉

(5)

(6)

通过算法关于z在t+1步的迭代式得到

(7)

由假设(III)可知

(8)

利用算法关于y在t+1步迭代式的一阶最优性条件得

∇g(yt+1)+〈B，λt〉+α〈B，Axt+1+Byt+1-b〉=0

再利用算法关于λ在t+2步的迭代式可得

∇g(yt+1)=-〈B，λt+1〉

(9)

结合(8)，(9)式可得

(10)

最后， 通过算法关于λ在t+1步的迭代式可得

M(xt+1，yt+1，yt，zt+1，λt)-M(xt+1，yt+1，yt，zt+1，λt+1)=

再由引理1可得

(11)

将(6)，(7)，(10)，(11)式相加， 则有

M(xt，yt，yt-1，zt，λt)-M(xt+1，yt+1，yt，zt+1，λt+1)≥

故引理3成立．

证首先， 通过完全平方可得

(12)

再利用假设(I)和(IV)， 可得

因此

(13)

将(13)式代入(12)式可得

(14)

(15)

(16)

下面的引理说明， 若算法停止， 则可以找到一对原始对偶解．

引理5若

μ0，v0

进一步简化得到

μ0，v0

我们可得

成立时， 即

则有

(17)

进而可以得到

则有

则有

(18)

通过(17)式可得

则有

这与(18)式矛盾， 则推论1成立．

定理1若假设(I)，(III)和(IV)成立， 序列{ωt}为P-ADMM所产生， 则下列结论成立

证1)由引理3可知

M(xt，yt，yt-1，zt，λt)-M(xt+1，yt+1，yt，zt+1，λt+1)≥

进而可得到

通过定理1可知

则可得

结论1)成立．

2) 由于

结合z的第t+1次迭代式zt+1=zt+β(xt+1-zt)可得

则结论2)成立．

3) 由1)， 2)两个结论可得

结合推论1有

则结论3)成立．

3 数值实验

本文考虑用P-ADMM解决一类非凸的船舶分布式能源管理问题， 在文献[17]中， 考虑具有多个代理的船舶动力系统， 且各代理根据各自的需求、 供给相互协调． 首先将船舶能量管理问题以多智能体系统的形式重新制定， 然后利用交替方向乘子法(ADMM)寻找模型中满足共识要求的最经济的工作点， 本文考虑如下可分非凸光滑的能量成本函数

s． t．x∈M

(19)

其中

M： ={x∈RD|-5.12≤xi≤5.12，i=1，2，…，D}

F(x)为能量成本函数，xi为共识变量，D为该问题的维度， 问题(19)可等价转化成如下问题

s． t．x=y，x∈M

(20)

问题(20)所对应的增广拉格朗日函数为

利用P-ADMM求解问题(20)．

rError=max{‖xt-xt+1‖， ‖yt-yt+1‖， ‖λt-λt+1‖}≤10-8

图1展示了在P-ADMM算法下船舶电力系统能量成本的走势情况， 其中G(xt)+H(yt)为成本函数，t为迭代步． 通过图1可以看出， 能量成本值从开始的下降逐渐趋于稳定， 最后达到收敛． 同时， 观察发现选择较大的β， 会使收敛速度加快， 即算法可以在更小的迭代步数下完成收敛， 减少了算法迭代的次数．

图1 成本函数

图2和图3分别展示了在参数β=0.2的条件下‖xt-yt‖和‖xt+1-zt‖的下降情况， 进一步验证了算法P-ADMM解决问题(20)的可行性． 从图2，3中可知， ‖xt-yt‖和‖xt+1-zt‖一开始下降得非常快， 再逐渐趋于平稳并达到收敛．

图2 ‖xt-yt‖

图3 ‖xt+1-zt‖

图4是基于问题(20)将P-ADMM和APGMM[17]在参数β=0.8的条件下进行了比较． 从图4中可以看到算法P-ADMM相对于算法APGMM在下降趋势和收敛步数上都具有较大的优势． APGMM算法开始迭代是波动的、 不稳定的． 考虑到目标函数的非凸性， 我们在运行算法时， 选取α=100， α=1 000两种情况进行比较． 由图4可知算法P-ADMM的下降速度快， 能够在更小的迭代步达到收敛．

图4 基于问题(20)的算法对比实验

4 结论

本文在梯度投影算法和ADMM基础上， 针对可分结构的非凸优化问题， 提出了一种新的P-ADMM， 该算法具有良好的收敛性， 简化了子问题的求解， 降低了运算成本， 且近似二次项的引入在保证算法的收敛性的同时也能够提升算法的收敛速度． 该算法在一类非凸的船舶能源管理问题中也得到了有效应用． P-ADMM在梯度投影时， 选取的步长是满足条件的定值， 但如何优化梯度投影的步长以提高算法速率需要进一步的研究．