Линейное программирование (13 октября 2016)

1. Связь с n-мерной геометрией: полупространства, выпуклость
2. Обучение перцептрона
1. Алгоритм
2. Конечность числа итераций
3. Точность сходимости, проблема уже в 2D
3. Решение LP
1. Бинпоиск по ответу
2. Убираем свободный член (заменили на положительную переменную)
4. Метод эллисоидов [ellipsoid] [MIT]
1. Общая идея: если центр вне политопа, уменьшим эллипсоид
2. Задание эллипсоида матрицей
3. Выбор направления сдвига центра
4. Формулы пересчёта. Обоснование: сжатие в n/(n+1) раз по главному направлению, растяжение в n/sqrt(n²-1) раз по всем остальным.
5. Число итераций: volume₀ = Cⁿ ≤ 2^cn2, volume_end ≥ 2^-cn2, log(volume_end/volume₀) = O(n⁴)

1. Задачи Ax &le b и Ax = b
2. Симплекс метод для задач Ax ≤ b
1. Ax + z = b, z − базисный план, z ≥ 0
2. Поиск начального решения: Ax - t + z ≤ b, t → 0 (+1 переменная)
3. Пересчёт базисного плана.
3. Двойственность
1. Слабая двойственность. Доказательство.
2. Сильная двойственность. Использование.
3. Доказательство сильной двойственности через Симплекс-Метод.