Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




 

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

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

 

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

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

 

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

 

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

 

 

 

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

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

Градиент

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

 

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

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

 

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

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

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

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

 

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

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

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

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

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

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

 

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

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

, – функция штрафа.

 

= 0 внутри допустимой области. Вне области она возрастает, чем дальше отходим от границ. Если min , то >0. Чем дальше переехали границу, тем больше. Сильно уменьшается сложность новой задачи. В штраф вводят параметр a ( ), который тоже изменяют.

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

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

 

 


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

 




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

vikidalka.ru - 2015-2018 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных