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

Один из частных случаев нелинейного программирования.

Применяют, если целевая функция имеет такой вид:

Все ограничения g_i являются линейными. В таком случае все ограничения сводятся к уравнению (*). В математическом смысле функция выпуклая.

Если есть какая-то добавочка, т.е. не привести – то получается общая задача нелинейного программирования и решать её намного сложнее.

Время не позволяет рассмотреть задачи, но отметим, что основным способом является метод Фрэнка-Вульфа.

Градиентный подход к решению задачи нелинейного программирования.

Суть метода: выбирается начальная точка x₀

Потом считается число r (следующая точка) и далее точка считается за начальную, ищется следующая.

Градиент

Двигаемся, направление градиента изменяется. Добираемся до границы и движемся по границе до точки экстремума.

1. Либо большое число мелких шагов, либо низкая точность.(главная проблема – выбор шага)

2. Сложно попасть не на локальную линию.

Существует несколько разновидностей градиентного подхода.

Один из вариантов – «метод наибыстрейшего подъема».

Вообще градиентный метод надо рассказывать 2-3 лекции.

Приращение max r выбирается таким, чтобы мы по данному направлению достигли бы наибольшего значения целевой функции.

Существует методы (градиентные):

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

• Метод проекции градиента (вычисляется градиент, потом проецируется на плоскости, выбираются направления)

• Последовательной минимизации

• Метод переменной метрики

• обобщенный метод Ньютона

Другая группа методов – метод штрафных функций и барьеров.

Метод барьеров – несколько иначе. За ограничения не выходим. Штрафную функцию добавляют внутри, при приближении к границе.

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

Вопросы к экзамену по ТПЗС:

Не нашли, что искали? Воспользуйтесь поиском: