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

Привет, Вы узнаете о том , что такое квадратичное программирование , Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое квадратичное программирование , настоятельно рекомендую прочитать все из категории Математическое программирование.

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

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

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

Дано:

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

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

минимизирует
при условиях

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

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

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

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

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

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

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

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

минимизировать
при условиях

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

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

Самый легкий способ решить эту систему — решить ее прямыми методами (например, с помощью LU-разложения, очень удобного для небольших задач). Об этом говорит сайт https://intellect.icu . Для больших задач возникают некоторые необычные трудности, наиболее заметные, когда задача не положительно определена (даже если положительно определена), что делает потенциально очень трудно найти хороший математический подход и существует много подходов, зависящих от задачи .

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

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

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

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

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

При некоторых ограничениях на сокращенная матрица будет положительно определена. Можно написать вариант метода сопряженных градиентов, при котором нет необходимости явного вычисления матрицы .

Лагранжева двойственност Двойственная задача

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

Если определим (лагранжеву) двойственную функцию как , мы ищем нижнюю границу , используя и положительную определенность мaтрицы Q:

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

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

минимизировать
при условиях	.

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

Сложность

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

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

Применение

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

Вау!! 😲 Ты еще не читал? Это зря!

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

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

Из статьи мы узнали кратко, но содержательно про квадратичное программирование