Totally relaxed, self-adaptive algorithm for solving variational inequalities over the intersection of sub-level sets

Abstract

In this paper we study the classical Variational Inequality (VI) over the intersection of sub-level sets of finite convex functions in real Hilbert spaces. The Subgradient Extragradient method of Censor et al. extend Korpelevich’s extragradient method by introducing an additional constructible set and then there is the need to calculate only one orthogonal projection onto the feasible set per each iteration instead of two as in. Motivated by this result, we propose a new extension, called the Totally Relaxed and Self-adaptive Subgradient Extragradient Method, which does not require the calculation of any exact projections onto the VI’s feasible set. Hence, any general convex feasible sets can be involved in the VI, such as the finite intersection of sub-level sets of convex functions. In our new scheme we also introduce an adaptive step-size rule which avoids the need to know a priori the Lipschitz constant of the VI associated mapping. Under mild and standard assumptions, we prove weak convergence of the proposed method at rate in the ergodic sense. Two numerical examples are presented to illustrate the behaviour and performances of out proposed scheme.

Keywords:

• Variational inequalities
• Lipschitz continuous mapping
• level sets
• half-spaces
• convergence rate

Acknowledgements

We wish to thank the anonymous referees for the thorough analysis and review, their comments and suggestions helped tremendously in improving the quality of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The first author’s work is supported by Open Fund of Tianjin Key Lab for Advanced Signal Processing [No. 2017ASP-TJ03]. Aviv Gibali’s work is supported by the EU FP7 IRSES program STREVCOMS [grant number PIRSES-GA-2013-612669].