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

Автор: Jack Heider (ChE 345 Spring 2015)
Стюард: Dajun Yue, Fengqi You

Оптимизация квадратичной функции.12

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

последовательном квадратичном программировании-методе решения более сложных задач нелинейного программирования.3,4 Эта проблема была впервые исследована в начале 1950-х годов. В первую очередь Вулфом и Фрэнком из Принстонского университета, разработавшими ее теоретические основы, и Марковицем, применившим ее к оптимизации портфеля. Подполе финансов.

Общая формулировка квадратичного программирования содержит квадратичную целевую функцию и линейные ограничения равенства и неравенства:2,5,6


s.t. Ax=a
Bx\le b
x\ge0

Целевая функция устроена так. Что вектор qсодержит все (однодифференцированные) линейные члены и

Qсодержит все (двудифференцированные) квадратичные члены. Проще говоря, Qэто матрица Гессиана целевой функции и qее градиент. По соглашению. Любые константы. Содержащиеся в целевой функции. Исключаются из общей формулировки.6 Половина перед квадратичным членом включается для удаления коэффициента (2). Который является результатом взятия производной полинома второго порядка.

Что касается ограничений. Матричное уравнение Ax=aсодержит все ограничения линейного равенства и Bx \le bявляется ограничениями линейного неравенства.

Когда существуют только ограничения неравенства (

Bx\le b), лагранжеан равен:6

Глобальные решения

Если целевая функция выпукла. То любой найденный локальный минимум также является единственным глобальным минимумом. Чтобы проанализировать выпуклость функции. Можно вычислить ее матрицу Гессиана и проверить. Что все собственные значения положительны, или. Что эквивалентно. Можно проверить. Что матрица Q положительно определена.6 Это достаточное условие. Означающее. Что оно не обязательно должно быть истинным для того. Чтобы локальный минимум был уникальным глобальным минимумом. Но гарантирует. Что это свойство сохраняется. Если оно истинно.

Условия ККТ

Решения могут быть проверены на оптимальность с использованием условий Каруша-Куна-Такера точно так же. Как это делается для других нелинейных задач:5

Условие 1: сумма градиентов равна нулю:

Условие 2: все ограничения выполнены:
Ax^*-a=0
Bx^*-b\le0

Условие 3: дополнительные условия:

Стратегии решения

Поскольку задачи квадратичного программирования являются простой формой нелинейной задачи. Они могут быть решены таким же образом. Как и другие задачи нелинейного программирования. Задача неограниченного квадратичного программирования наиболее проста для решения: просто установите производную (градиент) целевой функции равной нулю и решите.7 Более практичные (ограниченные) формулировки труднее решить. Типичным методом решения. Когда целевая функция строго выпукла и существуют только ограничения равенства. Является метод сопряженных градиентов. Если существуют ограничения неравенства (Bx\le b), то методы внутренней точки и активного набора являются предпочтительными методами решения. При наличии диапазона допустимых значений икс(в том виде x^L\le x\le x^U, в каком это имеет место для приложений обработки изображений и сигналов. Чаще всего используются методы доверительной области.4 Для всех выпуклых случаев решатель NLP в гаммах утилит оптимизации. Таких как KNITRO. MINOS или CONOPT. Может найти решения для задач квадратичного программирования.

Сюжет неограниченной целевой функции. Рисунок сгенерирован с помощью Wolfram Mathematica.

Этот пример демонстрирует. Как определить точку KKT конкретной задачи QP:



Перепишите ограничения.


Постройте градиенты.

Предполагая. Что все ограничения выполнены. Установите градиент равным нулю. Чтобы попытаться найти оптимум.

,

Сделайте ограничения g_1и g_3те , которые нарушаются, активными. Установите оба значения равными нулю.

Решите полученную систему уравнений.




Формулировка системы как одной матрицы и сокращения строк является одним из самых простых способов решения. Это дает:

Отбросьте ограничениеg_3, потому что отрицательно и разрешите систему. Это дает:

Который дает значение целевой функции f=11,25

Проверить линейную зависимость градиента:

Проверьте уникальность решения:

Поскольку оба собственных значения положительны. Матрица Гессиана является положительным детерминантом. И этот локальный минимум является глобальным минимумом целевой функции с учетом этих ограничений.

Некоторые из многочисленных приложений квадратичного программирования обсуждаются более подробно и сопровождаются общими моделями ниже. А также представлен список других областей. В которых QP имеет важное значение.

  • Квадратичная задача рюкзака (QKP)

В стандартной задаче о рюкзаке существует ряд предметов с различными весами и значениями. И элементы выбираются на основе того. Какая комбинация дает наибольшее общее значение. Не превышая общего предела веса рюкзака.

В задаче квадратичного ранца целевая функция квадратична или. Более конкретно, билинейна. А ограничения те же. Что и в типичной задаче ранца.8 QKP используются при проектировании почтовых серверов и для оптимизации расположения Кроме того. Задача может моделировать ситуации. В которых ограниченному числу людей поручается выполнение определенных задач. Требующих от них взаимодействия.9 Одна формулировка представлена ниже:8

Ax \le a

Квадратичная задача рюкзака. Хотя и выглядит очень простой. Является NP-трудной и. Следовательно. Трудной для решения. Чтобы облегчить получение решений. Эти проблемы часто линеаризуются.8

  • Модельное прогнозирующее управление

Квадратичное программирование также имеет важное применение в химической инженерии. Model predictive control (MPC) — это группа алгоритмов. Которые помогают управлять производством на химических заводах. Диктуя производство в каждой партии. В то время как часто формулируются как линейные программы. Поскольку полученные модели являются более стабильными. Надежными и простыми в решении. Модели MPC иногда изготавливаются с помощью квадратичного программирования.11 В качестве примера его полезности Ди Руско использовал квадратичное программирование в алгоритме MPC для термомеханического процесса пульпирования. Являющегося методом изготовления бумаги.11

  • Наименьшие квадраты

Регрессия наименьших квадратов является одним из наиболее распространенных типов регрессии и работает путем минимизации суммы квадратов разности между точками данных и предложенной подгонкой. Квадратичная оптимизация является одним из методов. Который может быть использован для выполнения регрессии наименьших квадратов и является более гибким. Чем большинство линейных методов. Одна из формулировок регрессионной модели квадратичного программирования выглядит следующим образом:

e'Ie
e = Y-X \beta

В этой модели \бета-версияи eнаходятся неизвестные параметры регрессии, Яи находится матрица идентичности, Икси Yсодержатся данные о независимых и зависимых переменных соответственно.

  • Другие приложения

Квадратичное программирование используется в широком спектре приложений. Не затронутых в приведенном выше примере. Другие основные области. В которых используются QP. Включают обработку сигналов и изображений12 и подполе оптимизации. Называемое оптимизацией с частными производными.3 QP также широко используются в финансах. Поскольку дисперсия. Используемая для измерения риска. Представляет собой функцию. Содержащую квадраты.13,14,15 Более конкретно. Марковиц получил Нобелевскую премию по экономике 1990 года за свою широко используемую модель. Которая использует квадратичное программирование для оптимизации величины риска. Принимаемого на основе дисперсий.

Кроме того, последовательное квадратичное программирование, алгоритм решения более сложных НЛП. Использующий подзадачи QP. Является одним из наиболее важных приложений.

Квадратичное программирование. Задача оптимизации квадратичной функции. Широко используется с момента своего развития в 1950-х годах. Поскольку это простой тип нелинейного программирования. Который может точно моделировать многие реальные системы. Особенно те. Которые зависят от двух переменных. Задачи, сформулированные таким образом. Просты в оптимизации. Когда целевая функция выпукла. QP находит применение в финансах. Различных типах компьютерных систем. Статистике. Химическом производстве и в алгоритмах для решения более сложных задач НЛП.

1. Фрэнк, Маргарита и Филип Вулф. — Алгоритм квадратичного программирования.Naval Research Logistics Quarterly 3 (1956): 95-110. Web. 4 июня 2015.
2. Floudas, Christodoulos A.. And V. Visweswaran. -Квадратичная оптимизация.Невыпуклая оптимизация и ее приложения, 2 (1995): 217-69. Web. 23 мая 2015 г.
3. Маккарл, Брюс А., Московиц. Герберт и Харли Фуртан. Международный журнал управленческих наук, 5 (1977): 43-55.
4. Гелету, Абеле. -Задачи квадратичного программирования.Технологический университет Ильменау. Web. 23 мая 2015 года.
5. Брэдли, Хэкс и Мэгнанти. Прикладное Математическое программирование. Бостон: Аддисон-Уэсли, 1997. 421-40. Web. 23 мая 2015.
6. Дженсен, Пол А. и Джонатан Ф. Бард. Модели и методы исследования операций. Техасский университет в Остине. Web. 23 мая 2015.
7. Биннер, Дэвид. Различные математические утилиты. AKiTi. Web. 23 мая 2015.
8. Писингер, Дэвид. Дискретная прикладная математика, 155 (2007): 623 – 648. 23 мая 2015.
9. Оптимизация сложной системы. Проект Optiscom. 2012. Web. 6 июня 2015.
10. Gallo, G., P. L. Hammer и B. Simeone. Математическое программирование 12 (1980): 132-149. Web. 24 мая 2015.
11. Di Ruscio, David. Университетский колледж Телемарк. Mar. 2001. Web. 24 May 2015.
12. Ma, W. K. Китайский университет Гонконга. Web. 24 мая 2015.
13. Tütüncü, Reha H. Токийский технологический институт. Весна 2003. Web. 23 Мая 2015.
14. Ван Слайк Р. Инженерная политехническая школа Нью-Йоркского университета. 16 Ноября 2007 г. Web. 24 мая 2015 г.
15. SAS/OR(R) 9.2 Руководство пользователя: Математическое программирование. Институт САС. Web. 23 мая 2015 года.