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

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science

Department dc:contributor.department

Computer Science

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2007

Author dc:creator

• Ahuja, Kapil

Chair dc:contributor.committeechair

• Watson, Layne T.

Committee members dc:contributor.committeemember

• Ribbens, Calvin J.
• Sachs, Ekkehard W.

• optimization
• complementarity
• nonlinear embedding
• Newton homotopy
• globally convergent

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

etd-03242007-211901

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/31539