A Homotopy-Based Algorithm for Mixed Complementarity Problems

This paper develops an algorithm for solving mixed complementarity problems that is based upon probability-one homotopy methods. After the complementarity problem is reformulated as a system of nonsmooth equations, a homotopy method is used to solve a sequence of smooth approximations to this system...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on optimization 2002, Vol.12 (3), p.583-605
Main Author: Billups, Stephen C.
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper develops an algorithm for solving mixed complementarity problems that is based upon probability-one homotopy methods. After the complementarity problem is reformulated as a system of nonsmooth equations, a homotopy method is used to solve a sequence of smooth approximations to this system of equations. The global convergence properties of this approach are qualitatively different from those of other recent methods, which rely upon decrease of a merit function. This enables the algorithm to reliably solve certain classes of problems that prove troublesome for other methods. To improve efficiency, the homotopy algorithm is embedded in a generalized Newton method.
ISSN:1052-6234
1095-7189
DOI:10.1137/S1052623498337431