Golden ratio algorithms for variational inequalities

• 成果类型: Article
• 署名作者: Malitsky, Yura
• 署名单位: University of Gottingen
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01416-w
• 发表日期: 2020
• 页码: 383-410
• 关键词: backward splitting method; inertial proximal method; monotone-operators; saddle-point; korpelevichs methods; convex-optimization; 1st-order methods; iterative methods; gradient methods; CONVERGENCE

摘要

The paper presents a fully adaptive algorithm for monotone variational inequalities. In each iteration the method uses two previous iterates for an approximation of the local Lipschitz constant without running a linesearch. Thus, every iteration of the method requires only one evaluation of a monotone operatorFand a proximal mappingg. The operatorFneed not be Lipschitz continuous, which also makes the algorithm interesting in the area of composite minimization. The method exhibits an ergodicO(1 / k) convergence rate andR-linear rate under an error bound condition. We discuss possible applications of the method to fixed point problems as well as its different generalizations.