Задача дополнительности является типом математической оптимизации задачи. Это проблема оптимизации (минимизации или максимизации) функции двух векторных переменных с учетом определенных требований (ограничений), которые включают: внутреннее произведение двух векторов должно равняться нулю, т. Е. Они ортогональны. [1] В частности, для конечномерных вещественных векторных пространств это означает, что если есть векторы X и Y со всеми неотрицательными компонентами ( x i ≥ 0 и y i ≥ 0 для всех: в первом квадранте, если двумерный, в первом октанте, если трехмерный), то для каждой пары компонентов x i и y i одна из пары должна быть равна нулю, отсюда и название комплементарности . например, X = (1, 0) и Y = (0, 2) являются дополнительными, а X = (1, 1) и Y = (2, 0) - нет. Проблема дополнительности - это частный случай вариационного неравенства .
История
Проблемы дополнительности изначально изучались, потому что условия Каруша – Куна – Таккера в линейном программировании и квадратичном программировании составляют проблему линейной дополнительности (LCP) или смешанную проблему дополнительности (MCP). В 1963 году Лемке и Хаусон показали, что для игр двух лиц вычисление точки равновесия по Нэшу эквивалентно LCP. В 1968 году Коттл и Данциг объединили линейное и квадратичное программирование и биматричные игры . С тех пор изучение проблем дополнительности и вариационных неравенств значительно расширилось.
Области математики и наук , которые внесли свой вклад в развитие теории дополнительности , включают: оптимизацию , равновесные задачи, вариационное неравенство теорию , теорию неподвижных точек , теорию топологической степени и нелинейный анализ .
Смотрите также
- Математическое программирование с равновесными ограничениями
- формат nl для представления проблем комплементарности
Рекомендации
- ^ Биллапс, Стивен; Мурти, Катта (2000). «Проблемы дополнительности» . Журнал вычислительной и прикладной математики . 124 (1–2): 303–318. Bibcode : 2000JCoAM.124..303B . DOI : 10.1016 / S0377-0427 (00) 00432-5 .
дальнейшее чтение
- Ричард В. Коттл; Чон-Ши Панг; Ричард Э. Стоун (1992). Проблема линейной дополнительности . Академическая пресса . ISBN 978-0-12-192350-1.
- Джордж Исак (1992). Проблемы дополнительности . Springer. ISBN 978-3-540-56251-1.
- Джордж Исак (2000). Топологические методы в теории дополнительности . Springer. ISBN 978-0-7923-6274-6.
- Франсиско Факчини; Чон-Ши Панг (2003). Конечномерные вариационные неравенства и проблемы дополнительности: v.1 и v.2 . Springer. ISBN 978-0-387-95580-3.
- Мурти, KG (1988). Линейная дополнительность, линейное и нелинейное программирование . Сигма-серия в прикладной математике. 3 . Берлин: Heldermann Verlag. с. xlviii + 629 с. ISBN 3-88538-403-5. Руководство по ремонту 0949214 . Архивировано из оригинала на 2010-04-01. CS1 maint: обескураженный параметр ( ссылка )
Коллекции
- Ричард Коттл; Ф. Джаннесси; Жак Луи Лионс, ред. (1980). Вариационные неравенства и проблемы дополнительности: теория и приложения . Джон Вили и сыновья . ISBN 978-0-471-27610-4.
- Майкл К. Феррис; Чон-Ши Панг, ред. (1997). Комплементарность и вариативные проблемы: современное состояние . СИАМ . ISBN 978-0-89871-391-6.