设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投搞
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
AdvancesinAppliedMathematics
应用数学进展
,2020,9(1),60-71
PublishedOnlineJanuary2020inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2020.91008
GaussBackSubstitutionAlternating
DirectionMethodforaClassofInverse
QuadraticProgramming
LidanLi
1,2
,HongweiZhang
1
,LiweiZhang
1
1
SchoolofMathematicalSciences,DalianUniversityofTechnology,DalianLiaoning
2
CollegeofScience,LiaoningTechnicalUniversity,FuxinLiaoning
Received:Dec.25
th
,2019;accepted:Jan.7
th
,2020;published:Jan.14
th
,2020
Abstract
Inthispaper,wesolve theinverseproblemof quadraticprogrammingwhoseobjective
functionisthesumofmatrixspectrumnormandvectorinfinitenorm.Wetransform
theproblemintoa convexoptimization problemwith objective functionseparable and
propose Gaussback substitution alternatingdirectionmethodtosolve it.Wefindthat
oneofitssubproblemsisstillaconvexoptimizationproblemwithobjectivefunction
separable,but itis impossibleto solve every variableaccurately.So weusethe inexact
methodtosolvethesubproblem.Finally,thenumericalexperimentoftheproblem
inthispaperisgiven.Thedatashowsthatthemethodinthispapercansolvethe
inversequadraticprogrammingproblemefficientlyandquickly.
Keywords
SpectrumNorm,InfiniteNorm,QuadraticProgramming,
G
−
ADMM
Method
Gauss
回代交替方向法求解一类二次规划逆问
题
文章引用
:
李丽丹
,
张宏伟
,
张立卫
.Gauss
回代交替方向法求解一类二次规划逆问题
[J].
应用数学进展
,2020,
9(1):60-71.DOI:10.12677/aam.2020.91008
李丽丹等
李丽丹
1,2
,张宏伟
1
,张立卫
1
1
大连理工大学数学科学学院,辽宁大连
2
辽宁工程技术大学理学院,辽宁阜新
收稿日期:
2019
年
12
月
25
日;录用日期:
2020
年
1
月
7
日;发布日期:
2020
年
1
月
14
日
摘要
本文求解了目标函数为矩阵谱范数与向量无穷范数之和的一类二次规划的逆问题。先将该问题转
化为目标函数可分离变量的凸优化问题,提出用
Gauss
回代交替方向法求解该问题。而对于其中
一个子问题的求解过程中发现其仍是目标函数可分离变量的凸优化问题,但无法精确求解每个变
量,所以采用非精确方法求解该子问题。最后给出采用的
Gauss
回代交替方向法求解本文问题的
数值实验。数据表明,本文所采用的方法能够高效快速地解决该二次规划逆问题。
关键词
谱范数,无穷范数,二次规划,
G
−
ADMM
法
Copyright© 2020byauthor(s)andHansPublishersInc.
This work is licensed under theCreative Commons Attribution InternationalLicense (CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.
引言
在本文里,我们考虑如下凸二次规划问题的逆问题:
min
f
(
x
)=
1
2
x
⊤
Gx
+
c
⊤
x
s
.
t
.x
∈
Ω
P
:=
{
x
′
∈
R
n
|
Ax
′
≥
b
}
(1.1)
其中
G
∈S
n
+
,
S
n
定义
n
×
n
对称矩阵空间,
S
n
+
定义了
n
×
n
半正定矩阵锥,
c
∈
R
n
,A
∈
R
m
×
n
,b
∈
R
m
�
令
A
:=(
a
1
,
···
,a
m
)
⊤
,a
i
∈
R
n
,i
=1
,
···
,m,
DOI:10.12677/aam.2020.9100861
应用数学进展
李丽丹等
我们用
SOL
(
P
)
表示问题
(
P
)
的最优解,并且在本文中假设
m
≤
n
。
给定问题
QP
(
G,c,A,b
)
的最优解
x
0
∈
Ω
P
以及
(
G,c
)
的估计值
(
G
0
,c
0
)
∈S
n
×
R
n
。在本文
中考虑的逆二次优化问题是找到一对值
(
G,c
)
∈S
n
+
×
R
n
使
IQP
(
G
0
,A,x
0
,c
0
)
min
∥
G
−
G
0
∥
2
+
∥
c
−
c
0
∥
∞
s
.
t
.x
0
∈
SOL
(
QP
(
G,c,A,b
))
,
(
G,c
)
∈S
n
+
×
R
n
,
(1.2)
其中
∥·∥
2
,
∥·∥
∞
分别表示矩阵的谱范数
(
即矩阵的最大奇异值
)
和向量的无穷范数。
根据传统的对偶理论,如果
G
∈S
n
+
,那么
x
0
∈
SOL
(
QP
(
G,c,A,b
))
的充分必要条件是存在
u
∈
R
m
满足
c
−
A
⊤
u
+
Gx
0
=0
,
0
≤
u
⊥
Ax
0
−
b
≥
0
.
(1.3)
不失一般性,假设前
p
个约束在
x
0
处是有效约束,或者等价写成
I
(
x
0
):=
{
j
|
a
⊤
j
x
0
−
b
j
=0
,j
=
1
,
···
m
}
=
{
1
,
···
p
}
。令
A
0
:=(
a
1
,
···
,a
p
)
⊤
,a
i
∈
R
n
,i
=1
,
···
,p,
即
A
0
是
A
的前
p
行。则
(1.3)
可以等价地表示为
c
−
A
⊤
0
y
+
Gx
0
=0
,
y
≥
0
,
(1.4)
其中
y
∈
R
p
是
u
的前
p
个元素。所以问题
IQP
(
G
0
,A,x
0
,c
0
)
可以被简化为
IQP
(
G
0
,A
0
,x
0
,c
0
)
min
∥
G
−
G
0
∥
2
+
∥
c
−
c
0
∥
∞
s
.
t
.c
−
A
⊤
0
y
+
Gx
0
=0
,
(
G,c,y
)
∈S
n
+
×
R
×
R
p
+
,
(1.5)
下面我们假设问题
(1.5)
有解的前提下来研究利用交替方向法求解它。由于交替方向法适用于目标
函数是可分离的优化问题,记
δ
R
p
+
(
·
)
是
R
p
+
上的指示函数,我们把问题
(1.5)
写成如下可分离形式
min
∥
G
−
G
0
∥
2
+
∥
c
−
c
0
∥
∞
+
δ
R
p
+
(
y
)
s
.
t
.c
−
A
⊤
0
y
+
Gx
0
=0
,
(
G,c,y
)
∈S
n
+
×
R
n
×
R
p
.
(1.6)
本文的组织结构如下:第
2
节给出求逆问题所需要的部分预备知识;第
3
节给出具体求解问
题
(1.6)
的
Gauss
回代方法的算法以及各子问题求解的具体步骤;第
4
节给出
Gauss
回代算法求
DOI:10.12677/aam.2020.9100862
应用数学进展
李丽丹等
解逆问题的数值结果;最后一节为结论。
2.
预备知识
我们需要讨论一下
Moreau-Yosida
正则化的一些性质。设
X
是一个有限维欧氏空间,其内积
⟨·
,
·⟩
X
引导的范数记为
∥·∥
X
.f
:
X7→
(
−∞
,
+
∞
]
是定义在
X
上的闭凸函数,则
f
在
x
∈X
点的
Moreau-Yosida
正则化定义如下:
min
y
∈X
f
(
y
)+
1
2
∥
y
−
x
∥
2
X
.
上述问题的唯一最优解记为
P
f
(
x
)
�
定义
f
的共轭函数
f
∗
(
x
)=
sup
y
∈X
{⟨
x,y
⟩
X
−
f
(
y
)
}
.
由
Moreau
分解理论
[1](
定理
31.5)
可知,对于
∀
x
∈X
,
我们有
x
=
P
f
(
x
)+
P
f
∗
(
x
)
.
(2.1)
如果
f
是范数函数,记
f
=
∥·∥
♮
�
则记
∥·∥
♯
为其对偶范数,定义为
∥
x
∥
♯
=
sup
y
∈X
{⟨
x,y
⟩
X
:
|
y
∥
♮
≤
1
}
,
则有
P
f
∗
(
x
)=Π
B
1
♯
(
x
)
,
其中闭球
B
1
♯
:=
{
x
∈X
:
|
x
∥
♯
≤
1
}
,而
Π
M
(
·
)
是到闭凸集
M
的投影算子,
即
Π
M
(
x
)=
Argmin
y
∈M
1
2
∥
x
−
y
∥
2
X
,
∀
x
∈X
.
则
(2.1)
可以写成
x
=
P
f
(
x
)+Π
B
1
♯
(
x
)
.
(2.2)
或等价为
P
f
(
x
)=
x
−
Π
B
1
♯
(
x
)
.
(2.3)
对于具体的矩阵的核范数,取
ˆ
τ>
0
,
令
f
ˆ
τ
:
R
m
×
n
7→
R
,
即
f
ˆ
τ
(
X
):=ˆ
τ
∥
X
∥
∗
�
函数
f
ˆ
τ
在点
X
∈
R
m
×
n
处
Moreau-Yosida
正则化定义如下:
min
Y
∈
R
m
×
n
f
ˆ
τ
(
Y
)+
1
2
∥
Y
−
X
∥
2
F
.
(2.4)
其中
∥·∥
F
为矩阵的
Frobenius
范数。事实上,矩阵的核范数的对偶函数是谱范数
(
矩阵的奇异值
之和
)
,定义为
∥·∥
2
�
根据
(2.2)
或
(2.3)
知
P
f
ˆ
τ
(
X
)=
X
−
Π
B
ˆ
τ
2
(
X
)
,
(2.5)
DOI:10.12677/aam.2020.9100863
应用数学进展
李丽丹等
其中闭球
B
ˆ
τ
2
定义为
B
ˆ
τ
2
:=
{
X
∈
R
m
×
n
:
∥
X
∥
2
≤
ˆ
τ
}
.
我们要想求解
(2.4)
,关键是如何求解
Π
B
ˆ
τ
2
(
X
)
�
事实上
Π
B
ˆ
τ
2
(
X
)
我们可以由下面两个命题得到。
命题
1.
([2])
x
∈
R
n
,
u
i
=
|
x
i
|
,i
=1
,...,n.
u
1
≥
...
≥
u
n
≥
0
,k
u
k
>z
k
≥
u
k
+1
立,
z
k
=
k
i
=1
u
i
−
ˆ
τ
k
.
C
ˆ
τ
1
:=
{
v
∈
R
n
:
∥
v
∥
1
≤
ˆ
τ
}
,
¯
x
:=Π
C
ˆ
τ
1
(
x
)
�
∥·∥
1
1
,
∥
v
∥
1
=
n
i
=1
|
v
i
|
�
x
∈C
ˆ
τ
1
,
¯
x
=
x
�
¯
x
i
=
sign
(
x
i
)(
u
i
−
z
k
)
,i
≤
k,
0
,i>k.
(2.6)
设
r
=
rank
(
X
)
,X
∈
R
m
×
n
�
令
X
的简化奇异值分解为
X
=
U
r
Diag
(
σ
(
X
))
V
⊤
r
,
(2.7)
其中
σ
(
X
)=(
σ
1
,...,σ
r
)
⊤
满足
σ
1
≥
σ
2
≥
...
≥
σ
r
>
0
,U
r
∈
R
m
×
r
,V
r
∈
R
n
×
r
为列正交阵。则
利用命题
1
和
JohnvonNeumann
迹不等式,如下命题成立。
命题
2.
X
∈
R
m
×
n
(2.7)
,
X
B
ˆ
τ
∗
Π
B
ˆ
τ
∗
(
X
)=
U
r
Diag
(¯
x
)
V
⊤
r
,
¯
x
=Π
C
ˆ
τ
1
(
σ
(
X
))
�
若
f
对应的是向量的无穷范数,令
ˇ
τ>
0
,f
ˇ
τ
:
R
n
7→
R
�
且
f
ˇ
τ
(
x
):=ˇ
τ
∥
x
∥
∞
�
函数
f
ˇ
τ
在点
x
∈
R
n
处
Moreau-Yosida
正则化定义如下:
min
y
∈
R
n
f
ˇ
τ
(
y
)+
1
2
∥
y
−
x
∥
2
.
(2.8)
∥·∥
表示向量的欧式范数。事实上,向量的无穷范数的对偶函数是向量的
1
范数。根据
(2.2)
或
(2.3)
,
同样有
P
f
ˇ
τ
(
x
)=
x
−
Π
B
ˇ
τ
1
(
x
)
,
(2.9)
其中闭球
B
ˇ
τ
1
定义为
B
ˇ
τ
1
:=
{
x
∈
R
n
:
∥
x
∥
1
≤
ˇ
τ
}
�
其中
Π
B
ˇ
τ
1
(
x
)
可由命题
1
得到。
3.Gauss
回代交替方向法求解逆问题
经典的交替方向法
(ADMM)
适用于线性约束目标可分离变量的优化问题,但从收敛性分析上
看
,
有两个变量的可分离变量形式的问题所对应的交替方向法,其收敛性证明可在文献
[3][4][5]
中找到。而对于变量个数超过两个的问题,收敛性分析证明仍然是开放的。而我们的问题
(1.6)
中
DOI:10.12677/aam.2020.9100864
应用数学进展
李丽丹等
的变量是三个,为了保证收敛,我们采用的
Gauss
回代交替方向法
[6]
求解它。
问题
(1.6)
的增广
Lagrange
函数为
L
β
(
G,c,y,λ
)=
∥
G
−
G
0
∥
2
+
∥
c
−
c
0
∥
∞
+
δ
R
p
+
(
y
)
−⟨
λ,c
−
A
⊤
0
y
+
Gx
0
⟩
+
β
2
∥
c
−
A
⊤
0
y
+
Gx
0
∥
2
F
其中
β>
0
是等式约束
c
−
A
⊤
0
y
+
Gx
0
=0
的罚参数,
∥·∥
F
表示矩阵的
Frobenius
范数,
∥·∥
表
示向量的欧式范数。为了方便下面的讨论,我们定义如下的符号以及矩阵
集合
W
:=
S
n
+
×
R
n
×
R
p
×
R
n
,
V
:=
R
n
×
R
p
×
R
n
.
w
=(
G,c,y,λ
)
∈W
,v
=(
c,y,λ
)
∈V
.
矩阵
H
=
Diag
(
βI,βA
0
A
⊤
0
,
1
β
I
)
,M
=
βI
00
−
βA
0
βA
0
A
⊤
0
0
00
1
β
I
,Q
=
βI
−
βA
⊤
0
I
−
βA
0
βA
0
A
⊤
0
−
A
0
I
−
A
⊤
0
1
β
I
.
(3.1)
结合上述矩阵,下面我们给出
Gauss
回代交替方向法的具体步骤。
算法
3.1(G-ADMM)
取定参数
β>
0
,α
∈
[0
,
1)
,
矩阵
M,H
由上述给出,给定当前迭代步
v
k
=(
c
k
,y
k
,λ
k
)
,
则新的迭代
步
w
k
+1
生成如下:
步
1
ADMM
步(预测步)获得
˜
w
k
=(
˜
G
k
,
˜
c
k
,
˜
y
k
,
˜
λ
k
):
˜
G
k
=
Argmin
G
∈S
n
+
{∥
G
−
G
0
∥
2
+
β
2
∥
c
k
−
A
⊤
0
y
k
+
Gx
0
−
λ
k
β
∥
2
}
(3.2)
˜
c
k
=
Argmin
c
∈
R
n
{∥
c
−
c
0
∥
∞
+
β
2
∥
c
−
A
⊤
0
y
k
+
˜
G
k
x
0
−
λ
k
β
∥
2
}
(3.3)
˜
y
k
=
Argmin
y
∈
R
p
+
{
β
2
∥
˜
c
k
−
A
⊤
0
y
+
˜
G
k
x
0
−
λ
k
β
∥
2
}
(3.4)
˜
λ
k
=
λ
k
−
β
(˜
c
k
−
A
⊤
0
˜
y
k
+
˜
G
k
x
0
)
(3.5)
步
2
Gauss
回代步(矫正步)
G
k
+1
=
˜
G
k
,
v
k
+1
=
v
k
−
αM
−⊤
H
(
v
k
−
˜
v
k
)
.
注解
1.
(1)
,
Gauss
,
[6]
;
v
k
+1
=
v
k
−
γα
∗
k
M
−⊤
H
(
v
k
−
˜
v
k
)
,
(3.6)
其中
γ
∈
(0
,
2)
,
α
∗
k
=
∥
v
k
−
˜
v
k
∥
2
H
+
∥
v
k
−
˜
v
k
∥
2
Q
2
∥
v
k
−
˜
v
k
∥
2
H
.
(2)
便于理论分析,我们固定参数
β
。关于动态调整
β
,见文献
[7][8]
。
(3)
算法的收敛性分析见
[6]
,这里不再赘述。
DOI:10.12677/aam.2020.9100865
应用数学进展
李丽丹等
3.1.
非精确求解子问题
(3.2)
子问题
(3.2)
可知是下述问题的最优解
min
∥
Y
∥
2
+
β
2
∥
b
k
+
Gx
0
∥
2
s
.
t
.G
−
G
0
=
Y,
G
≽
0
(3.7)
其中记
b
k
:=
c
k
−
A
⊤
0
y
k
−
λ
k
/
β.
我们注意到问题
(3.7)
是一个目标函数可分离的凸规划问题,且其
未知变量为两个,所以可以采用经典的交替方向法求解。此问题与
[9]
中求解问题非常相似,所以
我们也采用它的求解方法。问题
(3.7)
的增广
Lagrange
函数
L
ρ
(
Y,G,
Ξ)=
∥
Y
∥
2
+
ρ
2
∥
b
k
+
Gx
0
∥
2
−⟨
Ξ
,G
−
G
0
−
Y
⟩
+
ρ
2
∥
G
−
G
0
−
Y
∥
2
F
其中
ρ
是对应等式约束的罚参数。同样给出其交替方向法的迭代形式:
Y
l
+1
=
Argmin
{∥
Y
∥
2
+
ρ
2
∥
G
l
−
G
0
−
Y
−
Ξ
l
ρ
∥
2
F
}
(3.8)
G
l
+1
=
Argmin
G
∈S
n
+
{∥
Gx
0
+
b
k
∥
2
+
ρ
2
∥
G
−
(
G
0
+
Y
l
+1
+
Ξ
l
ρ
)
∥
2
F
}
(3.9)
Ξ
l
+1
=Ξ
l
−
ρ
(
G
l
+1
−
Y
l
+1
−
G
0
)
.
(3.10)
对于
(3.8)
,令
¯
Y
:=
G
l
−
G
0
−
Ξ
l
/
ρ.
由预备知识的公式
(2.4)
中的可得
Y
l
+1
=
¯
Y
−
Π
B
1/
ρ
∗
(
¯
Y
)
,
(3.11)
其中
Π
B
1/
ρ
∗
(
·
)
为到闭球
B
1/
ρ
∗
:=
{
X
∈
R
m
×
n
|∥
X
∥
∗
≤
1/
ρ
}
内的投影算子。
关于
(3.9)
,我们注意到其没有显示解,所以讨论其非精确求解。为保证解的稳定性,通常对
相应子问题进行加二次临近正则化项的正则化处理,即考虑如下极小值问题
G
l
+1
=
Argmin
G
∈S
n
+
{
β
2
∥
Gx
0
+
b
k
∥
2
+
ρ
2
∥
G
−
(
G
0
+
Y
l
+1
+
Ξ
l
ρ
)
∥
2
F
+
1
2
τ
∥
G
−
G
l
∥
2
F
}
(3.12)
其中
1/
τ>
0
为正则化临近参数。为了方便讨论,记
(3.12)
中的目标函数为
f
(
G
)
�
则
f
(
G
)
关于
G
的梯度为
∇
f
(
G
)=
β
2
(
Gx
0
+
b
k
)
x
0
⊤
+
x
0
(
Gx
0
+
b
k
)
⊤
+
ρ
G
−
(
G
0
+
Y
l
+1
+
Ξ
l
ρ
)
+
1
τ
(
G
−
G
l
)
(3.13)
令
G
l
+1
exact
为带正则化项子问题
(3.12)
的精确解,则有
G
l
+1
exact
满足投影方程
G
l
+1
exact
=
P
S
n
+
G
l
+1
exact
−
τ
∇
f
(
G
l
+1
exact
)
.
DOI:10.12677/aam.2020.9100866
应用数学进展
李丽丹等
值得注意的是,对于非精确标准的选取,应当考虑在具体计算中容易执行的不包含精确解
G
l
+1
exact
信息的非精确标准。为此本文选取
[10]
中给出的非精确标准来计算近似解
G
l
+1
。其方法是引入误
差项
ξ
l
G
,使得近似解满足新的带误差项
ξ
l
G
的投影方程
G
l
+1
=Π
S
n
+
G
l
+1
−
τ
∇
f
(
G
l
+1
)+
ξ
l
G
(3.14)
其中误差项
ξ
l
G
满足
[10]
中给的下列两种非精确标准之一,
绝对误差标准:
∥
ξ
l
G
∥
F
≤
ε
l
,
其中
∞
0
ε
l
<
+
∞
,
(3.15)
或
相对误差标准:
∥
ξ
l
G
∥
F
≤
ε
l
∥
G
l
+1
−
G
l
∥
F
,
其中
∞
0
ε
2
l
<
+
∞
.
(3.16)
我们选择按照如下方式求解满足
(3.15)
或
(3.16)
的误差项
ξ
l
G
和近似解
G
l
+1
。非精确迭代方法的基
本思想是在某种适当的非精确标准下寻求
G
l
+1
exact
的近似解,记为
G
l
+1
。首先选择一个收敛到精确
解
G
l
+1
exact
的近似序列
{
G
l
+1
j
}
�
即
G
l
+1
j
→
Π
S
n
+
G
l
+1
j
−
τ
∇
f
(
G
l
+1
j
)
,
当
j
→∞
.
(3.17)
定义新的序列
˜
G
l
+1
j
:=Π
S
n
+
G
l
+1
j
−
τ
∇
f
(
G
l
+1
j
)
.
(3.18)
由
(3.17)
知道,
G
l
+1
j
−
˜
G
l
+1
j
→
0
,
当
j
→∞
.
(3.19)
进而对于任意给定的
ε
l
�
存在整数
i
k
+1
,使得当
j>i
k
+1
时,恒有
∥
τ
∇
f
(
˜
G
l
+1
j
)
−
τ
∇
f
(
G
l
+1
j
)+
G
l
+1
j
−
˜
G
l
+1
j
∥
F
≤
ε
l
(3.20)
或者
∥
τ
∇
f
(
˜
G
l
+1
j
)
−
τ
∇
f
(
G
l
+1
j
)+
G
l
+1
j
−
˜
G
l
+1
j
∥
F
≤
ε
l
∥
G
l
+1
j
−
˜
G
l
+1
j
∥
F
.
(3.21)
事实上
(3.18)
可以写成
˜
G
l
+1
j
=Π
S
n
+
˜
G
l
+1
j
−
τ
∇
f
(
˜
G
l
+1
j
)+
τ
∇
f
(
˜
G
l
+1
j
)
−
τ
∇
f
(
G
l
+1
j
)+
G
l
+1
j
−
˜
G
l
+1
j
.
(3.22)
定义误差项
ξ
l
G
:=
τ
∇
f
(
˜
G
l
+1
j
)
−
τ
∇
f
(
G
l
+1
j
)+
G
l
+1
j
−
˜
G
l
+1
j
=
τβ
2
(
˜
G
l
+1
j
−
G
l
+1
j
)
x
0
x
0
⊤
+
x
0
((
˜
G
l
+1
j
−
G
l
+1
j
)
x
0
)
⊤
+
τρ
(
˜
G
l
+1
j
−
G
l
+1
j
)
.
(3.23)
判断误差项
ξ
l
G
是否满足
(3.20)
,其中
∞
0
ε
l
<
+
∞
或者
(3.21)
,其中
∞
0
ε
2
l
<
+
∞
.
如果一个成
DOI:10.12677/aam.2020.9100867
应用数学进展
李丽丹等
立,则停止迭代,并记
G
l
+1
:=
˜
G
l
+1
j
�
基于以上分析,我们采用非精确交替方向法求解子问题
(3.7)
,而其子问题
(3.8)
解
Y
可以给出
具体解析表达式,而
(3.9)
的解
G
每次迭代都只需求一个满足
(3.15)
或
(3.16)
的近似解即可。下面给
出求解问题
(3.7)
的非精确交替方向法的迭代格式,参见
[9]
。
算法
3.2
(
部分非精确算法求解子问题
(3.7))
。
取定参数
ρ>
0
,τ>
0
和常数
ε
l
满足
(3.15)
或
(3.16)
,给定当前迭代步
(
Y
l
,G
l
,
Ξ
l
)
,
则
(
Y
l
+1
,G
l
+1
,
Ξ
l
+1
)
生成如下:
步
1
按照
(3.11)
计算
Y
l
+1
�
步
2
计算
G
l
+1
使其满足投影方程
G
l
+1
=
P
S
n
+
G
l
+1
−
τ
∇
f
(
G
l
+1
)+
ξ
l
G
�
其中
ξ
l
G
满足非精确标准
(3.15)
或
(3.16)
。
步
3
Ξ
l
+1
=Ξ
l
−
ρ
(
G
l
+1
−
Y
l
+1
−
G
0
)
�
显然,算法
3.2
的有效性取决于快速地求解
Y
和
G
子问题,因为
Y
子问题可以精确求解
,
故算法
3.2
的关键是选取快速的内迭代求解
G
子问题以获取满足非精确标准的近似解
G
l
+1
。注
意到对于带正则项的
G
子问题
(3.12)
,其实质是一个标准的
Frobenius
范数下结构约束矩阵最小
二乘问题.我们选择谱投影梯度算法
(SPG)[11]
求近似解
G
l
+1
,利用
SPG
算法在非精确标准
(3.15)
或
(3.16)
下计算
(3.12)
的近似解
G
l
+1
和
ξ
l
G
的迭代格式如下:
算法
3.3
(SPG
算法在非精确标准
(3.15)
或
(3.16)
下计算
(3.12)
的近似解
G
l
+1
和
ξ
l
G
)
。
步
1
输入正整数
¯
M>
1
,参数
α
min
>
0
α
max
>α
min
,γ
∈
(0
,
1)
,
以及
0
<σ
1
<σ
2
<
1
.
任取
α
0
∈
[
α
min
,α
max
]
,
并取算法
1
中的第
l
步
G
l
作为初始矩阵,即令
G
0
=
G
l
,
并令
j
←
0
�
步
2
计算
D
j
=
P
S
n
+
(
G
j
−
α
j
∇
f
(
G
j
))
−
G
j
,
并令
λ
←
1
。
步
3
计算
ˆ
G
=
G
j
+
λD
j
�
步
4
若
f
(
ˆ
G
)
≤
max
0
≤
t
≤
min
{
j,
¯
M
−
1
}
f
(
G
j
−
t
)+
γλ
⟨
D
j
,
∇
f
(
G
j
)
⟩
,
(3.24)
则令
G
j
+1
=
ˆ
G,s
j
=
G
j
+1
−
G
j
,y
j
=
∇
f
(
G
j
+1
)
−∇
f
(
G
j
)
,
进入步
5
;否则定义
λ
new
∈
{
σ
1
λ,σ
2
λ
}
,λ
←
λ
new
,
返回步
3
。
步
5
计算
b
j
=
⟨
s
j
,y
j
⟩
,
若
b
j
≤
0
,
则令
α
j
+1
=
α
max
;
否则计算
a
j
=
⟨
s
j
,s
j
⟩
和
α
j
+1
=
min
{
α
max
,
max
{
α
min
,a
j
/
b
j
}}
,
并令
j
←
j
+1
�
步
6
令
˜
G
j
=
P
S
n
+
(
G
j
−
τ
∇
f
(
G
j
))
,ξ
l
G
=
τ
∇
f
(
˜
G
j
)
−
τ
∇
f
(
G
j
)+
G
j
−
˜
G
j
,
若
∥
ξ
l
G
∥
F
≤
ε
l
成立,其中
∞
l
=0
ε
l
<
+
∞
;
或者
∥
ξ
l
G
∥
F
≤
ε
l
∥
G
l
−
˜
G
j
∥
F
,
其中
∞
l
=0
ε
2
l
<
+
∞
,
则终止迭代并令
G
l
+1
=
˜
G
j
�
否则返回到步
2
。
该算法的收敛性分析参看
[9]
,这里不再详述。算法
3.2
的收敛准则标准取为
max
∥
Y
l
+1
−
Y
l
∥
F
,
∥
G
l
+1
−
G
l
∥
F
,
∥
G
l
−
G
0
−
Y
l
+1
∥
F
≤
ε,
DOI:10.12677/aam.2020.9100868
应用数学进展
李丽丹等
其中
ε
为预设的精度。
3.2.
求解子问题
(3.3)
记
c
′
=
c
−
c
0
,
¯
c
=
A
⊤
0
y
k
−
˜
G
k
x
0
−
λ
k
β
−
c
0
,
则子问题
(3.3)
另写为
˜
c
k
=
Argmin
c
′
∈
R
n
{∥
c
′
∥
∞
+
β
2
∥
c
′
−
¯
c
∥
2
}
+
c
0
.
由预备知识中的公式
(2.2)
或
(2.3)
可知
Argmin
c
′
∈
R
n
{∥
c
′
∥
∞
+
β
2
∥
c
′
−
¯
c
∥
2
}
=¯
c
−
Π
B
1/
ρ
1
(¯
c
)
,
其中
Π
B
1/
ρ
1
(
·
)
为到闭球
B
1/
ρ
1
:=
{
x
∈
R
n
|∥
x
∥
1
≤
1/
ρ
}
内的投影算子。而
Π
B
1/
ρ
1
(
·
)
的具体计算由命
题
1
得。
3.3.
求解子问题
(3.4)
˜
y
k
本质是下述问题的最优解
min
β
2
∥
˜
c
k
−
A
⊤
0
y
+
˜
G
k
x
0
−
λ
k
β
∥
2
s
.
t
.y
≥
0
为了方便,记
N
k
:=˜
c
k
+
˜
G
k
x
0
−
λ
k
β
,Q
0
:=
A
0
A
⊤
0
如果
A
0
是行满秩矩阵,则
˜
y
k
是下述简单凸二
次规划问题的解
min
f
k
:=
1
2
y
⊤
Q
0
y
−⟨
A
0
N
k
,y
⟩
s
.
t
.y
≥
0
(3.25)
我们只需利用
matlab
自带的函数
quadprog
求解此问题即可。
4.
数值实验
本节给出利用算法
3.1
求解逆问题
(1.6)
的数值实验。验的测试环境为
Win7
旗舰版操作系统,
存
4.0G
,频
3.40Hz,MATLABR2014a
。
1.
初始参数
A
0
∈
R
p
×
n
,c
0
∈
R
n
,G
0
∈S
n
均为随机生成
,
x
0
=
ones
(
n,
1)
。
2.
初始点的选取为
c
1
=
zeros
(
n,
1)
,
y
1
=
ones
(
p,
1)
,
λ
1
=
zeros
(
n,
1)
.
DOI:10.12677/aam.2020.9100869
应用数学进展
李丽丹等
3.
算法
3.1
的终止准则为
stopc
=
max
{
∥
G
k
+1
−
G
k
∥
F
∥
G
k
∥
F
+1
,
∥
c
k
+1
−
c
k
∥
1
∥
c
2
−
c
1
∥
1
,
∥
y
k
+1
−
y
k
∥
1
∥
y
2
−
y
1
∥
1
}≤
ϵ,
ϵ
为预设精度,实验中取
ϵ
=10
−
4
。
4.
β
=5
。
表
1
中各个变量说明:
p
,
n
表示矩阵
A
0
的行数和列数,
time
(
s
)
和
iter
分别表示算法
1
的运
行的时间和迭代次数,
res
表示终止准则
stopc
的最终值。
Table1.
Numericalresultsofalgorithms3.1
表
1.
算法
3.1
的数值结果
pntime(s)iterres
20208.36460.925e
−
04
205025.02360.873e
−
04
5050126.63380.569e
−
04
50100545.24670.654e
−
04
1001001134.14980.176e
−
04
1002002197.03310.54e
−
04
2002006231.06420.427e
−
04
5.
结论
本文求解了一类二次规划逆问题,该问题可转化为目标函数可分离变量的线性约束问题,由
于其未知变量超过两个,为了保证收敛性,故采用
Gauss
回代交替方向法求解,最后给出数值实
验,从数值实验中我们可以看出,法
3.1
对于求解本文提出的二次规划逆问题
(1.2)
在维数不是很
高的情况下还是非常有效的。
参考文献
[1]Rockafellar,R.T.(1970)ConvexAnalysis.PrincetonUniversityPress,Princeton.
https://doi.org/10.1515/9781400873173
[2]John, D.,Shai, S.S.,Yoram, S.,
et al.
(2008) EfficientProjections onto the
ℓ
1-Ball for Learning
inHighDimensions.
Proceedingsofthe25thInternationalConferenceonMachineLearning
,
Helsinki,Finland,July2008,272-279.
[3]Boyd,S.,Parikh,N.,Chu,E.,Peleato,B.andEckstein,J.(2011)DistributedOptimization
andStatisticalLearningviatheAlternatingDirectionMethodofMultipliers.
Foundations
andTrendsinMachineLearning
,
3
,1-122.https://doi.org/10.1561/2200000016
DOI:10.12677/aam.2020.9100870
应用数学进展
李丽丹等
[4]Eckstein,J.andBertsekas,D.P.(1992)OntheDouglas—RachfordSplittingMethodandthe
Proximal Point AlgorithmforMaximalMonotoneOperators.
MathematicalProgramming
,
55
,
293-318.https://doi.org/10.1007/BF01581204
[5]Gabay,D.andMercier,B.(1976)ADualAlgorithmforthe SolutionofNonlinearVariational
ProblemsviaFiniteElementApproximation.
ComputersMathematicswithApplications
,
2
,
17-40.https://doi.org/10.1016/0898-1221(76)90003-1
[6]He,B.,Tao,M.andYuan,X.(2012)AlternatingDirectionMethodwithGaussianBack
SubstitutionforSeparableConvexProgramming.
SIAMJournalonOptimization
,
22
,313-
340.https://doi.org/10.1137/110822347
[7]He,B.,Wang,S.andYang,H.(2003)AModifiedVariable-PenaltyAlternatingDirections
MethodforMonotoneVariationalInequalities.
JournalofComputationalMathematics
,
21
,
495-504.
[8]He,B.S.,Yang,H.andWang,S.L.(2000)AlternatingDirectionMethodwithSelf-Adaptive
PenaltyParametersforMonotoneVariationalInequalities.
JournalofOptimizationTheory
andApplications
,
106
,337-356.https://doi.org/10.1023/A:1004603514434
[9]
李姣芬
,
宋丹丹
,
李涛
,
等
.
核范数和谱范数下广义
Sylvester
方程最小二乘问题的有效算法
[J].
计算数学
,2017,39(2):129-150.
[10]Ng,M.K.,Wang,F.andYuan,X.(2011)InexactAlternatingDirectionMethodsforImage
Recovery.
SIAMJournalonScientificComputing
,
33
,1643-1668.
https://doi.org/10.1137/100807697
[11]Birgin,E.G.,Mario,J.andRaydan,M.M.(2000)NonmonotoneSpectralProjectedGradient
MethodsonConvexSets.
SIAMJournalonOptimization
,
10
,1196-1211.
https://doi.org/10.1137/S1052623497330963
DOI:10.12677/aam.2020.9100871
应用数学进展