可分离凸优化问题的非精确平行分裂算法

运筹学学报 ›› 2014, Vol. 18 ›› Issue (3): 33-46.

可分离凸优化问题的非精确平行分裂算法

杨赟¹, 彭拯^1,*

1. 福州大学数学与计算机科学学院, 福州 350108

出版日期:2014-09-15 发布日期:2014-09-15
通讯作者: 彭拯 E-mail:pzheng@fzu.edu.cn
基金资助:
国家自然科学基金(No. 61170308), 福建省自然科学基金(No. 2011J01008), 福州大学科技启动基金(No. 2013-XQ-29)

An inexact parallel splitting method for separable convex optimization problem

YANG Yun¹, PENG Zheng^1,*

1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China

Online:2014-09-15 Published:2014-09-15

摘要/Abstract

摘要： 针对一类可分离凸优化问题提出了一种非精确平行分裂算法. 该算法充分利用了所求解问题的可分离结构, 并对子问题进行非精确求解. 在适当的条件下, 证明了所提出的非精确平行分裂算法的全局收敛性, 初步的数值实验说明了算法有效性.

关键词: 凸优化, 可分离结构, 变分不等式, 平行分裂算法, 非精确

Abstract: In this paper, an inexact parallel splitting method is proposed for a class of separable convex optimization problem. The proposed method makes full use of the separability of the problem under consideration, and all sub-problems are solved inexactly. Under some suitable conditions, the convergence of the proposed method is proved. Some primary numerical results indicate the validity of the proposed method.

Key words: convex optimization, separable structure, variational inequality, parallel splitting method, inexact

中图分类号:

O221.2

杨赟, 彭拯. 可分离凸优化问题的非精确平行分裂算法[J]. 运筹学学报, 2014, 18(3): 33-46.

YANG Yun, PENG Zheng. An inexact parallel splitting method for separable convex optimization problem[J]. Operations Research Transactions, 2014, 18(3): 33-46.

参考文献

Yang J F, Zhang Y. Alternating direction algorithms for \ell_1-problems in compressive sensing [J]. SIAM Journal on Scientific Computing , 2011, 33 (1): 250-278.

Peng Z, Wu D H. An inexact parallel splitting augmented Lagrangian method for large system of linear equations [J]. Applied Mathematics and Computation , 2010, 216(5): 1624-1636.

曾玉华, 彭拯. 一种求解双目标规划的非精确交替方向法 [J]. 运筹学学报, 2010, 14(4): 121-128.

Chen C H, He B S, Yuan X M. Matrix completion via alternating direction methods [J]. IMA Journal of Numerical Analysis , 2012, 32(1): 227-245.

Tao M, He B S, Yuan X M. Solving a class of matrix minimization problems by linear variational inequality approaches [J]. Linear Algebra and its Applications , 2011, 434(11): 2343-2352.

Chan R H, Yang J F, Yuan X M. Alternating direction method for image inpainting in wavelet domain [J]. SIAM Journal on Imaging Sciences , 2011, 4(3): 807-826.

Nocedal J, Wright S J. Numerical Optimization [M]. New York: Springer-Verlag, 1999.

叶明露. 变分不等式的一类二次投影算法 [J]. 应用数学学报, 2012, 35(3): 529-535.

Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation [J]. Computers \& Mathematics with Applications, 1976, 2(1): 17-40.

Ye C H, Yuan X M. A descent method for structured monotone variational inequalities [J]. Optimization Methods and Software, 2007, 22(2): 329-338.

He B S, Liao L Z, Qian M J. Alternating projection based prediction-correction methods for structured variational inequalities [J]. Journal of Computational Mathematics , 2006, 24(6): 693-710.

Zhang W X, Han D R, Jiang S L. A modified alternating projection based prediction-correction method for structured variational inequalities [J]. Applied Numerical Mathematics, 2014, 83: 12-21.

He B S. Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities [J]. Computation Optimization and Applications, 2009, 42(2): 195-212.

Han D R, Yuan X M, Zhang W X. An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing [J]. Mathematics of Computation, 2014, 83: 2263-2291.

He B S, Xu M H. A general framework of contraction methods for monotone variational inequalities [J]. Pacific Journal of Optimization, 2008, 4(2): 195-212.

Li M, Yuan X M. An improved proximal-based decomposition method for structured monotone variational inequalities [J]. Applied Mathematics and Mechanics, 2007, 28(12): 1659-1668.

Han D, He H, Xu L. A proximal parallel splitting method for minimizing sum of convex functions with linear constraints [J]. Journal of Computational and Applied Mathematics, 2014, 256: 36-51.

Peng Z, Wu D H. An inexact proximal alternating directions method for monotone structured variational inequalities [C]// Proceedings of the International MultiConference of Engineers and Computer Scientists, 2010, 1977-1984.

Peng Z, Zhu W X. Partial inexact proximal alternating directions method for structured variational inequalities [J]. Optimization, 2014, 63(6): 1365-1376.

Fletcher R. Practical Methods of Optimization [M]. New York: John Wiley \& Sons, 2013.

[1]	黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.
[2]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[3]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[4]	冯俊锴, 张海斌, 秦嫒, 张凯丽. 解一类结构变分不等式问题的非精确并行交替方向法[J]. 运筹学学报, 2018, 22(2): 18-30.
[5]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[6]	何斯迈, 金羽佳, 王华, 葛冬冬. 在线学习方法综述: 汤普森抽样和其他方法[J]. 运筹学学报, 2017, 21(4): 84-102.
[7]	张勇, 叶万洲. 一种求解弹性l_2-l_q正则化问题的算法[J]. 运筹学学报, 2016, 20(4): 11-20.
[8]	王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112.
[9]	何炳生. 修正乘子交替方向法求解三个可分离算子的凸优化[J]. 运筹学学报, 2015, 19(3): 57-70.
[10]	程聪, 张立卫. 二次规划逆问题的牛顿方法[J]. 运筹学学报, 2014, 18(3): 60-70.
[11]	黄正海, 林贵华, 修乃华. 变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展[J]. 运筹学学报, 2014, 18(1): 113-133.
[12]	张杰, 徐成贤, 芮绍平. 线性二阶锥互补问题的一种非精确光滑算法[J]. 运筹学学报, 2011, 15(2): 95-102.