TY - JOUR
T1 - Steplengths in the extragradient type methods
AU - Wang, Xiang
AU - He, Bingsheng
AU - Liao, Li Zhi
N1 - Funding Information:
This research was supported in part by grants from Hong Kong Baptist University (FRG) and the Research Grant Council of Hong Kong.
PY - 2010/4/1
Y1 - 2010/4/1
N2 - The extragradient type methods are a class of efficient direct methods. For solving monotone variational inequalities, these methods only require function evaluation, and therefore are widely applied to black-box models. In this type of methods, the distance between the iterate and a fixed solution point decreases by iterations. Furthermore, in each iteration, the negative increment of such squared distance has a differentiable concave lower bound function without requiring any solution in its formula. In this paper, we investigate some properties for the lower bound. Our study reveals that the lower bound affords a steplength domain which guarantees the convergence of the entire algorithm. Based on these results, we present two new steplengths. One involves the projection onto the tangent cone without line search, while the other can be computed via searching the positive root of a one dimension concave lower bound function. Our preliminary numerical results confirm and illustrate the attractiveness of our contributions.
AB - The extragradient type methods are a class of efficient direct methods. For solving monotone variational inequalities, these methods only require function evaluation, and therefore are widely applied to black-box models. In this type of methods, the distance between the iterate and a fixed solution point decreases by iterations. Furthermore, in each iteration, the negative increment of such squared distance has a differentiable concave lower bound function without requiring any solution in its formula. In this paper, we investigate some properties for the lower bound. Our study reveals that the lower bound affords a steplength domain which guarantees the convergence of the entire algorithm. Based on these results, we present two new steplengths. One involves the projection onto the tangent cone without line search, while the other can be computed via searching the positive root of a one dimension concave lower bound function. Our preliminary numerical results confirm and illustrate the attractiveness of our contributions.
KW - Black-box model
KW - Extragradient type methods
KW - Monotone variational inequalities
KW - Projection
UR - http://www.scopus.com/inward/record.url?scp=75149118756&partnerID=8YFLogxK
U2 - 10.1016/j.cam.2009.11.037
DO - 10.1016/j.cam.2009.11.037
M3 - Journal article
AN - SCOPUS:75149118756
SN - 0377-0427
VL - 233
SP - 2925
EP - 2939
JO - Journal of Computational and Applied Mathematics
JF - Journal of Computational and Applied Mathematics
IS - 11
ER -