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

Эта статья требует внимания специалиста по математике . Конкретная проблема: некоторые элементы на этой странице нуждаются в разъяснении и / или экспертной проверке. См. Подробности на странице обсуждения . WikiProject Mathematics может помочь нанять эксперта. ( Февраль 2017 г. )

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

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

Постановка проблемы [ править ]

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

• действительный n- мерный вектор c ,
• п × п - мерный вещественный симметричная матрица Q ,
• м × п - мерная вещественная матрица и
• м - мерный вещественный вектор Ь ,

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

свести к минимуму	${\ displaystyle {\ tfrac {1} {2}} \ mathbf {x} ^ {\ mathrm {T}} Q \ mathbf {x} + \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x }}$
при условии	${\ Displaystyle А \ mathbf {х} \ prevq \ mathbf {b},}$

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

Наименьшие квадраты [ править ]

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

свести к минимуму	${\ Displaystyle {\ tfrac {1} {2}} \ | \ mathbf {R} \ mathbf {x} - \ mathbf {d} \ | ^ {2}}$
при условии	${\ Displaystyle А \ mathbf {х} \ prevq \ mathbf {b},}$

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

Обобщения [ править ]

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

Способы решения [ править ]

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

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

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

Ограничения равенства [ править ]

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

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

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

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

${\displaystyle {\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 есть), что потенциально очень затрудняет поиск хорошего численного подхода, и существует множество подходов, из которых можно выбирать в зависимости от проблема. ^[5]

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

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

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

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

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

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

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

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

решение которого дается формулой:

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

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

Лагранжева двойственность [ править ]

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

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

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

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

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

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

и поэтому лагранжиан, двойственный к КП, есть

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

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

Сложность [ править ]

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

Целочисленные ограничения [ править ]

В некоторых ситуациях один или несколько элементов вектора должны принимать целочисленные значения. Это приводит к формулировке задачи смешанно-целочисленного квадратичного программирования (MIQP). ^[10] Приложения MIQP включают водные ресурсы ^[11] и построение индексных фондов . ^[12]${\displaystyle x\in \mathbb {R} ^{n}}$

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

• Страница о QP
• Руководство по оптимизации NEOS: квадратичное программирование
• Квадратичное программирование