Лучшие вопросы
Таймлайн
Чат
Перспективы
Квадратичное программирование
Из Википедии, свободной энциклопедии
Remove ads
Квадратичное программирование (англ. quadratic programming, QP) — это процесс решения задачи оптимизации специального типа, а именно — задачи оптимизации (минимизации или максимизации) квадратичной функции нескольких переменных при линейных ограничениях на эти переменные. Квадратичное программирование является частным случаем нелинейного программирования.
Формулировка задачи
Суммиров вкратце
Перспектива
Задача квадратичного программирования с n переменными и m ограничениями можно сформулировать следующим образом[1].
Дано:
- вещественный n-мерный вектор c,
- n × n-мерная вещественная симметричная матрица Q,
- m × n-мерная вещественная матрица A
- вещественный m-мерный вектор b,
Целью задачи квадратичного программирования является поиск n-мерного вектора x, который
минимизирует | |
при условиях |
где xT обозначает транспонированный вектор. Обозначение Ax ≤ b означает, что любой элемент вектора Ax не превосходит соответствующего элемента вектора b.
Связанная задача программирования, квадратичная задача с квадратичными ограничениями[англ.] имеет квадратичные ограничения на переменные.
Remove ads
Методы решения
Суммиров вкратце
Перспектива
Для общих значений используются различные методы, среди них
- Метод внутренней точки
- Метод активного набора[англ.] [2]
- Метод обобщённого лагранжиана[англ.] [3]
- метод сопряжённых градиентов
- Метод проекции градиента
- Модификация симплекс-метода[2][4]
В случае, когда Q является положительно определённой, задача является частным случаем более общей задачи выпуклой оптимизации.
Ограничения – равенства
Задача квадратичного программирования несколько проще, если Q является положительно определённой и все ограничения являются равенствами (нет неравенств), поскольку в этом случае можно свести задачу к решению системы линейных уравнений. Если использовать множители Лагранжа и искать экстремум лагранжиана, можно легко показать, что решение задачи
минимизировать | |
при условиях |
определяется системой линейных уравнений
где — множество множителей Лагранжа, которые появляются вместе с решением .
Самый лёгкий способ решить эту систему — решить её прямыми методами (например, с помощью LU-разложения, очень удобного для небольших задач). Для больших задач возникают некоторые необычные трудности, наиболее заметные, когда задача не положительно определена (даже если положительно определена), что делает потенциально очень трудно найти хороший математический подход и существует много подходов, зависящих от задачи[источник не указан 3049 дней].
Если число ограничений не равно числу переменных, можно попробовать относительно простую атаку, заменив переменные таким образом, что ограничения будут выполняться безусловно. Например, допустим, что (переход к ненулевым значениям достаточно прост). Рассмотрим ограничения
Введём новый вектор , определённый равенством
где имеет размерность минус число ограничений. Тогда
и если матрица выбрана так, что , равенства в ограничениях будут выполняться всегда. Поиск матрицы подразумевает нахождение ядра матрицы , что более или менее просто, в зависимости от структуры матрицы . Подставляя новый вектор в исходные условия, получаем квадратичную задачу без ограничений:
и решение можно будет найти, решив уравнение
При некоторых ограничениях на сокращённая матрица будет положительно определена. Можно написать вариант метода сопряжённых градиентов, при котором нет необходимости явного вычисления матрицы [5].
Remove ads
Лагранжева двойственность
Суммиров вкратце
Перспектива
Двойственная задача Лагранжа для квадратичного программирования является также задачей квадратичного программирования. Чтобы это понять, остановимся на случае с положительно определённой матрицей Q. Выпишем множители Лагранжа функции
Если определим (лагранжеву) двойственную функцию как , мы ищем нижнюю границу , используя и положительную определённость мaтрицы Q:
Следовательно, двойственна функция равна
и двойственной задачей Лагранжа для исходной задачи будет
минимизировать | |
при условиях | . |
Кроме теории двойственности Лагранжа, существуют другие двойственные пары задач (например, двойственность Вулфа[англ.]).
Remove ads
Сложность
Для положительно определённой матрицы Q метод эллипсоидов решает задачу за полиномиальное время[6]. Если, с другой стороны, Q не является положительно определённой, то задача становится NP-трудной[7]. Фактически, даже если Q имеет единственное отрицательное собственное значение, задача NP-трудна[8].
Пакеты для решения и скриптовые языки
Remove ads
См. также
Примечания
Литература
Ссылки
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads