Линейное программирование 3: поллекции (17 марта 2025)

1. ♥️ Семинар: k-path от Кати Кравцовой
   
   
2. Cutting planes (см. олимпиадную лекцию)
   
   
3. Метод эллипсоидов (Хачиян'1972), полиномиальных в худшем способ, на практике бесполезен
   1. Задача: Ax ≤ b, ищем любое решение. Начальное данное, нам дан n-мерный эллипсоид, содержащий ответ
   2. Переход: или центр эллипсоида подходит, или есть неравенство-полупространство, которое не подходит, ответ по ту сторону плоскости от центра эллипсоида, осталось выбрать меньший по объёму эллипсоиод, содержащий нужную нам половину
   3. Математика эллипсоидов: положительно опеределённая матрица (пример и связь с x²/a² + y²/b² = 1)
   4. Меняем систему координат, что наш эллипсоид − сфера, а плоскость x₁ = 0
   5. Новый центр = (1/(n+1), 0, 0, ...), новый радиус = (n/(n+1),d,d,d...), где d = n/(n²-1)^1/2
   6. Сходимость: V₀ ≤ (nU)^Θ(n2), V_end ≥ V₀ ≥ (nU)^Θ(-n3), за один шаг объём уменьшается в exp(-1/2n) раз. Итого за 2n*ln(V_end/V₀) алгоритм сойдётся, O(2n*(n³+n²)*log(nU)) = O(n⁴*log(nU)) шагов.
   7. Общее время работы: число шагов * nm * точность вычислений = O^*(n⁴ * nm * n²)
   8. Обобщение: метод эллипсоидов можно применить для поиска пересечения любых выпуклых множеств. Мы пользовались тем, что за t умеем проверять, лежит ли точка в выпуклом множестве и за T строить опорную плоскость, получили решение за O(n⁴log(nU)) шагов, каждый за O(tm + T).
   
   
4. Двойственность
   1. Построение двойственных задач для Ax = b, x ≥ 0 | Ax ≤ b | Ax ≤ b, x ≥ 0
   2. Слабая и сильная теоремы двойственности
   3. Доказательство сильной теоремы двойственности: симплекс метод корректен и таскает за собой решения и прямой, и двойственной задач (откатываем решение с конца к началу)