基于近端算法的DC规划解球面约束下四次型极小化问题

2024-04-22舒杭,王洁

杭州电子科技大学学报(自然科学版) 2024年1期

舒杭,王洁

(1.杭州电子科技大学理学院,浙江杭州 310018;2.中国计量大学理学院,浙江杭州 310018)

0 引言

四次型极小化问题是张量逼近和多项式优化的交叉部分,是一类特殊的多项式优化问题。此问题有很多来源,并且在实际中有着广泛应用,许多实际问题的模型可表达为此形式,如图的稳定集问题、四阶张量的最佳秩一逼近问题、量子物理中的几何度量、光谱超图理论、扩散峰医学成像等。Aittomaki等[1]考虑波束优化问题并将其建模为多元四次型极小化模型。Aubry等[2]通过优化取实值的四次极小化模型来求解雷达信号问题。Mariere等[3]提出四次多项式优化模型并将其应用于数字通信的研究。

对于球面约束下的四次型极小化问题,可使用扩展的数值线性代数中的方法,例如对称移位高阶幂法(SS-HOPM),并且可以建立这种方法的良好性质。然而,采用一般非线性优化技术无法得出计算解的质量。特别是,我们无法判断计算解的全局最优性。对于能判断解的最优性的SDP松弛方法,却无法处理大规模问题。因此,我们对问题进行一些转化,使得重构后的问题变为两个凸函数的差的形式,此时就能采用DC算法来求解。但是该算法子问题的难度很大程度上取决于DC分解的选择,一般情况下子问题还需要借助于其他算法来求解,比如加速近端梯度(APG)算法,这也是DC算法的一个缺陷。我们根据近端算法,对DC算法进行一定改造,使得可以在DC算法的外框架上使用APG,简化子问题的求解,使得子问题不再需要借助于其他算法,我们将该方法根据加速方案的选择分别记为pDCA和aDCA。实验结果表明,此方法相较于对称移位高阶幂法和一般的DCA方法,在计算时间以及解的质量方面都得到了很大的提升。

1 问题描述及转化

张量是基于标量和矢量向更高维度的推广,标量和矢量都是张量的特殊情况,即标量和矢量分别是零阶张量和一阶张量。

(1)

s=i1+(i2-1)n,t=i3+(i4-1)n。

(2)

再将变量从向量转化为矩阵。令X=xxT,此时目标函数等价于〈AX,X〉。此时约束条件中还有变量未进行变换。

定理1[5]令x∈Rn,则集合

U={x|x∈Rn,xTx=1}

等价于集合

V={X|X=xxT,X≥0,〈I,X〉=1,rank(X)=1},

其中〈I,X〉=trace(X),X≥0表示矩阵为半正定矩阵,rank(X)表示为X的秩。

根据定理1,我们可以将对x的约束条件转化为对X的约束条件。此时问题形式如下:

min〈AX,X〉 s.t.X≥0, 〈I,X〉=1,rank(X)=1,

(3)

(4)

因为矩阵A是n2×n2的实对称矩阵,则可将矩阵A对角化,对应的正交矩阵设为Q。形式如:A=QTΛQ,其中Λ是由矩阵A特征值构成的对角矩阵。显然我们能将Λ拆分为两个正定的对角矩阵的差的形式,即Λ=Λ1-Λ2。设B=QTΛ1Q,C=QTΛ2Q。则〈AX,X〉=〈BX,X〉-〈CX,X〉。此时问题(4)的求解与以下问题的求解是等价的:

(5)

(6)

(7)

最终问题(7)等价于:

ming(X)-h(X) s.t.X∈Rn×n,

(8)

我们记P(X)=g(X)-h(X),那么P(X)即为所求目标函数。

2 pDCA以及aDCA

对于优化问题ming(X)-h(X),DC算法的一般迭代格式是在每一次迭代的过程中利用次微分对目标函数的凹部分进行线性近似,从而得到一个目标函数的凸近似。即:

其中λt∈∂h(Xt)。

对问题(8)使用以上迭代形式,此时我们得到pDCA的子问题形式为:

(9)

基于以上讨论,现在给出pDCA的主要步骤:

Input:给定一个四阶实对称张量,选定初始点X0∈Ω,并设置X-1=X0输入惩罚参数,{βt}⊆[0,1); for t=0,1,2,… 取ξt=2CXt+ρΓt,Γt∈∂Xtσ, 令Yt=Xt+βt(Xt-Xt-1), Xt+1=argminX∈Rn×n<2BYt-ξt,X>+L2X-Yt2+δΩ(X) =PΩYt-1L[2BYt-ξt] , end for