×

zbMATH — the first resource for mathematics

A pivoting algorithm for linear programming with linear complementarity constraints. (English) Zbl 1311.90152
Summary: We present a pivoting algorithm for solving linear programs with linear complementarity constraints. Our method generalizes the simplex method for linear programming to deal with complementarity conditions. We develop an anticycling scheme that can verify Bouligand stationarity. We also give an optimization-based technique to find an initial feasible vertex. Starting with a feasible vertex, our algorithm always finds a minimizer or an unbounded descent search direction in a finite number of pivoting steps.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K15 Numerical methods for variational inequalities and related problems
90C49 Extreme-point and pivoting methods
Software:
MacMPEC; AMPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1137/S1052623402401221 · Zbl 1097.90050
[2] DOI: 10.1007/s10107-006-0005-4 · Zbl 1119.90050
[3] DOI: 10.1023/A:1022645805569 · Zbl 0901.90153
[4] DOI: 10.1007/s10957-007-9263-4 · Zbl 1161.90442
[5] DOI: 10.1137/0911017 · Zbl 0702.65060
[6] DOI: 10.1145/362946.362982
[7] DOI: 10.1145/362946.362974 · Zbl 0181.19104
[8] DOI: 10.1007/s10589-005-3908-8 · Zbl 1121.90124
[9] DOI: 10.1016/S0377-2217(99)00297-0 · Zbl 0970.90048
[10] Chv√°tal, V. 1983. ”Linear Programming”. New York and San Francisco: W.H. Freeman & Company. · Zbl 0537.90067
[11] DOI: 10.1007/s101070100263 · Zbl 1049.90004
[12] DOI: 10.1137/040608015 · Zbl 1113.90146
[13] DOI: 10.1007/s101070050048 · Zbl 0959.65079
[14] DOI: 10.1137/S105262349833338X · Zbl 0997.90087
[15] DOI: 10.1080/10556780410001654241 · Zbl 1074.90044
[16] DOI: 10.1007/BF02591933 · Zbl 0574.65057
[17] DOI: 10.1137/S1052623402407382 · Zbl 1112.90098
[18] Fourer R., AMPL: A Modeling Language for Mathematical Programming, 2. ed. (2002)
[19] DOI: 10.1137/S1052623499363232 · Zbl 1005.65064
[20] Gill P. E., Numerical Linear Algebra and Optimization (1990)
[21] DOI: 10.1007/BF01593804 · Zbl 0443.90058
[22] DOI: 10.1137/0913069 · Zbl 0760.65063
[23] DOI: 10.1080/02331930701763405 · Zbl 1162.90560
[24] DOI: 10.1007/s10957-004-5154-0
[25] DOI: 10.1137/07068463x · Zbl 1163.90031
[26] DOI: 10.1137/07068463x · Zbl 1163.90031
[27] DOI: 10.1287/opre.19.6.1523 · Zbl 0228.90045
[28] DOI: 10.1287/opre.21.1.353 · Zbl 0274.90025
[29] DOI: 10.1137/S1052623497332329 · Zbl 0955.90134
[30] Jiang H., Comput. Optim. Appl. 123 pp 365– (2004)
[31] DOI: 10.1007/BF02098174 · Zbl 0749.90049
[32] DOI: 10.1007/s10898-006-9001-8 · Zbl 1131.90061
[33] DOI: 10.1007/s10957-007-9231-z · Zbl 1145.90075
[34] Leyffer S., MacMPEC: AMPL collection of MPECs (2000)
[35] DOI: 10.1080/10556780500140078 · Zbl 1134.90051
[36] DOI: 10.1007/0-387-34221-4_9 · Zbl 1190.90240
[37] S. Leyffer and T. Munson,A globally convergent filter method for MPECs, preprint (2007), ANL/MCS-P1457-0907, Argonne National Laboratory, Mathematics and Computer Science Division
[38] DOI: 10.1137/040621065 · Zbl 1112.90095
[39] DOI: 10.1016/0377-2217(93)90327-J · Zbl 0806.90086
[40] DOI: 10.1023/A:1008656806889 · Zbl 1040.90560
[41] DOI: 10.1287/moor.25.1.1.15213 · Zbl 1073.90557
[42] DOI: 10.1137/S1052623499361233 · Zbl 1010.90086
[43] Stange P., Electron. Trans. Numer. Anal. 26 pp 161– (2007)
[44] DOI: 10.1137/S1052623497321882 · Zbl 0967.90092
[45] DOI: 10.1016/j.jmaa.2004.10.032 · Zbl 1112.90062
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.