Métodos de Newton y cuasi-Newton para el problema de complementariedad generalizado

Abstract

En este trabajo de investigación, consideramos el problema de complementariedad generalizado y, con el fin de resolverlo, lo reformulamos, no solo como un sistema de ecuaciones no lineales no diferenciable mediante una familia uniparamétrica de funciones de complementariedad, sino como un problema de minimización continuamente diferenciable. Analizamos detalladamente el operador que define la reformulación como un sistema de ecuaciones no lineales y demostramos que los resultados obtenidos por otros autores para complementariedad no lineal se extienden naturalmente al problema de complementariedad generalizado. Para resolver el sistema de ecuaciones no lineales, e indirectamente el problema de complementariedad generalizado, proponemos inicialmente un algoritmo global, no suave, tipo Newton, para el cual demostramos resultados de convergencia global y analizamos su desempeño numérico. Posteriormente, con el mismo fin, proponemos una familia de métodos secantes de cambio mínimo, desarrollamos su respectiva teoría de convergencia y analizamos su desempeño numérico. Con el fin de globalizar la familia de métodos secantes, introducimos una búsqueda lineal libre de derivadas, con lo cual proponemos un algoritmo global genérico para resolver el problema de complementariedad generalizado mediante su reformulación como un problema de minimización. El carácter genérico del algoritmo se debe a que no se especifica la forma de actualizar las aproximaciones de las matrices del jacobiano generalizado. Bajo ciertas hipótesis, presentamos resultados de convergencia global para el nuevo algoritmo. Finalmente, abordamos el problema de la actualización de las aproximaciones basándonos en la teoría secante de cambio mínimo, con lo cual obtenemos un nuevo algoritmo global tipo secante y libre de derivadas para resolver el problema de complementariedad generalizado, el cual es un caso particular del algoritmo genérico propuesto previamente. Demostramos que cualquier sucesión generada por el nuevo algoritmo satisface las hipótesis de convergencia del algoritmo genérico heredando así, sus resultados de convergencia. Complementamos el desarrollo teórico con un análisis del desempeño numérico del algoritmo propuesto.

In this work, we consider the generalized complementarity problem. To solve it, we reformulate it as a nonsmooth system of equations using a one-parameter family of complementarity functions and as a minimization problem. We analyze in detail the operator that defines the reformulation as a system of equations and we show that the results obtained by other authors for nonlinear complementarity naturally extend to the generalized complementarity problem. In order to solve the system of nonlinear equations and indirectly the generalized complementarity problem, we initially propose a nonsmooth global Newton-type algorithm, for which we demonstrate global convergence results and analyze its numerical performance. After, with the same purpose, we propose a family of least-change secant methods, develop their respective theory of convergence, and analyze their numerical performance. To globalize the family of secant methods, we introduce a derivative-free linear search and propose a generic global algorithm to solve the generalized complementarity problem using its reformulation as a minimization problem. The generic name of the algorithm is due to the fact that the way to update the approximations of the generalized Jacobian matrices is not specified. Under certain hypotheses, we present global convergence results for the new algorithm. Finally, we analyze the problem of updating the approximations. We use leastchange secant theory and obtain a new derivative-free secant-type global algorithm which is a particular case of the generic algorithm. We show that any sequence generated by the new algorithm satisfies the convergence hypotheses of the generic algorithm, thus it inherit its convergence results. We complement the theoretical development with an analysis of the numerical performance of the proposed algorithm.