A Dynamical Systems Approach to Complementarity Problems

Abstract

none

The nonlinear complementarity problem (NCP) is not only central in the study of constrained optimization but also provides an important framework in modelling equilibrium problems in several areas such as engineering, economics and operations research. We solve the NCP using systems of ordinary differential equations inspired by (i) a reformulation approach via complementarity functions and (ii) a special type of smoothing method for NCPs. First, a neural network model is constructed based on the discrete-type generalization of the natural residual (NR) function and its two symmetrizations. We establish several important properties of their induced merit functions which are necessary not only in neural network approach but also in most NCP functions-based algorithms. Using these results, we analyze the formulated dynamical systems with parameter $p\geq 3$, $p$ is odd. Numerical experiments suggest that lower values of $p$ provide optimal speed of convergence and are further recommended due to ill-conditioning problems encountered when $p$ is large. To provide better convergence results, we construct new NCP functions by proposing a continuous-type generalization of the NR function, together with two symmetrizations, which involve a continuous tunable parameter $p\in (1,\infty)$. The extension is meaningful as it offers more stable dynamical systems with faster convergence speeds. More importantly, we discovered one class of NCP functions which can outperform the traditionally used (generalized) Fischer-Burmeister function. Second, a novel smoothing approach for complementarity problems will also be utilized to construct alternative dynamical systems for solving the NCP. We use some family of functions to construct smooth perturbations of the zero-level curve of the NR function, and introduce two important subclasses which have significantly different theoretical and numerical properties. A simple framework for generating functions from these subclasses is proposed. We establish sufficient conditions to guarantee asymptotic and exponential stability. Comparisons between the NCP-based and the smoothing type neural networks are also presented.