一种求解单调变分不等式的部分并行分裂LQP交替方向法

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

运筹学学报 ›› 2020, Vol. 24 ›› Issue (1): 101-114.doi: 10.15960/j.cnki.issn.1007-6093.2020.01.008

一种求解单调变分不等式的部分并行分裂LQP交替方向法

黎超琼, 李锋^*

云南师范大学数学学院, 昆明 650500

收稿日期:2017-12-22 发布日期:2020-03-09
通讯作者: 李锋 E-mail:lf_2364@126.com
基金资助:
国家自然科学基金（No.41671131）

A partial parallel splitting LQP alternating direction method of multipliers for solving monotone variational inequalities

LI Chaoqiong, LI Feng^*

School of Mathematics, Yunnan Normal University, Kunming 650500, China

Received:2017-12-22 Published:2020-03-09

摘要/Abstract

摘要： LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构，将原问题分解为多个更易求解的子问题，还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题，结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法，构造了新算法的两个下降方向，结合这两个下降方向得到了一个新的下降方向，沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下，证明了新算法的全局收敛性.

关键词: 变分不等式, 并行分裂法, LQP算法, 交替方向法

Abstract: Logarithmic-quadratic proximal (LQP) alternating direction method of multipliers is a very effective method for solving monotone variational inequality with separable structure. It can make full use of the objective function of the separable structure, the original problem is decomposed into multiple sub-problems which is easier to be solved. Logarithmic-quadratic proximal (LQP) alternating direction method of multipliers are also suitable ones for solving large-scale problem. For monotone variational inequality problem with three separable operators, combining the augmented Lagrangian method with the LQP alternating direction method of multipliers, a partial parallel splitting LQP alternating direction method of multipliers is obtained. We construct two descent directions, the new direction is obtained by combined with the two descent directions, and an appropriate step size is derived along this new descent direction. And we prove the global convergence of the algorithm under a weaker assumption.

Key words: variational inequality, parallel splitting method, logarithmic-quadratic proximal method, alternating direction method of multipliers

中图分类号:

O221.2

黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.

LI Chaoqiong, LI Feng. A partial parallel splitting LQP alternating direction method of multipliers for solving monotone variational inequalities[J]. Operations Research Transactions, 2020, 24(1): 101-114.

参考文献

[1] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite-element approximations[J]. Computers Mathematics with Applications, 1976, 2:17-40.
[2] Gabay D. Chapter ix applications of the method of multipliers to variational inequalities[J]. Studies in Mathematics and its Applications, 1983, 15:299-331.
[3] Boyd S, Parikh N, Chu E, et al. Distributed optimization andstatistical learning via the alternating direction method of multipliers[J]. Foundations & Trends in Machine Learning, 2010, 3:1-122.
[4] He B S, Liao L Z. Improvements of some projection methods for monotone nonlinear variational inequalities[J]. Journal of Optimization Theory and Applications, 2002, 112:111-128.
[5] Xu M H, Wu T. A class of linearized proximal alternating direction methods[J]. Journal of Optimization Theory and Applications, 2011, 151:321-337.
[6] Fazel M, Pong T K, Sun D F, et al. Hankel matrix rank minimization with applications to system identification and realization[J]. SIAM Journal on Matrix Analysis & Applications, 2013, 34:946-977.
[7] Yuan X M, Li M. An LQP-based decomposition method for solving a class of variational inequalities[J]. SIAM Journal on Optimization, 2011, 21(4):1309-1318.
[8] Auslender A, Teboulle M, Ben-Tiba S. A logarithmic-quadratic proximal method for variational inqualities[J]. Computational Optimization and Application, 1999, 12(1-3):31-40.
[9] Chen C H, He B S, Ye Y Y, et al. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent[DB-CD]. Mathematical Programming, 2016, 155(1-2):57-79.
[10] Hestenes M R. Multiplier and gradient methods[J]. Journal of Optimization Theory and Applications, 1969, 4:303-320.
[11] He B S. Parallel splitting augmented lagrangian methods for monotone structured variational inequalities[J]. Computational Optimization and Applications, 2009, 42:195-212.
[12] He B S, Tao M, Xu M H, et al. Alternating directions based contraction method for generally separable linearly constrained convex programming problems[J]. Optimization, 2013, 62:573-596.
[13] Zheng P, Wu D H. A partial parallel splitting augmented lagrangian method for solving constrained matrix optimization problems[J]. Computers and Mathematics with Applications, 2010, 60:1515-1524.
[14] Cao C X, Han D R, Xu L L. A new partial parallel splitting augmented lagrangian method for minimizing the sum of three convex functions[J]. Applied Mathematics and Computation, 2013, 219:5449-5457.
[15] 王宜举, 修乃华. 非线性最优化理论与方法[M]. 北京:科学出版社, 2012.
[16] Tao M, Yuan X M. On the O(1/t) convergence rate of alternating direction method with logarithmic-quadratic proximal regularization[J]. SIAM Journal on Optimization, 2012, 22(4):1431-1448.

一种求解单调变分不等式的部分并行分裂LQP交替方向法

A partial parallel splitting LQP alternating direction method of multipliers for solving monotone variational inequalities

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价

[1]	屈彪, 徐伟, 王新艳. 关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注[J]. 运筹学学报, 2021, 25(2): 144-148.
[2]	王秀玲, 龚循华. 对称向量拟均衡问题有效解的存在性[J]. 运筹学学报, 2021, 25(1): 73-80.
[3]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[4]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[5]	冯俊锴, 张海斌, 秦嫒, 张凯丽. 解一类结构变分不等式问题的非精确并行交替方向法[J]. 运筹学学报, 2018, 22(2): 18-30.
[6]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[7]	王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112.
[8]	何炳生. 修正乘子交替方向法求解三个可分离算子的凸优化[J]. 运筹学学报, 2015, 19(3): 57-70.
[9]	万芮, 徐姿. 广义交替近似梯度算法的线性收敛分析[J]. 运筹学学报, 2014, 18(3): 1-12.
[10]	杨赟, 彭拯. 可分离凸优化问题的非精确平行分裂算法[J]. 运筹学学报, 2014, 18(3): 33-46.
[11]	卢越, 张继宏, 张立卫. 一类二次规划逆问题的交替方向数值方法[J]. 运筹学学报, 2014, 18(2): 1-16.
[12]	黄正海, 林贵华, 修乃华. 变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展[J]. 运筹学学报, 2014, 18(1): 113-133.