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

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

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

Дано:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle B\mathbf {x} =0}$

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

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

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

${\displaystyle BZ\mathbf {y} =0}$

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

${\displaystyle {\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} }$

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

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

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

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

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

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

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

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

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

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

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

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

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

Сложность

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

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

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

См. также

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

Примечания

Литература

Ссылки

• от 7 июня 2011 на Wayback Machine
• от 18 июня 2017 на Wayback Machine
• от 10 мая 2015 на Wayback Machine