Abstract
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 ℓ 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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)
Ahuja R.K., Orlin J.B.: Inverse optimization. Oper. Res. 49(5), 771–783 (2001)
Anandalingam G., Friesz T.L.: Hierarchical optimization: an introduction. Ann. Oper. Res. 34(1), 1–11 (1992)
Audet C., Savard G., Zghal W.: New branch-and-cut algorithm for bilevel linear programming. J. Optim. Theory Appl. 38(2), 353–370 (2007)
Balas E.: Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971)
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)
Balas E., Perregaard M.: Lift-and-project for mixed 0-1 programming: recent progress. Dis. Appl. Math. 123(1–3), 129–154 (2002)
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)
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)
Burer S., Vandenbussche D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113(2), 259–282 (2008)
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)
Chang M.W., Lin C.J.: Leave-one-out bounds for support vector regression model selection. Neural Comput. 17, 1188–1222 (2005)
Chapelle O., Vapnik V., Bousquet O., Mukherjee S.: Choosing multiple parameters with support vector machines. Mach. Learn. 46, 131–159 (2002)
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)
Colson B., Marcotte P., Savard G.: An overview of bilevel optimization. Ann. Oper. Res. 153(1), 235–256 (2007)
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)]
Dempe S.: Foundations of Bilevel Programming. Kluwer, Dordrecht (2002)
Dempe, S., Dutta, J.: Is bilevel programming a special case of a mathematical program with complementarity constraints? Math. Program (2010) (online first)
Facchinei F., Pang J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems: vols. I and II. Springer, New York (2003)
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)
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)
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)
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)
Horn R.A., Johnson C.: Matrix Analysis. Cambridge University Press, Cambridge (1985)
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)
Hu, J.: On linear programs with linear complementarity constraints. PhD thesis, Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, August (2009)
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)
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)
Iyengar G., Kang W.: Inverse conic programming with applications. Oper. Res. Lett. 33(3), 319–330 (2005)
Keha, A.B.: A polyhedral study of nonconvex piecewise linear optimization. PhD thesis, Industrial Engineering, Georgia Institute of Technology, Atlanta, GA, August (2003)
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)
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)
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)
Kunapuli G., Hu J., Bennett K.P., Pang J.S.: Classification model selection via bilevel programming. Optim. Methods Softw. 23(4), 475–489 (2008)
Krishnan K., Mitchell J.E.: A unifying framework for several cutting plane methods for semidefinite programming. Optim. Methods Softw. 21(1), 57–74 (2006)
Lovász L., Schrijver A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2), 166–190 (1991)
Luedtke, J.: Integer programming approaches for some non-convex and stochastic optimization problems. PhD thesis, Industrial and Systems Engineering, Georgia Institute of Technology (2007)
Luo Z.-Q., Pang J.-S., Ralph D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
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)
Pang J.-S., Leyffer S.: On the global minimization of the Value-at-Risk. Optim. Methods Softw. 19(5), 611–631 (2004)
Pardalos, P.M.: The linear complementarity problem. In: Gomez, S., Hennart, J.P. (eds.) Advances in Optimization and Numerical Analysis, pp. 39–49 (1994)
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)
Qualizza, A., Belotti, P., Margot, F.: Linear programming relaxations of quadratically constrained quadratic programs. IMA Volume Series Springer, accepted (2010)
Rockafellar R.T., Uryasev S.: Optimization of conditional value-at-risk. J. Risk 2, 21–41 (2000)
Rockafellar R.T., Uryasev S.: Conditional value-at-risk for general loss distribution. J. Bank. Finance 26, 1443–1471 (2002)
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)
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)
Scheel H., Scholtes S.: Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25(1), 1–22 (2000)
Scholtes, S.: Active set methods for inverse linear complementarity problems. Technical report, Judge Institute of Management Science, Cambridge University, Cambridge CB2 1AG, November (1999)
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)
Sherali H.D., Fraticelli B.M.P.: Enhancing RLT relaxations via a new class of semidefinite cuts. J. Global Optim. 22, 233–261 (2002)
Vandenbussche D., Nemhauser G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102(3), 559–575 (2005)
Vandenbussche D., Nemhauser G.L.: A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102(3), 531–557 (2005)
Vapnik V.: Statistical Learning Theory. Wiley-Interscience, New York (1998)
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)
Vielma J.P., Keha A.B., Nemhauser G.L.: Nonconvex, lower semicontinuous piecewise linear optimization. Dis. Optim. 5(2), 467–488 (2008)
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)
Zhang J., Zhang L.: An augmented Lagrangian method for a type of inverse quadratic programming problems. Appl. Math. Optim. 61(1), 57–83 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
It is our great pleasure to dedicate this work to Professor Richard W. Cottle on the occasion of his 75th birthday in 2009. Professor Cottle is the father of the linear complementarity problem (LCP) [16]. The linear program with linear complementarity constraints (LPCC) treated in this paper is a natural extension of the LCP; our hope is that the LPCC will one day become as fundamental as the LCP, thereby continuing Professor Cottle’s legacy, bringing it to new heights, and extending its breadth. The work of the author John E. Mitchell was supported by the National Science Foundation under grant DMS-0715446 and by the Air Force Office of Sponsored Research under grant FA9550-08-1-0081. The work of the author Jong-Shi Pang was supported by the Office of Naval Research under grant no. N00014-06-1-0014, by the Air Force Office of Sponsored Research under grant FA9550-08-1-0061, and by the National Science Foundation under grant CMMI-0969600.
Rights and permissions
About this article
Cite this article
Hu, J., Mitchell, J.E., Pang, JS. et al. On linear programs with linear complementarity constraints. J Glob Optim 53, 29–51 (2012). https://doi.org/10.1007/s10898-010-9644-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-010-9644-3