Content area
Full Text
Comput Optim Appl (2008) 41: 363375
DOI 10.1007/s10589-007-9107-z
Received: 20 March 2006 / Revised: 15 January 2007 / Published online: 7 November 2007 Springer Science+Business Media, LLC 2007
Abstract Probability-one homotopy algorithms have strong convergence characteristics under mild assumptions. Such algorithms for mixed complementarity problems (MCPs) have potentially wide impact because MCPs are pervasive in science and engineering. A probability-one homotopy algorithm for MCPs was developed earlier by Billups and Watson based on the default homotopy mapping. This algorithm had guaranteed global convergence under some mild conditions, and was able to solve most of the MCPs from the MCPLIB test library. This paper extends that work by presenting some other homotopy mappings, enabling the solution of all the remaining problems from MCPLIB. The homotopy maps employed are the Newton homotopy and homotopy parameter embeddings.
Keywords Globally convergent Newton homotopy Nonlinear embedding Complementarity Optimization
1 Introduction
Probability-one homotopy methods have proven to be extremely successful in solving smooth systems of highly nonlinear equations. A fundamental reason is that these
K. Ahuja
Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061, USAe-mail: mailto:[email protected]
Web End [email protected]
L.T. Watson ( )
Departments of Computer Science and Mathematics, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061, USAe-mail: [email protected]
S.C. Billups
Department of Mathematical Sciences, University of Colorado at Denver and Health Sciences Center, Denver, CO 80217-3364, USA
Probability-one homotopy maps for mixed complementarity problems
Kapil Ahuja Layne T. Watson Stephen C. Billups
364 K. Ahuja et al.
methods do not depend on descent of a merit function and so are insensitive to local uctuations that can cause descent-based methods to get stuck in a local minimum. Homotopy methods work by following the zero curve of an appropriately dened homotopy mapping. As long as the function satises certain global characteristics (which depend on the choice of homotopy mapping), the zero curve is guaranteed, with probability one, to reach a solution.
Motivated by this theoretical advantage and the practical successes of these methods, a number of papers have extended probability-one homotopy methods to solve complementarity problems. Early work addressed linear complementarity problems (LCPs) [19] and nonlinear complementarity problems (NCPs) [15]. Probability-one homotopies were rst applied to mixed complementarity problems in [3]. There, the homotopy algorithm only...