Complementarity theory

<h2 id="history">History</h2>
<p>Complementarity problems were originally studied because the <a href="/facts/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions/ly7g2zST">Karush–Kuhn–Tucker conditions</a> in <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> and <a href="/facts/Quadratic_programming/ct4RIUgs">quadratic programming</a> constitute a <a href="/facts/Linear_complementarity_problem/eSKsgl38">linear complementarity problem</a> (LCP) or a <a href="/facts/Mixed_complementarity_problem/JJGMM3p1">mixed complementarity problem</a> (MCP). In 1963 <a href="/facts/Carlton_E._Lemke/us58aoPU">Lemke</a> and Howson showed that, for two person games, computing a <a href="/facts/Nash_equilibrium/l74xzIHd">Nash equilibrium</a> point is equivalent to an LCP. In 1968 <a href="/facts/Richard_W._Cottle/nqVBfQ7V">Cottle</a> and <a href="/facts/George_B._Dantzig/04se7h0M">Dantzig</a> unified linear and quadratic programming and <a href="/facts/Bimatrix_game/J0jHIycQ">bimatrix games</a>. Since then the study of complementarity problems and variational inequalities has expanded enormously.
</p><p>Areas of <a href="/facts/Mathematics/pxTouaz4">mathematics</a> and <a href="/facts/Science/IJoaD7rs">science</a> that contributed to the development of complementarity theory
include: <a href="/facts/Optimization_(mathematics)/oRn8Iv5I">optimization</a>, <a href="/facts/Equilibrium_point/DgbGMPkg">equilibrium</a> problems, <a href="/facts/Variational_inequality/p3Hy60WS">variational inequality theory</a>, <a href="/facts/Fixed_point_theory/Jvkz4SUu">fixed point theory</a>, <a href="/facts/Topological_degree_theory/YnxAP32b">topological degree theory</a> and <a href="/facts/Nonlinear_analysis/dVxYYVho">nonlinear analysis</a>.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Mathematical_programming_with_equilibrium_constraints/EvrVGtSm">Mathematical programming with equilibrium constraints</a></li>
<li><a href="/facts/Nl_(format)/9U0EyckP">nl format</a> for representing complementarity problems</li></ul>

<h2 id="further-reading">Further reading</h2>
<ul><li>Richard W. Cottle; Jong-Shi Pang; Richard E. Stone (1992). <i>The Linear Complementarity Problem</i>. <a href="/facts/Academic_Press/qxoKjzFy">Academic Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-12-192350-1.</li>
<li>George Isac (1992). <i>Complementarity Problems</i>. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-56251-1.</li>
<li>George Isac (2000). <i>Topological Methods in Complementarity Theory</i>. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-7923-6274-6.</li>
<li>Francisco Facchinei; Jong-Shi Pang (2003). <i>Finite-Dimensional Variational Inequalities and Complementarity Problems: v.1 and v.2</i>. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-95580-3.</li>
<li>Murty, K. G. (1988). <a href="https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/"><i>Linear complementarity, linear and nonlinear programming</i></a>. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-88538-403-5. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0949214">0949214</a>. Archived from <a href="http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/">the original</a> on 2010-04-01.</li></ul>
<h3>Collections</h3>
<ul><li>Richard Cottle; F. Giannessi; Jacques Louis Lions, eds. (1980). <i>Variational Inequalities and Complementarity Problems: Theory and Applications</i>. <a href="/facts/John_Wiley_%26_Sons/53g3LqJc">John Wiley & Sons</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-471-27610-4.</li>
<li>Michael C. Ferris; Jong-Shi Pang, eds. (1997). <i>Complementarity and Variational Problems: State of the Art</i>. <a href="/facts/SIAM/2HY4T5WY">SIAM</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-89871-391-6.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://web.archive.org/web/20080615162953/http://www.cs.wisc.edu/cpnet/">CPNET:Complementarity Problem Net</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Billups, Stephen; Murty, Katta (2000). "Complementarity Problems". Journal of Computational and Applied Mathematics. 124 (1–2): 303–318. Bibcode:2000JCoAM.124..303B. doi:10.1016/S0377-0427(00)00432-5. <a href="http://www-personal.umich.edu/~murty/LCPart.ps" target="_blank">http://www-personal.umich.edu/~murty/LCPart.ps</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Complementarity theory open-in-new

Complementarity theory