非凸非光滑不可分优化的两个线性邻近Peaceman-Rachford分裂算法

简金宝, 蔡靖民, 尹江华

计算数学 ›› 2023, Vol. 45 ›› Issue (4) : 426-446.

PDF(694 KB)
PDF(694 KB)
计算数学 ›› 2023, Vol. 45 ›› Issue (4) : 426-446. DOI: 10.12286/jssx.j2022-0948
论文

非凸非光滑不可分优化的两个线性邻近Peaceman-Rachford分裂算法

    简金宝, 蔡靖民, 尹江华
作者信息 +

TWO LINEAR PROXIMAL PEACEMAN-RACHFORD SPLITTING ALGORITHMS FOR NONCONVEX AND NONSMOOTH NONSEPARABLE OPTIMIZATION

    Jian Jinbao, Cai Jingmin, Yin Jianghua
Author information +
文章历史 +

摘要

本文研究一类非凸非光滑不可分优化. 基于Peaceman-Rachford(PR)分裂算法, 并结合Armijo线搜索技术及线性正则化技术, 提出了两个线性邻近PR分裂算法. 利用PR分裂算法思想, 将增广拉格朗日法涉及的子问题分解成两个小规模子问题. 为便于子问题的求解和使其具有良好的理论性质, 对子问题的目标函数中的光滑项作线性化处理, 并分别添加必要的正则项. 在常规假设下, 论证了算法的全局收敛性及迭代复杂性. 最后, 数值实验结果表明算法是有效的.

Abstract

This work studies a class of nonconvex and nonsmooth nonseparable optimization. Based on the Peaceman-Rachford (PR) splitting algorithm, two linear proximal PR splitting algorithms are proposed by combining the Armijo line search technique and the linear regularization technique. Using the idea of the PR splitting algorithm decomposes the subproblem associated with the augmented Lagrangian method into two small-scale subproblems. In order to facilitate the solution of the just-mentioned subproblems and make them have good theoretical properties, the smooth terms in the objective functions are linearized, and then the regularization terms are added to each subproblem respectively. Under usual conditions, the global convergence and the iteration complexity of the two proposed methods are proved. Finally, numerical experiments show that the two proposed algorithms are effective.

关键词

非凸非光滑不可分优化 / Peaceman-Rachford分裂算法 / 线性正则化技术 / Armijo线搜索 / 收敛性

Key words

Nonconvex and nonsmooth nonseparable optimization / Peaceman-Rachford splitting algorithm / Linear regularization technique / Armijo line search / Convergence

引用本文

导出引用
简金宝, 蔡靖民, 尹江华. 非凸非光滑不可分优化的两个线性邻近Peaceman-Rachford分裂算法. 计算数学, 2023, 45(4): 426-446 https://doi.org/10.12286/jssx.j2022-0948
Jian Jinbao, Cai Jingmin, Yin Jianghua. TWO LINEAR PROXIMAL PEACEMAN-RACHFORD SPLITTING ALGORITHMS FOR NONCONVEX AND NONSMOOTH NONSEPARABLE OPTIMIZATION. Mathematica Numerica Sinica, 2023, 45(4): 426-446 https://doi.org/10.12286/jssx.j2022-0948

参考文献

[1] Donoho D L. High-dimensional Data Analysis: The Curses and Blessings of Dimensionality[M]. AMS Math Challenges Lecture, 2000.
[2] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine learning, 2011, 3(1): 1–122.
[3] Han D R. A survey on some recent developments of alternating direction method of multipliers[J]. Journal of the Operations Research Society of China, 2022, 10(1): 1–52.
[4] Gabay D. Chapter IX Applications of the Method of Multipliers to Variational Inequalities[M]. Studies in mathematics and its applications. Elsevier, 1983, 15: 299–331.
[5] He B, Liu H, Wang Z, et al. A strictly contractive Peaceman-Rachford splitting method for convex programming[J]. SIAM Journal on Optimization, 2014, 24(3): 1011–1040.
[6] Li X X, Yuan X M. A proximal strictly contractive Peaceman-Rachford splitting method for convex programming with application to imaging[J]. SIAM Journal on Imaging Sciences, 2015, 8: 1332–1365.
[7] Li M, Yuan X M. A strictly contractive Peaceman-Rachford splitting method with logarithmicquadratic proximal regularization for convex programming[J]. Mathematics of Operations Research, 2015, 40: 842–858.
[8] He B, Ma F, Yuan X. Convergence study on the symmetric version of ADMM with larger step sizes[J]. SIAM Journal on Imaging Sciences, 2016, 9(3): 1467–1501.
[9] Chen Y N, Dai Y H, Han D R. Fiber orientation distribution estimation using a PeacemanRachford splitting method[J]. SIAM Journal on Imaging Sciences, 2016, 9: 573–604.
[10] Hong M, Luo Z Q, Razaviyayn M. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems[J]. SIAM Journal on Optimization, 2016, 26(1): 337–364.
[11] Cui Y, Li X, Sun D, et al. On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions[J]. Journal of Optimization Theory and Applications, 2016, 169(3): 1013–1041.
[12] Gao X, Zhang S Z. First-order algorithms for convex optimization with nonseparable objective and coupled constraints[J]. Journal of the Operations Research Society of China, 2017, 5(2): 131–159.
[13] Chen C, Li M, Liu X, et al. Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: Convergence analysis and insights[J]. Mathematical Programming, 2019, 173(1): 37–77.
[14] Li P, Shen Y, Jiang S, et al. Convergence study on strictly contractive Peaceman-Rachford s plitting method for nonseparable convex minimization models with quadratic coupling terms[J]. Computational Optimization and Applications, 2021, 78(1): 87–124.
[15] Nikolova M, Ng M K, Zhang S, et al. Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization[J]. SIAM Journal on Imaging Sciences, 2008, 1(1): 2–25.
[16] Gu S H, Zhang L, Zuo W M, et al. Weighted nuclear norm minimization with application to image denoising[C]. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014, 2862–2869.
[17] Bian W, Chen X. Linearly constrained non-Lipschitz optimization for image restoration[J]. SIAM Journal on Imaging Sciences, 2015, 8(4): 2294–2322.
[18] Liu J, Yuan L, Ye J. Dictionary lasso: Guaranteed sparse recovery under linear transformation[J]. arXiv preprint arXiv:1305.0047, 2013.
[19] Theerthamalai A, Maheswarapu S. An effective non-iterative “λ-logic based” algorithm for eco nomic dispatch of generators with cubic fuel cost function[J]. International Journal of Electrical Power and Energy Systems, 2010, 32(5): 539–542.
[20] Zhan J, Wu Q H, Guo C, et al. Economic dispatch with non-smooth objectives-part I: Local minimum analysis[J]. IEEE Transactions on Power Systems, 2014, 30(2): 710–721.
[21] 简金宝, 刘鹏杰, 江羡珍. 非凸多分块优化部分对称正则化交替方向乘子法[J]. 数学学报, 2021, 64(6): 1005–1026.
[22] Guo K, Han D, Wu T. Convergence of ADMM for optimization problems with nonseparable nonconvex objective and linear constraints[J]. Pacific Journal of Optimization, 2018, 14(3): 489–506.
[23] Guo K, Wang X. Convergence of generalized alternating direction method of multipliers for non separable nonconvex objective with linear constraints[J]. Journal of Mathematical Research with Applications, 2018, 38(5): 523–540.
[24] Chao M, Deng Z, Jian J. Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure[J]. Complexity, 2020, 2020: 6237942.
[25] 刘鹏杰, 简金宝, 马国栋, 等. 非凸不可分优化线性近似Bregman型Peaceman-Rachford分裂算法[J]. 数学学报, 2023, 66(1): 75–94.
[26] Wang Y, Yin W, Zeng J. Global convergence of ADMM in nonconvex nonsmooth optimization[J]. Journal of Scientific Computing, 2019, 78(1): 29–63.
[27] Jiang B, Lin T, Ma S, et al. Structured nonconvex and nonsmooth optimization: Algorithms and iteration complexity analysis[J]. Computational Optimization and Applications, 2019, 72(1): 115–157.
[28] Hien L T K, Phan D N, Gillis N. A framework of inertial alternating direction method of multipliers for non-convex non-smooth optimization[J]. arXiv preprint arXiv:2102.05433, 2021.
[29] 简金宝, 劳译娴, 晁绵涛, 等. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79–92.
[30] Jian J, Zhang C, Yin J, et al. Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems[J]. Journal of Optimization Theory and Applications, 2020, 186(1): 226–247.
[31] 简金宝, 张晨, 尹江华. 两分块非凸优化\ Peaceman-Rachford\ 分裂序列二次规划双步长算法[J]. 中国科学: 数学, 2022. DOI: 10.1360/SSM-2020-0297
[32] Nesterov Y. Introductory Lectures on Convex Optimization: A Basic Course[M]. Springer Science & Business Media, 2003.
[33] 简金宝. 光滑约束优化快速算法: 理论分析与数值实验[M]. 北京: 科学出版社, 2010.
[34] Fukushima M. 著, 林贵华译. 非线性最优化基础[M]. 北京: 科学出版社, 2011.
[35] Rockafellar R T, Wets R J B. Variational Analysis[M]. Springer Science & Business Media, 2009.
[36] Li G, Pong T K. Global convergence of splitting methods for nonconvex composite optimization[J]. SIAM Journal on Optimization, 2015, 25(4): 2434–2460.
[37] Zeng L, Xie J. Group variable selection via SCAD-L2[J]. Statistics, 2014, 48(1): 49–66.
[38] Fan J. Comments on “wavelets in statistics: A review” by A. Antoniadis[J]. Journal of the Italian Statistical Society, 1997, 6(2): 131–138.
[39] Wu Z, Li M. General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems[J]. Computational Optimization and Applications, 2019, 73(1): 129–158.

基金

国家自然科学基金(项目任务书编号: 12171106), 广西自然科学基金项目(项目任务书编号: 2023GXNSFBA026029, 2020GXNSFDA238017)资助.
PDF(694 KB)

314

Accesses

0

Citation

Detail

段落导航
相关文章

/