Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I've searched Google, but it seems that only research journal papers appear in search results, where some new, improved, or specialized extragradient method is discussed. I've also searched Wikipedia and Wolfram MathWorld.

I would like to perhaps know the straightforward definition of that, instead of deducing it from a number of articles, where the basic/original method is not defined.

share|improve this question

2 Answers 2

This is the key reference: G.M. Korpelevich, "The extragradient method for finding saddle points and other problems." Ekonomika i Matematicheskie Metody 12 (1976): 747-756.

I have not found this article online, but you can find a brief description here (page 1 and 2) and a more extensive description (with a convergence proof) here (pages 1-6). Volume II of Facchinei and Pang also has a chapter on the method.

share|improve this answer

Briefly, extragradient methods include an extrapolation step for the evaluation of the gradient for the next iteration, e.g., $$ \begin{aligned} \bar x^{k} &= x^k + \tau(x^k - x^{k-1}),\\ x^{k+1} &= x^k + \gamma_k \nabla f(\bar x^k), \end{aligned} $$ where $\gamma_k>0$ is a suitable step size and $\tau\in (0,1)$ is an extrapolation parameter.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.