A local Jacobian smoothing method for solving Nonlinear Complementarity Problems

Un método de alisamiento jacobiano local para resolver Problemas de complementariedad no lineal

En este trabajo, presentamos un suavizado de una familia de funciones de complementariedad no lineal y utilizamos sus propiedades en combinación con la estrategia del jacobiano suave para presentar un nuevo algoritmo generalizado de tipo Newton para resolver un sistema de ecuaciones no suave equivalente al Problema de Complementariedad No Lineal. Además, demostramos que el algoritmo converge localmente y q-cuadráticamente, y analizamos su rendimiento numérico.

INTRODUCCIÓN

Sea F : Rⁿ → Rⁿ una función continuamente diferenciable. El problema de complementariedad no lineal, NCP por sus siglas en inglés, consiste en encontrar un vector x ∈ Rⁿ que satisfaga las siguientes condiciones

x ≥ 0, F(x)≥0, x^TF(x) = 0.

Decimos que un vector en Rⁿ es no negativo si cada una de sus componentes es no negativa.

Existen numerosas y variadas aplicaciones de la NCP en Ingeniería [1, 2] y en Economía [3, 4]. En este último ámbito, complementariedad y equilibrio económico son sinónimos.

Una técnica, quizás la más popular, para resolver problemas de complementariedad no lineal es escribirlos de forma equivalente como un sistema de ecuaciones no lineal. En este proceso, se utiliza una función ϕ R² → R tal que

ϕ(a, b) = 0 ⇐⇒ a ≥ 0, b ≥ 0, ab = 0, (1)

llamada función de complementariedad [5].

La equivalencia (1) permite concluir que una función de complementariedad es no diferenciable debido a la falta de suavidad de su traza por la intersección con el plano xy que no es diferenciable en (0, 0).

Dada una función de complementariedad ϕ y una función Φ: Rⁿ → Rⁿ, definimos el sistema de ecuaciones no lineal por

          ϕ(x₁,F₁(x))

Φ(x) =                     =0, (2)

          ϕ(x_n,F_n(x))

que es no diferenciable debido a la falta de suavidad de ϕ. De (1) se deduce que una condición necesaria y suficiente para que un vector x_∗ resuelva la NCP es que este vector resuelva el sistema (2).

Dos ejemplos de funciones de complementariedad, muy utilizadas, son las siguientes

ϕ(a, b) = min{a, b}, ϕ(a, b) = √a² + b² - a - b,

que se denominan función mínima [6] y función de Fischer-Burmeister [7], respectivamente.