Оглавление [Скрыть]
Квадратично ограниченная квадратичная программа
-
Определение и свойства QCQP
- QCQP – это задача оптимизации с квадратичными функциями как для целевой функции, так и для ограничений.
- Если все матрицы P0, …, Pm положительно полуопределены, задача является выпуклой, в противном случае – невыпуклой.
- Если P1, …, Pm равны нулю, ограничения становятся линейными, и задача превращается в квадратичную программу.
-
Сложность решения
- Решение общего случая QCQP является NP-сложной задачей.
- Целочисленное программирование 0-1 может быть сведено к QCQP, что делает его также NP-сложным.
-
Методы решения
- Существуют два основных подхода к решению QCQP: полуопределенное программирование (SDP) и метод переформулировки-линеаризации (RLT).
- Для некоторых классов задач доступны точные релаксации, такие как SOCP и LP.
-
Примеры использования
- QCQP применяется для решения задач в теории графов, таких как максимальное сокращение, и в высокоточных приложениях, например, в фотолитографии.
-
Решатели и языки программирования
- Существуют рекомендации по использованию решателей и скриптовых языков для решения QCQP.
-
Дополнительные ресурсы
- В статье есть ссылки на дальнейшее чтение и внешние ресурсы.
Полный текст статьи: