Least Change Secant Update Methods for Nonlinear Complementarity Problem

Métodos secantes de cambio mínimo para el problema de complementariedad no lineal

En este trabajo generamos una familia de métodos secante de cambio mínimo para resolver Problemas de Complementariedad no Lineal vía su reformulación como un sistema de ecuaciones no lineales no diferenciable usando una clase de funciones de complementariedad propuesta por Kanzow and Kleinmichel. Bajo ciertas hipótesis demostramos que esta familia proporciona algoritmos local y superlinealmente convergentes. Experimentos numéricos preliminares demuestran un buen desempeño de los algoritmos propuestos.

1 INTRODUCCIÓN

Sea F:ℝn → ℝn, F(x)=(F₁(x),...,F_n(x)) una cartografía continuamente diferenciable. El problema de complementariedad no lineal, NCP por sus siglas en inglés, consiste en encontrar un vector x ∈ ℝn tal que,

​$x\ge 0,F(x)\ge 0,x^{T}F(x)=0.$     (1)

Aquí, y ≥ 0 para y ∈ ℝn significa y_i ≥ 0 para y todo i=1,...,n. La tercera condición en (1) requiere que los vectores x y F(x) sean ortogonales; por esta razón, se llama condición de complementariedad.

La NCP surge en muchas aplicaciones tales como problemas de contacto mecánico por fricción [1], problemas de diseño de mecánica estructural, problemas de elasto-hidrodinámica de lubricación [2], problemas de equilibrio de tráfico [3], así como problemas relacionados con modelos de equilibrio económico [4]. La importancia de la PNC en las áreas de Física, Ingeniería y Economía se debe a que el concepto de complementariedad es sinónimo de la noción de sistema en equilibrio. En los últimos años se han estudiado diversas técnicas para resolver el NCP, una de las cuales consiste en reformularlo como un sistema no liso de ecuaciones no lineales utilizando funciones especiales denominadas funciones de complementariedad [5]. Una función φ: ℝ₂→ ℝ tal que

​$\phi (a,b)=0\Leftarrow \Rightarrow a\ge 0,b\ge 0,ab=0,$     (2)

se llama función de complementariedad.

Geométricamente, la equivalencia (2) significa que la traza de la función φ obtenida por la intersección con el plano xy es la curva formada por los semiejes positivos x e y, que no es diferenciable en (0,0). Esta falta de suavidad en la curva implica la no diferenciabilidad de la función φ.

Para reformular el NCP como un sistema de ecuaciones no lineales, es necesario considerar una función de complementariedad φ y definir Φ: ℝn→ ℝn mediante

​$Φ (x) = egin{pmatrix} φ(x_1,F_1(x)) φ(x_n,F_n(x)) end{pmatrix},$     (3)