一类分式优化问题的带非单调线搜索的近端梯度次梯度算法研究.pdf

Advances in Applied Mathematics A?,2024,13(3),1129-1139Published Online March 2024 in Hans.https:/www.hanspub.org/journal/aamhttps:/doi.org/10.12677/aam.2024.133105azK?N|?CFgF?n?XU9vF2024c2?27FF2024c3?21FuF2024c3?28F?azKf1wY1w?11wk?K?5,?)zK?#=N|?CFgF(NL-PGSA)d?uKurdyka-Lojasiewicz5?y)?S?5?l1/l2D&EK?1?y?T?k?5czCFgF5Research on the ProximalGradient-Subgradient Algorithm withNonmonotonic Line Search for a Classof Fractional Optimization ProblemsJing ZhangDepartment of Mathematics,School of Sciences,Hebei University of Technology,TianjinReceived:Feb.27th,2024;accepted:Mar.21st,2024;published:Mar.28th,2024:.azK?N|?CFgFJ.A?,2024,13(3):1129-1139.DOI:10.12677/aam.2024.133105AbstractThis paper mainly considers a class of fractional optimization problems where thenumerator is a sum of a convex nonsmooth continuous function and a nonconvexsmooth function,while the denominator is a convex nonsmooth function.We first givethe first-order optimality condition of the problem,and then a new algorithm,calledproximal gradient-subgradient algorithm with nonmonotonic line search(NL-PGSA),is proposed for solving the fractional optimization problems.Moreover,the globalconvergence of the entire sequence generated by NL-PGSA algorithm has been provenbased on the Kurdyka-Lojasiewicz property.Finally,some numerical experiments onthe l1/l2sparse signal recovery problems are conducted to demonstrate the efficiencyof the proposed algorithm.KeywordsFractional Optimization,Proximal Gradient-Subgradient Algorithm,ConvergenceAnalysisCopyright c?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.?aA?zK/:min?f(x)+h(x)g(x):x :=x Rn:g(x)6=0?,(1.1)f,g,h:Rn R:=(,+vXeb?b?1.1.(i)fT?ke.3k?Y?DOI:10.12677/aam.2024.1331051130A?(ii)hkLipschitzYF?Y=3Lipschitz L,v|h(x)h(y)k Lkx yk,x,y Rn.(iii)g(iv)f+h3RnK?3Rn?u0,g 0 3dom(f).d?b?K(1.1)?)3U?zK?zz?8IKzK3N+k?AX&47L 8?d?KNJ?k?zK?g)zK(?=yK(1.1)?)x?Rn?de?K?)minf(x)+h(x)c?g(x):x ,(1.2)c?“LK(1.1)?c?=f(x?)+h(x?)g(x?),T?:)5?zK?:w,K(1.1)?)?(JkJ?Dinkelbachs 9,Td?cS“?ck?“c?NS“exk+1 argminf(x)+h(x)ckg(x):x ,(1.3)ck=f(xk)+h(xk)g(xk),uT?z 1012.,?lK(1.3)T8I?)?(JCBot?0.l(1.4)S“S?g(x)3xk?5m,?l5U5w?K5?CF?JpN?J?p?Zhang?14J?CFgF?(PGSA)5)K?S“exk+1 argmin?f(x)+?h?xk?ckyk+1,x xk?+12k?x xk?2:x?,(1.5)yk+1 g(xk),0 k 1/L,ck=f(xk)+h(xk)g(xk).w?S“?h(x)ckg(x)?5mTkf?Cfd?J?|?CFgF(PGSA-L),?y50 k1L,?T?6?L?d?DOI:10.12677/aam.2024.1331051131A?z 14?u3f?cJe?,?BB?U?3vKurdyka-Lojasiewicz5?e?y?52.?e0?Rnnmh,iIOSkk,kk1Ol18S?5IS(x)IS(x):=(0,if x S,+,otherwise.(2.1)u*?:Rn(,+,k?dom:=x Rn:(x)dom()KT?48S Rn,?dist(,S):Rn RLx?S?l=dist(x,S):=infySkx yk,x Rn.2.1.(Kurdyka-Lojasiewicz5 15)?:RnRT?eY x dom(),XJ3 (0,+,x?+O9ve?:0,)R+:=0,+)(i)(0)=0,(ii)3(0,)Y0 0,(iii)x O x Rn:(x)(x)0,0 t 0?F(xk):k N?N?BP4x=xk xk1,4h=h(xk)h(xk1),uk,0?)Xek,0=maxn,minn,|hx,hi|khk22oo,if hx,hi 6=0,else.(3.4)?e5XenTn?y?5n3.2.?xk:k N?NL-PGSA)K(1.1)?S“:?Kf(xk+1)+h(xk+1)+(1kL2)?xk+1 xk?2 ckg(xk+1),(3.5)k N,?xk?dom(F).y.8B?1yk:x0 dom(F),?k N,kx0,x1,xkdom(F)dNL-PGSA?S“e9Cf?1k?xk xk+1 kh?xk?+kckyk+1?f?xk+1?,DOI:10.12677/aam.2024.1331051133A?b?1.1,f?f?xk+1?+1k?xk xk+1 kh?xk?+kckyk+1,xk xk+1?f?xk?n?f?xk+1?+?xk+1 xk,h?xk?ckyk+1?+1k?xk+1 xk?22 f?xk?,(3.6)d?hLipschitzY?h(xk+1)h(xk)+?h(xk),xk+1 xk?+L2?xk+1 xk?2,(3.7)gk N,ck=f(xk)+h(xk)g(xk)0,dckg(xk)+?ckyk+1,xk+1 xk?ckg(xk+1).(3.8)(3.6),(3.7)(3.8)(ckg(xk)=f(xk)+h(xk)g(xk)g(xk)=f(xk)+h(xk),?f(xk+1)+h(xk+1)+(1kL2)?xk+1 xk?2 ckg(xk+1),?xk+1/dom(F)=dom(f),dg(xk+1)=0,b?1.1,f+h 0,dNL-PGSA?0 k 0?F?xk+1?+(1kL2)?xk+1 xk?2g(xk+1)F?xk?,(3.9)?e5y(ii),?(3.9)?klk=0?K?F?xK+1?+KXk=0(1kL2)?xk+1 xk?2g(xk+1)F?x0?.(3.10)DOI:10.12677/aam.2024.1331051134A?u90 k2L,?PKk=0(1kL2)kxk+1xkk2g(xk+1)k.,-K ,?limkkxkxk1k2g(xk+1)=0.(i)(ii),(iii)?e5NL-PGSA?53?b?ekyuz?S7L3kgS“Ske?b?b?3.1.?c0 R,Y8x Rn:F(x)c0 k.b?3.2.f3k?LipschitzY?b?3.3.g3YgLipschitzY?n3.4.3b?3.1?e?M:=supg(x):x lev(F(x),c0),K(i)3TgS“NL-PGSA?133k =2tL+M,T:=llog(aM+L)log t+1m(ii)k N,kxk lev(F,c0)?xk:k N?k.?(iii)S?F(xl(k):k N?O?y.ky(i),n3.3?(3.10)?k N,F(xk)F(x0),/b?3.1,?xk:k N?k.?d?g?gYd3M 0,?k N,kg(xk)M,NL-PGSA?S“ek,02L,d3S“T?k N,kk2L+M=/t.?e5k8Bw,x0 lev(F,c0),?xidS“?)?:xi lev(F,c0),i=0,1,k,?y(i),I?k /t k xk+1 dom(F),eF?xk+1?cka2?xk+1 xk?22,(3.11)dn3.3(i),9k2L+M2L,?xk+1 dom(F),F?xk+1?ck(1kL2)?xk+1 xk?2g(xk+1)ckM2?xk+1 xk?2g(xk+1),(3.12)dF?xk+1?ck c0,d xk+1 lev(F,c0),d?/g?xk+1?M,d(3.12)?(3.11).?e5yxk+1 lev(F,c0),l(k):=max?j:j argmax?F?xi?:k N+i k?,(3.13)DOI:10.12677/aam.2024.1331051135A?/9(3.3)?i k,F(xi+1)F?xl(i)?,dF?xl(i+1)?=maxi+1N+ji+1F?xj?=max?F?xi+1?,maxi+1N+jiF?xj?max?F?xi+1?,F?xl(i)?=F?xl(i)?.(3.14)?F?xk+1?F?xl(k)?F?xl(0)?=c0.n?y?en=z 14n5.2n5.3,n3.5LNL-PGSA?fS?n3.6LNL-PGSA?n3.5.3b?1.1,b?3.1?cJe,?xk:k N?NL-PGSA)?S?,K?xk:k N?:F?.:n3.6.3b?1.1,3.1,3.29b?3.3?cJe?F3k?:vKL5?xk:k N?NL-PGSA)?S?KPk=1?xk+1 xk?2 0,?zKe?K?dmin?kxk1+12kAx bk2kxk:x x x,x Rn?.(4.2)w,K(4.2)K(1.1)?AN5fkxk153x x x,x Rn?h=12kAx bk2,g=kxk,=x Rn:g(x)6=0,pA Rmn,b Rm.du8IazK(?1?(g?N/d:U?3p&x5)x0.?e5?E?D?K?&x Rn,J?K?|f8?l?2D,3T8)|v Rn,sgn“LIO?x=sgn(v).?b Rm,b=A x,x=2 1n,x=2 1n,p1n“Lk?u1?n?e5I xvK(4.2)?75k x 3K(4.2)?c=K,e x kk1(e x)(k k2)(e x)=e x/K,K0 (k k1)(e x)e c(k k)(e x).d?DOI:10.12677/aam.2024.1331051136A?x x x,A x=b,?0?k k1+xRn:xx x?(e x)+AT(Ae x b)e c(k k)(e x).X xK(4.2)?)NL-PGSAPGSA-L 14,?1?e5?N?NL-PGSA.L=kAk2,0,0=1/L,=103,t=0.5,N=4.PGSA-L.J?z 143?e5?O(m,n)=(512,8192)(m,n)=(640,10240),J?DD=1,5,10,15,K=12,16 5l1/l2D&EK3z(D,K)?X)100g100g?(J?zg?x0=x+0.4,p Rnv1,1?!?S“g?1000kxkxk1k/max1,kxkk 105S“XL 1L 23S“gCPUm()S“?lL?(?Ly?Table 1.Solving problem(4.2)when(m,n)=(512,8192),=5 104L 1.)K(4.2),(m,n)=(512,8192),=5 104itertimeF vall1/l2PGSA-Ll1/l2NL-PGSAl1/l2PGSA-Ll1/l2NL-PGSAl1/l2PGSA-Ll1/l2NL-PGSAD=1,K=124824022.232972.216220.0987590.0907651D=1,K=164844062.242212.216450.0988030.0906339D=5,K=124834032.234812.214230.0982820.0907574D=5,K=164824032.240312.226850.0984580.0908579D=10,K=124824012.231662.213560.0981170.0907067D=10,K=164834022.231022.212560.0989730.0905531D=15,K=124864022.233082.212040.0986650.0909149D=15,K=164834022.232082.210720.0986060.0902784Table 2.Solving problem(4.2)when(m,n)=(640,10240),=5 104L 2.)K(4.2),(m,n)=(640,10240),=5 104itertimeF vall1/l2PGSA-Ll1/l2NL-PGSAl1/l2PGSA-Ll1/l2NL-PGSAl1/l2PGSA-Ll1/l2NL-PGSAD=1,K=124834043.444322.997390.1923450.1917892D=1,K=164874023.434522.998160.1930240.1915356D=5,K=124824033.443712.995150.1929640.1912004D=5,K=164834043.447352.992250.1927180.1911423D=10,K=124854053.443452.993410.1923430.1911445D=10,K=164824033.444622.992350.1922740.1911234D=15,K=124824033.443512.995320.1924940.1912451D=15,K=164834053.662092.539880.2547090.0563043DOI:10.12677/aam.2024.1331051137A?5.(?aA?zKJ?#?N|?CFgFk3?y5?cJe*?Jk|u/?8I?)NC,/?y?k?5z1 Baldacci,R.,Lim,A.,Traversi,E.and Calvo,R.W.(2020)Optimal Solution of Vehicle RoutingProblems with Fractional Objective Function.Transportation Science,54,434-452.https:/doi.org/10.1287/trsc.2019.09292 Rahimi,Y.,Wang,C.,Dong,H.and Lou,Y.(2019)A Scale-Invariant Approach for SparseSignal Recovery.SIAM Journal on Scientific Computing,41,A3649-A3672.https:/doi.org/10.1137/18M123147X3 Studer,C.and Baraniuk,R.G.(2014)Stable Restoration and Separation of ApproximatelySparse Signals.Applied and Computational Harmonic Analysis,37,12-35.https:/doi.org/10.1016/j.acha.2013.08.0064 Cand es,E.,Romberg,J.K.and Tao,T.(2006)Stable Signal Recovery from Incomplete andInaccurate Measurements.Communications on Pure and Applied Mathematics,59,1207-1223.https:/doi.org/10.1002/cpa.201245 Hoyer,P.O.(2004)Non-Negative Matrix Factorization with Sparseness Constraints.Journalof Machine Learning Research,5,1457-1469.6 Shen,K.and Yu,W.(2018)Fractional Programming for Communication SystemsPart I:Power Control and Beamforming.IEEE Transactions on Signal Processing,66,2616-2630.https:/doi.org/10.1109/TSP.2018.28127337 Zappone,A.,Sanguinetti,L.and Debbah,M.(2017)Energy-Delay Efficient Power Control inWireless Networks.IEEE Transactions on Communications,66,418-431.https:/doi.org/10.1109/TCOMM.2017.27556448 Konno,H.and Inori,M.(1989)Bond Portfolio Ptimization by Bilinear Fractional Program-ming.Journal of the Operations Research Society of Japan,32,143-158.https:/doi.org/10.15807/jorsj.32.1439 Clemmensen,L.,Hastie,T.,Witten,D.and Ersbll,B.(2100)Sparse Discriminant Analysis.Technometrics,53,406-413.https:/doi.org/10.1198/TECH.2011.0811810 Ibaraki,T.(1983)Prametric Approaches to Fractional Programs.Mathematical Programming,26,345-362.https:/doi.org/10.1007/BF02591871DOI:10.12677/aam.2024.1331051138A?11 Pang,J.S.(1980)A Parametric Linear Complementarity Technique for Optimal PortfolioSelection with a Risk-Free Asset.Operation Research,28,927-941.https:/doi.org/10.1287/opre.28.4.92712 Schaible,S.(1976)Fractional Programming.II,on Dinkelbachs Algorithm.Management Sci-ence,22,868-873.https:/doi.org/10.1287/mnsc.22.8.86813 Bot,R.I.and Csetnek,E.R.(2017)Proximal-Gradient Algorithms for Fractional Programming.Optimization,66,1383-1396.https:/doi.org/10.1080/02331934.2017.129459214 Zhang,N.and Li,Q.(2022)First-Order Algorithms for a Class of Fractional OptimizationProblems.SIAM Journal on Optimization,32,100-129.https:/doi.org/10.1137/20M132538115 Attouch,H.,Bolte,J.,Redont,P.and Soubeyran,A.(2010)Proximal Alternating Minimiza-tion and Projection Methods for Nonconvex Problems:An Approach Based on the Kurdyka-Lojasiewicz Inequality.Mathematics of Operations Research,35,438-457.https:/doi.org/10.1287/moor.1100.0449DOI:10.12677/aam.2024.1331051139A?