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

• Определение и свойства QCQP

  • QCQP — это задача оптимизации с квадратичными функциями как для целевой функции, так и для ограничений. 
  • Если все матрицы P0, …, Pm положительно полуопределены, задача является выпуклой, в противном случае — невыпуклой. 
  • Если P1, …, Pm равны нулю, ограничения становятся линейными, и задача превращается в квадратичную программу. 

• Сложность решения

  • Решение общего случая QCQP является NP-сложной задачей. 
  • Целочисленное программирование 0-1 может быть сведено к QCQP, что делает его также NP-сложным. 

• Методы решения

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

• Примеры использования

  • QCQP применяется для решения задач в теории графов, таких как максимальное сокращение, и в высокоточных приложениях, например, в фотолитографии. 

• Решатели и языки программирования

  • Существуют рекомендации по использованию решателей и скриптовых языков для решения QCQP. 

• Дополнительные ресурсы

  • В статье есть ссылки на дальнейшее чтение и внешние ресурсы.