求解绝对值方程稀疏解的增广拉格朗日方法

孙敏,田茂英

(1.枣庄学院 数学与统计学院,山东 枣庄 277160;2.山东煤炭卫生学校,山东 枣庄 277160)

考虑如下绝对值方程的稀疏解问题:

(1)

其中x∈Rn,A∈Rn×n,b∈Rn,‖x‖0表示x的l0-范数,|x|表示对x的每个分量取绝对值.

如果将问题(1)的目标函数去掉,则问题(1)退化成经典的绝对值方程问题,因此问题(1)的研究范围比绝对值方程更广泛:如果绝对值方程有唯一解,则该唯一解也是问题(1)的最优解;如果绝对值方程有多重解,则问题(1)可以求出其中最稀疏的解,即零元素最少的解.

近年来,绝对值方程逐渐成为优化领域的一个研究热点.目前相关研究内容主要是其解存在的充分条件与具体的求解算法.在解的存在性条件方面的成果包括:Mangasarian给出了多种绝对值方程无解、唯一解或多重解的条件[13];雍龙泉给出了一个绝对值方程存在唯一解的条件[4].在求解算法方面的成果可以分为连续算法与离散算法,其中连续算法包括各类神经网络方法[5,6];离散算法包括各种迭代算法,比如不动点迭代法[4]、牛顿类迭代法[3],SOR类迭代法[7,8]等.最近几年,关于绝对值方程的一些研究成果已经被推广到张量形式的绝对值方程[9,10].

目前国内外对绝对值方程稀疏解问题的研究还比较少,主要研究成果包括:廖芸等[11]最早给出了求解绝对值方程稀疏解的两类方法,其中一类是将该问题转换成松弛为l1-范数优化问题,然后再继续转化为线性规划问题,另一类是利用一个凹函数来逼近l0-范数,并对该凹函数进行线性化,再通过求解一系列线性规划问题来求解问题(1).王鹏等[12]借助prox算子,提出了求解问题(1)的松弛形式的不动点算法.基于不动点方程,张晓敏[13]设计了一类神经网络算法来求解问题(1)的松弛形式.

本文继续研究问题(1)的数值算法.借鉴压缩感知模型的转换思想,首先将问题(1)的目标函数松弛为决策变量的l1-范数.再结合增广拉格朗日方法,将松弛问题转化成4块可分离的凸规划问题,进而设计了一类预估-校正格式的增广拉格朗日方法.与类似方法相比,本文设计的方法充分利用了迭代的最新信息,对决策变量采用交替、并行混合更新策略,同时校正步的步长取值范围更大.

1 凸优化模型

与压缩感知模型相比,问题(1)的约束中多了一项|x|,这也是其名称中“绝对值”的来历.受压缩感知模型的启发,将问题(1)松弛为如下形式

(2)

其中‖x‖1表示x的l1-范数,即元素绝对值的和.令y=|x|,得问题(2)的等价形式

(3)

对问题(3)的约束进行松弛,得线性规划问题

(4)

虽然问题(4)是问题(3)的松弛形式,但是由于目标函数的作用,问题(2)(3)与(4)是等价的.

继续将问题(4)的不等式约束改写成等式约束.为此,引入松弛变量u,v∈Rn,得

(5)

其中e=[1,1,…,1]T∈Rn.显然问题(5)属于如下4块可分离凸规划问题

(6)

显然矩阵Ai(i=1,2,3,4)都是列满秩的.

2 增广拉格朗日方法

本节设计一类求解4块可分离凸规划(6)的增广拉格朗日方法,并分析其全局收敛性.问题(6)的增广拉格朗日函数是

其中β>0是罚参数,λ∈R3n是拉格朗日乘子.

θ(w)-θ(w*)+(w-w*)TF(w)≥0,∀w∈W,

(7)

(w-w')T(F(w)-F(w'))=0,∀w,w'∈R7n.

(8)

基于前面的分析,下面给出求解问题(6)的增广拉格朗日方法.

算法:增广拉格朗日方法

(9a)

(9b)

(9c)

(9d)

(9e)

步3(收敛性检验)如果

步4(校正步)按下面的格式得到新的迭代点wk+1:

(10)

令k=k+1,返回第2步.

证明 对于任意的w∈W,由(9a)-(9d)的一阶最优性条件得

结合(9e),上面的4个不等式可以改写成

(11)

其中

如果引理的条件成立,则由(11)得

基于引理1、(8)与(11),类似于[14]引理3、引理4与定理1的证明,下面的结论成立.

引理2对于问题(7)的任意解w*,算法生成的点列满足

其中

引理3对于问题(7)的任意解w*,算法生成的点列满足

其中

本节最后给出算法求解问题(6)的具体迭代格式.关键是(9)的前4个最优化子问题的求解.结合问题(6)的特殊结构,利用(9)可得

其它步骤都是显式迭代,不再列出.

3 数值实验

本节给出一个利用算法求绝对值方程稀疏解的实验.所有实验都是利用MATLABR2014a编程实现的.

考虑问题(2),其中

这个问题有两个可行解

显然x1是问题(2)的最优解.初始状态的分量都取为1,β=1.仿真结果绘制在图1中,其中横坐标为迭代次数,纵坐标是算法产生的点列与最优解之间的距离.

图1 算法的仿真结果

由图1可以看出,算法成功求解了该问题.一开始收敛速度比较快,到迭代次数超过1600之后,算法趋于平稳,最后稳定在大约10-5.

4 小 结

本文设计了一个求解绝对值方程稀疏解的增广拉格朗日方法.该方法采用预估-校正格式,在预估步,采用增广拉格朗日方法迭代格式,在校正步采用常步长,其中常步长的取值范围大于其它类似的方法.数值实验表明该方法可以求解绝对值方程的稀疏解,但是求解速度不快,下一步将研究加速增广拉格朗日方法.