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

Квадратичное программирование ( QP ) — это процесс решения определенных математической оптимизации, задач включающих квадратичные функции . В частности, стремятся оптимизировать (минимизировать или максимизировать) многомерную квадратичную функцию с учетом линейных ограничений на переменные. Квадратичное программирование — это разновидность нелинейного программирования .

«Программирование» в этом контексте относится к формальной процедуре решения математических задач. Это использование датируется 1940-ми годами и не связано конкретно с более поздним понятием «компьютерное программирование». Чтобы избежать путаницы, некоторые практики предпочитают термин «оптимизация», например, «квадратичная оптимизация». ^[1]

Формулировка задачи

Задачу квадратичного программирования с $n$ переменными и $m$ ограничениями можно сформулировать следующим образом. ^[2]Данный:

вещественный n - $мерный$ вектор $c$ ,
n $\times n симметричная$ -мерная вещественная матрица $Q$ ,
матрица $m \times n$ размерности $и$ вещественная
m $-мерный$ вещественный вектор $b$ ,

Цель квадратичного программирования — найти $n-$ мерный вектор $x$ , который будет

минимизировать	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
при условии	$A\mathbf {x} \preceq \mathbf {b} ,$

где $х Т$ обозначает транспонирование вектора x $означает ,$ , а обозначение $A x ⪯ b$ что каждый элемент вектора $A x$ меньше или равен соответствующему элементу вектора $b$ (покомпонентное неравенство).

Ограниченные наименьшие квадраты

В частном случае, когда $Q$ является симметричным положительно определенным , функция стоимости сводится к методу наименьших квадратов:

минимизировать	${\tfrac {1}{2}}\\|R\mathbf {x} -\mathbf {d} \\|^{2}$
при условии	$A\mathbf {x} \preceq \mathbf {b} ,$

где $Q = R Т R$ следует из Холецкого Q $c$ и $разложения = - R Т д$ . И наоборот, любая такая программа наименьших квадратов с ограничениями может быть эквивалентно сформулирована как задача квадратичного программирования, даже для общей неквадратной $R-$ матрицы.

Обобщения

При минимизации функции $f$ в окрестности некоторой контрольной точки $x 0$ а $Q$ устанавливается в ее матрицу Гессе $H (f (x 0) ),$ c $устанавливается$ в ее градиент $\nabla f (x 0)$ . Связанная с этим задача программирования, квадратичное программирование с квадратичными ограничениями , может быть поставлена путем добавления квадратичных ограничений на переменные.

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

Для решения общих задач обычно используются различные методы, в том числе

внутренняя точка ,
активный набор , ^[3]
расширенный лагранжиан , ^[4]
сопряженный градиент ,
градиентная проекция ,
расширения симплексного алгоритма . ^[3]

В случае, когда $Q$ положительно определена , проблема является частным случаем более общей области выпуклой оптимизации .

Ограничения равенства

Квадратичное программирование особенно просто, когда $Q$ положительно определен и существуют только ограничения равенства; в частности, процесс решения является линейным. Используя множители Лагранжа и ища экстремум лагранжиана, можно легко показать, что решение проблемы с ограничениями равенства

{\text{Minimize}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x}

{\text{subject to}}\quad E\mathbf {x} =\mathbf {d}

задается линейной системой

{\begin{bmatrix}Q&E^{\top }\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}

где $λ$ — набор множителей Лагранжа, которые выходят из решения вместе с $x$ .

Самый простой способ приблизиться к этой системе — прямое решение (например, LU-факторизация ), которое для небольших задач очень практично. Для больших задач система создает некоторые необычные трудности, в первую очередь то, что проблема никогда не является положительно определенной (даже если $Q$ такова), что потенциально очень затрудняет поиск хорошего численного подхода, и существует множество подходов на выбор в зависимости от проблема.

Если ограничения не слишком тесно связывают переменные, относительно простой атакой является изменение переменных так, чтобы ограничения были безоговорочно удовлетворены. Например, предположим, что $d = 0$ (обобщение до ненулевого значения несложно). Глядя на уравнения ограничений:

E\mathbf {x} =0

ввести новую переменную $y,$ определенную как

Z\mathbf {y} =\mathbf {x}

где $y$ имеет размерность $x$ минус количество ограничений. Затем

EZ\mathbf {y} =\mathbf {0}

и если $Z$ выбрано так, что $EZ = 0,$ уравнение ограничения всегда будет выполняться. такого $Z$ влечет за собой нахождение нулевого пространства E $Нахождение$ или менее просто в зависимости от структуры $E.$ , что более Подстановка в квадратичную форму дает задачу неограниченной минимизации:

{\tfrac {1}{2}}\mathbf {x} ^{\top }Q\mathbf {x} +\mathbf {c} ^{\top }\mathbf {x} \quad \implies \quad {\tfrac {1}{2}}\mathbf {y} ^{\top }Z^{\top }QZ\mathbf {y} +\left(Z^{\top }\mathbf {c} \right)^{\top }\mathbf {y}

решение которого дает:

Z^{\top }QZ\mathbf {y} =-Z^{\top }\mathbf {c}

При определенных условиях на $Q$ приведенная матрица $Z Т QZ$ будет положительно определенным. Можно написать вариант метода сопряженных градиентов который позволяет избежать явного вычисления $Z.$ , ^[5]

Лагранжева двойственность

Лагранжев, двойственный к задаче квадратичного программирования, также является задачей квадратичного программирования. Чтобы убедиться в этом, давайте сосредоточимся на случае, когда $c = 0$ и $Q$ положительно определен. Запишем функцию Лагранжа как

L(x,\lambda )={\tfrac {1}{2}}x^{\top }Qx+\lambda ^{\top }(Ax-b).

Определив (лагранжеву) двойственную функцию $g (λ)$ как $g(\lambda )=\inf _{x}L(x,\lambda )$ , мы находим нижнюю границу , $L$ используя $\nabla _{x}L(x,\lambda )=0$ и положительная определенность $Q$ :

x^{*}=-Q^{-1}A^{\top }\lambda .

Следовательно, двойственная функция

g(\lambda )=-{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top }\lambda -\lambda ^{\top }b,

и поэтому лагранжиан, двойственный к задаче квадратичного программирования, равен

{\text{maximize}}_{\lambda \geq 0}\quad -{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top }\lambda -\lambda ^{\top }b.

Помимо лагранжевой теории двойственности, существуют и другие пары двойственности (например , Вулфа и др.).

Сложность во время выполнения

Выпуклое квадратичное программирование

Для положительно определенного $Q$ , когда проблема выпуклая, метод эллипсоида решает проблему за (слабо) полиномиальное время . ^[6]

Ye and Tse ^[7] представить алгоритм с полиномиальным временем, который расширяет алгоритм Кармаркара от линейного программирования до выпуклого квадратичного программирования. В системе с n переменными и L входными битами их алгоритм требует O(L n) итераций, каждая из которых может быть выполнена с использованием O(L n ³) арифметических операций с общей сложностью выполнения O( L ² н ⁴).

Капур и Вайдья ^[8] представить другой алгоритм, который требует O( L * log L * n ^3.67 * log n ) арифметические операции.

Невыпуклое квадратичное программирование

Если $Q$ неопределенно (поэтому проблема невыпуклая), то проблема NP-трудна . ^[9] Простой способ убедиться в этом — рассмотреть невыпуклое квадратичное ограничение x _i² = Икс _я . Это ограничение эквивалентно требованию, чтобы x _i находился в {0,1}, то есть x _i является двоичной целочисленной переменной. Следовательно, такие ограничения можно использовать для моделирования любой целочисленной программы с двоичными переменными, которая, как известно, является NP-трудной.

Более того, эти невыпуклые задачи могут иметь несколько стационарных точек и локальных минимумов. Фактически, даже если $Q$ имеет только одно отрицательное собственное значение , проблема (строго) NP-трудна . ^[10]

Более того, найти точку ККТ невыпуклой квадратичной программы CLS-трудно. ^[11]

Смешанно-целочисленное квадратичное программирование

В некоторых ситуациях один или несколько элементов вектора $x$ должны принимать целочисленные значения. Это приводит к формулировке задачи смешанно-целочисленного квадратичного программирования (MIQP). ^[12] Приложения MIQP включают водные ресурсы. ^[13] и создание индексных фондов . ^[14]

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

Имя	Информация о письме
АИММС	Программный комплекс для моделирования и решения задач оптимизации и планирования.
АЛГЛИБ	Числовая библиотека с двойной лицензией (GPL/собственная) (C++, .NET).
AMPL	Популярный язык моделирования для крупномасштабной математической оптимизации.
APMonitor	Пакет моделирования и оптимизации для систем LP , QP, NLP , MILP , MINLP и DAE в MATLAB и Python.
Артелис Книтро	Интегрированный пакет для нелинейной оптимизации
КГАЛ	Пакет вычислительной геометрии с открытым исходным кодом, который включает в себя решатель квадратичного программирования.
Комплексный комплекс	Популярный решатель с API (C, C++, Java, .Net, Python, Matlab и R). Бесплатно для ученых.
Excel Функция решения	Нелинейный решатель, адаптированный к электронным таблицам, в которых оценки функций основаны на пересчете ячеек. Базовая версия доступна как стандартное дополнение к Excel.
ГАМС	Система моделирования высокого уровня для математической оптимизации.
GNU Октава	Бесплатный (лицензия GPLv 3) матрично-ориентированный язык программирования общего назначения для числовых вычислений, аналогичный MATLAB. Квадратичное программирование в GNU Octave доступно через qp. команду
HiGHS	Программное обеспечение с открытым исходным кодом для решения моделей линейного программирования (LP), смешанно-целочисленного программирования (MIP) и выпуклого квадратичного программирования (QP).
ИМСЛ	Набор математических и статистических функций, которые программисты могут встраивать в свои программные приложения.
ИПОРТ	IPOPT (Interior Point OPTimizer) — это программный пакет для крупномасштабной нелинейной оптимизации.
Юлия	Язык программирования высокого уровня с известным пакетом решений JuMP.
Клен	Язык программирования общего назначения для математики. Решение квадратичной задачи в Maple осуществляется с помощью команды QPSolve .
МАТЛАБ	Универсальный матрично-ориентированный язык программирования для численных вычислений. Для квадратичного программирования в MATLAB требуется Optimization Toolbox в дополнение к базовому продукту MATLAB.
Математика	Язык программирования общего назначения для математики, включая символьные и числовые возможности.
МОИСЕЙ	Решатель для крупномасштабной оптимизации с API для нескольких языков (C++, Java, .Net, Matlab и Python).
Цифровая библиотека НАГ	Коллекция математических и статистических процедур, разработанных группой числовых алгоритмов для нескольких языков программирования (C, C++, Fortran, Visual Basic, Java и C#) и пакетов (MATLAB, Excel, R, LabVIEW). Глава «Оптимизация» библиотеки NAG включает процедуры для решения задач квадратичного программирования как с разреженными, так и с неразреженными матрицами линейных ограничений, а также процедуры для оптимизации линейных, нелинейных сумм квадратов линейных или нелинейных функций с нелинейными, ограниченными ограничениями или без них. . В библиотеке NAG есть процедуры как для локальной, так и для глобальной оптимизации, а также для решения непрерывных или целочисленных задач.
Питон	Язык программирования высокого уровня с привязками для большинства доступных решателей. Квадратичное программирование доступно через функциюsolve_qp или путем прямого вызова определенного решателя.
Р (Фортран)	GPL Универсальная кроссплатформенная среда статистических вычислений, лицензируемая по лицензии .
САС /ИЛИ	Набор решателей для линейной, целочисленной, нелинейной, без производной, сетевой, комбинаторной оптимизации и оптимизации с ограничениями; язык алгебраического моделирования OPTMODEL; и множество вертикальных решений, направленных на конкретные проблемы/рынки, все из которых полностью интегрированы с системой SAS .
Суан Шу	набор алгоритмов оптимизации с открытым исходным кодом для решения LP , QP, SOCP , SDP , SQP на Java
ТК Солвер	Программная система для математического моделирования и решения проблем, основанная на декларативном языке, основанном на правилах, коммерциализированная Universal Technic Systems, Inc.
ТОМЛАБ	Поддерживает глобальную оптимизацию, целочисленное программирование, все типы наименьших квадратов, линейное, квадратичное и неограниченное программирование для MATLAB . TOMLAB поддерживает такие решатели, как CPLEX , SNOPT и KNITRO .
XPRESS	Решатель для крупномасштабных линейных программ, квадратичных программ, общих нелинейных и смешанно-целочисленных программ. Имеет API для нескольких языков программирования, также имеет язык моделирования Mosel и работает с AMPL, GAMS . Бесплатно для академического использования.

Расширения

Полиномиальная оптимизация ^[15] представляет собой более общую структуру, в которой ограничения могут быть полиномиальными функциями любой степени, а не только 2.

См. также

Ссылки

^ Райт, Стивен Дж. (2015), «Непрерывная оптимизация (нелинейное и линейное программирование)», Николас Дж. Хайэм; и др. (ред.), Princeton Companion to Applied Mathematics , Princeton University Press, стр. 281–293.
^ Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин, Нью-Йорк: Springer-Verlag . п. 449 . ISBN 978-0-387-30303-1 . .
^ Jump up to: ^а ^б Мурти, Катта Г. (1988). Линейная дополнительность, линейное и нелинейное программирование . Серия Сигма в прикладной математике. Том. 3. Берлин: Хелдерманн Верлаг. стр. xlviii+629 стр. ISBN 978-3-88538-403-8 . МР 0949214 . Архивировано из оригинала 1 апреля 2010 г.
^ Дельбос, Ф.; Гилберт, Дж.Ч. (2005). «Глобальная линейная сходимость расширенного лагранжева алгоритма для решения задач выпуклой квадратичной оптимизации» (PDF) . Журнал выпуклого анализа . 12 : 45–69. Архивировано (PDF) из оригинала 9 октября 2022 г.
^ Гулд, Николас И.М.; Хрибар, Мэри Э.; Носедал, Хорхе (апрель 2001 г.). «О решении задач квадратичного программирования с ограничениями равенства, возникающих при оптимизации». СИАМ J. Sci. Вычислить . 23 (4): 1376–1395. CiteSeerX 10.1.1.129.7555 . дои : 10.1137/S1064827598345667 .
^ Kozlov, M. K.; S. P. Tarasov; Leonid G. Khachiyan (1979). "[Polynomial solvability of convex quadratic programming]". Doklady Akademii Nauk SSSR . 248 : 1049–1051. Translated in: Советская математика -- Документы . 20 : 1108–1111. {{cite journal}}: Отсутствует или пусто |title= ( помощь )
^ Йе, Иньюй; Це, Эдисон (1 мая 1989 г.). «Расширение проективного алгоритма Кармаркара для выпуклого квадратичного программирования» . Математическое программирование . 44 (1): 157–179. дои : 10.1007/BF01587086 . ISSN 1436-4646 . S2CID 35753865 .
^ Капур, С; Вайдья, премьер-министр (1 ноября 1986 г.). «Быстрые алгоритмы выпуклого квадратичного программирования и многопродуктовых потоков» . Материалы восемнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '86 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 147–159. дои : 10.1145/12130.12145 . ISBN 978-0-89791-193-1 . S2CID 18108815 .
^ Сахни, С. (1974). «Проблемы, связанные с вычислениями» (PDF) . SIAM Journal по вычислительной технике . 3 (4): 262–279. CiteSeerX 10.1.1.145.8685 . дои : 10.1137/0203021 .
^ Пардалос, Панос М.; Вавасис, Стивен А. (1991). «Квадратичное программирование с одним отрицательным собственным значением (строго) NP-трудно». Журнал глобальной оптимизации . 1 (1): 15–22. дои : 10.1007/bf00120662 . S2CID 12602885 .
^ Фернли, Джон; Голдберг, Пол В.; Холлендер, Александрос; Савани, Рахул (2023). «Сложность вычисления ККТ-решений квадратичных программ». arXiv : 2311.13738 [ cs.CC ].
^ Лазими, Рафаэль (1 декабря 1982 г.). «Смешанно-целочисленное квадратичное программирование». Математическое программирование . 22 (1): 332–349. дои : 10.1007/BF01581047 . ISSN 1436-4646 . S2CID 8456219 .
^ Пропато Марко; Убер Джеймс Дж. (1 июля 2004 г.). «Проектирование бустерной системы с использованием квадратичного программирования смешанных целых чисел». Журнал планирования и управления водными ресурсами . 130 (4): 348–352. дои : 10.1061/(ASCE)0733-9496(2004)130:4(348) .
^ Корнюжоль, Жерар; Пенья, Хавьер; Смокер, Рекха (2018). Методы оптимизации в финансах (2-е изд.). Кембридж, Великобритания: Издательство Кембриджского университета. стр. 167–168. ISBN 9781107297340 .
^ Туй, Хоанг (2016), Туй, Хоанг (редактор), «Полиномиальная оптимизация» , Выпуклый анализ и глобальная оптимизация , Оптимизация Спрингера и ее приложения, том. 110, Чам: Springer International Publishing, стр. 435–452, номер документа : 10.1007/978-3-319-31484-6_12 , ISBN. 978-3-319-31484-6 , получено 16 декабря 2023 г.

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

Коттл, Ричард В.; Панг, Чон-Ши; Стоун, Ричард Э. (1992). Проблема линейной дополнительности . Информатика и научные вычисления. Бостон, Массачусетс: Academic Press, Inc., стр. xxiv+762 стр. ISBN. 978-0-12-192350-1 . МР 1150683 .
Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN 978-0-7167-1045-5 . А6: MP2, стр. 245.
Гулд, Николас И.М.; Туант, Филипп Л. (2000). «Библиография по квадратичному программированию» (PDF) . Внутренний отчет группы численного анализа RAL, 2000-1.

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

[PrincetonCompanion-1] Райт, Стивен Дж. (2015), «Непрерывная оптимизация (нелинейное и линейное программирование)», Николас Дж. Хайэм; и др. (ред.), Princeton Companion to Applied Mathematics , Princeton University Press, стр. 281–293.

[2] Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин, Нью-Йорк: Springer-Verlag . п. 449 . ISBN 978-0-387-30303-1 . .

[ioe.engin.umich-3] Jump up to: ^а ^б Мурти, Катта Г. (1988). Линейная дополнительность, линейное и нелинейное программирование . Серия Сигма в прикладной математике. Том. 3. Берлин: Хелдерманн Верлаг. стр. xlviii+629 стр. ISBN 978-3-88538-403-8 . МР 0949214 . Архивировано из оригинала 1 апреля 2010 г.

[4] Дельбос, Ф.; Гилберт, Дж.Ч. (2005). «Глобальная линейная сходимость расширенного лагранжева алгоритма для решения задач выпуклой квадратичной оптимизации» (PDF) . Журнал выпуклого анализа . 12 : 45–69. Архивировано (PDF) из оригинала 9 октября 2022 г.

[5] Гулд, Николас И.М.; Хрибар, Мэри Э.; Носедал, Хорхе (апрель 2001 г.). «О решении задач квадратичного программирования с ограничениями равенства, возникающих при оптимизации». СИАМ J. Sci. Вычислить . 23 (4): 1376–1395. CiteSeerX 10.1.1.129.7555 . дои : 10.1137/S1064827598345667 .

[6] Kozlov, M. K.; S. P. Tarasov; Leonid G. Khachiyan (1979). "[Polynomial solvability of convex quadratic programming]". Doklady Akademii Nauk SSSR . 248 : 1049–1051. Translated in: Советская математика -- Документы . 20 : 1108–1111. {{cite journal}}: Отсутствует или пусто |title= ( помощь )

[7] Йе, Иньюй; Це, Эдисон (1 мая 1989 г.). «Расширение проективного алгоритма Кармаркара для выпуклого квадратичного программирования» . Математическое программирование . 44 (1): 157–179. дои : 10.1007/BF01587086 . ISSN 1436-4646 . S2CID 35753865 .

[8] Капур, С; Вайдья, премьер-министр (1 ноября 1986 г.). «Быстрые алгоритмы выпуклого квадратичного программирования и многопродуктовых потоков» . Материалы восемнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '86 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 147–159. дои : 10.1145/12130.12145 . ISBN 978-0-89791-193-1 . S2CID 18108815 .

[9] Сахни, С. (1974). «Проблемы, связанные с вычислениями» (PDF) . SIAM Journal по вычислительной технике . 3 (4): 262–279. CiteSeerX 10.1.1.145.8685 . дои : 10.1137/0203021 .

[10] Пардалос, Панос М.; Вавасис, Стивен А. (1991). «Квадратичное программирование с одним отрицательным собственным значением (строго) NP-трудно». Журнал глобальной оптимизации . 1 (1): 15–22. дои : 10.1007/bf00120662 . S2CID 12602885 .

[11] Фернли, Джон; Голдберг, Пол В.; Холлендер, Александрос; Савани, Рахул (2023). «Сложность вычисления ККТ-решений квадратичных программ». arXiv : 2311.13738 [ cs.CC ].

[12] Лазими, Рафаэль (1 декабря 1982 г.). «Смешанно-целочисленное квадратичное программирование». Математическое программирование . 22 (1): 332–349. дои : 10.1007/BF01581047 . ISSN 1436-4646 . S2CID 8456219 .

[13] Пропато Марко; Убер Джеймс Дж. (1 июля 2004 г.). «Проектирование бустерной системы с использованием квадратичного программирования смешанных целых чисел». Журнал планирования и управления водными ресурсами . 130 (4): 348–352. дои : 10.1061/(ASCE)0733-9496(2004)130:4(348) .

[14] Корнюжоль, Жерар; Пенья, Хавьер; Смокер, Рекха (2018). Методы оптимизации в финансах (2-е изд.). Кембридж, Великобритания: Издательство Кембриджского университета. стр. 167–168. ISBN 9781107297340 .

[15] Туй, Хоанг (2016), Туй, Хоанг (редактор), «Полиномиальная оптимизация» , Выпуклый анализ и глобальная оптимизация , Оптимизация Спрингера и ее приложения, том. 110, Чам: Springer International Publishing, стр. 435–452, номер документа : 10.1007/978-3-319-31484-6_12 , ISBN. 978-3-319-31484-6 , получено 16 декабря 2023 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

v т и Проблемы дополнительности и алгоритмы
Complementarity Problems	Linear programming (LP) Quadratic programming (QP) Linear complementarity problem (LCP) Mixed linear (MLCP) Mixed (MCP) Nonlinear (NCP)
Basis-exchange algorithms	Simplex (Dantzig) Revised simplex Criss-cross Lemke