A study of the difference-of-convex approach for solving linear programs with complementarity constraints

This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their st...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2018-05, Vol.169 (1), p.221-254
Main Authors: Jara-Moroni, Francisco, Pang, Jong-Shi, Wächter, Andreas
Format: Article
Language:English
Subjects:
Algorithms
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Formulations
Full Length Paper
Integer programming
Linear programming
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Nonlinear programming
Numerical Analysis
Theoretical
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-c316t-dd9fc634becfb09173a95bb64cbebe6fc7358e583b914bdef493381207db94a93
cites cdi_FETCH-LOGICAL-c316t-dd9fc634becfb09173a95bb64cbebe6fc7358e583b914bdef493381207db94a93
container_end_page 254
container_issue 1
container_start_page 221
container_title Mathematical programming
container_volume 169
creator Jara-Moroni, Francisco
Pang, Jong-Shi
Wächter, Andreas
description This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results, including comparisons with an existing nonlinear programming solver and the mixed-integer formulation, are presented to elucidate the effectiveness of the overall DC approach.
doi_str_mv 10.1007/s10107-017-1208-6
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_1963773391</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1963773391</sourcerecordid><originalsourceid>FETCH-LOGICAL-c316t-dd9fc634becfb09173a95bb64cbebe6fc7358e583b914bdef493381207db94a93</originalsourceid><addsrcrecordid>eNp1kE9PAyEQxYnRxFr9AN5IPKNQdtnl2DT-S5p40TMBdmi32UIFWu23l2Y9ePE0mcx7b2Z-CN0yes8obR4So4w2hLKGsBltiThDE1ZxQSpRiXM0oXRWk1oweomuUtpQShlv2wnq5zjlfXfEweG8Btz1zkEEb4EER2zwB_jGereLQds1diHiFIZD71d46D3oiMtkFfU24a8-r7EN290AW_BZxz4fS-9Tjrr3OV2jC6eHBDe_dYo-nh7fFy9k-fb8upgvieVMZNJ10lnBKwPWGSpZw7WsjRGVNWBAONvwuoW65UayynTgKsl5W35uOiMrLfkU3Y255bLPPaSsNmEffVmpmBS8aTiXrKjYqLIxpBTBqV3stzoeFaPqRFSNRFUhqk5ElSie2ehJRetXEP8k_2v6Aence04</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1963773391</pqid></control><display><type>article</type><title>A study of the difference-of-convex approach for solving linear programs with complementarity constraints</title><source>Business Source Ultimate【Trial: -2024/12/31】【Remote access available】</source><source>ABI/INFORM Global</source><source>Springer Link</source><creator>Jara-Moroni, Francisco ; Pang, Jong-Shi ; Wächter, Andreas</creator><creatorcontrib>Jara-Moroni, Francisco ; Pang, Jong-Shi ; Wächter, Andreas</creatorcontrib><description>This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results, including comparisons with an existing nonlinear programming solver and the mixed-integer formulation, are presented to elucidate the effectiveness of the overall DC approach.</description><identifier>ISSN: 0025-5610</identifier><identifier>EISSN: 1436-4646</identifier><identifier>DOI: 10.1007/s10107-017-1208-6</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer Berlin Heidelberg</publisher><subject>Algorithms ; Calculus of Variations and Optimal Control; Optimization ; Combinatorics ; Formulations ; Full Length Paper ; Integer programming ; Linear programming ; Mathematical and Computational Physics ; Mathematical Methods in Physics ; Mathematics ; Mathematics and Statistics ; Mathematics of Computing ; Nonlinear programming ; Numerical Analysis ; Theoretical</subject><ispartof>Mathematical programming, 2018-05, Vol.169 (1), p.221-254</ispartof><rights>Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2017</rights><rights>Mathematical Programming is a copyright of Springer, (2017). All Rights Reserved.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c316t-dd9fc634becfb09173a95bb64cbebe6fc7358e583b914bdef493381207db94a93</citedby><cites>FETCH-LOGICAL-c316t-dd9fc634becfb09173a95bb64cbebe6fc7358e583b914bdef493381207db94a93</cites><orcidid>0000-0002-3278-5637</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/1963773391?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11688,27924,27925,36060,44363</link.rule.ids></links><search><creatorcontrib>Jara-Moroni, Francisco</creatorcontrib><creatorcontrib>Pang, Jong-Shi</creatorcontrib><creatorcontrib>Wächter, Andreas</creatorcontrib><title>A study of the difference-of-convex approach for solving linear programs with complementarity constraints</title><title>Mathematical programming</title><addtitle>Math. Program</addtitle><description>This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results, including comparisons with an existing nonlinear programming solver and the mixed-integer formulation, are presented to elucidate the effectiveness of the overall DC approach.</description><subject>Algorithms</subject><subject>Calculus of Variations and Optimal Control; Optimization</subject><subject>Combinatorics</subject><subject>Formulations</subject><subject>Full Length Paper</subject><subject>Integer programming</subject><subject>Linear programming</subject><subject>Mathematical and Computational Physics</subject><subject>Mathematical Methods in Physics</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Mathematics of Computing</subject><subject>Nonlinear programming</subject><subject>Numerical Analysis</subject><subject>Theoretical</subject><issn>0025-5610</issn><issn>1436-4646</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kE9PAyEQxYnRxFr9AN5IPKNQdtnl2DT-S5p40TMBdmi32UIFWu23l2Y9ePE0mcx7b2Z-CN0yes8obR4So4w2hLKGsBltiThDE1ZxQSpRiXM0oXRWk1oweomuUtpQShlv2wnq5zjlfXfEweG8Btz1zkEEb4EER2zwB_jGereLQds1diHiFIZD71d46D3oiMtkFfU24a8-r7EN290AW_BZxz4fS-9Tjrr3OV2jC6eHBDe_dYo-nh7fFy9k-fb8upgvieVMZNJ10lnBKwPWGSpZw7WsjRGVNWBAONvwuoW65UayynTgKsl5W35uOiMrLfkU3Y255bLPPaSsNmEffVmpmBS8aTiXrKjYqLIxpBTBqV3stzoeFaPqRFSNRFUhqk5ElSie2ehJRetXEP8k_2v6Aence04</recordid><startdate>20180501</startdate><enddate>20180501</enddate><creator>Jara-Moroni, Francisco</creator><creator>Pang, Jong-Shi</creator><creator>Wächter, Andreas</creator><general>Springer Berlin Heidelberg</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><orcidid>https://orcid.org/0000-0002-3278-5637</orcidid></search><sort><creationdate>20180501</creationdate><title>A study of the difference-of-convex approach for solving linear programs with complementarity constraints</title><author>Jara-Moroni, Francisco ; Pang, Jong-Shi ; Wächter, Andreas</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c316t-dd9fc634becfb09173a95bb64cbebe6fc7358e583b914bdef493381207db94a93</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Algorithms</topic><topic>Calculus of Variations and Optimal Control; Optimization</topic><topic>Combinatorics</topic><topic>Formulations</topic><topic>Full Length Paper</topic><topic>Integer programming</topic><topic>Linear programming</topic><topic>Mathematical and Computational Physics</topic><topic>Mathematical Methods in Physics</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Mathematics of Computing</topic><topic>Nonlinear programming</topic><topic>Numerical Analysis</topic><topic>Theoretical</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Jara-Moroni, Francisco</creatorcontrib><creatorcontrib>Pang, Jong-Shi</creatorcontrib><creatorcontrib>Wächter, Andreas</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</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 Database‎ (1962 - current)</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</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</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>ProQuest Science Journals</collection><collection>ProQuest Engineering Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business (ProQuest)</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>Mathematical programming</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Jara-Moroni, Francisco</au><au>Pang, Jong-Shi</au><au>Wächter, Andreas</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A study of the difference-of-convex approach for solving linear programs with complementarity constraints</atitle><jtitle>Mathematical programming</jtitle><stitle>Math. Program</stitle><date>2018-05-01</date><risdate>2018</risdate><volume>169</volume><issue>1</issue><spage>221</spage><epage>254</epage><pages>221-254</pages><issn>0025-5610</issn><eissn>1436-4646</eissn><abstract>This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results, including comparisons with an existing nonlinear programming solver and the mixed-integer formulation, are presented to elucidate the effectiveness of the overall DC approach.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer Berlin Heidelberg</pub><doi>10.1007/s10107-017-1208-6</doi><tpages>34</tpages><orcidid>https://orcid.org/0000-0002-3278-5637</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0025-5610
ispartof Mathematical programming, 2018-05, Vol.169 (1), p.221-254
issn 0025-5610
1436-4646
language eng
recordid cdi_proquest_journals_1963773391
source Business Source Ultimate【Trial: -2024/12/31】【Remote access available】; ABI/INFORM Global; Springer Link
subjects Algorithms
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Formulations
Full Length Paper
Integer programming
Linear programming
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Nonlinear programming
Numerical Analysis
Theoretical
title A study of the difference-of-convex approach for solving linear programs with complementarity constraints
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T20%3A23%3A49IST&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=A%20study%20of%20the%20difference-of-convex%20approach%20for%20solving%20linear%20programs%20with%20complementarity%20constraints&rft.jtitle=Mathematical%20programming&rft.au=Jara-Moroni,%20Francisco&rft.date=2018-05-01&rft.volume=169&rft.issue=1&rft.spage=221&rft.epage=254&rft.pages=221-254&rft.issn=0025-5610&rft.eissn=1436-4646&rft_id=info:doi/10.1007/s10107-017-1208-6&rft_dat=%3Cproquest_cross%3E1963773391%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c316t-dd9fc634becfb09173a95bb64cbebe6fc7358e583b914bdef493381207db94a93%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1963773391&rft_id=info:pmid/&rfr_iscdi=true