A HYBRID PROXIMAL EXTRAGRADIENT SELF-CONCORDANT PRIMAL BARRIER METHOD FOR MONOTONE VARIATIONAL INEQUALITIES

被引:5
|
作者
Monteiro, Renato D. C. [1 ]
Sicre, Mauricio R. [2 ]
Svaiter, B. F. [3 ]
机构
[1] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA
[2] Univ Fed Bahia, Inst Matemat, BR-40170110 Salvador, BA, Brazil
[3] Inst Matematica Pura & Aplicada, BR-22460320 Rio De Janeiro, RJ, Brazil
基金
美国国家科学基金会;
关键词
self-concordant barriers; hybrid proximal extragradient; interior-point methods; monotone variational inequality; complexity; Newton method; ITERATION-COMPLEXITY; CUBIC REGULARIZATION; CONVEX-OPTIMIZATION; POINT ALGORITHM; OPERATORS; ENLARGEMENT;
D O I
10.1137/130931862
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
This paper presents a hybrid proximal extragradient (HPE) self-concordant primal barrier method for solving a monotone variational inequality over a closed convex set endowed with a self-concordant barrier and with an underlying map that has Lipschitz continuous derivative. In contrast to the iteration of a previous method developed by the first and third authors that has to compute an approximate solution of a linearized variational inequality, the one of the present method solves a simpler Newton system of linear equations. The method performs two types of iterations, namely, those that follow ever changing interior paths and those that correspond to large-step HPE iterations. Due to its first-order nature, the present method is shown to have a better iteration-complexity than its zeroth order counterparts such as Korpelevich's algorithm and Tseng's modified forward-backward splitting method, although its work per iteration is larger than the one for the latter methods.
引用
收藏
页码:1965 / 1996
页数:32
相关论文
共 50 条