一种基于M范数惩罚项的线性化ADMM算法.pdf

Advances in Applied Mathematics 应用数学进展应用数学进展,2024,13(4),1637-1642 Published Online April 2024 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2024.134155 文章引用文章引用:王博冉.一种基于 M 范数惩罚项的线性化 ADMM 算法J.应用数学进展,2024,13(4):1637-1642.DOI:10.12677/aam.2024.134155 一种基于一种基于M范数惩罚项的线性化范数惩罚项的线性化ADMM算法算法 王博冉王博冉 中央民族大学理学院，北京 收稿日期：2024年3月25日；录用日期：2024年4月22日；发布日期：2024年4月29日 摘摘 要要 ADMM算法是求解两块可分凸优化问题的经典算法，主要思想是在增广拉格朗日乘子法的基础上，利用算法是求解两块可分凸优化问题的经典算法，主要思想是在增广拉格朗日乘子法的基础上，利用目标函数关于两块变量的可分性，降低了求解子问题的计算难度。当增广拉格朗日函数中的惩罚项是目标函数关于两块变量的可分性，降低了求解子问题的计算难度。当增广拉格朗日函数中的惩罚项是M范数时，求解子问题往往较为困难。因此，我们在增广拉格朗日函数的基础上，通过增加一个半正定或范数时，求解子问题往往较为困难。因此，我们在增广拉格朗日函数的基础上，通过增加一个半正定或正定的临近项，将正定的临近项，将M范数的惩罚项变为范数的惩罚项变为2范数的惩罚项，这样，就可以很快得到子问题的闭形式解。该方范数的惩罚项，这样，就可以很快得到子问题的闭形式解。该方法同时具备弱化的惩罚项的条件和半正定临近项的优势，具有更广的适用性和更高的求解效率。这种改法同时具备弱化的惩罚项的条件和半正定临近项的优势，具有更广的适用性和更高的求解效率。这种改进的新算法可以看成临近点算法，它的收敛性易于分析，且无需要较强的假设条件。实验结果表明，新进的新算法可以看成临近点算法，它的收敛性易于分析，且无需要较强的假设条件。实验结果表明，新算法和其他几种主流的高效算法相比，新算法是可行的。算法和其他几种主流的高效算法相比，新算法是可行的。关键词关键词 变分不等式，交替方向乘子法，临近点算法，全局收敛性变分不等式，交替方向乘子法，临近点算法，全局收敛性 A Linearized ADMM Algorithm Based on M-Norm Penalty Terms Boran Wang College of Science,Minzu University of China,Beijing Received:Mar.25th,2024;accepted:Apr.22nd,2024;published:Apr.29th,2024 Abstract The ADMM algorithm is a conventional strategy for solving two separable convex optimization problems.Its fundamental idea is to use the objective function on the basis of augmented Lagrangian multiplier method,reducing the computing burden of addressing subproblems.When the penalty term in the augmented Lagrangian function is M-norm,it is generally more difficult to solve subprob-lems.As a consequence of augmented Lagrange function,we shift the penalty term of the M-norm to the penalty term of the 2-norm by adding a semipositive definite or positive definite proximity 王博冉 DOI:10.12677/aam.2024.134155 1638 应用数学进展 term,allowing us to rapidly find the closed form solution of the subproblem.This approach has the advantages of a weaker penalty term and a semipositive definite proximity term,which allows for a broader range of applications.This improved new algorithm can be viewed as a proximity point algorithm,which is easy to analyze in terms of convergence and does not require strong assumptions.Experimental results show that the new algorithm is feasible compared to several other mainstream efficient algorithms.Keywords Variational Inequality,Alternating Direction Method of Multipliers,Proximity Point Algorithm,Global Convergence Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 本文考虑如下具有线性约束的可分凸优化问题：()()min,f xg y AxByb xX yY+=(1)其中1nfRR：和2ngRR：是凸函数(但不一定光滑)，121,m nm nnmARBRbRXR和2nYR是闭凸集。众所周知，交替方向乘子法是求解(1)的有效方法，该方法最早由 Gabay 和 Mercier，Glowinski 1以及 Marrocco 2提出，该方法是一种求解具有可分离的凸优化问题的重要方法，由于其收敛速度快、收敛性能好，在求解可分离凸优化问题上具有简单、灵活、实用性强的特点，可以将大规模问题拆分成两个甚至多个小规模的子问题，随后交替求解各个小规模子问题，从而提高了求解的速率，其优势在于利用对偶上升算法的可分离性，后来被广泛研究与应用。为了提高 ADMM 的适用性，一些学者提出了许多改进的 ADMM 方法。He 等人在文献3中提出了不定临近线性化 ADMM。Gao 4提出了如下一个带不定临近正则项的线性化 ADMM。Fang 5将增广Lagrange 函数中的惩罚项采用 M-范数，M 是一个是对称正定矩阵。将 2-范数形式改进为 M-范数形式，弱化了惩罚项的条件。因为 2-范数形式的惩罚项是矩阵范数 M-范数的一种特殊形式，所以 M-范数的使用范围更广。基于上述讨论，本文结合半正定临近项和基于 M-范数的惩罚项，提出了一种求解可分凸优化问题(1)的基于 M-范数惩罚项的带半正定临近项的线性化 ADMM 算法。新方法在 y-子问题中引入了一个半正定临近项，进而将 M-范数惩罚项转化为 2 范数惩罚项。该方法同时具备弱化的惩罚项的条件和半正定临近项的优势，具有更广的适用性和更高的求解效率。针对所提出的算法，本文基于变分不等式和最优化理论给出了严格的收敛性分析以及收敛速率分析，并通过数值实验验证了算法的有效性。2.一种基于一种基于 M 范数惩罚项的范数惩罚项的 ADMM 算法算法 假设:nfRR+和:ng RR+是合适的、闭的、凸函数。本文提出的算法如下：算法 1.一种基于 M 范数惩罚项的 ADMM 算法 Open AccessOpen Access王博冉 DOI:10.12677/aam.2024.134155 1639 应用数学进展 输入：000 xy，计算：111kkkxy+，()1argmin,kkkxxLx y+=()211argmin,1/2kkkkyDyLxyyy+=+()111kkkkM AxByb+=+若满足停止准则，则输出：111kkkxy+，其中()()()()2,2TMLx yf xg yAxBybAxByb=+，M 是一个正定矩阵，()TTDsIB MB sB MB=是一个半正定矩阵。3.收敛性分析收敛性分析 引理 3.1.设序列kw由算法 1 迭代产生，令xuy=，()()(),xuf xg ywy=+=。那么有()1wk+，()()()()()111111101TkTkkkkTkkkkAF wBMB yyOuuwwB MBDOyyOM+(2)其中()11111TkkTkkkAF wBAxByb+=+。引理 3.2.设序列kw由算法 1 迭代产生，则 1kw+，()()()()()()()11111,TkkkkkkTAuuwwF wMB yyvvG vvwB+(3)其中1,1TB MBDOyGvOM+=。证明：因为()()()()110,TkkwwF wF ww+，所以 F 是单调算子。由(2)可得，(3)成立。引理 3.3.设序列kw由算法 1 迭代产生，其中*,w 为变分不等式的解集，那么有()()()()1*111TTkkkkkkkvvG vvB yy+(4)证明：()()1*1TkkkvvG vv+王博冉 DOI:10.12677/aam.2024.134155 1640 应用数学进展 ()()()()()()1*1*1*11*1*11*TkTTkkkkkTkTkkkTxxAuuwwF wMB yyyyBxxAMB yyyyB+=()()()()()1*1*111TTkkkkkkkkAxAxByByB yyB yy+=引理 3.4.设序列kw由算法 1 迭代产生，那么有：()()2211111122TkkkkkkkkDDB yyyyyy+(5)证明：对于算法 1，由变分不等式可得：()()()()11111,0,TkkkkkTkkkkyY g yg yyyBD yyyY+()()()()1111,0,TkkkkkTkkkkyY g yg yyyBD yyyY+两式相加可得：()()()()11110TkkTkkkkkkyyBDyyyy+所以()()()()()11111TTkkTkkkkkkkkyyByyDyyyy+。由柯西不等式可得：()()()22111111122TkkkkkkkkkkDDyyDyyyyyyyy+故(5)得证。引理 3.5.设序列kw由算法 1 迭代产生，那么有：()()221*1111122TkkkkkkkDDvvG vvyyyy+(6)证明：()()()()22*1*1221*11*122221*1112kkkkGGkkkkkkGGkkkkkkkGGDDvvvvvvvvvvvvG vvvvvvyyyy+=+显然，(6)式成立。定理 3.1.对于任意的*w，序列221*1kkkGDvvyy+是单调递减的。证明：由引理 3.5 可得：()()222221*11*1kkkkkkkkGGDGDvvvvyyvvyy+因为210kkGvv+，所以22221*1*1kkkkkkGDGDvvyyvvyy+。故序列221*1kkkGDvvyy+是单调递减的。定理 3.2.设序列kw由算法 1 迭代产生，那么序列jkv收敛到v。证明：因为()()222221*11*1kkkkkkkkGGDGDvvvvyyvvyy+。对上式求和可得：22211*011kkkGGDvvvvyy+=+。王博冉 DOI:10.12677/aam.2024.134155 1641 应用数学进展 因为 G 是正定的，所以211kkkGvv+=是正项级数。由正项级数收敛的必要条件可知：21lim0kkGkvv+=。因为()()222221*11*10kkkkkkkkGGDGDvvvvyyvvyy+。所以222221*11*01,1kkkkGGDGDvvvvyyvvyyk+。所以序列kv是有界的并且至少存在一个聚点v，存在一个子列jkv收敛到v。即limjkkvv=，其中*yvV=。定理 3.3.w是(1)的一个解。证明：因为21lim0kkGkvv+=，所以()1lim0kkkyy+=和()1lim0kkk+=。由变分不等式可知：()()()()()11111111,0,1kkTkTkkTkTkkkkwuuAF wBMB yyOwwwB MBDOyyOM+令上式中k，可得：()()()()0TuuwwF w+，故w是(1)的解。4.数值实验数值实验 统计中的 LASSO 问题如下：221,1min.2x yAxbyst xy+=(7)其中,m nmnnARbRxRyR。使用算法 1 求解(7)得到x子问题：()11kTkTkxA bIA A y+=+。并且 y 子问题的闭式解是：()111,kkkkkyshrink yM yx+=+。子问题的解为：()111kkkkM xy+=，其中,TTMIA A DA A=。本文通过数值实验比较了算法 1 和线性化 DMM 算法的迭代次数。将每个算法的参数设置如下：算法 1：0.001,1,0.1TTA AA b=+=。Linearized ADMM:0.001,1,0.1TTA AA b=+=，TDIA A=。停止准则是：()111,kkprikkdualxyyy+，其中()111maxpriabsrelkkdualabsrelknxyny+=+=+，。pri和dual被设置为410和210。对于给定的维度mn，我们随机生成数据，如下所示：王博冉 DOI:10.12677/aam.2024.134155 1642 应用数学进展 ()()()()001,1,0.001,1pxsprandn npArandn m nbA xsqrtrandn mn=+二种算法的实验结果如表 1 所示：Table 1.Comparison of the number of iterations between Algorithm 1 and Linearized ADMM 表表 1.算法 1 和 Linearized ADMM 的迭代次数比较 矩阵维数(m n)算法 1 的迭代次数 Linearized ADMM的迭代次数 750 2500 40 53 900 3000 39 52 1050 3500 38 51 1200 4000 38 51 1500 5000 35 48 实验结果表明，算法 1 的迭代次数少。因此，算法 1 是有可比较性的。5.结论结论 在本文中，我们提出了一种基于 M 范数罚项的具有半正定邻近项的广义线性化 ADMM 算法，对其进行了全局收敛性分析。最后，通过数值实验验证了算法的有效性。参考文献参考文献 1 Gabay,D.and Mercier,B.(1976)A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation.Computers&Mathematics with Applications,2,17-40.https:/doi.org/10.1016/0898-1221(76)90003-1 2 Glowinski,R.and Marrocco,A.(1974)Analyse numrique du champ magntique dun alternateur par lments finis et sur-relaxation ponctuelle non linaire.Computer Methods in Applied Mechanics and Engineering,3,55-85.https:/doi.org/10.1016/0045-7825(74)90042-5 3 He,B.,Ma,F.and Yuan,X.(2020)Optimally Linearizing the Alternating Direction Method of Multipliers for Convex Programming.Computational Optimization and Applications,75,361-388.https:/doi.org/10.1007/s10589-019-00152-3 4 Gao,B.and Ma,F.(2016)Symmetric ADMM with Positive-Indefinite Proximal Regularization for Linearly Con-strained Convex Optimization.http:/www.optimization-online.org 5 Fang,C.,Chen,J.and Chen,S.(2022)Image Denoising Algorithm of Compressed Sensing Based on Alternating Di-rection Method of Multipliers.International Journal of Modeling,Simulation,and Scientific Computing,13,2250009.https:/doi.org/10.1142/S179396232250009X