Forward Vs Backward Difference in Continuous Space

Continuous Optimization

The forward–backward–forward method from continuous and discrete perspective for pseudo-monotone variational inequalities in Hilbert spaces

Abstract

Tseng's forward–backward–forward algorithm is a valuable alternative for Korpelevich's extragradient method when solving variational inequalities over a convex and closed set governed by monotone and Lipschitz continuous operators, as it requires in every step only one projection operation. However, it is well-known that Korpelevich's method converges and can therefore be used also for solving variational inequalities governed by pseudo-monotone and Lipschitz continuous operators. In this paper, we first associate to a pseudo-monotone variational inequality a forward–backward–forward dynamical system and carry out an asymptotic analysis for the generated trajectories. The explicit time discretization of this system results into Tseng's forward–backward–forward algorithm with relaxation parameters, which we prove to converge also when it is applied to pseudo-monotone variational inequalities. In addition, we show that linear convergence is guaranteed under strong pseudo-monotonicity. Numerical experiments are carried out for pseudo-monotone variational inequalities over polyhedral sets and fractional programming problems.

Section snippets

Introduction and preliminaries

In this paper, the object of our investigation is the following variational inequality of Stampacchia type:

Find x* ∈C such that $〈F\left(x^{*}\right),x-x^{*}〉\ge 0\forall x\in C,$ where C is a nonempty, convex and closed subset of the real Hilbert space H, endowed with inner product ⟨ · ,  · ⟩ and corresponding norm ‖ · ‖, and F: H →H is a Lipschitz continuous operator. We abbreviate the problem (1) as VI(F, C) and denote its solution set by Ω.

Variational inequalities (VIs) are powerful mathematical models which unify

A dynamical system of forward–backward–forward type

In this section we will approach the solution set of VI(F, C) from a continuous perspective by means of trajectories generated by the following dynamical system of forward–backward–forward type $\{\begin{array}{cc}y\left(t\right)\hfill & =P_C(x\left(t\right)-\lambda F\left(x\left(t\right)\right))\hfill \\ \dot{x}\left(t\right)+x\left(t\right)\hfill & =y\left(t\right)+\lambda \left[F\right(x\left(t\right))-F(y\left(t\right)\left)\right]\hfill \\ x\left(0\right)\hfill & =x_0,\hfill \end{array}$ where λ > 0 and x ₀ ∈H. The formulation of (4) has its roots in Banert and Boţ (2018), where the continuous counterpart of Tseng's algorithm has been considered in the more general context of a monotone inclusion problem. The existence and

The forward–backward–forward algorithm with relaxation parameters

In this section we analyze the convergence of Tseng's forward–backward–forward algorithm with relaxation parameters derived in Remark 2.1 by the time discretization of the dynamical system (4) in the context of solving pseudo-monotone variational inequalities.

Algorithm 3.1

Initialization: Choose the starting point x ₀ ∈H, the step size λ > 0, and the sequence of relaxation parameters (ρ_n ) _n ≥ 0. Set $n=0$ .

Step 1: Compute $y_n=P_C(x_n-\lambda F\left(x_n\right)).$

If $y_n=x_n$ or $F\left(y_n\right)=0,$ then STOP: y_n is a solution.

Step 2: Set $x_{n+1}={\rho }_n(y_n+\lambda (F(x_{}$

Numerical experiments

In this section we present two numerical experiments which we carried out in order to compare Algorithm 3.1 with other algorithms in the literature designed for solving pseudo-monotone variational inequalities. We implemented the numerical codes in Matlab and performed all computations on a Linux desktop with an Intel(R) Core(TM) i5-4670S processor at 3.10 gigahertz. In our experiments we considered only variational inequalities governed by pseudo-monotone operators which are not monotone.

Let

Conclusions and further research

The object of our investigation was a variational inequality of Stampacchia type over a nonempty, convex and closed set governed by a pseudo-monotone and Lipschitz continuous operator. We associated to it a forward–backward–forward dynamical system and carried out a Lyapunov-type analysis in order to prove the asymptotic convergence of the generated trajectories to a solution of the variational inequality. The explicit time discretization of the dynamical system leads to Tseng's

Acknowledgments

The authors are grateful to three anonymous reviewers for their pertinent comments and remarks which improved the quality of the paper.

References (34)

• et al.

  Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces

  Journal of Optimization Theory and Applications

  (2014)

• S. Banert et al.

  A forward-backward-forward differential equation and its asymptotic properties

  Journal of Convex Analysis

  (2018)

• H.H. Bauschke et al.

  Convex analysis and monotone operator theory in hilbert spaces

  CMS books in mathematics

  (2011)

• J.Y. Bello Cruz et al.

  Convergence of direct methods for paramonotone variational inequalities

  Computational Optimization and Applications

  (2010)

• M. Bianchi et al.

  On pseudomonotone maps t for which $-t$ is also pseudomonotone

  Journal of Convex Analysis

  (2003)

• R.I. Boţ et al.

  Proximal-gradient algorithms for fractional programming

  Optimization

  (2017)

• J.M. Borwein et al.

  Convex analysis and nonlinear optimization: Theory and examples

  (2006)

• L.C. Ceng et al.

  Weak convergence of an iterative method for pseudomonotone variational inequalities and fixed-point problems

  Journal of Optimization Theory and Applications

  (2010)

• Y. Censor et al.

  The subgradient extragradient method for solving variational inequalities in Hilbert space

  Journal of Optimization Theory and Applications

  (2011)

• Y. Censor et al.

  Extensions of Korpelevich's extragradient method for the variational inequality problem in euclidean space

  Optimization

  (2012)

R.W. Cottle et al.

On pseudo-convex functions of nonnegative variables

Mathematical Programming

(1971)

R.W. Cottle et al.

Pseudo-monotone complementarity problems in Hilbert space

Journal of Optimization Theory and Applications

(1992)

C.D. Dang et al.

On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators

Computational Optimization and Applications

(2015)

F. Facchinei et al.

Finite-dimensional variational inequalities and complementarity problems

(2003)

N. Hadjisavvas et al.

Pseudomonotone operators: A survey of the theory and its applications

Journal of Optimization Theory and Applications

(2012)

P.T. Harker et al.

A damped-Newton method for the linear complementarity problem

S. Karamardian et al.

Seven kinds of monotone maps

Journal of Optimization Theory and Applications

(1990)

Cited by (67)

Recommended articles (6)

View full text

© 2020 Elsevier B.V. All rights reserved.

linoldideady.blogspot.com

Source: https://www.sciencedirect.com/science/article/abs/pii/S037722172030388X