×

zbMATH — the first resource for mathematics

On linear programs with linear complementarity constraints. (English) Zbl 1254.90111
Summary: The paper is a manifestation of the fundamental importance of the linear program with linear complementarity constraints (LPCC) in disjunctive and hierarchical programming as well as in some novel paradigms of mathematical programming. In addition to providing a unified framework for bilevel and inverse linear optimization, nonconvex piecewise linear programming, indefinite quadratic programs, quantile minimization, and \(\ell _{0}\) minimization, the LPCC provides a gateway to a mathematical program with equilibrium constraints, which itself is an important class of constrained optimization problems that has broad applications. We describe several approaches for the global resolution of the LPCC, including a logical Benders approach that can be applied to problems that may be infeasible or unbounded.

MSC:
90C05 Linear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmed S., Shapiro A.: Solving chance-constrained stochastic programs via sampling and integer programming. In: Chen, Z.L., Raghavan, S. (eds) TutORials in Operations Research, chapter 12, pp. 261–269. INFORMS, London (2008)
[2] Ahuja R.K., Orlin J.B.: Inverse optimization. Oper. Res. 49(5), 771–783 (2001) · Zbl 1163.90764
[3] Anandalingam G., Friesz T.L.: Hierarchical optimization: an introduction. Ann. Oper. Res. 34(1), 1–11 (1992) · Zbl 0751.90067
[4] Audet C., Savard G., Zghal W.: New branch-and-cut algorithm for bilevel linear programming. J. Optim. Theory Appl. 38(2), 353–370 (2007) · Zbl 1161.90442
[5] Balas E.: Intersection cuts–a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971) · Zbl 0219.90035
[6] Balas E., Ceria S., Cornuéjols G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58, 295–324 (1993) · Zbl 0796.90041
[7] Balas E., Perregaard M.: Lift-and-project for mixed 0-1 programming: recent progress. Dis. Appl. Math. 123(1–3), 129–154 (2002) · Zbl 1076.90031
[8] Balas E., Perregaard M.: A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0-1 programming. Math. Program. 94(2-3), 221–245 (2003) · Zbl 1030.90068
[9] Bennett, K.P., Ji, X., Hu, J., Kunapuli, G., Pang, J.-S.: Model selection via bilevel programming. In: Proceedings of the International Joint Conference on Neural Networks (IJCNN’06) Vancouver, pp. 1922–1929. B.C. Canada, July 16–21 (2006)
[10] Burer S., Vandenbussche D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113(2), 259–282 (2008) · Zbl 1135.90034
[11] Burer S., Vandenbussche D.: Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43(2), 181–195 (2009) · Zbl 1170.90522
[12] Chang M.W., Lin C.J.: Leave-one-out bounds for support vector regression model selection. Neural Comput. 17, 1188–1222 (2005) · Zbl 1096.68128
[13] Chapelle O., Vapnik V., Bousquet O., Mukherjee S.: Choosing multiple parameters with support vector machines. Mach. Learn. 46, 131–159 (2002) · Zbl 0998.68101
[14] Chung K.W., Kao W.C., Sun C.L., Wang L.L., Lin C.J.: Radius margin bounds for support vector machines with the RBF kernel. Neural Comput. 15, 2643–2681 (2003) · Zbl 1085.68123
[15] Colson B., Marcotte P., Savard G.: An overview of bilevel optimization. Ann. Oper. Res. 153(1), 235–256 (2007) · Zbl 1159.90483
[16] 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
[17] Dempe S.: Foundations of Bilevel Programming. Kluwer, Dordrecht (2002) · Zbl 1038.90097
[18] Dempe, S., Dutta, J.: Is bilevel programming a special case of a mathematical program with complementarity constraints? Math. Program (2010) (online first) · Zbl 1235.90145
[19] Facchinei F., Pang J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems: vols. I and II. Springer, New York (2003) · Zbl 1062.90002
[20] Floudas C.A., Pardalos P.M.: A Collection of Test Problems for Constrained Global Optimization Algorithms, vol. 455 of Lecture Notes in Computer Science. Springer, New York (1990) · Zbl 0718.90054
[21] Floudas C.A., Pardalos P.M., Adjiman C., Esposito W.R., Gümüs Z.H., Harding S.T., Klepeis J.L., Meyer C.A., Schweiger C.A.: Handbook of Test Problems in Local and Global Optimization, vol. 33 of Nonconvex Optimization and its Applications. Kluwer, Dordrecht (1999) · Zbl 0943.90001
[22] Giannessi, F., Tomasin, E.: Nonconvex quadratic programs, linear complementarity problems, and integer linear programs. In: Conti, R., Ruberti, A. (eds.) Fifth Conference on Optimization Techniques (Rome 1973), Part I, vol. 3 of Lecture Notes in Computer Science, pp. 437–449. Springer, Berlin (1973) · Zbl 0274.90039
[23] Grone B., Johnson C.R., Marques de Sa E., Wolkowicz H.: Positive definite completions of partial Hermitian matrices. Lin. Alg. Appl. 58, 109–124 (1984) · Zbl 0547.15011
[24] Horn R.A., Johnson C.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001
[25] Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization, 2nd edn, Vol. 48 of Nonconvex Optimization and its Applications. Kluwer, Dordrecht (2000) · Zbl 0966.90073
[26] Hu, J.: On linear programs with linear complementarity constraints. PhD thesis, Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, August (2009)
[27] Hu, J., Mitchell, J.E., Pang, J.S.: An LPCC approach to nonconvex quadratic programs. Technical report, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180. Accepted for publication in Mathematical Programming. May (2008) · Zbl 1244.90177
[28] Hu J., Mitchell J.E., Pang J.S., Bennett K.P., Kunapuli G.: On the global solution of linear programs with linear complementarity constraints. SIAM J. Optim. 19(1), 445–471 (2008) · Zbl 1163.90031
[29] Iyengar G., Kang W.: Inverse conic programming with applications. Oper. Res. Lett. 33(3), 319–330 (2005) · Zbl 1140.90465
[30] Keha, A.B.: A polyhedral study of nonconvex piecewise linear optimization. PhD thesis, Industrial Engineering, Georgia Institute of Technology, Atlanta, GA, August (2003)
[31] Keha A.B., de Farias I.R. Jr, Nemhauser G.L.: Models for representing piecewise linear cost functions. Oper. Res. Lett. 32(1), 44–48 (2004) · Zbl 1056.90107
[32] Keha A.B., de Farias I.R. Jr, Nemhauser G.L.: A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization. Oper. Res. 54(5), 847–858 (2006) · Zbl 1167.90589
[33] Kunapuli, G., Hu, J., Bennett, K.P., Pang, J.S.: Bilevel model selection for support vector machines. In: Data Mining and Mathematical Programming, vol 45 of CRM Proceedings and Lecture Notes, pp. 129–158. Centre de Recherches Mathématiques (2008) · Zbl 1145.68488
[34] Kunapuli G., Hu J., Bennett K.P., Pang J.S.: Classification model selection via bilevel programming. Optim. Methods Softw. 23(4), 475–489 (2008) · Zbl 1151.90541
[35] Krishnan K., Mitchell J.E.: A unifying framework for several cutting plane methods for semidefinite programming. Optim. Methods Softw. 21(1), 57–74 (2006) · Zbl 1181.90215
[36] Lovász L., Schrijver A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2), 166–190 (1991) · Zbl 0754.90039
[37] Luedtke, J.: Integer programming approaches for some non-convex and stochastic optimization problems. PhD thesis, Industrial and Systems Engineering, Georgia Institute of Technology (2007)
[38] Luo Z.-Q., Pang J.-S., Ralph D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
[39] Pang J.-S., Fukushima M.: Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints. Comput. Optim. Appl. 13(1–3), 111–136 (1999) · Zbl 1040.90560
[40] Pang J.-S., Leyffer S.: On the global minimization of the Value-at-Risk. Optim. Methods Softw. 19(5), 611–631 (2004) · Zbl 1114.91320
[41] Pardalos, P.M.: The linear complementarity problem. In: Gomez, S., Hennart, J.P. (eds.) Advances in Optimization and Numerical Analysis, pp. 39–49 (1994) · Zbl 0821.90118
[42] Prékopa A.: Probabilistic programming. In: Ruszczynski, A., Shapiro, A. (eds) Stochastic Programming, chapter 5, Handbooks in Operations Research and Management Science, vol. 10., Elsevier, Amsterdam (2003) · Zbl 0679.90046
[43] Qualizza, A., Belotti, P., Margot, F.: Linear programming relaxations of quadratically constrained quadratic programs. IMA Volume Series Springer, accepted (2010) · Zbl 1242.90155
[44] Rockafellar R.T., Uryasev S.: Optimization of conditional value-at-risk. J. Risk 2, 21–41 (2000)
[45] Rockafellar R.T., Uryasev S.: Conditional value-at-risk for general loss distribution. J. Bank. Finance 26, 1443–1471 (2002)
[46] Saxena A., Bonami P., Lee J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations. Math. Program. 124(1–2), 383–411 (2010) · Zbl 1198.90330
[47] Saxena, A., Bonami, P., Lee, J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations. Technical Report RC24695, IBM. Accepted for publication in Mathematical Programming August (2008) · Zbl 1229.90144
[48] Scheel H., Scholtes S.: Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25(1), 1–22 (2000) · Zbl 1073.90557
[49] Scholtes, S.: Active set methods for inverse linear complementarity problems. Technical report, Judge Institute of Management Science, Cambridge University, Cambridge CB2 1AG, November (1999)
[50] Sherali H.D., Adams W.P.: A hierarchy of relaxation between the continuous and convex hull representations for zero-one programming problems. SIAM J. Dis. Math. 3, 411–430 (1990) · Zbl 0712.90050
[51] Sherali H.D., Fraticelli B.M.P.: Enhancing RLT relaxations via a new class of semidefinite cuts. J. Global Optim. 22, 233–261 (2002) · Zbl 1045.90044
[52] Vandenbussche D., Nemhauser G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102(3), 559–575 (2005) · Zbl 1137.90010
[53] Vandenbussche D., Nemhauser G.L.: A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102(3), 531–557 (2005) · Zbl 1137.90009
[54] Vapnik V.: Statistical Learning Theory. Wiley-Interscience, New York (1998) · Zbl 0935.62007
[55] Vielma J.P., Ahmed S., Nemhauser G.L.: Mixed-integer models for nonseparable piecewise linear optimization: Unifying framework and extensions. Oper. Res. 58(2), 303–315 (2010) · Zbl 1226.90046
[56] Vielma J.P., Keha A.B., Nemhauser G.L.: Nonconvex, lower semicontinuous piecewise linear optimization. Dis. Optim. 5(2), 467–488 (2008) · Zbl 1190.90149
[57] Xiao X., Zhang L., Zhang J.: A smoothing Newton method for a type of inverse semi-definite quadratic programming problem. J. Comput. Appl. Math. 223(1), 485–498 (2009) · Zbl 1155.65051
[58] Zhang J., Zhang L.: An augmented Lagrangian method for a type of inverse quadratic programming problems. Appl. Math. Optim. 61(1), 57–83 (2010) · Zbl 1201.90152
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.