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

'''Квадратичное программирование''' ({{Lang-en|quadratic programming}}, ''QP'') — это процесс решения задачи [[Оптимизация (математика)|оптимизации]] специального типа, а именно — задачи оптимизации (минимизации или максимизации)  [[Квадратичная функция|квадратичной функции]] нескольких переменных при линейных [[Программирование в ограничениях|ограничениях]] на эти переменные. Квадратичное программирование является частным случаем [[Нелинейное программирование|нелинейного программирования]].

==Формулировка задачи==
Задача квадратичного программирования с ''n'' переменными и ''m'' ограничениями можно сформулировать следующим образом{{sfn|Nocedal, Wright|2006|с=449}}.

Дано:
* вещественный ''n''-мерный вектор {{math|'''c'''}},
* {{math|''n'' × ''n''}}-мерная вещественная [[симметричная матрица]] ''Q'',
* {{math|''m'' × ''n''}}-мерная вещественная матрица ''A'' 
* вещественный ''m''-мерный вектор {{math|'''b'''}},
Целью задачи квадратичного программирования является поиск ''n''-мерного вектора {{math|'''x'''}}, который

{| cellspacing="10"
|-
| минимизирует
| <math>\tfrac{1}{2} \mathbf{x}^\mathrm{T} Q\mathbf{x} + \mathbf{c}^\mathrm{T} \mathbf{x}</math>
|-
| при условиях
| <math> A \mathbf{x} \leq \mathbf{b},</math>
|}
где {{math|'''x'''<sup>T</sup>}} обозначает [[Транспонированная матрица|транспонированный]] вектор. Обозначение {{math|''A'''''x''' ≤ '''b'''}} означает, что любой элемент вектора {{math|''A'''''x'''}} не превосходит соответствующего элемента вектора {{math|'''b'''}}.

Связанная задача программирования, {{нп5|квадратичная задача с квадратичными ограничениями|||quadratically constrained quadratic program}} имеет квадратичные ограничения на переменные.

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

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

:*[[Метод внутренней точки]]
:*{{нп5|Метод активного набора|||active set}} {{sfn|Murty|1988|с=xlviii+629}}
:*{{нп5|Метод обобщённого лагранжиана|||Augmented Lagrangian method}} {{sfn|Delbos, Gilbert|2005|с=45–69}}
:*[[Метод сопряжённых градиентов (для решения СЛАУ)|метод сопряжённых градиентов]]
:*Метод проекции градиента
:*Модификация [[Симплекс-метод|симплекс-метода]]{{sfn|Murty|1988|с=xlviii+629}}{{sfn|Кюнци, Крелле|1965|с=161-179}}

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

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

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

{| cellspacing="10"
|-
| минимизировать
| <math>\tfrac{1}{2} \mathbf{x}^\mathrm{T} Q\mathbf{x} + \mathbf{c}^\mathrm{T} \mathbf{x}</math>
|-
| при условиях
| <math>B\mathbf{x} =\mathbf{d}</math>
|}

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

:<math>
\begin{bmatrix}
   Q & B^T \\
   B & 0
\end{bmatrix} 
\begin{bmatrix}
   \mathbf x \\
   \lambda
\end{bmatrix}
= 
\begin{bmatrix}
   -\mathbf c \\
   \mathbf d
\end{bmatrix}
</math>

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

Самый лёгкий способ решить эту систему — решить её прямыми методами (например, с помощью [[LU-разложение|LU-разложения]], очень удобного для небольших задач). Для больших задач возникают некоторые необычные трудности, наиболее заметные, когда задача не положительно определена (даже если <math>Q</math> положительно определена), что делает потенциально очень трудно найти хороший математический подход и существует много подходов, зависящих от задачи{{нет АИ|4|03|2017}}.

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

:<math>B\mathbf{x} = 0</math>

Введём новый вектор <math>\mathbf y</math>, определённый равенством

:<math>Z \mathbf{y} = \mathbf x</math>

где <math>\mathbf y</math> имеет размерность <math>\mathbf x</math> минус число ограничений. Тогда

:<math>B Z \mathbf{y} = 0</math>

и если матрица <math>Z</math> выбрана так, что <math>B Z = 0</math>, равенства в ограничениях будут выполняться всегда. Поиск матрицы <math>Z</math> подразумевает нахождение [[Ядро (линейная алгебра)|ядра]] матрицы <math>B</math>, что более или менее просто, в зависимости от структуры матрицы <math>B</math>. Подставляя новый вектор в исходные условия, получаем квадратичную задачу без ограничений:

:<math>
\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 Q Z \mathbf{y} + (Z^T \mathbf{c})^T \mathbf{y}
</math>

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

:<math>
Z^T Q Z \mathbf{y} = -Z^T \mathbf{c}
</math>

При некоторых ограничениях на <math>Q</math> сокращённая матрица <math>Z^T Q Z</math> будет положительно определена. Можно написать вариант [[Метод сопряжённых градиентов (для решения СЛАУ)|метода сопряжённых градиентов]], при котором нет необходимости явного вычисления матрицы <math>Z</math>{{sfn|Gould, Hribar, Nocedal|2001|с=1376–1395}}.

==Лагранжева двойственность ==
{{See also|Двойственная задача}}

[[Двойственность_(оптимизация)#Двойственная_задача|Двойственная]] задача Лагранжа для квадратичного программирования является также задачей квадратичного программирования. Чтобы это понять, остановимся на случае <math>c=0</math> с положительно определённой матрицей Q. Выпишем [[Метод множителей Лагранжа|множители Лагранжа]] функции 
:<math>L(x,\lambda) = \tfrac{1}{2} x^{T}Qx + \lambda^{T}(Ax-b). </math>
Если определим (лагранжеву) двойственную функцию <math>g(\lambda)</math> как <math>g(\lambda) = \inf_{x} L(x,\lambda) </math>, мы ищем [[Точная верхняя и нижняя границы|нижнюю границу]]  <math>L</math>, используя <math>\nabla_{x} L(x,\lambda)=0</math> и положительную определённость мaтрицы Q:

:<big><math> x^* =  -Q^{-1}A^{T}\lambda.  </math></big>

Следовательно, двойственна функция равна 
:<math>g(\lambda) = -\tfrac{1}{2}\lambda^{T}AQ^{-1}A^{T}\lambda - \lambda^{T}b,</math>
и двойственной задачей Лагранжа для исходной задачи будет

{| cellspacing="10"
|-
| минимизировать
| <math> -\tfrac{1}{2}\lambda^{T}AQ^{-1}A^{T}\lambda - \lambda^{T}b</math>
|-
| при условиях
| <math>\lambda \geqslant 0</math>.
|}

Кроме теории двойственности Лагранжа, существуют другие двойственные пары задач (например, {{нп5|двойственность Вулфа|||Wolfe duality}}).

==Сложность==

Для [[Положительно определённая матрица|положительно определённой матрицы]] ''Q'' [[метод эллипсоидов]] решает задачу за [[Временная сложность алгоритма|полиномиальное время]]{{sfn|Козлов, Тарасов, Хачиян|1980|с=1049–1051}}.  Если, с другой стороны, ''Q'' не является положительно определённой, то задача становится [[NP-трудность|NP-трудной]]{{sfn|Sahni|1974|с=262–279}}.  Фактически, даже если ''Q'' имеет единственное отрицательное [[Собственный вектор|собственное значение]], задача [[NP-трудность|NP-трудна]]{{sfn|Pardalos, Vavasis|1991|с=15–22}}.

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

{| class="wikitable"
|-
!Название
!Описание
|-
|{{нп5|AIMMS}}|| Система для моделирования и решения задач оптимизации и расписаний
|-
| {{нп5|ALGLIB}}|| Библиотека программ (C++, .NET) численного анализа с двойным лицензированием  (GPL/proprietary).
|-
|[[AMPL (язык программирования)|AMPL]]|| Популярный язык моделирования для математической оптимизации большого размера.
|-
|{{нп5|APMonitor (язык моделирования)|APMonitor||APMonitor}}|| Моделирование и оптимизация для задач [[Линейное программирование|LP]] (линейное программирование), QP (квадратичное программирование), [[Нелинейное программирование|NLP]] (нелинейное программирование), [[Целочисленное программирование|MILP]] (целочисленное программирование), MINLP (смешанное целочисленное нелинейное программирование) и {{нп5|Дифференциально-алгебраическое уравнение|DAE||Differential algebraic equation}} (дифференциально-алгебраические уравнения) в MATLAB и Python.
|-
|{{нп5|CGAL}}|| Вычислительный геометрический пакет с открытым кодом, который включает систему решения задач квадратичного программирования. 
|-
|[[CPLEX]]|| Популярная система решения задач с API (C, C++, Java, .Net, Python, Matlab и R).  Бесплатна для академического использования.
|-
|Система поиска решений в [[Microsoft Excel|Excel]]|| Система решения нелинейных задач, приспособленная для электронных таблиц, в которой вычислений функций основывается на значении ячеек. Базовая версия доступна как стандартное дополнение для Excel.
|-
|{{нп5|Система общего алгебраического моделирования|GAMS||General Algebraic Modeling System}} || Система моделирования высокого уровня для математической оптимизации
|-
|{{нп5|Gurobi}}|| Система решения задач с параллельными алгоритмами для задач линейного программирования большого размера, задач квадратичного программирования и смешанно–целочисленных задач. Бесплатна для академического использования.
|-
|{{нп5|Численная библиотека IMSL|IMSL||IMSL Numerical Libraries}}|| Набор математических и статистических функций, которые может программист включить в своё приложение.
|-
|{{нп5|IPOPT}}|| Пакет IPOPT (Interior Point OPTimizer, Оптимизатор внутренней точки) — это пакет программирования для нелинейных задач большого размера
|- 
|{{нп5|Artelys Knitro}} || Коммерческий интегрированный пакет для нелинейной оптимизации
|-
|[[Maple]]|| Язык программирования общего назначения для математики. Для решения квадратичных задач в Maple используется команда [http://www.maplesoft.com/support/help/Maple/view.aspx?path=Optimization/QPSolve QPSolve] {{Wayback|url=http://www.maplesoft.com/support/help/Maple/view.aspx?path=Optimization%2FQPSolve |date=20210512200813 }}.
|-
|[[MATLAB]]|| Матрично-ориентированный язык программирования общего назначения  для численных вычислений.  Для решения задач квадратичного программирования в MATLAB требуется вдобавок к базовому продукту MATLAB дополнение «Optimization Toolbox»
|-
|[[Mathematica]]|| Язык программирования общего назначения для математики, включающий символьные и численные возможности.
|-
|{{нп5|MOSEK}}|| Система для решения задач оптимизации большого размера, включает API для нескольких языков (C++, Java, .Net, Matlab и Python)
|-
|{{нп5|Числовая библиотека NAG|||NAG Numerical Library}}|| Набор математических и статистических процедур, разработанных компанией {{нп5|Numerical Algorithms Group}} для нескольких языков программирования (C, C++, Fortran, Visual Basic, Java и C#) и пакетов (MATLAB, Excel, R, LabVIEW). Раздел оптимизации библиотеки NAG  включает процедуры для задач квадратичного программирования с редкими и плотными матрицами ограничений, а также процедуры для оптимизации линейных и нелинейных функций, сумм квадратов линейных и нелинейных функций.  В библиотеке NAG имеются процедуры как для локальной, так и глобальной оптимизации, а также для задач целочисленного программирования.
|-
|{{нп5|OptimJ}}|| Свободно распространяемый, основанный на Java язык моделирования для оптимизации и поддерживающий несколько целевых систем решений. Существует плагин для Eclipse {{sfn|Zesch, Hellingrath|2010}}{{sfn|Burkov, Chaib-draa|2010}}
|-
|[[R (язык программирования)|R]] ||Универсальный кросс-платформенный  вычислительный пакет с лицензией [[GNU General Public License|GPL]] (см. раздел [https://cran.r-project.org/web/packages/quadprog/index.html quadprog] {{Wayback|url=https://cran.r-project.org/web/packages/quadprog/index.html |date=20170619235616 }} этого пакета). Переведён [https://github.com/albertosantini/node-quadprog на javascript] {{Wayback|url=https://github.com/albertosantini/node-quadprog |date=20170411032410 }} под лицензией [[Лицензия MIT|MIT]]. Переведён [http://accord-framework.net/ на C#] {{Wayback|url=http://accord-framework.net/ |date=20150408124727 }} под лицензией [[GNU Lesser General Public License|LGPL]].
|-
|{{нп5|Система SAS|SAS||SAS System}}/OR|| Система для решения линейных, целочисленных , комбинаторных, нелинейных, недиференцируемых задач, задач на сетях и оптимизации в ограничениях. {{нп5|Язык алгебраического моделирования|||Algebraic modeling language}} [http://support.sas.com/documentation/cdl/en/ormpug/63975/HTML/default/ormpug_optmodel_sect005.htm OPTMODEL] {{Wayback|url=http://support.sas.com/documentation/cdl/en/ormpug/63975/HTML/default/ormpug_optmodel_sect005.htm |date=20160908232042 }} и ряд вертикальных решений, нацеленных на специфичные задачи, полностью интегрированы с |SAS/.
|-
|{{нп5|TK Solver}}|| Система математического моделирования  и решения задач, основанная на декларативном языке, базирующемся на продукционных правилах. Система коммерциализирована компанией [http://www.uts.com  Universal Technical Systems, Inc.] {{Wayback|url=http://www.uts.com/ |date=20220401132546 }}.
|-
|{{нп5|TOMLAB}}||Поддерживает глобальную оптимизацию, решение задач целочисленного программирования, все типы метода наименьших квадратов, решение задач линейного квадратичного программирования для [[MATLAB]]. TOMLAB поддерживает системы решения Gurobi, [[CPLEX]], {{нп5|SNOPT}} и {{нп5|Artelys Knitro|KNITRO}}.
|}

==См. также==
*[[Метод опорных векторов]]
*[[Последовательное квадратичное программирование]]
*[[Линейное программирование]]

==Примечания==
{{примечания|2}}
==Литература==
{{refbegin|colwidth=30em}}
*{{книга
|автор=Г.П. Кюнци, В. Крелле
|ref=Кюнци, Крелле
|заглавие=Нелинейное программирование
|издательство=«Советское радио»
|место=Москва
|год=1965
}}
*{{книга
|автор=Jorge Nocedal, Stephen J. Wright
|ref=Nocedal, Wright
|заглавие=Numerical Optimization
|ссылка=https://archive.org/details/numericaloptimiz00noce_513
|издательство=[[Springer-Verlag]]
|место=Berlin, New York
|издание=2nd
|isbn=978-0-387-30303-1
|год=2006
|страницы=[https://archive.org/details/numericaloptimiz00noce_513/page/n467 449]
}}
*{{книга
 |автор               = Katta G. Murty
 |ref                      = Murty
 |заглавие         = Linear complementarity, linear and nonlinear programming
 |серия               = Sigma Series in Applied Mathematics
 |том                   = 3
 |издательство = Heldermann Verlag
 |место               = Berlin
 |год                   = 1988
 |страницы         = xlviii+629 pp.
 |isbn                     = 3-88538-403-5
 |url                      = http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/
 |mr                       = 949214
 |ссылка= https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/
 }}
*{{статья
|автор=F. Delbos, J.Ch. Gilbert
|ref=Delbos, Gilbert
|год=2005
|заглавие=Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems
|издание=Journal of Convex Analysis
|том=12
|страницы=45—69
|url=http://www.heldermann-verlag.de/jca/jca12/jca1203_b.pdf
}}
*{{статья
|url=http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf
|автор=Felix Zesch, Bernd Hellingrath
|ref=Zesch, Hellingrath
|заглавие=An optimization model for mixed-model assembly lines
|издание=Integrated Production-Distribution Planning | publisher = University of Münster
|год=2010
}}
*{{книга
|url=http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076
|заглавие=Proceedings of  the  Twenty-Fourth  AAAI  Conference  on  Artificial Intelligence (AAAI-10)
|вклад=An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games 
|автор=Andriy Burkov, Brahim Chaib-draa
|ref=Burkov, Chaib-draa
|год=2010
|издательство=AAAI Press
|место=Atlanta, USA
}}
*{{статья
|автор=Nicholas I. M. Gould, Mary E. Hribar, Jorge Nocedal
|ref=Gould, Hribar, Nocedal
|год=2001
|заглавие=On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization
|издательство=SIAM Journal of Scientific Computing
|страницы=1376—1395
|том=23
|выпуск= 4
|citeseerx=10.1.1.129.7555
}}
* {{статья
|автор=М. К. Козлов, С. П. Тарасов, Л. Г. Хачиян
|ref=Козлов, Тарасов, Хачиян
|заглавие=Полиномиальная разрешимость выпуклого квадратичного программирования,
|издание=Ж. вычисл. матем. и матем. физ.
|год=1980
|том=20,
|выпуск=5
}}
*{{статья
|автор= S. Sahni
|ref=Sahni
|заглавие=Computationally related problems
|издание=SIAM Journal on Computing
|том=3
|страницы=262—279
|год=1974
 | doi=10.1137/0203021
}}
*{{статья
|заглавие=Quadratic programming with one negative eigenvalue is NP-hard
|автор=Panos M. Pardalos, Stephen A. Vavasis
|ref= Pardalos, Vavasis
|издание=Journal of Global Optimization
|том=1
|выпуск=1
|год=1991
|страницы=15—22
|doi=10.1007/bf00120662
}}
* {{книга
|автор=Richard W. Cottle, Jong-Shi Pang, Richard E. Stone
|ref= Cottle, Pang, Stone
|заглавие=The linear complementarity problem
|серия=Computer Science and Scientific Computing
|издательство=Academic Press, Inc.
|место=Boston, MA
|год=1992
|страницы=xxiv+762 pp.
|isbn=0-12-192350-9
|mr = 1150683
}}
* {{книга
|автор=Michael R. Garey, David S. Johnson
|ref=Garey, Johnson
|год=1979
|заглавие=Computers and Intractability: A Guide to the Theory of NP-Completeness
|ссылка=https://archive.org/details/computersintract0000gare
|издательство=W.H. Freeman
|isbn=0-7167-1045-5
}} A6: MP2, pg.245.
* {{cite web
|author=Nicholas I. M. Gould, Philippe L. Toint
|title=A Quadratic Programming Bibliography
|publisher=RAL Numerical Analysis Group Internal Report 2000-1
|url=ftp://ftp.numerical.rl.ac.uk/pub/qpbook/qp.pdf
|format=PDF
|date=2000
}}
{{refend}}
 
==Ссылки==
*[http://www.numerical.rl.ac.uk/qp/qp.html A page about QP] {{Wayback|url=http://www.numerical.rl.ac.uk/qp/qp.html |date=20110607212051 }}
*[http://neos-guide.org/content/quadratic-programming NEOS Optimization Guide: Quadratic Programming] {{Wayback|url=http://neos-guide.org/content/quadratic-programming |date=20170618153553 }}
*[http://apmonitor.com/online/view_pass.php?f=qp2.apm Solve an example Quadratic Programming (QP) problem] {{Wayback|url=http://apmonitor.com/online/view_pass.php?f=qp2.apm |date=20150510224252 }} 

[[Категория:Теория оптимизации]]
{{rq|checktranslate|style}}