Mathematical Programming

, Volume 169, Issue 1, pp 221–254

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

• Francisco Jara-Moroni
• Jong-Shi Pang
• Andreas Wächter
Full Length Paper Series B

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

## Keywords

Difference-of-convex Complementarity constraints Penalty functions Bilevel programming

## Mathematics Subject Classification

90C05 Linear programming 90C30 Nonlinear programming 90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions)

## Notes

### Acknowledgements

We thank a referee for very helpful comments that have improved the presentation of the paper.

## References

1. 1.
Bai, L., Mitchell, J.E., Pang, J.S.: On convex quadratic programs with linear complementarity constraints. Comput. Optim. Appl. 54(3), 517–544 (2013)
2. 2.
Burdakov, O., Kanzow, Ch., Schwartz, A.: Mathematical programs with cardinality constraints: reformulation by complementarity-type constraints and a regularization method. Preprint 324, Institute of Mathematics, University of Würzburg, Germany (2014) (last revised February 2015)Google Scholar
3. 3.
Byrd, R.H., Nocedal, J., Waltz, R.A.: KNITRO: an integrated package for nonlinear optimization. In: di Pillo, G., Roma, M. (eds.) Large-Scale Nonlinear Optimization, pp. 35–59. Springer, Berlin (2006)
4. 4.
5. 5.
Fang, H.R., Leyffer, S., Munson, T.S.: A pivoting algorithm for linear programs with complementarity constraints. Optim. Methods Softw. 27(1), 89–114 (2012)
6. 6.
Feng, M., Mitchell, J.E., Pang, J.S., Wächter, A., Shen, X.: Complementarity formulations of $$\ell _0$$-norm optimization problems. Pac. J. Optim. (accepted August 2016)Google Scholar
7. 7.
Fletcher, R., Leyffer, S.: Solving mathematical program with complementarity constraints as nonlinear programs. Optim. Methods Softw. 19(1), 15–40 (2004)
8. 8.
Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Program. 91(2), 239–270 (2002)
9. 9.
Fletcher, R., Leyffer, S., Ralph, D., Scholtes, S.: Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17(1), 259–286 (2006)
10. 10.
Fletcher, R., Leyffer, S.: Toint, Ph.L: On the global convergence of a filter-SQP algorithm. SIAM J. Optim. 13(1), 44–59 (2002)
11. 11.
Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. Boyd & Fraser, San Francisco (2003)
12. 12.
Hu, J., Mitchell, J.E., Pang, J.S.: An LPCC approach to nonconvex quadratic programs. Math. Program. 133(1), 243–277 (2012)
13. 13.
Hu, J., Mitchell, J.E., Pang, J.S., Yu, B.: On the global solution of linear programs with linear complementarity constraints. SIAM J. Optim. 19(1), 445–471 (2008)
14. 14.
Hu, J., Mitchell, J.E., Pang, J.S., Yu, B.: On linear programs with linear complementarity constraints. J. Global Optim. 53(1), 29–51 (2012)
15. 15.
Ibaraki, T.: Complementary programming. Oper. Res. 19(6), 1523–1529 (1971)
16. 16.
Ibaraki, T.: The use of cuts in complementary programming. Oper. Res. 21(1), 353–359 (1973)
17. 17.
Jeroslow, R.G.: Cutting planes for complementarity constraints. SIAM J. Control Optim. 16(1), 56–62 (1978)
18. 18.
Judice, J.J.: Algorithms for linear programming with linear complementarity constraints. TOP 20(1), 4–25 (2012)
19. 19.
Le Thi, H.A., Huynh, V.N., Pham Dinh, T.: DC Programming and DCA for General DC Programs. Advances in Intelligent Systems and Computing, pp. 15–35. Springer, Berlin (2014)
20. 20.
Le Thi, H.A., Pham Dinh, T.: Recent advances in DC programming and DCA. Trans. Comput. Collect. Intell. 8342, 1–37 (2014)Google Scholar
21. 21.
Le Thi, H.A., Pham Dinh, T.: The state of the art in DC programming and DCA. Research Report, Lorraine University (2013)Google Scholar
22. 22.
Le Thi, H.A., Pham Dinh, T.: On solving linear complemetarity problems by DC programming and DCA. Comput. Optim. Appl. 50(3), 507–524 (2011)
23. 23.
Le Thi, H.A., Pham Dinh, T.: The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133, 23–46 (2005)
24. 24.
Leyffer, S., Munson, T.S.: A globally convergent Filter method for MPECs. Preprint ANL/MCSP1457-0907, Argonne National Laboratory, Mathematics and Computer Science Division (revised April 2009)Google Scholar
25. 25.
Leyffer, S., Lopez-Calva, G., Nocedal, J.: Interior point methods for mathematical programs with complementarity constraints. SIAM J. Optim. 17(1), 52–77 (2006)
26. 26.
Leyffer, S.: MacMPEC: AMPL collection of MPECs (2000). http://www.mcs.anl.gov/~leyffer/MacMPEC/
27. 27.
Luo, Z.Q., Pang, J.S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
28. 28.
Mangasarian, O.L.: Solution of general linear complementarity problems via nondifferentiable concave minimization. Acta Mathematica Vietnamica 22(1), 199–205 (1997)
29. 29.
Muu, L.D., Dinh, Q.T., Le Thi, H.A., Pham Dinh, T.: A new decomposition algorithm for globally solving mathematical programs with affine equilibrium constraints. Acta Mathematica Vietnamica 37(2), 201–218 (2012)
30. 30.
Pang, J.S., Razaviyayn, M., Alvarado, A.: Computing B-stationary points of nonsmooth DC programs. Math. Oper. Res. (2016).
31. 31.
Pham Dinh, T., Le Thi, H.A.: Convex analysis approach to DC programming: theory, algorithm and applications. Acta Mathematica Vietnamica 22(1), 289–355 (1997)
32. 32.
Rockafeelar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
33. 33.
Scheel, H., Scholtes, S.: Mathematical program with complementarity constraints: stationarity, optimality and sensitivity. Math. Oper. Res. 25(1), 1–22 (2000)
34. 34.
Yu, B.: A branch and cut approach to linear programs with linear complementarity constraints. Ph.D. thesis. Department of Decision Sciences and Engineering Systems, Rensselaer Polytechic Institute (2011)Google Scholar
35. 35.
Yu, B., Mitchell, J.E., Pang, J.S.: Obtaining tighter relaxations of mathematical programs with complementarity constraints. In: Terlaky, T., Curtis, F. (eds.) Modeling and Optimization: Theory and Applications, pp. 1–23. Springer Proceedings in Mathematics and Statistics, New York (2012)Google Scholar

© Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2017

## Authors and Affiliations

• Francisco Jara-Moroni
• 1
• Jong-Shi Pang
• 2
• Andreas Wächter
• 1
1. 1.Department of Industrial Engineering and Management SciencesNorthwestern UniversityEvanstonUSA
2. 2.Department of Industrial and Systems EngineeringUniversity of Southern CaliforniaLos AngelesUSA
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.852082371711731, "perplexity": 22372.60652340243}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-39/segments/1537267161638.66/warc/CC-MAIN-20180925123211-20180925143611-00119.warc.gz"}