×

A study of the difference-of-convex approach for solving linear programs with complementarity constraints. (English) Zbl 1397.90264

Summary: 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.

MSC:

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

Software:

KNITRO; MacMPEC; AMPL
PDFBibTeX XMLCite
Full Text: DOI

References:

[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) · Zbl 1295.90035 · doi:10.1007/s10589-012-9497-4
[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) · Zbl 1332.90220
[3] Byrd, RH; Nocedal, J.; Waltz, RA; Pillo, G. (ed.); Roma, M. (ed.), KNITRO: an integrated package for nonlinear optimization, 35-59 (2006), Berlin · Zbl 1108.90004 · doi:10.1007/0-387-30065-1_4
[4] Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. SIAM classics in applied mathematics 60, Philadelphia (2009) [Originally published by Academic Press, Boston (1992)] · Zbl 0757.90078
[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) · Zbl 1311.90152 · doi:10.1080/10556788.2010.512956
[6] Feng, M., Mitchell, J.E., Pang, J.S., Wächter, A., Shen, X.: Complementarity formulations of \[\ell_0\] ℓ0-norm optimization problems. Pac. J. Optim. (accepted August 2016) · Zbl 1474.90476
[7] Fletcher, R., Leyffer, S.: Solving mathematical program with complementarity constraints as nonlinear programs. Optim. Methods Softw. 19(1), 15-40 (2004) · Zbl 1074.90044 · doi:10.1080/10556780410001654241
[8] Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Program. 91(2), 239-270 (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244
[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) · Zbl 1112.90098 · doi:10.1137/S1052623402407382
[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) · Zbl 1029.65063 · doi:10.1137/S105262340038081X
[11] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. Boyd & Fraser, San Francisco (2003) · Zbl 0701.90062
[12] Hu, J., Mitchell, J.E., Pang, J.S.: An LPCC approach to nonconvex quadratic programs. Math. Program. 133(1), 243-277 (2012) · Zbl 1244.90177 · doi:10.1007/s10107-010-0426-y
[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) · Zbl 1163.90031 · doi:10.1137/07068463x
[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) · Zbl 1254.90111 · doi:10.1007/s10898-010-9644-3
[15] Ibaraki, T.: Complementary programming. Oper. Res. 19(6), 1523-1529 (1971) · Zbl 0228.90045 · doi:10.1287/opre.19.6.1523
[16] Ibaraki, T.: The use of cuts in complementary programming. Oper. Res. 21(1), 353-359 (1973) · Zbl 0274.90025 · doi:10.1287/opre.21.1.353
[17] Jeroslow, R.G.: Cutting planes for complementarity constraints. SIAM J. Control Optim. 16(1), 56-62 (1978) · Zbl 0395.90076 · doi:10.1137/0316005
[18] Judice, J.J.: Algorithms for linear programming with linear complementarity constraints. TOP 20(1), 4-25 (2012) · Zbl 1267.90108 · doi:10.1007/s11750-011-0228-2
[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) · Zbl 1322.90072
[20] Le Thi, H.A., Pham Dinh, T.: Recent advances in DC programming and DCA. Trans. Comput. Collect. Intell. 8342, 1-37 (2014)
[21] Le Thi, H.A., Pham Dinh, T.: The state of the art in DC programming and DCA. Research Report, Lorraine University (2013)
[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) · Zbl 1237.90234 · doi:10.1007/s10589-011-9398-y
[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) · Zbl 1116.90122 · doi:10.1007/s10479-004-5022-1
[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)
[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) · Zbl 1112.90095 · doi:10.1137/040621065
[26] Leyffer, S.: MacMPEC: AMPL collection of MPECs (2000). http://www.mcs.anl.gov/ leyffer/MacMPEC/
[27] Luo, Z.Q., Pang, J.S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996) · Zbl 1139.90003 · doi:10.1017/CBO9780511983658
[28] Mangasarian, O.L.: Solution of general linear complementarity problems via nondifferentiable concave minimization. Acta Mathematica Vietnamica 22(1), 199-205 (1997) · Zbl 0895.90167
[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) · Zbl 1248.49042
[30] Pang, J.S., Razaviyayn, M., Alvarado, A.: Computing B-stationary points of nonsmooth DC programs. Math. Oper. Res. (2016). https://doi.org/10.1287/moor.2016.0795 · Zbl 1359.90106
[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) · Zbl 0895.90152
[32] Rockafeelar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0932.90001 · doi:10.1515/9781400873173
[33] Scheel, H., Scholtes, S.: Mathematical program with complementarity constraints: stationarity, optimality and sensitivity. Math. Oper. Res. 25(1), 1-22 (2000) · Zbl 1073.90557 · doi:10.1287/moor.25.1.1.15213
[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)
[35] Yu, B.; Mitchell, JE; Pang, JS; Terlaky, T. (ed.); Curtis, F. (ed.), Obtaining tighter relaxations of mathematical programs with complementarity constraints, 1-23 (2012), New York · Zbl 1346.90686
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.