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

В математической оптимизации квадратичная программа с квадратичными ограничениями ( 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. доступны релаксации ^[1]

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

Полуопределенное программирование

Когда 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, используя такие функции, как Минимизировать .

Ссылки

^ Кимизука, Масаки; Ким, Сунён; Ямасита, Макото (2019). «Решение проблем объединения с дискретизацией по времени с помощью методов релаксации и перепланирования LP и SOCP». Журнал глобальной оптимизации . 75 (3): 631–654. дои : 10.1007/s10898-019-00795-w . ISSN 0925-5001 . S2CID 254701008 .
^ Ким, Сунён; Кодзима, Масакадзу (2003). «Точные решения некоторых невыпуклых задач квадратичной оптимизации с помощью релаксаций SDP и SOCP». Вычислительная оптимизация и приложения . 26 (2): 143–154. дои : 10.1023/А:1025794313696 . S2CID 1241391 .
^ Перейти обратно: ^а ^б Бюрер, Сэмюэл; Йе, Иньюй (04.02.2019). «Точные полуопределенные формулировки для класса (случайных и неслучайных) невыпуклых квадратичных программ». Математическое программирование . 181 : 1–17. arXiv : 1802.02688 . дои : 10.1007/s10107-019-01367-2 . ISSN 0025-5610 . S2CID 254143721 .

Бойд, Стивен; Ливен Ванденберге (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: квадратичное программирование с квадратичными ограничениями

[1] Кимизука, Масаки; Ким, Сунён; Ямасита, Макото (2019). «Решение проблем объединения с дискретизацией по времени с помощью методов релаксации и перепланирования LP и SOCP». Журнал глобальной оптимизации . 75 (3): 631–654. дои : 10.1007/s10898-019-00795-w . ISSN 0925-5001 . S2CID 254701008 .

[2] Ким, Сунён; Кодзима, Масакадзу (2003). «Точные решения некоторых невыпуклых задач квадратичной оптимизации с помощью релаксаций SDP и SOCP». Вычислительная оптимизация и приложения . 26 (2): 143–154. дои : 10.1023/А:1025794313696 . S2CID 1241391 .

[:0-3] Перейти обратно: ^а ^б Бюрер, Сэмюэл; Йе, Иньюй (04.02.2019). «Точные полуопределенные формулировки для класса (случайных и неслучайных) невыпуклых квадратичных программ». Математическое программирование . 181 : 1–17. arXiv : 1802.02688 . дои : 10.1007/s10107-019-01367-2 . ISSN 0025-5610 . S2CID 254143721 .

[1]

[2]

[3]