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!
cited_by cdi_FETCH-LOGICAL-c420t-44c46b940a459aa6f717e339d8a3db29075874d57c6cd742fedc5140c301cd263
cites cdi_FETCH-LOGICAL-c420t-44c46b940a459aa6f717e339d8a3db29075874d57c6cd742fedc5140c301cd263
container_end_page 375
container_issue 3
container_start_page 363
container_title Computational optimization and applications
container_volume 41
creator Ahuja, Kapil
Watson, Layne T.
Billups, Stephen C.
description 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.
doi_str_mv 10.1007/s10589-007-9107-z
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_36035886</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1585357841</sourcerecordid><originalsourceid>FETCH-LOGICAL-c420t-44c46b940a459aa6f717e339d8a3db29075874d57c6cd742fedc5140c301cd263</originalsourceid><addsrcrecordid>eNp1kEtLxDAUhYMoOI7-AHfFhbvqzbvZKYMvGNCFrkOaptqhbWrSAWd-vSkVBMHNfcB3zr0chM4xXGEAeR0x8ELlacwVTmV_gBaYS5qTQrFDtABFRC4A6DE6iXEDAEpSskA3L8GXpmzaZtzlvnfZh-_86Idd1pkhZrUPWdd8uSqzvhta17l-NCGx2ZB0aY-n6Kg2bXRnP32J3u7vXleP-fr54Wl1u84tIzDmjFkmSsXAMK6MEbXE0lGqqsLQqiQKJC8kq7i0wlaSkdpVlmMGlgK2FRF0iS5n33T4c-viqLsmWte2pnd-GzUVQHlRTODFH3Djt6FPv2mCueBYqCJBeIZs8DEGV-shNJ0JO41BT4HqOVA9jVOgep80ZNbExPbvLvwa_y_6BlPDePU</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>215651698</pqid></control><display><type>article</type><title>Probability-one homotopy maps for mixed complementarity problems</title><source>Business Source Ultimate</source><source>ABI/INFORM Global</source><source>Springer Nature</source><creator>Ahuja, Kapil ; Watson, Layne T. ; Billups, Stephen C.</creator><creatorcontrib>Ahuja, Kapil ; Watson, Layne T. ; Billups, Stephen C.</creatorcontrib><description>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.</description><identifier>ISSN: 0926-6003</identifier><identifier>EISSN: 1573-2894</identifier><identifier>DOI: 10.1007/s10589-007-9107-z</identifier><language>eng</language><publisher>Boston: Springer US</publisher><subject>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</subject><ispartof>Computational optimization and applications, 2008-12, Vol.41 (3), p.363-375</ispartof><rights>Springer Science+Business Media, LLC 2007</rights><rights>Springer Science+Business Media, LLC 2008</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c420t-44c46b940a459aa6f717e339d8a3db29075874d57c6cd742fedc5140c301cd263</citedby><cites>FETCH-LOGICAL-c420t-44c46b940a459aa6f717e339d8a3db29075874d57c6cd742fedc5140c301cd263</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/215651698/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/215651698?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11688,27924,27925,36060,36061,44363,74895</link.rule.ids></links><search><creatorcontrib>Ahuja, Kapil</creatorcontrib><creatorcontrib>Watson, Layne T.</creatorcontrib><creatorcontrib>Billups, Stephen C.</creatorcontrib><title>Probability-one homotopy maps for mixed complementarity problems</title><title>Computational optimization and applications</title><addtitle>Comput Optim Appl</addtitle><description>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.</description><subject>Algorithms</subject><subject>Computer science</subject><subject>Convergence</subject><subject>Convex and Discrete Geometry</subject><subject>Management Science</subject><subject>Mapping</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Nonlinear equations</subject><subject>Nonlinear programming</subject><subject>Operations Research</subject><subject>Operations Research/Decision Theory</subject><subject>Optimization</subject><subject>Optimization techniques</subject><subject>Statistics</subject><subject>Studies</subject><issn>0926-6003</issn><issn>1573-2894</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2008</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kEtLxDAUhYMoOI7-AHfFhbvqzbvZKYMvGNCFrkOaptqhbWrSAWd-vSkVBMHNfcB3zr0chM4xXGEAeR0x8ELlacwVTmV_gBaYS5qTQrFDtABFRC4A6DE6iXEDAEpSskA3L8GXpmzaZtzlvnfZh-_86Idd1pkhZrUPWdd8uSqzvhta17l-NCGx2ZB0aY-n6Kg2bXRnP32J3u7vXleP-fr54Wl1u84tIzDmjFkmSsXAMK6MEbXE0lGqqsLQqiQKJC8kq7i0wlaSkdpVlmMGlgK2FRF0iS5n33T4c-viqLsmWte2pnd-GzUVQHlRTODFH3Djt6FPv2mCueBYqCJBeIZs8DEGV-shNJ0JO41BT4HqOVA9jVOgep80ZNbExPbvLvwa_y_6BlPDePU</recordid><startdate>20081201</startdate><enddate>20081201</enddate><creator>Ahuja, Kapil</creator><creator>Watson, Layne T.</creator><creator>Billups, Stephen C.</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope></search><sort><creationdate>20081201</creationdate><title>Probability-one homotopy maps for mixed complementarity problems</title><author>Ahuja, Kapil ; Watson, Layne T. ; Billups, Stephen C.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c420t-44c46b940a459aa6f717e339d8a3db29075874d57c6cd742fedc5140c301cd263</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2008</creationdate><topic>Algorithms</topic><topic>Computer science</topic><topic>Convergence</topic><topic>Convex and Discrete Geometry</topic><topic>Management Science</topic><topic>Mapping</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Nonlinear equations</topic><topic>Nonlinear programming</topic><topic>Operations Research</topic><topic>Operations Research/Decision Theory</topic><topic>Optimization</topic><topic>Optimization techniques</topic><topic>Statistics</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Ahuja, Kapil</creatorcontrib><creatorcontrib>Watson, Layne T.</creatorcontrib><creatorcontrib>Billups, Stephen C.</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ProQuest_ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Global</collection><collection>Computing Database</collection><collection>Science Database</collection><collection>Engineering Database</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>ProQuest Central Basic</collection><jtitle>Computational optimization and applications</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Ahuja, Kapil</au><au>Watson, Layne T.</au><au>Billups, Stephen C.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Probability-one homotopy maps for mixed complementarity problems</atitle><jtitle>Computational optimization and applications</jtitle><stitle>Comput Optim Appl</stitle><date>2008-12-01</date><risdate>2008</risdate><volume>41</volume><issue>3</issue><spage>363</spage><epage>375</epage><pages>363-375</pages><issn>0926-6003</issn><eissn>1573-2894</eissn><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.</abstract><cop>Boston</cop><pub>Springer US</pub><doi>10.1007/s10589-007-9107-z</doi><tpages>13</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0926-6003
ispartof Computational optimization and applications, 2008-12, Vol.41 (3), p.363-375
issn 0926-6003
1573-2894
language eng
recordid cdi_proquest_miscellaneous_36035886
source Business Source Ultimate; ABI/INFORM Global; Springer Nature
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
title Probability-one homotopy maps for mixed complementarity problems
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T15%3A23%3A34IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Probability-one%20homotopy%20maps%20for%20mixed%20complementarity%20problems&rft.jtitle=Computational%20optimization%20and%20applications&rft.au=Ahuja,%20Kapil&rft.date=2008-12-01&rft.volume=41&rft.issue=3&rft.spage=363&rft.epage=375&rft.pages=363-375&rft.issn=0926-6003&rft.eissn=1573-2894&rft_id=info:doi/10.1007/s10589-007-9107-z&rft_dat=%3Cproquest_cross%3E1585357841%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c420t-44c46b940a459aa6f717e339d8a3db29075874d57c6cd742fedc5140c301cd263%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=215651698&rft_id=info:pmid/&rfr_iscdi=true