一种新的求解单调变分不等式的非精确并行分裂法

A new inexact parallel splitting method for monotone variational inequalities with separable structures

摘要:

本文提出了求解可分离结构单调变分不等式的一种新的非精确并行分裂算法。对于求解变分不等式式问题现已存在一些经典的算法如增广Lagrange法和交替方向法，但是它们均需要精确求解子变分不等式。然而实际中这些子变分不等式很难或者根本就无法得到精确解。因此最近一种非精确交替方向法被提了出来。但是当数据的维数很大的时候，并行分裂法比交替方向法更有效。基于这种非精确交替方向法，本文提出了一种新的并行分裂。在适当的条件下，本文给出了算法的收敛性证明，并且通过数值实验证明了算法的有效性。

Abstract:

This paper presents a new inexact parallel splitting method for solving variational inequalities (VIs) with separable structures. To solve VIs, some classical methods augmented Lagrangian method and alternating direction method of multipliers (ADMM) were presented, but they require solving sub-VIs exactly. However, these sub-VIs could be too difficult or impossible to be solved exactly in many practical applications. Recently, an inexact alternating direction method (IADM) was proposed in Chen (J Optim Theory Appl,2014,163:439). But when the dimensionality of data is tremendous large, parallel splitting method (PSM) is more efficient than ADMM. So based on IADM, we proposed a new inexact parallel splitting method (NIPSM). Convergence of the new method is proved under mild assumptions and some numerical results demonstrate that the new method NIPSM is efficient.