Условные экстремумы. Условия Куна —Таккера. Метод Лагранжа

Ocобенности задачи на условный оптимум: 1. главная проблема - единственность решения; 2. наряду с глобальным может существовать множество локальных экстремумов.

Самая известная задача на условный экстремум – задача линейного программирования.

Более общая задача на условный экстремум – задача нелинейного программирования.

Условие Куна-Таккера - обобщение условия максимума функции многих переменных на задачу с ограничениями типа неотрицательности факторов. Условия Куна –Таккера (первого порядка) имеют вид (x - вектор):

Метод неопределенных множителей Лагранжа применяется для решения задач на условный оптимум. Если ограничения линейны и соответствующий якобиан задачи не вырожден, можно m переменных выразить через остальные n-m; эти значения подставляются в целевую функцию, и тогда задача сводится к задаче на безусловный оптимум относительно n-m переменных.

Лагранж предложил другой метод решения задачи на условный оптимум: Вводится функция (функция Лагранжа или лагранжиан): и ищутся ее критические точки.

Главная особенность метода Лагранжа заключается в том, что он сводит задачу условного экстремума к задаче безусловного экстремума.

28. Методы поиска экстремумов. Метод Гаусса – Зейделя. Метод крутого восхождения Бокса-Уилсона.

Методы поиска экстремумов делятся на три большие класса: безградиентные; градиентные; методы, использующие производные высших порядков.К безградиентным методам относятся: Симплексный метод, Метод Хука-Дживса, Метод Нелдера-Мида.

К градиентным методам относится: Метод Гаусса-Зайделя, Метод наискорейшего спуска

и др.

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

Метод крутого восхождения Бокса-Уилсона: При использовании алгоритма крутого восхождения пошаговое движение из точки вектора совершается в направлении наискорейшего возрастания функции, т.е. по градиенту в этой точке. Однако, в отличии от градиентного метода, корректировка направления производится не после каждого следующего шага, а только по достижению частного экстремума.

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