Global Convergence Enhancement of Classical Linesearch Interior Point Methods for Mixed Complementarity Problems

Benedetta Morini
Dipartimento di Energetica "S. Stecco''
University of Florence
Italy

The problem we address is to find a solution of a Mixed Complementarity Problem (MCP), i.e. we seek for a vector x = (v,s,z) Î IRm+2n with s,z Î IRn+, that satisfies

H(x) = æ
ç
è
F(v,s,z)
SZ e
 ö
÷
ø 		= 0,
(1)
where F:IRm+2n ® IRm+n, S = diag(s), Z = diag(z), e = (1,1,¼,1)T Î IRn. MCPs are constrained nonlinear systems of equations which arise frequently in practice. In fact, many economics and engineering applications can be modeled by (1).

MCPs problems can be effectively solved by linesearch Interior Point methods. They are Quasi-Newton methods that start from a point (v0,s0,z0) such that s0,z0 Î IR++ and generate sequences of points in the region IRm×IRn++×IRn++. In particular, at the k-th iteration they compute a Newton-like step and apply a backtracking scheme along it in order to maintain sk+1 and zk+1 positive and to decrease a suitable merit function.

However, recent works have shown that these methods may manifest a weakness of convergence since they can converge to a point that is neither a solution of the MCP nor a stationary point for the merit function. Failures can be ascribed to an intrinsic flaw of the Newton direction. This phenomenon was first outlined in the 1970s by Powell in the simple context of nonlinear equations.

Here we consider the problem of enhancing the convergence properties of linesearch Interior Point methods. The globalization strategy we propose is designed to leave the Newton direction when it reveals to be unsatisfactory, i.e. when too many backtracks are required to maintain positive the bounded variables or to decrease the value of the merit function. The key feature of our proposal is the definition of a new piecewise linear path exploited by the backtracking strategy. The new path has a simple and inexpensive formulation. Moreover, the theoretical analysis of its properties yields to a strategy that allows for an automatic transition from the Newton direction to alternative directions. Theoretical and computational results show the effectiveness of our proposal.

This is a joint work with Stefania Bellavia, University of Florence.

File translated from TEX by TTH, version 1.94.
On 9 Jan 2003, 18:02.