Квадратичная программа с квадратичными ограничениями

В математической оптимизации квадратичная программа с квадратичными ограничениями ( QCQP ) представляет собой задачу оптимизации, в которой и целевая функция , и ограничения являются квадратичными функциями . Он имеет форму

${\begin{aligned}&{\text{minimize}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{0}x+q_{0}^{\mathrm {T} }x\\&{\text{subject to}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{i}x+q_{i}^{\mathrm {T} }x+r_{i}\leq 0\quad {\text{for }}i=1,\dots ,m,\\&&&Ax=b,\end{aligned}}$

где P ₀ , ..., P _m — n матрицы размера ×n и x ∈ R ^н — переменная оптимизации.

Если P0 _, ,..., Pm _то все положительно полуопределенны задача выпуклая . Если эти матрицы не являются ни положительными, ни отрицательно полуопределенными, задача невыпуклая. Если все P ₁ , ... , P _m равны нулю, то ограничения фактически линейны и задача представляет собой квадратичную программу .

Твердость

Решение общего случая является NP-трудной задачей. Чтобы убедиться в этом, обратите внимание, что два ограничения x ₁ ( x ₁ − 1) ≤ 0 и x ₁ ( x ₁ − 1) ≥ 0 эквивалентны ограничению x ₁ ( x ₁ − 1) = 0, которое, в свою очередь, эквивалентно ограничению x ₁ ∈ {0, 1}. Следовательно, любую целочисленную программу 0–1 (в которой все переменные должны быть либо 0, либо 1) можно сформулировать как квадратичную программу с квадратичными ограничениями. Поскольку целочисленное программирование 0–1 в целом является NP-сложным, QCQP также является NP-трудным.

Релаксация

Существует два основных ослабления QCQP: использование полуопределенного программирования (SDP) и использование метода переформулировки-линеаризации (RLT). Для некоторых классов задач QCQP (а именно, QCQP с нулевыми диагональными элементами в матрицах данных) конусного программирования второго порядка (SOCP) и линейного программирования (LP), обеспечивающие то же целевое значение, что и релаксация SDP. доступны релаксации

Невыпуклые КККП с неположительными недиагональными элементами могут быть точно решены с помощью релаксаций SDP или SOCP. и, если быть точным, существуют достаточные условия, проверяемые полиномиально по времени, для релаксации SDP общих QCQP. Более того, было показано, что класс случайных общих КККП имеет точные полуопределенные релаксации с высокой вероятностью, пока число ограничений растет не быстрее, чем фиксированный полином от числа переменных.

Semidefinite programming

Когда P0 _{и может} ,..., Pm _— положительно определенные матрицы , проблема является выпуклой быть легко решена с использованием методов внутренних точек , как это делается при полуопределенном программировании .

Пример

• Max Cut — это задача теории графов, которая является NP-сложной. Для данного графа задача состоит в том, чтобы разделить вершины на два множества так, чтобы как можно больше ребер переходило из одного множества в другое. Max Cut можно сформулировать как QCQP, а релаксация двойственной SDP обеспечивает хорошие нижние границы.
• QCQP используется для точной настройки машины в высокоточных приложениях, таких как фотолитография .

Решатели и языки сценариев (программирования)

Имя	Краткая информация
Артелис Книтро	Knitro — это решатель, специализирующийся на нелинейной оптимизации, но также решающий задачи линейного программирования, задачи квадратичного программирования, конусного программирования второго порядка, системы нелинейных уравнений и задачи с ограничениями равновесия.
ФИКО Экспресс	Коммерческий решатель оптимизации для линейного программирования, нелинейного программирования, смешанного целочисленного линейного программирования, выпуклого квадратичного программирования, выпуклого квадратичного программирования с квадратичными ограничениями, конического программирования второго порядка и их аналогов со смешанными целыми числами.
AMPL
Комплексный комплекс	Популярный решатель с API для нескольких языков программирования. Бесплатно для ученых.
МОИСЕЙ	Решатель для крупномасштабной оптимизации с API для нескольких языков (C++,java,.net, Matlab и python).
ТОМЛАБ	Поддерживает глобальную оптимизацию, целочисленное программирование, все типы наименьших квадратов, линейное, квадратичное и неограниченное программирование для MATLAB . TOMLAB поддерживает такие решатели, как CPLEX , SNOPT и KNITRO .
Вольфрам Математика	Способен решать проблемы типа QCQP, используя такие функции, как Минимизировать .

Ссылки

• Бойд, Стивен; Ливен Ванденберге (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-83378-3 .

Дальнейшее чтение

В статистике

• Альберс С.Дж., Кричли Ф., Гауэр, Дж.К. (2011). «Задачи квадратичной минимизации в статистике» (PDF) . Журнал многомерного анализа . 102 (3): 698–713. дои : 10.1016/j.jmva.2009.12.018 . hdl : 11370/6295bde7-4de1-48c2-a30b-055eff924f3e . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

Внешние ссылки

• Руководство по оптимизации NEOS: квадратичное программирование с квадратичными ограничениями