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

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

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

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

Дано:

• вещественный n-мерный вектор Шаблон:Math,
• Шаблон:Math-мерная вещественная симметричная матрица Q,
• Шаблон:Math-мерная вещественная матрица A
• вещественный m-мерный вектор Шаблон:Math,

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

минимизирует	$\frac{1}{2}{𝐱}^{\mathrm{T}}Q𝐱+{𝐜}^{\mathrm{T}}𝐱$
при условиях	$A𝐱\le 𝐛,$

где Шаблон:Math обозначает транспонированный вектор. Обозначение Шаблон:Math означает, что любой элемент вектора Шаблон:Math не превосходит соответствующего элемента вектора Шаблон:Math.

Связанная задача программирования, Шаблон:Нп5 имеет квадратичные ограничения на переменные.

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

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

• Метод внутренней точки
• Шаблон:Нп5 Шаблон:Sfn
• Шаблон:Нп5 Шаблон:Sfn
• метод сопряжённых градиентов
• Метод проекции градиента
• Модификация симплекс-методаШаблон:SfnШаблон:Sfn

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

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

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

минимизировать	$\frac{1}{2}{𝐱}^{\mathrm{T}}Q𝐱+{𝐜}^{\mathrm{T}}𝐱$
при условиях	$B𝐱=𝐝$

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

$\left[\begin{array}{cc}Q& B^T\\ B& 0\end{array}\right]\left[\begin{array}{c}𝐱\\ \lambda \end{array}\right]=\left[\begin{array}{c}-𝐜\\ 𝐝\end{array}\right]$

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

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

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

$B𝐱=0$

Введём новый вектор $𝐲$, определённый равенством

$Z𝐲=𝐱$

где $𝐲$ имеет размерность $𝐱$ минус число ограничений. Тогда

$BZ𝐲=0$

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

$\frac{1}{2}{𝐱}^{T}Q𝐱+{𝐜}^T𝐱\Rightarrow \frac{1}{2}{𝐲}^T{Z}^{T}QZ𝐲+(Z^T𝐜{)}^T𝐲$

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

$Z^{T}QZ𝐲=-Z^T𝐜$

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

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

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

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

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

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

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

$g(\lambda )=-\frac{1}{2}{\lambda }^{T}A{Q}^{-1}{A}^T\lambda -{\lambda }^{T}b,$

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

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

Кроме теории двойственности Лагранжа, существуют другие двойственные пары задач (например, Шаблон:Нп5).

Сложность

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

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

Название	Описание
Шаблон:Нп5	Система для моделирования и решения задач оптимизации и расписаний
Шаблон:Нп5	Библиотека программ (C++, .NET) численного анализа с двойным лицензированием (GPL/proprietary).
AMPL	Популярный язык моделирования для математической оптимизации большого размера.
Шаблон:Нп5	Моделирование и оптимизация для задач LP (линейное программирование), QP (квадратичное программирование), NLP (нелинейное программирование), MILP (целочисленное программирование), MINLP (смешанное целочисленное нелинейное программирование) и Шаблон:Нп5 (дифференциально-алгебраические уравнения) в MATLAB и Python.
Шаблон:Нп5	Вычислительный геометрический пакет с открытым кодом, который включает систему решения задач квадратичного программирования.
CPLEX	Популярная система решения задач с API (C, C++, Java, .Net, Python, Matlab и R). Бесплатна для академического использования.
Система поиска решений в Excel	Система решения нелинейных задач, приспособленная для электронных таблиц, в которой вычислений функций основывается на значении ячеек. Базовая версия доступна как стандартное дополнение для Excel.
Шаблон:Нп5	Система моделирования высокого уровня для математической оптимизации
Шаблон:Нп5	Система решения задач с параллельными алгоритмами для задач линейного программирования большого размера, задач квадратичного программирования и смешанно–целочисленных задач. Бесплатна для академического использования.
Шаблон:Нп5	Набор математических и статистических функций, которые может программист включить в своё приложение.
Шаблон:Нп5	Пакет IPOPT (Interior Point OPTimizer, Оптимизатор внутренней точки) — это пакет программирования для нелинейных задач большого размера
Шаблон:Нп5	Коммерческий интегрированный пакет для нелинейной оптимизации
Maple	Язык программирования общего назначения для математики. Для решения квадратичных задач в Maple используется команда QPSolve Шаблон:Wayback.
MATLAB	Матрично-ориентированный язык программирования общего назначения для численных вычислений. Для решения задач квадратичного программирования в MATLAB требуется вдобавок к базовому продукту MATLAB дополнение «Optimization Toolbox»
Mathematica	Язык программирования общего назначения для математики, включающий символьные и численные возможности.
Шаблон:Нп5	Система для решения задач оптимизации большого размера, включает API для нескольких языков (C++, Java, .Net, Matlab и Python)
Шаблон:Нп5	Набор математических и статистических процедур, разработанных компанией Шаблон:Нп5 для нескольких языков программирования (C, C++, Fortran, Visual Basic, Java и C#) и пакетов (MATLAB, Excel, R, LabVIEW). Раздел оптимизации библиотеки NAG включает процедуры для задач квадратичного программирования с редкими и плотными матрицами ограничений, а также процедуры для оптимизации линейных и нелинейных функций, сумм квадратов линейных и нелинейных функций. В библиотеке NAG имеются процедуры как для локальной, так и глобальной оптимизации, а также для задач целочисленного программирования.
Шаблон:Нп5	Свободно распространяемый, основанный на Java язык моделирования для оптимизации и поддерживающий несколько целевых систем решений. Существует плагин для Eclipse Шаблон:SfnШаблон:Sfn
R	Универсальный кросс-платформенный вычислительный пакет с лицензией GPL (см. раздел quadprog Шаблон:Wayback этого пакета). Переведён на javascript Шаблон:Wayback под лицензией MIT. Переведён на C# Шаблон:Wayback под лицензией LGPL.
Шаблон:Нп5/OR	Система для решения линейных, целочисленных , комбинаторных, нелинейных, недиференцируемых задач, задач на сетях и оптимизации в ограничениях. Шаблон:Нп5 OPTMODEL Шаблон:Wayback и ряд вертикальных решений, нацеленных на специфичные задачи, полностью интегрированы с |SAS/.
Шаблон:Нп5	Система математического моделирования и решения задач, основанная на декларативном языке, базирующемся на продукционных правилах. Система коммерциализирована компанией Universal Technical Systems, Inc. Шаблон:Wayback.
Шаблон:Нп5	Поддерживает глобальную оптимизацию, решение задач целочисленного программирования, все типы метода наименьших квадратов, решение задач линейного квадратичного программирования для MATLAB. TOMLAB поддерживает системы решения Gurobi, CPLEX, Шаблон:Нп5 и Шаблон:Нп5.

См. также

• Метод опорных векторов
• Последовательное квадратичное программирование
• Линейное программирование

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга A6: MP2, pg.245.
• Шаблон:Cite web

Ссылки

• A page about QP Шаблон:Wayback
• NEOS Optimization Guide: Quadratic Programming Шаблон:Wayback
• Solve an example Quadratic Programming (QP) problem Шаблон:Wayback