基于镜像下降的分布式弱凸优化算法研究

程松松; 陈茹; 樊渊; 邱剑彬

doi:10.16383/j.aas.c240784

基于镜像下降的分布式弱凸优化算法研究

doi: 10.16383/j.aas.c240784 cstr: 32138.14.j.aas.c240784

程松松^1,,
陈茹^1,,
樊渊^1,,
邱剑彬^2,

1.
安徽大学电气工程与自动化学院, 计算智能与信号处理教育部重点实验室合肥 230601
2.
哈尔滨工业大学智能控制与系统研究所哈尔滨 150080

基金项目: 国家自然科学基金(62103003, U21B6001, 62273121), 安徽省科技创新攻坚计划(202423i08050033)资助

详细信息

作者简介:
程松松：安徽大学电气工程与自动化学院副教授. 2018年获得中国科学技术大学控制科学与工程专业博士学位. 主要研究方向为分布式计算、优化与博弈. E-mail: sscheng@ahu.edu.cn

陈茹：安徽大学电气工程与自动化学院硕士研究生. 主要研究方向为基于对偶理论的分布式非凸优化与博弈. E-mail: ruchen@stu.ahu.edu.cn

樊渊：安徽大学电气工程与自动化学院教授. 2011年获得中国科学技术大学和香港城市大学控制科学与工程专业博士学位. 主要研究方向为分布式控制与优化, 机器人导航与控制. 本文通信作者. E-mail: yuanf@ahu.edu.cn

邱剑彬：哈尔滨工业大学智能控制与系统研究所教授. 2009年获得中国科学技术大学和香港城市大学机械电子工程专业博士学位. 主要研究方向为智能控制理论与应用, 人工智能大模型, 航天器智能自主控制, 智能机器人. E-mail: jbqiu@hit.edu.cn

计量
- 文章访问数: 19
- HTML全文浏览量: 6
- 被引次数: 0
出版历程
- 收稿日期: 2024-12-09
- 录用日期: 2025-05-13
- 网络出版日期: 2025-07-14

Distributed Mirror Descent Algorithm Design for Weakly Convex Optimization

1.
Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Electrical Engineering and Automation, Anhui University, Hefei 230601
2.
Research Institute of Intelligent Control and Systems, Harbin Institute of Technology, Harbin 150080

Funds: Supported by National Natural Science Foundation of China (62103003, U21B6001, 62273121) and Anhui Province Science and Technology Innovation Key Project (202423i08050033)

More Information

Author Bio:
CHENG Song-Song　Associate Professor at the School of Electrical Engineering and Automation, Anhui University. He received his Ph.D. degree in control science and engineering from the University of Science and Technology of China in 2018. His current research interest covers distributed computation, optimization, and games

CHEN Ru　Master student at the School of Electrical Engineering and Automation, Anhui University. Her current research interest covers distributed nonconvex optimization and game based on duality theory

FAN Yuan　Professor at the School of Electrical Engineering and Automation, Anhui University. He received his Ph.D. degree in control science and engineering from the University of Science and Technology of China and the City University of Hong Kong in 2011. His current research interest covers distributed control and optimization, robot navigation and control. Corresponding author of this paper

QIU Jian-Bin　Professor at the Institute of Intelligent Control and System, Harbin Institute of Technology. He received his Ph.D. degree in mechatronics engineering from the University of Science and Technology of China and the City University of Hong Kong in 2009. His current research interest covers intelligent control theory and application, artificial intelligence large model, intelligent autonomous control of spacecraft, and intelligent robotics

摘要

摘要: 机器学习中的诸多非凸优化问题, 如鲁棒相位恢复、低秩矩阵补全以及稀疏字典学习等, 本质上可归结为弱凸优化问题. 然而, 弱凸优化问题固有的非凸特性使得此类问题的求解极具挑战. 此外, 由于系统复杂度和问题规模的增加以及相关参数的分布式存储需求, 传统基于单个个体的集中式计算框架难以高效求解此类问题. 针对上述挑战, 设计了一种分布式镜像下降算法, 并从Bregman-Moreau包络的角度分析了其收敛性, 证明了算法的收敛速度为${O}(\ln K/{\sqrt K})$, 其中$K$为算法的迭代步数. 进一步地, 考虑目标函数梯度信息难以精确获取的情形, 采用正交随机方向矩阵法进行梯度估计. 相较于传统的基于随机向量的方法, 该方法利用多维方向信息进行估计, 从而显著提高了梯度信息的估计精度和效率. 基于高效的梯度信息估计, 提出了一种分布式零阶镜像下降算法, 并获得了与已知精确梯度信息情形下相一致的收敛速度. 最后, 通过相位恢复问题的数值仿真和实验验证了所提出的两种算法的有效性.
- 分布式优化 /
- 弱凸 /
- 镜像下降 /
- Bregman-Moreau包络 /
- 零阶梯度
Abstract: Many non-convex optimization problems in machine learning, such as robust phase retrieval, low-rank matrix recovery, and sparse dictionary learning, can be fundamentally modeled as weakly convex optimization problems. However, the inherent non-convex property of weakly convex optimization makes solving such problems particularly challenging. Besides, with the increase of systems' complexity and problem scale, as well as distributed storage of related parameters, traditional centralized frameworks based on a single node are difficult to solve such problems efficiently. To address these challenges, we propose a distributed mirror descent algorithm and analyze its convergence from the perspective of the Bregman-Moreau envelope. We establish a convergence rate of ${O}(\ln K/{\sqrt K})$, where $K$ is the number of iterations. Moreover, considering that exact gradient information of the objective function is difficult to obtain, we propose a gradient estimation scheme based on orthogonal random direction matrices. Compared to conventional methods based on random vectors, this scheme utilizes multi-dimensional directional information to achieve significantly higher accuracy and efficiency in gradient estimation. Furthermore, we design a distributed zeroth-order mirror descent algorithm based on the effective gradient estimation results and achieve a comparable convergence to the algorithm designed based on exact gradient information. Finally, we illustrate the effectiveness of the two proposed algorithms by numerical simulations and experiments based on the phase retrieval problem.
- Distributed optimization /
- weakly convex /
- mirror descent /
- Bregman-Moreau envelop /
- zeroth-order gradient
注释:

1) 1¹ 考虑非光滑凸函数$ h(\cdot):{\bf R}_{}^{m}\rightarrow {\bf R} $, $ {{\mathit{\boldsymbol{u}}}} $为其定义域$ {\rm dom} h $中一点. 若向量$ {{\mathit{\boldsymbol{g}}}}\in{\bf R}^{m} $满足$ h({{\mathit{\boldsymbol{v}}}})\ge h({{\mathit{\boldsymbol{u}}}})+ \langle {{\mathit{\boldsymbol{g}}}}, {{\mathit{\boldsymbol{v}}}}-{{\mathit{\boldsymbol{u}}}} \rangle $, $ \forall {{\mathit{\boldsymbol{v}}}}\in {\rm dom} h $, 则称$ {{\mathit{\boldsymbol{g}}}} $为函数$ h(\cdot) $在点$ {{\mathit{\boldsymbol{u}}}} $处的一个次梯度; 此外, 记$ \partial h({{\mathit{\boldsymbol{u}}}})=\{{{\mathit{\boldsymbol{g}}}}|{{\mathit{\boldsymbol{g}}}}\in{\bf R}^{m}, \;h({{\mathit{\boldsymbol{v}}}})\ge $$ h({{\mathit{\boldsymbol{u}}}})+ \langle {{\mathit{\boldsymbol{g}}}}, \;{{\mathit{\boldsymbol{v}}}}-{{\mathit{\boldsymbol{u}}}} \rangle, \forall {{\mathit{\boldsymbol{v}}}} \in {\rm dom} h\} $为函数$ h(\cdot) $在点$ {{\mathit{\boldsymbol{u}}}} $处的次梯度集合^[29].

HTML全文

图 1 网络化系统示意图

Fig. 1 Networked system schematic

下载: 全尺寸图片幻灯片

图 2 例1中算法1与2的仿真结果

Fig. 2 Simulation results of Algorithms 1 and 2 in Example 1

下载: 全尺寸图片幻灯片

图 3 例1中算法2与文献[21]中算法的仿真结果

Fig. 3 Simulation results of Algorithm 2 and the algorithm from [21] in Example 1

下载: 全尺寸图片幻灯片

图 4 例2中算法1、2和文献[21]中算法的图像恢复效果

Fig. 4 Image recovery results of Algorithms 1, 2 and the algorithm from [21] in Example 2

下载: 全尺寸图片幻灯片

图 5 例3中算法1、2和文献[21]中算法的图像恢复效果

Fig. 5 Image recovery results of Algorithms 1, 2 and the algorithm from [21] in Example 3

下载: 全尺寸图片幻灯片

参考文献(31)

[1]	衣鹏, 洪奕光. 分布式合作优化及其应用. 中国科学: 数学, 2016, 46(10): 1547−1564 Yi Peng, Hong Yi-Guang. Distributed cooperative optimization and its applications. Sci Sin Math, 2016, 46(10): 1547−1564
[2]	谢佩, 游科友, 洪奕光, 谢立华. 网络化分布式凸优化算法研究进展. 控制理论与应用, 2018, 35(07): 918−927 doi: 10.7641/CTA.2018.80205 Xie Pei, You Ke-You, Hong Yi-Guang, Xie Li-Hua. A survey of distributed convex optimization algorithms over networks. Control Theory & Applications, 2018, 35(07): 918−927 doi: 10.7641/CTA.2018.80205
[3]	Nedić A, Liu J. Distributed optimization for control. Annual Review of Control, Robotics, and Autonomous Systems, 2018, 1(1): 77−103
[4]	Yang T, Yi X L, Wu J F, Yuan Y, Wu D, Meng Z Y, Hong Y G, Wang H, Lin Z Y, Johansson K H. A survey of distributed optimization. Annual Reviews in Control, 2019, 47: 278−305 doi: 10.1016/j.arcontrol.2019.05.006
[5]	杨涛, 柴天佑. 分布式协同优化的研究现状与展望. 中国科学: 技术科学, 2020, 50(11): 1414−1425 doi: 10.1360/SST-2020-0040 Yang Tao, Chai Tian-You. Research status and prospects of distributed collaborative optimization. Sci Sin Tech, 2020, 50(11): 1414−1425 doi: 10.1360/SST-2020-0040
[6]	邓文, 李伟健, 曾宪琳, 洪奕光. 矩阵方程的分布式求解算法研究概述. 控制理论与应用, 2021, 38(11): 1695−1706 doi: 10.7641/CTA.2021.10671 Deng Wen, Li Wei-Jian, Zeng Xian-Lin, Hong Yi-Guang. A survey of distributed algorithms for solving matrix equations. Control Theory & Applications, 2021, 38(11): 1695−1706 doi: 10.7641/CTA.2021.10671
[7]	杨涛, 徐磊, 易新蕾, 张圣军, 陈蕊娟, 李渝哲. 基于事件触发的分布式优化算法. 自动化学报, 2022, 48(1): 133−143 Yang Tao, Xu Lei, Yi Xin-Lei, Zhang Sheng-Jun, Chen Rui-Juan, Li Yu-Zhe. Event-triggered distributed optimization algorithms. Acta Automatica Sinica, 2022, 48(1): 133−143
[8]	Yang S F, Liu Q S, Wang J. A multi-agent system with a proportional-integral protocol for distributed constrained optimization. IEEE Transactions on Automatic Control, 2016, 62(7): 3461−3467
[9]	Zhu Y N, Yu W W, Wen G H, Chen G R. Projected primal-dual dynamics for distributed constrained nonsmooth convex optimization. IEEE Transactions on Cybernetics, 2018, 50(4): 1776−1782
[10]	Yuan K, Ling Q, Yin W T. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 2016, 26(3): 1835−1854 doi: 10.1137/130943170
[11]	Pu S, Shi W, Xu J M, Nedić A. Push-pull gradient methods for distributed optimization in networks. IEEE Transactions on Automatic Control, 2021, 66(1): 1−16 doi: 10.1109/TAC.2020.2972824
[12]	Nedić A, Ozdaglar A, Parrilo P A. Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 2010, 55(4): 922−938 doi: 10.1109/TAC.2010.2041686
[13]	Lei J L, Chen H F, Fang H T. Primal-dual algorithm for distributed constrained optimization. Systems & Control Letters, 2016, 96: 110−117
[14]	Cheng S S, Liang S, Fan Y, Hong Y G. Distributed gradient tracking for unbalanced optimization with different constraint sets. IEEE Transactions on Automatic Control, 2023, 68(6): 3633−3640
[15]	Beck A, Teboulle M. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 2003, 31(3): 167−175 doi: 10.1016/S0167-6377(02)00231-6
[16]	Yuan D M, Hong Y G, Ho D W, Jiang G P. Optimal distributed stochastic mirror descent for strongly convex optimization. Automatica, 2018, 90: 196−203 doi: 10.1016/j.automatica.2017.12.053
[17]	Yang Y, Jia Q S, Xu Z B, Guan X H, Spanos C J. Proximal ADMM for nonconvex and nonsmooth optimization. Automatica, 2022, 146: 110551
[18]	Hou J, Zeng X L, Wang G, Sun J, Chen J. Distributed momentum-based Frank-Wolfe algorithm for stochastic optimization. IEEE/CAA Journal of Automatica Sinica, 2022, 10(3): 685−699
[19]	Chen S X, Garcia A, Shahrampour S. On distributed nonconvex optimization: Projected subgradient method for weakly convex problems in networks. IEEE Transactions on Automatic Control, 2021, 67(2): 662−675
[20]	Wei M L, Yu W W, Liu H Z, Xu Q. Distributed weakly convex optimization under random time-delay interference. IEEE Transactions on Network Science and Engineering, 2024, 11(1): 212−224 doi: 10.1109/TNSE.2023.3294414
[21]	Wang Y H, Zhao W X, Hong Y G, Zamani M. Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks. SIAM Journal on Control and Optimization, 2019, 57(4): 2821−2842 doi: 10.1137/18M119046X
[22]	Pang Y P, Hu G Q. Randomized gradient-free distributed optimization methods for a multiagent system with unknown cost function. IEEE Transactions on Automatic Control, 2019, 65(1): 333−340
[23]	Pang Y P, Hu G Q. Gradient-free distributed optimization with exact convergence. Automatica, 2022, 144: 110474
[24]	Yi X L, Zhang S J, Yang T, Johansson K H. Zeroth-order algorithms for stochastic distributed nonconvex optimization. Automatica, 2022, 142: 110353 doi: 10.1016/j.automatica.2022.110353
[25]	Xu L, Yi X L, Deng C, Shi Y, Chai T Y, Yang T. Quantized zeroth-order gradient tracking algorithm for distributed nonconvex optimization under Polyak-Łojasiewicz condition. IEEE Transactions on Cybernetics, 2024, 54(10): 5746−5758 doi: 10.1109/TCYB.2024.3384924
[26]	Wang R Y, Fan Y, Cheng S S. Zeroth-order algorithm design with orthogonal direction for distributed weakly convex optimization, the 63rd IEEE Conference on Decision and Control (CDC2024), 2024, Milan, Italy.
[27]	Juditsky A, Kwon J, Moulines É. Unifying mirror descent and dual averaging. Mathematical Programming, 2023, 199: 793−830
[28]	Moreau J J. Proximitè et dualitè dans un espace hilbertien. Bull. De La Sociètè Mathèmatique De France, 1965, 93: 273−299
[29]	刘浩洋, 户将, 李勇锋, 文再文. 最优化: 建模、算法与理论. 北京: 高等教育出版社, 2020. Liu Hao-Yang, Hu Jiang, Li Yong-Feng, Wen Zai-Wen. Optimization: Modeling, Algorithm and Theory. Beijing: Higher Education Press, 2020.
[30]	Ram S S, Nedić A, Veeravalli V V. Distributed stochastic subgradient projection algorithms for convex optimization. Journal of Optimization Theory and Applications, 2010, 147: 516−545 doi: 10.1007/s10957-010-9737-7
[31]	Zhou W X, Zhou Y, Chen X L, Ning T T, Chen H Y, Guo Q, Zhang Y W, Liu P X, Zhang Y J, Li C, Chu Y C, Sun T, Jiang C. Pancreatic cancer-targeting exosomes for enhancing immunotherapy and reprogramming tumor microenvironment. Biomaterials, 2021, 268: 120546 doi: 10.1016/j.biomaterials.2020.120546