# Стэнфордский онлайн-курс: линейная условная оптимизация и алгоритм симплекса

Источник: https://www.youtube.com/watch?v=gmdrc9vGnJ0
Канал: Stanford Online
Опубликовано: 14.06.2024

---

В рамках лекции Стэнфордского университета подробно разбираются основы линейной условной оптимизации и классический симплекс-метод. Автор курса наглядно демонстрирует математический аппарат, позволяющий находить глобально оптимальные решения для сложных задач со множеством ограничений. Основной акцент сделан на переходе от геометрической интуиции выпуклых множеств к строгой программной реализации алгоритма на языке Julia.

## 🎯 Суть линейного программирования и глобальная оптимальность
[[JUMP:0:04]]

В инженерном проектировании и реальных прикладных задачах существует огромный стимул сводить возникающие проблемы к форме линейной условной оптимизации. Главная причина заключается в том, что такие задачи можно решать с достижением глобального оптимума чрезвычайно эффективно. Даже если реальные целевые функции или ограничения изначально не являются линейными, разработчики часто используют линеаризованные аппроксимации для упрощения вычислений. Благодаря современным алгоритмическим подходам, сегодня можно находить точные глобальные решения для масштабных систем, содержащих миллионы переменных и миллионы ограничений. В инженерной практике такие математические модели принято называть линейными программами.

## 📐 Математическая формулировка и геометрия выпуклости
[[JUMP:2:07]]

Математически стандартная форма линейной программы записывается как минимизация целевой функции $c^T x$ при условиях $Ax \le b$ и $x \ge 0$. Вектор $c$ является константным вектором коэффициентов, а $x$ представляет собой вектор проектировочных переменных. Градиент целевой функции всегда перпендикулярен линиям уровня (контурам равенства). Каждое линейное ограничение-неравенство вида $w^T x \le b$ геометрически делит пространство на два полупространства. 

Пересечение множества таких полупространств формирует допустимое множество решений задачи. Поскольку полупространства являются выпуклыми множествами, их пересечение также всегда выпукло. Для иллюстрации понятия выпуклости лектор приводит шутливую аналогию: популярный персонаж Бэймакс (Baymax) из анимационного фильма «Город героев» из-за своей формы не является выпуклым множеством, однако его голова вполне удовлетворяет этому критерию. 

Главное свойство выпуклой задачи линейного программирования — любой локальный минимум автоматически оказывается глобальным минимумом. Лектор выделяет три принципиальных типа точек внутри допустимого множества:

* Внутренние точки (Interior) — никогда не бывают оптимальными, так как всегда можно улучшить значение целевой функции, сдвигаясь вдоль направления антиградиента $-c$.
* Точки на гранях (Face) — могут быть оптимальными только тогда, когда градиент целевой функции строго перпендикулярен этой грани; в таком случае задача имеет бесконечное число решений.
* Вершины (Vertex) — угловые точки многогранника, в которых гарантированно существует уникальное оптимальное решение линейной программы, если оно в принципе единственно.

## 🔄 Переход к форме равенств и каноническим допущениям
[[JUMP:9:39]]

Для практической реализации алгоритмов, в частности симплекс-метода, задачи переводят из стандартной формы неравенств в форму равенств. Это достигается путем введения неотрицательных слак-переменных (slack variables) $s \ge 0$, которые поглощают разницу между левой и правой частями ограничений. Например, ограничение-неравенство $x \ge 1$ преобразуется в жесткое равенство $x - s = 1$, а условие $x \le 1$ превращается в равенство вида $x + s = 1$. 

Работа именно с формой равенств является строгой конвенцией для вычислительного ядра симплекс-алгоритма. Еще одно базовое допущение метода — требование неотрицательности всех компонентов вектора переменных ($x \ge 0$), что заставляет вычисления происходить исключительно в положительном квадранте пространства проектирования. Если исходная инженерная задача содержит переменные без ограничения знака, к ним применяется предварительное математическое расщепление.

## 🔑 Условия Лагранжа первого порядка: необходимость и достаточность
[[JUMP:13:30]]

Для анализа оптимальности конкретных вершин используются условия первого порядка (условия Каруша — Куна — Таккера), базирующиеся на классической функции Лагранжа. В общем виде Лагранжиан включает целевую функцию и систему штрафов за нарушение ограничений-неравенств и ограничений-равенств. Для канонической линейной программы функция Лагранжа записывается формулой $L(x, \mu, \lambda) = c^T x - \mu^T x + \lambda^T (Ax - b)$. Лектор подробно останавливается на четырех ключевых условиях:

1. Допустимость по исходным переменным (Primal Feasibility) — точка обязана строго удовлетворять системе равенств $Ax = b$ и условию неотрицательности $x \ge 0$.
2. Допустимость по двойственным переменным (Dual Feasibility) — компоненты вектора множителей Лагранжа $\mu$ для ограничений-неравенств должны быть строго неотрицательными ($\mu \ge 0$), чтобы обеспечивать корректное направление штрафа в оптимизационном рельефе.
3. Дополняющая нежесткость (Complementary Slackness) — покомпонентное произведение $\mu_i x_i$ должно быть равно нулю, что означает: либо ограничение активно на границе ($x_i = 0$), либо соответствующий множитель штрафа равен нулю ($\mu_i = 0$).
4. Стационарность (Stationarity) — градиент функции Лагранжа по переменным $x$ равен нулю, что выражается векторным уравнением $A^T \lambda + \mu = c$.

Уникальная особенность линейного программирования заключается в том, что данные условия первого порядка являются не просто необходимыми, но и абсолютно достаточными. Если анализируемая точка удовлетворяет всем четырем критериям, алгоритм может мгновенно завершить работу — глобальный оптимум гарантированно найден.

## 🧩 Разбиение вершин и линейная алгебра базиса
[[JUMP:22:34]]

Каждая вершина многогранника допустимых решений математически определяется тем, что ровно $n - m$ компонентов вектора переменных $x$ строго равны нулю. Здесь $n$ обозначает общее количество переменных в форме равенств, а $m$ — число ограничений-равенств (количество строк в матрице $A$). С позиции линейной алгебры, обнуление $n - m$ свободных переменных эквивалентно исключению соответствующих столбцов из матрицы ограничений $A$. 

Если оставшаяся квадратная матрица $A_{basis}$ размера $m \times m$ является обратимой (имеет полный ранг), то система уравнений имеет единственное решение, четко задающее координаты вершины многогранника. На основе этого математического свойства переменные разделяются на два ключевых множества:

* Базисный сет (Basis set) — подмножество индексов переменных, значения которых в вершине могут быть строго больше нуля («занятые» переменные).
* Свободный сет (Free set) — подмножество индексов переменных, которые жестко приравнены к нулю («вакантные» переменные).

Лектор обращает внимание на важный нюанс: любая вершина имеет ассоциированное с ней разбиение индексов, но не любое произвольное разбиение индексов порождает реальную вершину, так как выделенная подматрица $A_{basis}$ может оказаться вырожденной и необратимой. Для вычисления координат вектора $x$ по заданному базису в коде на языке Julia подматрица инвертируется и умножается на вектор ограничений $b$.

## 🚀 Алгоритм симплекса: Оптимизация (Фаза 2)
[[JUMP:35:28]]

Симплекс-метод гарантированно находит точное решение для любой допустимой и ограниченной линейной программы. На верхнем уровне абстракции алгоритм последовательно перемещается от одной вершины к другой по ребрам многогранника, проверяя на каждом шаге условия оптимальности KKT. Процесс жестко разделен на две фазы: Фаза 1 отвечает за поиск стартовой допустимой вершины, а Фаза 2 реализует движение к финальной оптимальной точке. 

В рамках Фазы 2 на каждой итерации происходит контролируемый обмен: выбирается один «входящий» индекс $q$ из свободного множества и один «выходящий» индекс $p$ из текущего базиса. Математический вывод формул стационарности показывает, что значение целевой функции уменьшается при переходе к соседней вершине только в том случае, если двойственная переменная $\mu_q$ строго отрицательна. Для выбора входящей переменной применяется жадная эвристика (greedy heuristic), отбирающая индекс с наибольшим отрицательным значением двойственной переменной. 

Выходящий из базиса индекс $p$ определяется с помощью теста минимального отношения (minimum ratio test). Этот тест вычисляет, до какого максимального значения можно увеличивать входящую переменную $x_q$, чтобы ни одна из текущих базисных переменных не ушла в отрицательную область, нарушив базовое условие допустимости. Вся программная логика Фазы 2 оптимизации лаконично умещается всего в 100 строк кода на языке Julia.

## 🏁 Инициализация алгоритма: Поиск начальной вершины (Фаза 1)
[[JUMP:1:07:36]]

Для запуска итерационного процесса Фазы 2 алгоритму критически важно иметь легитимную стартовую вершину. Как объясняет лектор, задача поиска начального допустимого разбиения сама по себе требует решения отдельной вспомогательной (auxiliary) линейной программы. Чтобы избежать бесконечной логической петли, конструируется искусственная математическая модель, куда вводятся дополнительные фиктивные переменные $z \ge 0$. 

Целью Фазы 1 становится минимизация суммы этих искусственных переменных при модифицированном ограничении $Ax + Zz = b$. Матрица $Z$ представляет собой диагональную матрицу, содержащую $+1$ или $-1$ на диагонали в зависимости от знака соответствующих элементов вектора ограничений $b$. Для такой искусственной задачи тривиально задается начальный рабочий базис, полностью состоящий из индексов переменных $z$. 

Если исходная инженерная задача в принципе имеет допустимые решения, то в ходе оптимизации вспомогательной программы все переменные $z$ гарантированно обнуляются, а возвращенный алгоритмом базис становится строго допустимым стартом для оригинальной задачи. Если же по завершении Фазы 1 переменные $z$ не удается свести к нулю, это служит математическим доказательством того, что исходная система ограничений несовместна, и задача не имеет решений. Лектор резюмирует, что переменные $z$ необходимо временно сохранять в структурах данных даже после их обнуления, так как их индексы могут легитимно входить в финальный рабочий базис разбиения.