×

Algorithms for linear programming with linear complementarity constraints. (English) Zbl 1267.90108

Summary: Linear programming with linear complementarity constraints (LPLCC) is an area of active research in optimization, due to its many applications, algorithms, and theoretical existence results. In this paper, a number of formulations for important nonconvex optimization problems is first reviewed. The most relevant algorithms for computing a complementary feasible solution, a stationary point, and a global minimum for the LPLCC are also surveyed, together with some comments about their efficiency and efficacy in practice.

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Software:

BARON; MINOS; MacMPEC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Khayyal F (1987) An implicit enumeration procedure for the general linear complementarity problem. Math Program Stud 31:1–20 · Zbl 0623.90079 · doi:10.1007/BFb0121176
[2] Anitescu M (2005) On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J Optim 15:1203–1236 · Zbl 1097.90050 · doi:10.1137/S1052623402401221
[3] Anitescu M, Tseng P, Wright SJ (2007) Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties. Math Program 110:337–371 · Zbl 1119.90050 · doi:10.1007/s10107-006-0005-4
[4] Audet C, Hansen P, Jaumard B, Savard G (1999) A symmetrical linear maxmin approach to disjoint bilinear programming. Math Program 85:573–592 · Zbl 0980.90051 · doi:10.1007/s101070050072
[5] Audet C, Savard G, Zghal W (2007) New branch-and-cut algorithm for bilevel linear programming. J Optim Theory Appl 134:353–370 · Zbl 1161.90442 · doi:10.1007/s10957-007-9263-4
[6] Bard J (1999) Practical bilevel optimization: algorithms and applications. Kluwer Academic, Dordrecht · Zbl 0943.90078
[7] Bard J, Moore J (1990) A branch and bound algorithm for the bilevel programming problem. SIAM J Sci Stat Comput 11:281–292 · Zbl 0702.65060 · doi:10.1137/0911017
[8] Bazaraa M, Sherali H, Shetty C (2006) Nonlinear programming: theory and algorithms, 3rd edn. Wiley, New York · Zbl 1140.90040
[9] Benson H, Sen A, Shanno D, Vanderbei R (2005) Interior-point algorithms, penalty methods and equilibrium problems. Comput Optim Appl 34:155–182 · Zbl 1121.90124 · doi:10.1007/s10589-005-3908-8
[10] Burer S, Vandenbussche D (2008) A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math Program, Ser A 113:259–282 · Zbl 1135.90034 · doi:10.1007/s10107-006-0080-6
[11] Colson B, Marcotte P, Savard G (2005) Bilevel programming: a survey. 4OR 3:87–107 · Zbl 1134.90482 · doi:10.1007/s10288-005-0071-0
[12] Cottle R, Pang J-S, Stone R (1992) The linear complementarity problem. Academic Press, New York · Zbl 0757.90078
[13] de Sabóia CHM, Campêlo M, Scheimberg S (2004) A computational study of global algorithms for linear bilevel programming. Numer Algorithms 35:155–173 · Zbl 1054.65060 · doi:10.1023/B:NUMA.0000021760.62160.a4
[14] Dempe S (2002) Foundations of bilevel programming. Kluwer Academic, Dordrecht · Zbl 1038.90097
[15] Dirkse S, Ferris M, Meeraus A (2005) Mathematical programs with equilibrium constraints: automatic reformulation and solution via constrained optimization. In: Kehoe T, Srinivasan T, Whalley J (eds) Frontiers in applied general equilibrium modeling. Cambridge University Press, Cambridge, pp 67–93 · Zbl 1203.91142
[16] Facchinei F, Jiang H, Qi L (1999) A smoothing method for mathematical programs with equilibrium constraints. Math Program 85:107–134 · Zbl 0959.65079 · doi:10.1007/s101070050048
[17] Fang HR, Leyffer S, Munson T (2009) A pivoting algorithm for linear programming with linear complementarity constraints. Optim Methods Softw (to appear). http://www.mcs.anl.gov/uploads/cels/papers/P1680.pdf · Zbl 1311.90152
[18] Fernandes L, Friedlander A, Guedes MC, Júdice J (2001) Solution of a general linear complementarity problem using smooth optimization and its application to bilinear programming and LCP. Appl Math Optim 43:1–19 · Zbl 1033.90132 · doi:10.1007/s002450010021
[19] Fletcher R, Leyffer S (2004) Solving mathematical programs with complementarity constraints as nonlinear programs. Optim Methods Softw 19:15–40 · Zbl 1074.90044 · doi:10.1080/10556780410001654241
[20] Fletcher R, Leyffer S, Ralph D, Scholtes S (2006) Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J Optim 17:259–286 · Zbl 1112.90098 · doi:10.1137/S1052623402407382
[21] Fukushima M, Tseng P (2002) An implementable active-set algorithm for computing a B-stationary point of the mathematical program with linear complementarity constraints. SIAM J Optim 12:724–739 · Zbl 1005.65064 · doi:10.1137/S1052623499363232
[22] Fukushima M, Luo Z-Q, Pang J-S (1998) A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints. Comput Optim Appl 10:5–34 · Zbl 0904.90153 · doi:10.1023/A:1018359900133
[23] Gill P, Murray W, Wright M (1981) Practical optimization. Academic Press, London · Zbl 0503.90062
[24] Gümüz ZH, Floudas CA (2005) Global optimization of mixed-integer bilevel programming problems. Comput Manag Sci 2:181–212 · Zbl 1112.90061 · doi:10.1007/s10287-005-0025-1
[25] Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J Sci Stat Comput 13:1194–1217 · Zbl 0760.65063 · doi:10.1137/0913069
[26] Hu XM, Ralph D (2004) Convergence of a penalty method for mathematical programming with complementarity constraints. J Optim Theory Appl 123:365–390 · doi:10.1007/s10957-004-5154-0
[27] Hu J, Mitchell JE, Pang J-S, Bennett KP, Kunapuli G (2008) On the global solution of linear programs with linear complementarity constraints. SIAM J Optim 19:445–471 · Zbl 1163.90031 · doi:10.1137/07068463x
[28] Hu J, Mitchell J, Pang J-S (2010) An LPCC approach to nonconvex quadratic programs. Math. Program. (to appear). doi: 10.1007/s10107-010-0426-y · Zbl 1244.90177
[29] Ibaraki T (1971) Complementary programming. Oper Res 19:1523–1529 · Zbl 0228.90045 · doi:10.1287/opre.19.6.1523
[30] Jeroslow RG (1978) Cutting-planes for complementarity constraints. SIAM J Control Optim 16:56–62 · Zbl 0395.90076 · doi:10.1137/0316005
[31] Jiang H, Ralph D (1999) Smooth SQP methods for mathematical programs with nonlinear complementarity constraints. SIAM J Optim 10:779–808 · Zbl 0955.90134 · doi:10.1137/S1052623497332329
[32] Jiang H, Ralph D (2003) Extension of quasi-Newton methods to mathematical programs with complementarity constraints Comput Optim Appl 25:123–150 · Zbl 1038.90100 · doi:10.1023/A:1022945316191
[33] Júdice J, Faustino A (1988) An experimental investigation of enumerative methods for the linear complementarity problem. Comput Oper Res 15:417–426 · Zbl 0647.90095 · doi:10.1016/0305-0548(88)90058-5
[34] Júdice J, Faustino A (1991) A computational analysis of LCP methods for bilinear and concave quadratic programming. Comput Oper Res 18:645–654 · Zbl 0741.90050 · doi:10.1016/0305-0548(91)90002-9
[35] Júdice J, Faustino A (1992) A SLCP method for bilevel linear programming. Ann Oper Res 34:89–106 · Zbl 0749.90049 · doi:10.1007/BF02098174
[36] Júdice J, Faustino A (1994) The linear-quadratic bilevel programming problem. Inf Syst Oper Res 32:87–98 · Zbl 0805.90098
[37] Júdice JJ, Vicente LN (1994) On the solution and complexity of a generalized linear complementarity problem. J Glob Optim 4:415–424 · Zbl 0801.90107 · doi:10.1007/BF01099266
[38] Júdice J, Sherali H, Ribeiro I, Faustino A (2006) A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints. J Glob Optim 136:89–114 · Zbl 1131.90061 · doi:10.1007/s10898-006-9001-8
[39] Júdice J, Sherali H, Ribeiro I, Faustino A (2007) A complementarity active-set algorithm for mathematical programming problems with equilibrium constraints. J Optim Theory Appl 136:467–481 · Zbl 1145.90075 · doi:10.1007/s10957-007-9231-z
[40] Konno H (1971) Bilinear programming: Part II–applications of bilinear programming. Technical Report, Department of Operations Research, Stanford University
[41] Le Thi H, Pham Dinh T (2005) 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 · Zbl 1116.90122 · doi:10.1007/s10479-004-5022-1
[42] Le Thi H, Pham Dinh T (2011) On solving linear complementarity problems by DC programming and DCA. Comput Optim Appl (to appear). doi: 10.1007/s10589-011-9398-y · Zbl 1237.90234
[43] Leyffer S, López-calva G, Nocedal J (2004) Interior methods for mathematical programs with complementarity constraints. SIAM J Optim 17:52–77 · Zbl 1112.90095 · doi:10.1137/040621065
[44] Luo Z, Pang J-S, Ralph D (1997) Mathematical programs with equilibrium constraints. Cambridge University Press, New York · Zbl 0898.90006
[45] Mangasarian OL (1995) The linear complementarity problem as a separable bilinear program. J Glob Optim 6:153–161 · Zbl 0835.90102 · doi:10.1007/BF01096765
[46] Mangasarian OL (2007) Absolute value programming. Comput Optim Appl 36:43–53 · Zbl 1278.90386 · doi:10.1007/s10589-006-0395-5
[47] Murtagh B, Saunders A (1983) MINOS 5.0 user’s guide. Technical Report SOL 83-20, Department of Operations Research, Stanford University
[48] Murty K (1976) Linear and combinatorial programming. Wiley, New York · Zbl 0334.90032
[49] Murty K (1988) Linear complementarity, linear and nonlinear programming. Heldermann, Berlin · Zbl 0634.90037
[50] Nocedal J, Wright SJ (2006) Numerical optimization. Springer, Berlin · Zbl 1104.65059
[51] Outrata J, Kocvara M, Zowe J (1998) Nonsmooth approach to optimization problems with equilibrium constraints: theory, applications and numerical results. Kluwer Academic, Boston · Zbl 0947.90093
[52] Pang J-S, Fukushima M (1999) Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints. Comput Optim Appl 13:111–136 · Zbl 1040.90560 · doi:10.1023/A:1008656806889
[53] Ralph D (2008) Nonlinear programming advances in mathematical programming with complementarity constraints. R Soc (submitted). http://www.eng.cam.ac.uk/wdr241/Papers/MPCC-review.pdf
[54] Sahinidis NV, Tawarmalani M (2005) BARON 7.2.5: global optimization of mixed-integer nonlinear programs. User’s Manual
[55] Scheel H, Scholtes S (2000) Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity. Math Oper Res 25:1–22 · Zbl 1073.90557 · doi:10.1287/moor.25.1.1.15213
[56] Scholtes S (1999) Active set methods for inverse linear complementarity problems. Technical Report, Judge Institute of Management Research
[57] Scholtes S (2000) Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J Optim 11:918–936 · Zbl 1010.90086 · doi:10.1137/S1052623499361233
[58] Sherali HD, Adams WP (1999) A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Kluwer Academic, Dordrecht
[59] Sherali HD, Krishnamurthy RS, Al-Khayyal FA (1998) Enumeration approach for linear complementarity problems based on a reformulation-linearization technique. J Optim Theory Appl 99:481–507 · Zbl 0911.90328 · doi:10.1023/A:1021734613201
[60] Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math Program 99:563–591 · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[61] Vandenbussche D, Nemhauser G (2005) A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math Program, Ser A 102:559–575 · Zbl 1137.90010 · doi:10.1007/s10107-004-0550-7
[62] Ye JJ (1999) Optimality conditions for optimization problems with complementarity constraints. SIAM J Optim 9:374–387 · Zbl 0967.90092 · doi:10.1137/S1052623497321882
[63] Ye JJ (2005) Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. J Math Anal Appl 307:350–369 · Zbl 1112.90062 · doi:10.1016/j.jmaa.2004.10.032
[64] Ye Y (1993) A fully polynomial-time approximation algorithm for computing a stationary point of the general linear complementarity problem. Math Oper Res 18:334–345 · Zbl 0791.90060 · doi:10.1287/moor.18.2.334
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.