An interior point method for constrained saddle point problems

AUTOR(ES)

Iusem, Alfredo N., Kallio, Markku

FONTE

Computational & Applied Mathematics

DATA DE PUBLICAÇÃO

2004

RESUMO

We present an algorithm for the constrained saddle point problem with a convex-concave function L and convex sets with nonempty interior. The method consists of moving away from the current iterate by choosing certain perturbed vectors. The values of gradients of L at these vectors provide an appropriate direction. Bregman functions allow us to define a curve which starts at the current iterate with this direction, and is fully contained in the interior of the feasible set. The next iterate is obtained by moving along such a curve with a certain step size. We establish convergence to a solution with minimal conditions upon the function L, weaker than Lipschitz continuity of the gradient of L, for instance, and including cases where the solution needs not be unique. We also consider the case in which the perturbed vectors are on certain specific curves starting at the current iterate, in which case another convergence proof is provided. In the case of linear programming, we obtain a family of interior point methods where all the iterates and perturbed vectors are computed with very simple formulae, without factorization of matrices or solution of linear systems, which makes the method attractive for very large and sparse matrices. The method may be of interest for massively parallel computing. Numerical examples for the linear programming case are given.

Documentos Relacionados

• An alternating LHSS preconditioner for saddle point problems
• Spectral properties of the preconditioned AHSS iteration method for generalized saddle point problems
• Security constrained optimal active power flow via network model and interior point method
• An inexact interior point proximal method for the variational inequality problem
• A numerical implementation of an interior point method for semidefinite programming