Квадратичное программирование: решение задачи по шагам

Квадратичное программирование (КП) - это задача оптимизации, в которой целевая функция квадратичная, а ограничения линейные. Такие задачи встречаются в планировании производства, портфельной теории и регрессии с ограничениями: везде, где издержки растут не пропорционально отклонению от плана, а квадратично. В отличие от линейного программирования, где оптимум всегда лежит в вершине допустимого многогранника, в КП оптимум может оказаться и внутри ребра, и в вершине - это и делает задачу интереснее и чуть сложнее. Ниже разберём общий вид задачи, условия Каруша-Куна-Таккера, метод активных ограничений и решим конкретный пример с проверкой знаков. Чтобы сразу увидеть, как меняется решение при разных данных, покрути калькулятор ниже - он показывает допустимую область, линию уровня целевой функции и найденный оптимум одновременно.

Общий вид задачи квадратичного программирования

В общем виде задача КП записывается так:

$\min_x \; \frac{1}{2} x^\top Q x + c^\top x \quad \text{при} \quad Ax \le b,\; x \ge 0,$

где $Q$ - симметричная матрица (для выпуклой задачи - положительно полуопределённая), $c$ - вектор линейных коэффициентов, $A$ и $b$ задают линейные ограничения. Если $Q$ положительно определена, целевая функция строго выпукла и задача имеет единственный минимум. В этой статье разберём частный, но показательный случай - раздельно-квадратичную целевую функцию с одним ресурсным ограничением:

$f(x, y) = \frac{1}{2}p(x - x_0)^2 + \frac{1}{2}q(y - y_0)^2 \to \min, \qquad x + y \le S,\; x, y \ge 0.$

Здесь $x_0, y_0$ - целевые (желаемые) объёмы двух видов продукции, $p, q > 0$ - коэффициенты, показывающие, насколько дорого обходится отклонение от плана, а $S$ - общий лимит ресурса, который тратят оба продукта поровну на единицу выпуска. Матрица $Q = \operatorname{diag}(p, q)$ здесь диагональна и положительно определена, поэтому задача строго выпукла - минимум единственный.

Условия Каруша-Куна-Таккера для задачи КП

Чтобы найти оптимум с ограничениями, составляем функцию Лагранжа с множителем $\lambda \ge 0$ для ресурсного ограничения и множителями $\mu_1, \mu_2 \ge 0$ для неотрицательности:

$L(x, y, \lambda, \mu_1, \mu_2) = f(x, y) + \lambda(x + y - S) - \mu_1 x - \mu_2 y.$

Рассчитать для своей задачи

Условия ККТ требуют одновременно четырёх вещей: стационарности (градиент Лагранжиана по $x, y$ равен нулю), допустимости прямой задачи ($x+y\le S$, $x,y\ge0$), допустимости двойственной ($\lambda, \mu_1, \mu_2 \ge 0$) и дополняющей нежёсткости ($\lambda(x+y-S)=0$, $\mu_1 x = 0$, $\mu_2 y = 0$). Последнее условие - ключевое: множитель может быть положительным, только если соответствующее ограничение выполняется как равенство. Стационарность по $x$ и $y$ (при $x,y>0$, то есть $\mu_1=\mu_2=0$) даёт:

$p(x - x_0) + \lambda = 0, \qquad q(y - y_0) + \lambda = 0 \quad \Longrightarrow \quad x = x_0 - \frac{\lambda}{p}, \;\; y = y_0 - \frac{\lambda}{q}.$

Метод активных ограничений

Метод активных ограничений решает задачу перебором гипотез о том, какие ограничения выполняются как равенства («активны»), а какие - нет:

1. Гипотеза «ничего не активно». Проверяем безусловный минимум $(x_0, y_0)$. Если $x_0 + y_0 \le S$ - он же и есть решение, $\lambda = 0$.
2. Гипотеза «активно только ресурсное ограничение». Подставляем $x = x_0 - \lambda/p$, $y = y_0 - \lambda/q$ в равенство $x + y = S$ и находим множитель в замкнутой форме:

$\lambda = \frac{pq\,(x_0 + y_0 - S)}{p + q}.$

Если оба полученных $x, y \ge 0$ - гипотеза подтвердилась, это и есть оптимум. Если одна из координат получилась отрицательной - переходим к следующей гипотезе.

1. Гипотеза «активны ресурс и одна из неотрицательностей». Например, если $x$ ушёл в минус - фиксируем $x = 0$, тогда из ресурсного ограничения $y = S$: решение - вершина допустимого треугольника.

Рассчитать для своей задачи

На рисунке видно, почему метод и называется «активных ограничений»: допустимое множество - треугольник с вершинами $(0,0)$, $(S,0)$, $(0,S)$, а линии уровня целевой функции - концентрические эллипсы вокруг целевой точки $(x_0,y_0)$. Оптимум - это самая маленькая (по значению $f$) линия уровня, которая ещё касается треугольника. Если целевая точка уже внутри треугольника, касание происходит в самой этой точке. Если она снаружи, эллипс расширяется, пока не коснётся ближайшего ребра или вершины.

Разбор числового примера

Возьмём данные по умолчанию в калькуляторе: целевые объёмы $x_0 = 8$, $y_0 = 7$, коэффициенты издержек $p = 1$, $q = 2$, ресурс $S = 10$. Сначала проверяем гипотезу «ничего не активно»: $x_0 + y_0 = 15 > S = 10$, значит, целевая точка не помещается в допустимую область, и ресурсное ограничение обязано быть активным.

Считаем множитель Лагранжа по формуле:

$\lambda = \frac{p q (x_0+y_0-S)}{p+q} = \frac{1 \cdot 2 \cdot (15 - 10)}{1 + 2} = \frac{10}{3} \approx 3{,}33.$

Подставляем в выражения для координат:

$x^\ast = x_0 - \frac{\lambda}{p} = 8 - \frac{10/3}{1} \approx 4{,}67, \qquad y^\ast = y_0 - \frac{\lambda}{q} = 7 - \frac{10/3}{2} \approx 5{,}33.$

Обе координаты положительны, значит, гипотеза подтвердилась - вершину проверять не нужно. Проверка: $x^\ast + y^\ast = 4{,}67 + 5{,}33 = 10 = S$ - сходится. Значение целевой функции в оптимуме:

$f^\ast = \frac{1}{2}(4{,}67-8)^2 + \frac{1}{2}\cdot 2 \cdot (5{,}33-7)^2 \approx 5{,}56 + 2{,}78 = 8{,}33.$

Экономический смысл множителя Лагранжа

Множитель $\lambda$ - это не просто вспомогательное число, а теневая цена ресурса: он показывает, на сколько вырастут минимальные издержки, если ужесточить ограничение $S$ ровно на единицу. В примере выше $\lambda \approx 3{,}33$ означает, что уменьшение ресурса на единицу (с 10 до 9) увеличит издержки примерно на 3,33 - и наоборот, ослабление ограничения на единицу настолько же их снизит. Именно поэтому в задачах планирования множитель Лагранжа читают как справедливую внутреннюю цену дефицитного ресурса: если внешняя цена его покупки ниже $\lambda$, выгодно докупить ресурс, если выше - не стоит.

Частые ошибки

• Проверка знаков множителей пропускается. Если после решения системы стационарности получилась отрицательная координата, это не «странный ответ» - это сигнал, что гипотеза об активных ограничениях неверна, и нужно перейти к следующей (вершина треугольника).
• Ограничение считается активным без проверки. Если целевая точка и так лежит в допустимой области ($x_0+y_0 \le S$), ресурсное ограничение не активно, и множитель Лагранжа обязан быть равен нулю - принудительная подстановка в равенство $x+y=S$ даст неверный, завышенный ответ.
• Путаница знака при подстановке $\lambda$. В стационарности $p(x-x_0)+\lambda=0$ множитель входит со знаком «плюс» именно потому, что ограничение записано как $x+y-S\le 0$; при другой форме записи ограничения знак меняется - важно быть последовательным.
• Игнорирование условия выпуклости. Метод активных ограничений в этой простой форме работает, только если $Q$ положительно (полу)определена. Если в матрице издержек встречаются отрицательные коэффициенты, задача может быть невыпуклой, и такого простого решения через стационарность недостаточно.

FAQ

Чем задача квадратичного программирования отличается от линейного программирования? В линейном программировании целевая функция линейна, и оптимум всегда находится в вершине допустимого многогранника. В квадратичном программировании целевая функция выпуклая (не линейная), поэтому оптимум может лежать и внутри ребра допустимой области, а не только в вершине.

Как понять, активно ли ограничение, не решая всю задачу? Достаточно проверить, попадает ли безусловный минимум целевой функции в допустимую область. Если да - ограничение не активно и его можно отбросить. Если нет - ограничение обязательно активно в оптимуме (для выпуклой задачи).

Что делать, если проекция на границу даёт отрицательную координату? Это означает, что оптимум лежит не на этом ребре, а в вершине допустимой области, где активны сразу два ограничения (например, ресурсное и неотрицательность одной из переменных). Нужно зафиксировать эту переменную равной нулю и пересчитать вторую из оставшегося ограничения.

Коротко

Задача квадратичного программирования решается методом активных ограничений: сначала проверяется, укладывается ли безусловный минимум в допустимую область, а если нет - строится система стационарности с множителем Лагранжа для активного ограничения. Если проекция на границу даёт отрицательные координаты, решение ищут в вершине допустимой области. Множитель Лагранжа $\lambda$ при этом получает смысл теневой цены ресурса - меры того, насколько ужесточение ограничения увеличивает минимальные издержки.