Probability-one homotopy maps for mixed complementarity problems

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 develope...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2008-12, Vol.41 (3), p.363-375
Main Authors: Ahuja, Kapil, Watson, Layne T., Billups, Stephen C.
Format: Article
Language:English
Subjects:
Algorithms
Computer science
Convergence
Convex and Discrete Geometry
Management Science
Mapping
Mathematics
Mathematics and Statistics
Nonlinear equations
Nonlinear programming
Operations Research
Operations Research/Decision Theory
Optimization
Optimization techniques
Statistics
Studies
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: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.
ISSN:0926-6003
1573-2894
DOI:10.1007/s10589-007-9107-z