Линейная задача о дополнительности

Линейная задача о дополнительности (LCP) — задача математической теории оптимизации, часто возникающая в вычислительной механике и охватывающая хорошо известное квадратичное программирование как частный случай. Задача была предложена Коттлом и Данцигом в 1968 году^[1][2][3].

Формулировка

Даны действительные матрица M и вектор q. Задача линейной дополнительности (LCP) предусматривает определение по (q, M) векторов z и w, которые удовлетворяют следующим ограничениям:

• ${\displaystyle w,z\geqslant 0,}$ (то есть каждая компонента этих векторов неотрицательна)
• ${\displaystyle z^{T}w=0}$ или, что эквивалентно, ${\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.}$ Это условие из теории дополнительности^[англ.], так как из него следует тот факт, что для всех ${\displaystyle i}$ хотя бы одна из величин ${\displaystyle w_{i}}$ и ${\displaystyle z_{i}}$ может быть положительна.
• ${\displaystyle w=Mz+q}$

Достаточным условием существования и единственности решения этой задачи является то, что матрица M должна быть симметричной положительно определённой. Если матрица M такова, что LCP (q, M) имеет решение для каждого q, то M является Q-матрицей. Если M таково, что LCP (q, M) имеет единственное решение для каждого q, то M является P-матрицей. Обе эти характеристики являются достаточными и необходимыми^[4].

Вектор w является переменной рассогласования^[5] и поэтому она обычно отбрасывается после нахождения z. Таким образом, задача также может быть сформулирована следующим образом:

• ${\displaystyle Mz+q\geqslant 0}$
• ${\displaystyle z\geqslant 0}$
• ${\displaystyle z^{\mathrm {T} }(Mz+q)=0}$ (условие дополнительности)

Примечания

1. Murty, 1988.
2. Cottle, Pang, Stone, 1992.
3. Cottle, Dantzig, 1968.
4. Murty, 1972.
5. Taylor, 2015, p. 172.

Ссылки

• Björner, Anders. 10 Linear programming // Oriented Matroids / Anders Björner, Michel Las Vergnas, Bernd Sturmfels … [и др.]. — Cambridge University Press, 1999. — P. 417–479. — ISBN 978-0-521-77750-6. — doi:10.1017/CBO9780511586507.
• Cottle, R. W.; Dantzig, G. B. (1968). Complementary pivot theory of mathematical programming. Linear Algebra and Its Applications. 1: 103–125. doi:10.1016/0024-3795(68)90052-9.
• Cottle, Richard W. The linear complementarity problem / Richard W. Cottle, Jong-Shi Pang, Richard E. Stone. — Boston, MA : Academic Press, Inc., 1992. — P. xxiv+762 pp. — ISBN 978-0-12-192350-1.
• Cottle, R. W.; Pang, J.-S.; Venkateswaran, V. (March-April 1989). Sufficient matrices and the linear complementarity problem. Linear Algebra and Its Applications. 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. MR 0986877.
• Csizmadia, Zsolt; Illés, Tibor (2006). New criss-cross type algorithms for linear complementarity problems with sufficient matrices (PDF). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. S2CID 24418835.
• Fukuda, Komei; Namiki, Makoto (March 1994). On extremal behaviors of Murty's least index method. Mathematical Programming. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636.
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). Criss-cross methods: A fresh view on pivot algorithms. Mathematical Programming, Series B. Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint.
• den Hertog, D.; Roos, C.; Terlaky, T. (1993-07-01). The linear complementarity problem, sufficient matrices, and the criss-cross method (PDF). Linear Algebra and Its Applications. 187: 1–14. doi:10.1016/0024-3795(93)90124-7.
• Murty, Katta G. (January 1972). On the number of solutions to the complementarity problem and spanning properties of complementary cones (PDF). Linear Algebra and Its Applications. 5 (1): 65–108. doi:10.1016/0024-3795(72)90019-5. hdl:2027.42/34188.
• Murty, K. G. Linear complementarity, linear and nonlinear programming. — Berlin : Heldermann Verlag, 1988. — Vol. 3. — ISBN Updated and free PDF version at Katta G. Murty's website.
• Taylor, Joshua Adam. Convex Optimization of Power Systems. — Cambridge University Press, 2015. — ISBN 9781107076877.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). Pivot rules for linear programming: A Survey on recent theoretical developments. Annals of Operations Research. Degeneracy in optimization problems. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077.
• Todd, Michael J. (1985). Linear and quadratic programming in oriented matroids. Journal of Combinatorial Theory. Series B. 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. MR 0811116.