Линейное программирование 4 (24 марта 2025)

1. Сведения разных форм LP, частные случаи LP (m уравнений, n неизвестных)
   1. (cx → max) ↔ (cx → min)
   2. (cx → max) → поиск произвольного решения (бинпоиск по ответу)
   3. Ax = b, x ≥ 0 ⇒ m ≤ n (линейно независимые строки)
   4. Ax ≥ b ⇒ m ≥ n (линейно независимые столбцы)
   
   
2. Обучение Перцептрона
   1. Формулировка: нейрон/перцептрон, отделимость точек плоскостью, форма ∀i <a_i,x> >0
   2. Алгоритм для Ax > 0: начинаем с x₀ = 0, пока ∃ a_ij <x_j, a_i> ≤ 0, x_j+1 = x_j + a_ij
   3. Конечность числа итераций: |a_i| = 1, |x_k|² = |x_k-1 + a_ik|² ≤ |x_k-1|² + 1 ≤ k
   4. Конечность числа итераций: x^* − ответ, |x^*| = 1, тогда <x_k,x^*> ≤ k * min_i<a_i,x^*> и <x_k,x^*> ≤ |x_k|
   5. Точность сходимости (проблема проявляется уже в 2D, когда ∃ a_i, a_j: <a_i, a_j> мало)
   
   
3. ♥ Ax ≤ b для малых n − пересечение полуплоскостей, полупространств.
   1. Решение для n=1 за O(m)
   2. Рандомизированное решение для n=2 за O(m)
   3. Рандомизированное решение за O(m×n!)
   4. Рандомизированное решение за O(m² n)
   
   
4. Алгебра
   1. Унимодулярная матрица. Минор. Тотальная унимодулярность (TU).
   2. Ax = b, Ax ≤ b, целочисленность решений для TU матрицы A.
   3. Тотальная унимодулярность матрицы инцидентности двудольного графа.
   4. Что будет для недвудольных? Раздвоение недвудольного, полуцелое решение.
   
   
5. Двойственность
   1. Построение двойственных задач для Ax = b, x ≥ 0 | Ax ≤ b | Ax ≤ b, x ≥ 0
   2. Слабая и сильная теоремы двойственности
   3. Доказательство сильной теоремы двойственности: симплекс метод корректен и таскает за собой решения и прямой, и двойственной задач (откатываем решение с конца к началу)
   
   
6. Упражнения
   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. Если у задачи нет решений, или максимум не ограничен, что с двойственной задачей?
   
   
7. Матричные игры
   1. Детерминированные стратегии. Вероятностные стратегии.
   2. Оптимальная вероятностная стратегия: min_i(∑a_ijx_j) → max
   3. Записываем задачу через LP для первого и второго игроков. Проверяем, что задача второго двойственна задаче первого.
   4. ♥ Теорема Нэша для матричных игр (сильная теорема двойственности для уже записанных задач LP)