An Asymmetric Proximal Decomposition Method for Convex Programming with Linearly Coupling Constraints

The problems studied are the separable variational inequalities with linearly coupling constraints. Some existing decomposition methods are very problem specific, and the computation load is quite costly. Combining the ideas of proximal point algorithm (PPA) and augmented Lagrangian method (ALM), we propose an asymmetric proximal decomposition method (AsPDM) to solve a wide variety separable problems. By adding an auxiliary quadratic term to the general Lagrangian function, our method can take advantage of the separable feature. We also present an inexact version of AsPDM to reduce the computation load of each iteration. In the computation process, the inexact version only uses the function values. Moreover, the inexact criterion and the step size can be implemented in parallel. The convergence of the proposed method is proved, and numerical experiments are employed to show the advantage of AsPDM. 1. Introduction The original model considered here is the convex minimization problem with linearly coupling constraints: where , are given matrixes, are given -vector, and are the th block convex differentiable functions for each . This special problem is called convex separable problem. Problems possessing such separable structure arise in discrete-time deterministic optimal control and in the scheduling of hydroelectric power generation [1]. Note that are differentiable, setting ; by the well-known minimum principle in nonlinear programming, it is easy to get an equivalent form of problem (1.1): find such that where Problems of this type are called separable variational inequalities (VIs). We will utilize this equivalent formulation and provide method for solution of separable VI. One of the best-known algorithms for solving convex programming or equivalent VI is the proximal point algorithm (PPA) first proposed by Martinet (see [2]) and had been studied well by Rockafellar [3, 4]. PPA and its dual version, the method of multipliers, draw on a large volume of prior work by various authors [5–9]. However, classical PPA and most of its subsequence papers cannot take advantage of the separability of the original problem, and this makes them inefficient in solving separable structure problems. One major direction of PPA’s study is to develop decomposition methods for separable convex programming and VI. The motivations for decomposition techniques are splitting the problem into isolate smaller or easier subproblems and parallelizing computations on specific parallel computing device. Decomposition-type methods [10–14] for large-scale problems have been widely