Квадратичное программирование с квадратичными ограничениями (QCQP): полуопределенная релаксация

Математическая модель QCQP содержит квадратичную целевую функцию и набор ограничений вида (X^T * P_i * X + Q_i^T * X + r_i <= 0). Вычислительная сложность задачи всецело зависит от свойств матриц P_i. Если абсолютно все эти матрицы являются положительно полуопределенными, геометрически ограничения образуют пересечение многомерных эллипсоидов (выпуклых фигур). Такая задача является строго выпуклой и легко решается алгоритмами внутренней точки за полиномиальное время. Но если хотя бы одна матрица индефинитна, ограничение превращается в гиперболоид или седловидную поверхность. Область допустимых решений становится невыпуклой (может распадаться на изолированные куски), и задача мгновенно приобретает статус NP-трудной.

Для обхода этой алгебраической ловушки исследователи операций используют гениальный трюк — полуопределенную релаксацию (Semidefinite Relaxation, SDR). Идея заключается в переходе в пространство более высокой размерности. Вводится новая вспомогательная матрица Y, которая по определению должна быть строго равна произведению X * X^T. Квадратичная форма X^T * P_i * X переписывается через оператор матричного следа: Trace(P_i * Y). Благодаря этому фокусу все нелинейные (квадратичные) члены магически превращаются в простые линейные функции от элементов новой матрицы Y. Целевая функция и все ограничения становятся абсолютно линейными!

Проблема заключается лишь в одном нелинейном условии, связывающем матрицу Y и вектор X: ранг матрицы, составленной из Y и X, должен быть строго равен единице. Этот жесткий алгебраический барьер делает задачу труднорешаемой. Суррогатная релаксация Шора (Shor relaxation) заключается в том, что мы просто отбрасываем требование о ранге матрицы, заменяя его более мягким условием: матрица-разность (Y - X * X^T) должна быть положительно полуопределенной. В результате сложнейшая невыпуклая задача QCQP превращается в задачу полуопределенного программирования (Semidefinite Programming, SDP), которая является выпуклой и безупречно решается суперкомпьютерами.

Решив релаксированную задачу SDP, алгоритм получает нижнюю границу (Lower Bound) глобального минимума. Затем с помощью процедур рандомизации (генерации случайных гауссовых векторов на основе полученной ковариационной матрицы Y) извлекается приближенное, физически допустимое решение исходной невыпуклой задачи QCQP. Аппарат полуопределенной релаксации совершил переворот в управлении умными электросетями (Smart Grids), позволив диспетчерам рассчитывать оптимальные параметры напряжения и токов для минимизации потерь мощности в масштабах национальных энергосистем, доказывая, что невыпуклую физику мира можно обуздать матричными инструментами высшей алгебры.