- Research
- Open access
- Published:
Parallel LQP alternating direction method for solving variational inequality problems with separable structure
Journal of Inequalities and Applications volume 2014, Article number: 392 (2014)
Abstract
In this paper, we propose a logarithmic-quadratic proximal alternating direction method for structured variational inequalities. The predictor is obtained by solving series of related systems of nonlinear equations, and the new iterate is obtained by a convex combination of the previous point and the one generated by a projection-type method along a new descent direction. Global convergence of the new method is proved under certain assumptions. Preliminary numerical experiments are included to verify the theoretical assertions of the proposed method.
MSC: 90C33, 49J40.
1 Introduction
The problem we are concerned with in this paper is for the following variational inequalities: find such that
with
where , are given matrices, is a given vector, and , are given monotone operators. Studies and applications of such problems can be found in [1–11]. By attaching a Lagrange multiplier vector to the linear constraint , problem (1.1)-(1.2) can be explained in terms of finding such that
where
Problem (1.3)-(1.4) is referred to as SVI (structured variational inequalities).
The alternating direction method (ADM) is a powerful method for solving the structured problem (1.3)-(1.4), since it decomposes the original problems into a series of subproblems with a lower scale, originally proposed by Gabay and Mercier [4] and Gabay [3]. The classical proximal alternating direction method (PADM) [12–15] is an effective numerical approach for solving variational inequalities with separable structure. In [16], He proposed splitting augmented Lagrangian methods for structured monotone variational inequalities whose operator is composed by two separable operators. For given , the predictor is obtained via the following steps:
Step 1. Solve the following variational inequality to obtain :
Step 2. Solve the following variational inequality to obtain :
Step 3. Update via
The main advantage of the method of [16] is that the predictor is obtained by solving subproblems in a parallel wise. Recently, Yuan and Li [17] have developed a logarithmic quadratic proximal (LQP)-based decomposition method by applying the LQP terms to regularize the ADM subproblems. The new iterative in [17] is obtained via the following procedure: From a given , and , is obtained via solving the following system:
where . Note that the LQP method was presented originally in [18]. Later, Bnouhachem et al. [19–21] have proposed a new inexact LQP alternating direction method by solving a series of related systems of nonlinear equations. Very recently, Li [22] presented an LQP-based prediction-correction method: the new iterate is obtained by a convex combination of the previous point and the one generated by a projection-type method along a descent direction.
In the present paper, inspired by the above cited works and by the recent works going in this direction, we proposed a new LQP-based prediction-correction method. The predictor is obtained by using the idea of He [16] to solve series of related systems of nonlinear equations, and the new iterate is obtained by a convex combination of the previous point and the one generated by a projection-type method along another descent direction. Under certain conditions, we proved the global convergence of the proposed algorithm. Preliminary numerical experiments are included to verify the theoretical assertions of the proposed method.
2 The proposed method
In this section, we recall some basic definitions and properties, which will be frequently used in our later analysis. Some useful results proved already in the literature are also summarized. The first lemma provides some basic properties of projection onto Ω.
Lemma 2.1 Let G be a symmetric positive definite matrix and Ω be a nonempty closed convex subset of , we denote as the projection under the G-norm, i.e.,
Then, we have the following inequalities:
In course, we always make the following standard assumptions:
Assumption A f is monotone with respect to and g is monotone with respect to .
Assumption B The solution set of SVI, denoted by , is nonempty.
Now, we suggest and consider the new LQP alternating direction method (LQP-ADM) for solving SVI as follows.
Prediction step: For a given , and , the predictor is obtained via solving the following system:
Correction step: The new iterate is given by
where
and
We need the following result in the convergence analysis of the proposed method.
Lemma 2.2 [17]
Let q be a monotone mapping of u with respect to and be positive definite diagonal matrix. For given , if we let and be an n-vector whose jth element is , then the equation
has a unique positive solution u. Moreover, for any , we have
In the next theorem, we show that is lower bounded away from zero, and it is one of the keys to prove the global convergence results.
Theorem 2.1 For given , let be generated by (2.4a)-(2.4c), then we have the following:
and
Proof It follows from (2.7) that
By using the Cauchy-Schwarz inequality, we have
and
Substituting (2.13) and (2.14) into (2.12), we get
Therefore, it follows from (2.6) and (2.10) that
and this completes the proof. □
3 Basic results
In this section, we prove some basic properties, which will be used to establish the sufficient and necessary conditions for the convergence of the proposed method. The following results are due to applying Lemma 2.2 to the LQP system in the prediction step of the proposed method.
Lemma 3.1 For given , let be generated by (2.4a)-(2.4c). Then for any , we have
and
where
Proof Applying Lemma 2.2 to (2.4a) by setting , , in (2.9) and
we get
Recall
Adding (3.4) and (3.5), we obtain
Similarly, applying Lemma 2.2 to (2.4b), substituting , , , and replacing R, n with S, m, respectively, in (2.9) and
we get
Recall
Adding (3.6) and (3.7), we have
The assertion of this lemma is proved. □
Theorem 3.1 Let , be defined by (2.5) and
then we have
Proof It follows from (3.1) and (3.2) that
which implies
Since and , it follows from (2.3) that
From (2.5), we get
Using the following identity:
for , , and (3.11), we obtain
Using the definition of and (3.12), we get
Using the monotonicity of f and g, we obtain
and consequently
and it follows that
Applying (3.14) to the last term on the right side of (3.13), we obtain
Adding (3.10) (multiplied by σ) to (3.15), we get
and by using the notation of in (2.7), the theorem is proved. □
From the computational point of view, a relaxation factor is preferable in the correction. We are now in a position to prove the contractive property of the iterative sequence.
Theorem 3.2 Let be a solution of SVI and let be generated by (2.5). Then and are bounded sequences, and
where
Proof It follows from (3.9), (2.10), and (2.11) that
Since , we have
and thus is a bounded sequence.
It follows from (3.16) that
which means that
Since is a bounded sequence, we conclude that is also bounded. □
4 Convergence of the proposed method
In this section, we prove the global convergence of the proposed method. The following results can be proved by using the technique of Lemma 5.1 in [19].
Lemma 4.1 For given , let be generated by (2.4a)-(2.4c). Then for any , we have
and
Proof Similarly as in (3.4), we have
which implies
By a simple manipulation, we have
and the assertion (4.1) is proved. Similarly we can prove the assertion (4.2). □
Now, we are ready to prove the convergence of the proposed method.
Theorem 4.1 The sequence generated by the proposed method converges to some which is a solution of SVI.
Proof It follows from (3.17) that
and
Moreover, (4.1) and (4.2) imply that
and
We deduce from (4.3) that
Since is bounded, it has at least one cluster point. Let be a cluster point of and the subsequence converges to . It follows from (4.4) and (4.5) that
and consequently
which means that is a solution of SVI.
Now, we prove that the sequence converges to . Since
for any , there exists an such that
Therefore, for any , it follows from (3.16) and (4.6) that
This implies that the sequence converges to which is a solution of SVI. □
5 Preliminary computational results
In this section, we report some numerical results of the proposed method, we consider the following optimization problem with matrix variables:
where is the matrix Fröbenius norm, i.e., ,
Note that the matrix Fröbenius norm is induced by the inner product
Note that problem (5.1) is equivalent to the following:
by attaching a Lagrange multiplier to the linear constraint , the Lagrange function of (5.2) is
which is defined on . If is a KKT point of (5.2), then (5.2) can be converted to the following variational inequality: find such that
Problem (5.3) is a special case of (1.3)-(1.4) with matrix variables, where , , , , and .
For simplification, we take , and where and are scalars. In all tests we take , and as the initial point in the test. The iteration is stopped as soon as
All codes were written in Matlab, we compare the proposed method with that in [22]. The iteration numbers, denoted by k, and the computational time for problem (5.1) with different dimensions are given in Tables 1 and 2.
Tables 1 and 2 show that the proposed method is more flexible and efficient. Moreover, it demonstrates computationally that the new method is more effective than the method presented in [22] in the sense that the new method needs fewer iterations and less computational time.
6 Conclusions
In this paper, we propose a new logarithmic-quadratic proximal alternating direction method (LQP-ADM) for solving structured variational inequalities. Each iteration of the new LQP-ADM includes a prediction step, where a prediction point is obtained by using the idea of He [16], and a correction step, where the new iterate is generated by a convex combination of the previous iterate and the one generated by a projection-type method along a new descent direction. Global convergence of the proposed method is proved under mild assumptions.
References
Eckstein J, Bertsekas DB: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 1992, 55: 293-318. 10.1007/BF01581204
Fortin M, Glowinski R: Augmented Lagrangian Methods: Applications to the Solution of Boundary-Valued Problems. North-Holland, Amsterdam; 1983.
Gabay D: Applications of the method of multipliers to variational inequalities. In Augmented Lagrange Methods: Applications to the Solution of Boundary-Valued Problems. Edited by: Fortin M, Glowinski R. North-Holland, Amsterdam; 1983:299-331.
Gabay D, Mercier B: A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 1976, 2: 17-40. 10.1016/0898-1221(76)90003-1
Glowinski R: Numerical Methods for Nonlinear Variational Problems. Springer, New York; 1984.
Glowinski R, Le Tallec P SIAM Studies in Applied Mathematics. In Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia; 1989.
Teboulle M: Convergence of proximal-like algorithms. SIAM J. Optim. 1997, 7: 1069-1083. 10.1137/S1052623495292130
He BS, Yang H: Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities. Oper. Res. Lett. 1998, 23: 151-161. 10.1016/S0167-6377(98)00044-3
Kontogiorgis S, Meyer RR: A variable-penalty alternating directions method for convex optimization. Math. Program. 1998, 83: 29-53.
Jiang ZK, Bnouhachem A: A projection-based prediction-correction method for structured monotone variational inequalities. Appl. Math. Comput. 2008, 202: 747-759. 10.1016/j.amc.2008.03.018
Tao M, Yuan XM: On the convergence rate of alternating direction method with logarithmic-quadratic proximal regularization. SIAM J. Optim. 2012,22(4):1431-1448. 10.1137/110847639
Chen G, Teboulle M: A proximal-based decomposition method for convex minimization problems. Math. Program. 1994, 64: 81-101. 10.1007/BF01582566
Eckstein J: Some saddle-function splitting methods for convex programming. Optim. Methods Softw. 1994, 4: 75-83. 10.1080/10556789408805578
He BS, Liao LZ, Han DR, Yang H: A new inexact alternating directions method for monotone variational inequalities. Math. Program. 2002, 92: 103-118. 10.1007/s101070100280
Hamdi A, Mishra SK: Decomposition methods based on augmented Lagrangians: a survey. In Topics in Nonconvex Optimization: Theory and Applications. Springer, Berlin; 2011:175-204.
He BS: Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities. Comput. Optim. Appl. 2009, 42: 195-212. 10.1007/s10589-007-9109-x
Yuan XM, Li M: An LQP-based decomposition method for solving a class of variational inequalities. SIAM J. Optim. 2011,21(4):1309-1318. 10.1137/070703557
Auslender A, Teboulle M, Ben-Tiba S: A logarithmic-quadratic proximal method for variational inequalities. Comput. Optim. Appl. 1999, 12: 31-40. 10.1023/A:1008607511915
Bnouhachem A, Benazza H, Khalfaoui M: An inexact alternating direction method for solving a class of structured variational inequalities. Appl. Math. Comput. 2013, 219: 7837-7846. 10.1016/j.amc.2013.01.067
Bnouhachem A, Xu MH: An inexact LQP alternating direction method for solving a class of structured variational inequalities. Comput. Math. Appl. 2014, 67: 671-680. 10.1016/j.camwa.2013.12.010
Bnouhachem A: On LQP alternating direction method for solving variational. J. Inequal. Appl. 2014., 2014: Article ID 80
Li M: A hybrid LQP-based method for structured variational inequalities. Int. J. Comput. Math. 2012,89(10):1412-1425. 10.1080/00207160.2012.688822
Acknowledgements
The authors would like to thank Qatar University for providing excellent research facilities under the Start-Up Grant: QUSG-CAS-DMSP-13/14-8.
Author information
Authors and Affiliations
Corresponding author
Additional information
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
All authors read and approved the final manuscript.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0), which permits use, duplication, adaptation, distribution, and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Bnouhachem, A., Hamdi, A. Parallel LQP alternating direction method for solving variational inequality problems with separable structure. J Inequal Appl 2014, 392 (2014). https://doi.org/10.1186/1029-242X-2014-392
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/1029-242X-2014-392