一类非光滑凸优化问题的邻近梯度算法

doi:10.15960/j.cnki.issn.1007-6093.2021.01.005

运筹学学报 ›› 2021, Vol. 25 ›› Issue (1): 61-72.doi: 10.15960/j.cnki.issn.1007-6093.2021.01.005

一类非光滑凸优化问题的邻近梯度算法

李红武¹^,²^,(), 谢敏¹, 张榕³

1. 北京工业大学应用数理学院, 北京 100124
2. 南阳师范学院数学与统计学院, 河南南阳 473061
3. 汉能薄膜发电集团总部, 北京 100101

收稿日期:2019-04-01 出版日期:2021-03-15 发布日期:2021-03-05
通讯作者: 李红武 E-mail:xmin@emails.bjut.edu.cn
作者简介:李红武 E-mail: xmin@emails.bjut.edu.cn
基金资助:
国家自然科学基金(11771003)

A proximal gradient method for nonsmooth convex optimization problems

Hongwu LI¹^,²^,(), Min XIE¹, Rong ZHANG³

1. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China
2. School of mathematics and statistics, Nanyang Normal University, Nanyang 473061, Henan, China
3. Hanergy Thin Film Power Group Head Quaters, Beijing 100101, China

Received:2019-04-01 Online:2021-03-15 Published:2021-03-05
Contact: Hongwu LI E-mail:xmin@emails.bjut.edu.cn

摘要/Abstract

摘要：

考虑求解目标函数为光滑损失函数与非光滑正则函数之和的凸优化问题的一种基于线搜索的邻近梯度算法及其收敛性分析，证明了在梯度局部Lipschitz连续条件下该算法是$R$-线性收敛的，并在非光滑部分为稀疏块LASSO正则函数情况下给出了误差界条件成立的证明，得到了线性收敛率。最后，数值实验结果验证了方法的有效性。

关键词: 非光滑凸优化, 邻近梯度法, 局部Lipschitz连续, 误差界, 线性收敛

Abstract:

A Proximal Gradient Method based on linesearch (L-PGM) and its convergence for solving the convex optimization problems which objective function is the sum of smooth loss function and non-smooth regular function are studied in this paper. Considering the loss function's gradient is locally Lipschitz continuous in the problems, the R-linear convergence rate of the L-PGM method is proved. Then, focusing on the problems regularized by the sparse group Lasso function, we prove that the error bound holds around the optimal solution set, thus, the linear convergence for solving such problems with the L-PGM method is given. Finally, The preliminary experimental results support our theoretical analysis.

Key words: nonsmooth convex optimization, proximal gradientmethod, locally lipschitz continuous, error bound, linearconvergence

中图分类号:

O221

李红武, 谢敏, 张榕. 一类非光滑凸优化问题的邻近梯度算法[J]. 运筹学学报, 2021, 25(1): 61-72.

Hongwu LI, Min XIE, Rong ZHANG. A proximal gradient method for nonsmooth convex optimization problems[J]. Operations Research Transactions, 2021, 25(1): 61-72.

图/表 3

1	Fan J , Li R . Variable selection via nonconcave penalized likelihood and its oracle properties[J]. Publications of the American Statistical Association, 2001, 96 (456): 1348- 1359. doi: 10.1198/016214501753382273
2	Zou H , Hastie T . Regularization and variable selection via the elastic net[J]. Journal of the Royal Statistical Society, 2005, 67 (2): 301- 320. doi: 10.1111/j.1467-9868.2005.00503.x
3	Zhang H B , Jiang J J , Luo Z Q . On the linear convergence of a proximal gradient method for a class of nonsmooth convex minimization problems[J]. Journal of the Operations Research Society of China, 2013, 1 (2): 163- 186. doi: 10.1007/s40305-013-0015-x
4	Cruz J Y B , Nghia T T A . On the convergence of the forward-backward splitting method with linesearches[J]. Optimization Methods and Software, 2016, 31 (6): 1209- 1238. doi: 10.1080/10556788.2016.1214959
5	Yu M . Proximal extrapolated gradient methods for variational inequalities[J]. Optimization Methods and Software, 2018, 33 (1): 140- 164. doi: 10.1080/10556788.2017.1300899
6	Tseng P . Approximation accuracy, gradient methods, and error bound for structured convex optimization[J]. Mathematical Programming, 2010, 125 (2): 263- 295. doi: 10.1007/s10107-010-0394-2
7	Rockafellar T R , Wets J B . Variational Analysis[M]. New York: Springer-Verlag, 1998.
8	Combettes P L . Signal recovery by proximal forward-backward splitting[J]. Siam Journal on Multiscale Modeling and Simulation, 2006, 4 (4): 1168- 1200.
10	Nesterov Y . Introductory Lectures on Convex Optimization: a Basic Course[M]. Boston: Springer, 2004.
11	Zhang H B , Wei J , Li M X , et al. On proximal gradient method for the convex problems regularized with the group reproducing kernel norm[J]. Journal of Global Optimization, 2014, 58 (1): 169- 188. doi: 10.1007/s10898-013-0034-5
12	Luo Z Q , Tseng P . On the linear convergence of descent methods for convex essentially smooth minimization[J]. SIAM Journal on Control and Optimization, 1992, 30 (2): 408- 425. doi: 10.1137/0330025

A	L-PGM
size	iter.	CPU(s)	opt.
randn(50, 100)	156	0.588 0	18.646 6
randn(80, 500)	325	2.296 8	20.111 9
randn(50, 1 000)	439	4.343 0	14.333 1
randn(80, 5 000)	529	24.273	16.642 3
randn(100, 9 000)	598	60.417 1	17.053 9
randn(50, 10 000)	737	60.368 7	10.168 3
randn(80, 30 000)	1001	298.617 7	13.164 9
randn(150, 50 000)	908	617.833 9	19.094 9

[1]	张玉茹, 张雪, 兰茹. 一类线性反问题的变尺度外推硬阈值算法[J]. 运筹学学报（中英文）, 2025, 29(2): 158-174.
[2]	陈巧, 林惠玲. 广义混合拟变分不等式的间隙函数及其误差界[J]. 运筹学学报（中英文）, 2025, 29(2): 44-57.
[3]	王茂然, 蔡邢菊, 吴中明, 韩德仁. 多模式交通均衡问题的一阶分裂算法[J]. 运筹学学报, 2023, 27(2): 63-78.
[4]	曾友芳, 唐春明. 二阶锥规划一个超线性收敛的非内部连续化算法[J]. 运筹学学报, 2015, 19(1): 18-30.
[5]	万芮, 徐姿. 广义交替近似梯度算法的线性收敛分析[J]. 运筹学学报, 2014, 18(3): 1-12.
[6]	赵奇, 张燕. 求解极小极大问题的非单调过滤算法[J]. 运筹学学报, 2012, 16(2): 91-104.
[7]	简金宝, 韦小鹏, 曾汉君, 潘华琴. 一般约束优化基于识别函数的模松弛算法[J]. 运筹学学报, 2011, 15(2): 28-44.

一类非光滑凸优化问题的邻近梯度算法

A proximal gradient method for nonsmooth convex optimization problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

相关文章 7

编辑推荐

Metrics

本文评价