Interior proximal extragradient method for equilibrium problems

Abstract

The Bregman function-based Proximal Point Algorithm (BPPA) is an efficient tool for solving equilibrium problems and fixed-point problems. Extending rather classical proximal regularization methods, the main additional feature consists in an application of zone coercive regularizations. The latter allows to treat the generated subproblems as unconstrained ones, albeit with a certain precaution in numerical experiments. However, compared to the (classical) Proximal Point Algorithm for equilibrium problems, convergence results require additional assumptions which may be seen as the price to pay for unconstrained subproblems. Unfortunately, they are quite demanding – for instance, as they imply a sort of unique solvability of the given problem. The main purpose of this paper is to develop a modification of the BPPA, involving an additional extragradient step with adaptive (and explicitly given) stepsize. We prove that this extragradient step allows to leave out any of the additional assumptions mentioned above. Hence, though still of interior proximal type, the suggested method is applicable to an essentially larger class of equilibrium problems, especially including non-uniquely solvable ones.

Keywords:

• Equilibrium problems
• fixed-point problems
• rescaled Bregman distances
• Proximal Point Algorithm
• interior-point effect

AMS Subject Classifications:

• 65J20
• 65K10
• 91A06
• 91A10

Notes

1 We refer to [11] for a detailed description of the enhancements compared to the original paper of Flåm and Antipin.

2 This assumption might also be replaced by conditions not occuring in [11, Theorem 1] as long as they still imply well-definedness of the studied method.

3 For the subsequent analysis, it is completely irrelevant whether or not.

4 Following a combination of the references,[22, 26] other examples may also be deduced, e.g. for being a ball. Of course, in case of more complex and / or unbounded feasible sets , it is rather unlikely that is explicitly invertible. Anyway, the extragradient step then still appears to be numerically attractive due to its above construction; for instance, it is uniquely solvable.