6
$\begingroup$

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.

$\endgroup$

5 Answers 5

7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

I can confirm that there is no agreement of what "extragradient method" really means. I know the interpretation by Christian Clason but I also know the one that is linked in Carlo Beenakkers answer. Let me add my point of view:

For simplicity consider a convex minimization problem $$ \min_{x\in C} F(x) $$ with a convex , lower semi-continuous function $F$ and a convex, closed set $C$.

Optima $u^*$ of this problem are characterized by $$ u^* = P_C(u^* - \sigma\nabla F(u^*)) $$ where $P_C$ is the projection onto $C$ and $\sigma>0$. Doing a fixed point iteration for this equation gives $$ u^{n+1} = P_C(u^n - \sigma\nabla F(u^n)), $$ which is the standard projected gradient method.

Now we introduce a new variable $\bar u$ in the optimality condition and write it as $$ u^* = P_c(u^* - \sigma\nabla F(\bar u)),\qquad u^* = \bar u. $$ This seems artificial but now we can devise a new iteration and decide on different update rules for the artificial variable $\bar u$. The projected gradient method just takes $\bar u^{n+1} = u^{n+1}$. The extragradient method uses another extra gradient step for the new variable and reads as $$ u^{n+1} = P_C(u^n - \sigma\nabla F(\bar u^n)),\qquad \bar u^{n+1} = P_C(u^{n+1} - \sigma \nabla F(\bar u^n)) $$ The benefit of this approach is that, although you make a new gradient step and usually have "better convergence", you have to evaluate the gradient of $F$ only once per iteration (but have to do two projections). If the cost for the evaluation of the gradient dominates the cost for the projection the, you may gain something.

A similar motivation for extragradient methods can be done for methods for variational inequalities, monotone inclusions or saddle-point problems…

$\endgroup$
5
$\begingroup$

it seems that Dirk's comment has some problem: Extragradient method, in each iteration, evaluate the gradient at two different points, but not reuse the gradient evaluation:

This seems artificial but now we can devise a new iteration and decide on different update rules for the artificial variable $\bar u$. The projected gradient method just takes $\bar u^{n+1} = u^{n+1}$. The extragradient method uses another extra gradient step for the new variable and reads as $$ u^{n+1} = P_C(u^n - \sigma\nabla F(\bar u^n)),\qquad \bar u^{n+1} = P_C(u^{n+1} - \sigma \nabla F(\bar u^n)) $$ The benefit of this approach is that, although you make a new gradient step and usually have "better convergence", you have to evaluate the gradient of $F$ only once per iteration (but have to do two projections). If the cost for the evaluation of the gradient dominates the cost for the projection the, you may gain something.

In fact, according to Nesterov's 2003 dual extraploation paper: http://link.springer.com/article/10.1007%2Fs10107-006-0034-z#page-1

it should be writen as

$$ u^{n+1} = P_C(u^n - \sigma\nabla F(\bar u^n)),\qquad \bar u^{n+1} = P_C( u^n - \sigma \nabla F(u^{n+1})) $$

where the only reused part is $$u^n$$

$\endgroup$
3
  • 3
    $\begingroup$ Well, this shows that the term "extragradient" is indeed used differently. $\endgroup$
    – Dirk
    Feb 27, 2015 at 7:22
  • 1
    $\begingroup$ Could you please show me anywhere the extragradient is interpreted as re-using the gradient evaluated at one single point? Including papers about Korpelevich original method that Carlo posted in OP and some slides I found online, it seems that I have not seen the case of reusing the gradient. Cheers, $\endgroup$ Feb 28, 2015 at 8:03
  • $\begingroup$ So based on this answer, it seems that the extragradient method is similar to the implicit Euler method? $\endgroup$ Dec 14, 2022 at 13:48
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think this may correct, but it is for the simple case when there is no constraint set, and the method is not as interesting in this case. $\endgroup$
    – Stephen
    Apr 7, 2015 at 16:01
2
$\begingroup$

A good discussion is in this recent preprint: Proximal Reinforcement Learning. They use the same definition as in dragonxlwang's answer, and discuss its relation to the mirror-prox method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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