| Revista: | Computational & applied mathematics |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000272471 |
| ISSN: | 1807-0302 |
| Autores: | Iusem, Alfredo N1 Kallio, Markku2 |
| Instituciones: | 1Instituto de Matematica Pura e Aplicada, Rio de Janeiro. Brasil 2Helsinki School of Economics, Helsinki. Finlandia |
| Año: | 2004 |
| Volumen: | 23 |
| Número: | 1 |
| Paginación: | 1-31 |
| País: | Brasil |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Aplicado, descriptivo |
| Resumen en inglés | 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 |
| Disciplinas: | Ciencias de la computación, Matemáticas |
| Palabras clave: | Matemáticas puras, Punto silla, Desigualdades variacionales, Programación lineal, Métodos de punto interior, Distancias de Bregman |
| Keyword: | Computer science, Mathematics, Pure mathematics, Saddle point, Variational inequalities, Linear programming, Interior point methods, Bregman distance |
| Texto completo: | Texto completo (Ver HTML) |
