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

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

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

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

Дано:

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

Целью задачи квадратичного программирования является поиск n-мерного вектора x, который

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

где x^T обозначает транспонированный вектор. Обозначение Ax ≤ b означает, что любой элемент вектора Ax не превосходит соответствующего элемента вектора b.

Связанная задача программирования, квадратичная задача с квадратичными ограничениями^[англ.] имеет квадратичные ограничения на переменные.

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

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

Метод внутренней точки
Метод активного набора^[англ.] ^[2]
Метод обобщённого лагранжиана^[англ.] ^[3]
метод сопряжённых градиентов
Метод проекции градиента
Модификация симплекс-метода^[2]^[4]

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

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

Задача квадратичного программирования несколько проще, если Q является положительно определённой и все ограничения являются равенствами (нет неравенств), поскольку в этом случае можно свести задачу к решению системы линейных уравнений. Если использовать множители Лагранжа и искать экстремум лагранжиана, можно легко показать, что решение задачи

минимизировать	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
при условиях	$B\mathbf {x} =\mathbf {d}$

определяется системой линейных уравнений

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

где $\lambda$ — множество множителей Лагранжа, которые появляются вместе с решением $\mathbf {x}$ .

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

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

B\mathbf {x} =0

Введём новый вектор $\mathbf {y}$ , определённый равенством

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

где $\mathbf {y}$ имеет размерность $\mathbf {x}$ минус число ограничений. Тогда

BZ\mathbf {y} =0

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

{\tfrac {1}{2}}\mathbf {x} ^{T}Q\mathbf {x} +\mathbf {c} ^{T}\mathbf {x} \quad \Rightarrow \quad {\tfrac {1}{2}}\mathbf {y} ^{T}Z^{T}QZ\mathbf {y} +(Z^{T}\mathbf {c} )^{T}\mathbf {y}

и решение можно будет найти, решив уравнение

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

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

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

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

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

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

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

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

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

и двойственной задачей Лагранжа для исходной задачи будет

минимизировать	$-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b$
при условиях	$\lambda \geqslant 0$ .

Кроме теории двойственности Лагранжа, существуют другие двойственные пары задач (например, двойственность Вулфа^[англ.]).

Сложность

Для положительно определённой матрицы Q метод эллипсоидов решает задачу за полиномиальное время^[6]. Если, с другой стороны, Q не является положительно определённой, то задача становится NP-трудной^[7]. Фактически, даже если Q имеет единственное отрицательное собственное значение, задача NP-трудна^[8].

Пакеты для решения и скриптовые языки

Название	Описание
AIMMS^[англ.]	Система для моделирования и решения задач оптимизации и расписаний
ALGLIB^[англ.]	Библиотека программ (C++, .NET) численного анализа с двойным лицензированием (GPL/proprietary).
AMPL	Популярный язык моделирования для математической оптимизации большого размера.
APMonitor^[англ.]	Моделирование и оптимизация для задач LP (линейное программирование), QP (квадратичное программирование), NLP (нелинейное программирование), MILP (целочисленное программирование), MINLP (смешанное целочисленное нелинейное программирование) и DAE^[англ.] (дифференциально-алгебраические уравнения) в MATLAB и Python.
CGAL^[англ.]	Вычислительный геометрический пакет с открытым кодом, который включает систему решения задач квадратичного программирования.
CPLEX	Популярная система решения задач с API (C, C++, Java, .Net, Python, Matlab и R). Бесплатна для академического использования.
Система поиска решений в Excel	Система решения нелинейных задач, приспособленная для электронных таблиц, в которой вычислений функций основывается на значении ячеек. Базовая версия доступна как стандартное дополнение для Excel.
GAMS^[англ.]	Система моделирования высокого уровня для математической оптимизации
Gurobi^[англ.]	Система решения задач с параллельными алгоритмами для задач линейного программирования большого размера, задач квадратичного программирования и смешанно–целочисленных задач. Бесплатна для академического использования.
IMSL^[англ.]	Набор математических и статистических функций, которые может программист включить в своё приложение.
IPOPT^[англ.]	Пакет IPOPT (Interior Point OPTimizer, Оптимизатор внутренней точки) — это пакет программирования для нелинейных задач большого размера
Artelys Knitro^[англ.]	Коммерческий интегрированный пакет для нелинейной оптимизации
Maple	Язык программирования общего назначения для математики. Для решения квадратичных задач в Maple используется команда QPSolve Архивная копия от 12 мая 2021 на Wayback Machine.
MATLAB	Матрично-ориентированный язык программирования общего назначения для численных вычислений. Для решения задач квадратичного программирования в MATLAB требуется вдобавок к базовому продукту MATLAB дополнение «Optimization Toolbox»
Mathematica	Язык программирования общего назначения для математики, включающий символьные и численные возможности.
MOSEK^[англ.]	Система для решения задач оптимизации большого размера, включает API для нескольких языков (C++, Java, .Net, Matlab и Python)
Числовая библиотека NAG^[англ.]	Набор математических и статистических процедур, разработанных компанией Numerical Algorithms Group^[англ.] для нескольких языков программирования (C, C++, Fortran, Visual Basic, Java и C#) и пакетов (MATLAB, Excel, R, LabVIEW). Раздел оптимизации библиотеки NAG включает процедуры для задач квадратичного программирования с редкими и плотными матрицами ограничений, а также процедуры для оптимизации линейных и нелинейных функций, сумм квадратов линейных и нелинейных функций. В библиотеке NAG имеются процедуры как для локальной, так и глобальной оптимизации, а также для задач целочисленного программирования.
OptimJ^[англ.]	Свободно распространяемый, основанный на Java язык моделирования для оптимизации и поддерживающий несколько целевых систем решений. Существует плагин для Eclipse ^[9]^[10]
R	Универсальный кросс-платформенный вычислительный пакет с лицензией GPL (см. раздел quadprog Архивная копия от 19 июня 2017 на Wayback Machine этого пакета). Переведён на javascript Архивная копия от 11 апреля 2017 на Wayback Machine под лицензией MIT. Переведён на C# Архивная копия от 8 апреля 2015 на Wayback Machine под лицензией LGPL.
SAS^[англ.]/OR	Система для решения линейных, целочисленных , комбинаторных, нелинейных, недиференцируемых задач, задач на сетях и оптимизации в ограничениях. Язык алгебраического моделирования^[англ.] OPTMODEL Архивная копия от 8 сентября 2016 на Wayback Machine и ряд вертикальных решений, нацеленных на специфичные задачи, полностью интегрированы с \|SAS/.
TK Solver^[англ.]	Система математического моделирования и решения задач, основанная на декларативном языке, базирующемся на продукционных правилах. Система коммерциализирована компанией Universal Technical Systems, Inc. Архивная копия от 1 апреля 2022 на Wayback Machine.
TOMLAB^[англ.]	Поддерживает глобальную оптимизацию, решение задач целочисленного программирования, все типы метода наименьших квадратов, решение задач линейного квадратичного программирования для MATLAB. TOMLAB поддерживает системы решения Gurobi, CPLEX, SNOPT^[англ.] и KNITRO^[англ.].

См. также

Примечания

↑ Nocedal, Wright, 2006, с. 449.
↑ ¹ ² Murty, 1988, с. xlviii+629.
↑ Delbos, Gilbert, 2005, с. 45–69.
↑ Кюнци, Крелле, 1965, с. 161-179.
↑ Gould, Hribar, Nocedal, 2001, с. 1376–1395.
↑ Козлов, Тарасов, Хачиян, 1980, с. 1049–1051.
↑ Sahni, 1974, с. 262–279.
↑ Pardalos, Vavasis, 1991, с. 15–22.
↑ Zesch, Hellingrath, 2010.
↑ Burkov, Chaib-draa, 2010.

Литература

Г.П. Кюнци, В. Крелле. Нелинейное программирование. — Москва: «Советское радио», 1965.
Jorge Nocedal, Stephen J. Wright. Numerical Optimization. — 2nd. — Berlin, New York: Springer-Verlag, 2006. — С. 449. — ISBN 978-0-387-30303-1.
Katta G. Murty. Linear complementarity, linear and nonlinear programming. — Berlin: Heldermann Verlag, 1988. — Т. 3. — С. xlviii+629 pp.. — (Sigma Series in Applied Mathematics). — ISBN 3-88538-403-5.
F. Delbos, J.Ch. Gilbert. Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems // Journal of Convex Analysis. — 2005. — Т. 12. — С. 45—69.
Felix Zesch, Bernd Hellingrath. An optimization model for mixed-model assembly lines // Integrated Production-Distribution Planning. — 2010.
Andriy Burkov, Brahim Chaib-draa. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10). — Atlanta, USA: AAAI Press, 2010.
Nicholas I. M. Gould, Mary E. Hribar, Jorge Nocedal. On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization. — SIAM Journal of Scientific Computing, 2001. — Т. 23, вып. 4. — С. 1376—1395.
М. К. Козлов, С. П. Тарасов, Л. Г. Хачиян. Полиномиальная разрешимость выпуклого квадратичного программирования, // Ж. вычисл. матем. и матем. физ.. — 1980. — Т. 20,, вып. 5.
S. Sahni. Computationally related problems // SIAM Journal on Computing. — 1974. — Т. 3. — С. 262—279. — doi:10.1137/0203021.
Panos M. Pardalos, Stephen A. Vavasis. Quadratic programming with one negative eigenvalue is NP-hard // Journal of Global Optimization. — 1991. — Т. 1, вып. 1. — С. 15—22. — doi:10.1007/bf00120662.
Richard W. Cottle, Jong-Shi Pang, Richard E. Stone. The linear complementarity problem. — Boston, MA: Academic Press, Inc., 1992. — С. xxiv+762 pp.. — (Computer Science and Scientific Computing). — ISBN 0-12-192350-9.
Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H. Freeman, 1979. — ISBN 0-7167-1045-5. A6: MP2, pg.245.
Nicholas I. M. Gould, Philippe L. Toint. A Quadratic Programming Bibliography (неопр.) (PDF). RAL Numerical Analysis Group Internal Report 2000-1 (2000).

Ссылки

A page about QP Архивная копия от 7 июня 2011 на Wayback Machine
NEOS Optimization Guide: Quadratic Programming Архивная копия от 18 июня 2017 на Wayback Machine
Solve an example Quadratic Programming (QP) problem Архивная копия от 10 мая 2015 на Wayback Machine

[_267fbce467573b4b-1] Nocedal, Wright, 2006, с. 449.

[_7ff11c218b712f87-2] ¹ ² Murty, 1988, с. xlviii+629.

[_b7e5bf7987fa79ff-3] Delbos, Gilbert, 2005, с. 45–69.

[_63975c92471d492a-4] Кюнци, Крелле, 1965, с. 161-179.

[_6a211c2f668b8c4b-5] Gould, Hribar, Nocedal, 2001, с. 1376–1395.

[_9f9e4abf91d3b64c-6] Козлов, Тарасов, Хачиян, 1980, с. 1049–1051.

[_a0bd20554a878d24-7] Sahni, 1974, с. 262–279.

[_f98e7a3b76214b5f-8] Pardalos, Vavasis, 1991, с. 15–22.

[_7794eb310d5aaf47-9] Zesch, Hellingrath, 2010.

[_5538e08edae4c4c7-10] Burkov, Chaib-draa, 2010.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]