{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/31539"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/31539","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Probability-One Homotopy Maps for Mixed Complementarity Problems","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 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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ahuja, Kapil"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Computer Science","degree_department":"Computer Science","school":null,"contributors":[],"advisors":[],"committee_chairs":["Watson, Layne T."],"committee_members":["Ribbens, Calvin J.","Sachs, Ekkehard W."],"year":2007,"date_issued":"2007-03-19","date_published":"2007-03-19","updated_at":"2026-07-24T05:56:30Z","subjects":["optimization","complementarity","nonlinear embedding","Newton homotopy","globally convergent"],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-03242007-211901"],"render_values":[{"text":"etd-03242007-211901","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/31539","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Watson, Layne T."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Ribbens, Calvin J.","Sachs, Ekkehard W."]},{"key":"dc:contributor.department","label":"Department","values":["Computer Science"]},{"key":"dc:creator","label":"Author","values":["Ahuja, Kapil"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-14T20:32:50Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-14T20:32:50Z","2007-04-10"]},{"key":"dc:date.issued","label":"Date","values":["2007-03-19"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["optimization","complementarity","nonlinear embedding","Newton homotopy","globally convergent"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-03242007-211901"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/31539"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:title","label":"Title","values":["Probability-One Homotopy Maps for Mixed Complementarity Problems"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Watson, Layne T."],"dc:contributor.committeemember":["Ribbens, Calvin J.","Sachs, Ekkehard W."],"dc:contributor.department":["Computer Science"],"dc:creator":["Ahuja, Kapil"],"dc:date.accessioned":["2014-03-14T20:32:50Z"],"dc:date.available":["2014-03-14T20:32:50Z","2007-04-10"],"dc:date.issued":["2007-03-19"],"dc:description.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 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."],"dc:description.degree":["Master of Science"],"dc:identifier.other":["etd-03242007-211901"],"dc:identifier.uri":["http://hdl.handle.net/10919/31539"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["optimization","complementarity","nonlinear embedding","Newton homotopy","globally convergent"],"dc:title":["Probability-One Homotopy Maps for Mixed Complementarity Problems"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-24T05:56:30Z"}