Линейное программирование − 3 (27-е марта 2024)

1. Двойственность
   1. Построение двойственных задач для Ax = b, x ≥ 0 | Ax ≤ b | Ax ≤ b, x ≥ 0
   2. Слабая и сильная теоремы двойственности
   3. Доказательство сильной теоремы двойственности: симплекс метод корректен и таскает за собой решения и прямой, и двойственной задач (откатываем решение с конца к началу)
   
   
2. Упражнения
   1. Даны k n-мерных сфер. Найти ∀ точку пересечения.
   2. Даны k n-мерных конусов. Найти ∀ точку пересечения в предположении, что она ∃ и имеет координаты до 10²⁰.
   3. Запишите двойственную в общем виде для задачи Ax ≥ b, x ≥ 0, c^tx → max
   4. Запишите двойственную к x₁ + x₂ ≤ 2, 3x₁ + x₂ ≤ 5, x₁ + 3x₂ ≤ 5, 2x₁ + 3x₂ → max. Нарисуйте обе задачи.
   5. Если у задачи нет решений, или максимум не ограничен, что с двойственной задачей?
   
   
3. Алгебра
   1. Унимодулярная матрица. Минор. Тотальная унимодулярность (TU).
   2. Ax = b, Ax ≤ b, целочисленность решений для TU матрицы A.
   3. Тотальная унимодулярность матрицы инцидентности двудольного графа.
   4. Что будет для недвудольных? Раздвоение недвудольного, полуцелое решение.
   
   
4. Метод эллипсоидов (Хачиян'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).
   
   
5. [skipped] Метод внутренней точки (Interior Point)
   1. [skipped] Постановка задачи, оптимизируемая функция m*ln(c*x-betta) + sum_i ln(a_i*x-b_i) (m − просто большой коэффициент, обозначающий важность данного условия)
   2. [skipped] Основной шаг метода внутренней точки: чуть увеличить барьер (betta += 1/20m^0.5 * (c*x-betta)) и шаг метода Ньютона
   3. [skipped] Метод Ньютона: как минимизировать функцию?
   
   
6. [skipped] Матричные игры
   1. [skipped] Детерминированные стратегии. Вероятностные стратегии.
   2. [skipped] Оптимальная вероятностная стратегия: min_i(∑a_ijx_j) → max
   3. [skipped] Записываем задачу через LP для первого и второго игроков. Проверяем, что задача второго двойственна задаче первого.
   4. [skipped] ♥ Теорема Нэша для матричных игр (сильная теорема двойственности для уже записанных задач LP)
   
   
7. [skipped] Сведения разных форм LP, частные случаи LP (m уравнений, n неизвестных)
   1. [skipped] Ax = b, x ≥ 0 в Ax > 0 (Перцептрон) (спроецировали, если попали гуд, если нет, ищем положительный луч)
   2. [skipped] Ax ≥ b для случая m ≤ n (через двойственность)
   
   
8. [skipped] Время работы Симплекса
   1. [skipped] Hirsch_conjecture
   2. [skipped] Kalai and Kleitman ’93 : n^log₂m
   
   
9. [skipped] Выпуклая оболочка в k-D
   1. [skipped] Задача близкая к LP: построение выпуклой оболочки в d-мерном пространстве
   2. [skipped] Пример, для d-мерного пространства: кубик, 2d граней, 2^d вершин.
   3. [skipped] Что ищем? Пример, для d-мерного пространства: 2d вершин, 2^d граней (индукция)
   4. [skipped] Сведение через линейное выражение новых точек
   5. [skipped] Сведение через Ax ≥ λ