ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ
Все методы оптимизации могут искать и минимум, и максимум при незначительных изменениях в алгоритмах. Действительно для того, чтобы найти максимум (минимум) функции нужно искать минимум (максимум) целевой функции с противоположным знаком. Для того, чтобы найти максимум (минимум) функции нужно искать минимум (максимум) целевой функции с противоположным знаком.
МЕТОД ЗОЛОТОГО СЕЧЕНИЯ
Метод основан на делении текущего отрезка [a, b], где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу Золотого сечения, для определения следующего отрезка, содержащего максимум.
Многомерная оптимизация. Метод покоординатного спуска. Многомерная оптимизация - оптимизация при нескольких управляющих переменных
Методы, использующие только значения функции: ü Метод покоординатного спуска (метод Гаусса); ü Метод деформируемого многогранника (симплексный метод); ü Метод Хука–Дживса; ü Алгоритм Розенброка; ü Метод Пауэлла и сопряженные направления. Методы, требующие вычисления первых производных функции (градиента): ü Метод градиентного спуска; ü Метод Ньютена; ü Метод сопряженных градиентов; ü Многопараметрический поиск.
Линии постоянного уровня. «Рельеф функции» удобно рассмотреть на примере функции двух переменных z= F( x, y). Это функция описывает некоторую поверхность в трехмерном пространстве с координатами z, x, y. Задача F( x, y)→ min означает поиск низшей точки этой поверхности. Проведем сечения поверхности равно отстоящими плоскостями, которые параллельны плоскости изменения переменных x и y. Линии этих сечений проецируем на плоскость изменения переменных. Получим концентрические окружности. Эти линии называются линиями постоянного уровня. Основная характеристика любой из линий это то, что в любой точке этой линии значение функции постоянно.
Метод покоординатного спуска (метод Гаусса)
Это простейший алгоритм, заключающийся в том, что на каждом шаге (каждой итерации) минимизация осуществляется только по одной компоненте вектора переменных. Алгоритм расчета: 1) Задается начальное приближение; 2) Фиксируются все координаты, кроме одной, ищется минимум одномерным поиском; 3) Предыдущий шаг повторяется для всех координат. Алгоритм расчета: Выберем нулевое приближение (начальные значения) х0, y0 Фиксируем значение координаты y= y0 , тогда функция будет зависеть только от одной переменной х ; обозначим ее через f1( x)= F( x; y0). Используя какой-либо способ одномерной оптимизации, найдем х1 при котором f1( x) минимальна. Получился шаг из точки (х0; y0) в точку (х1; y0) по направлению, параллельному оси х. Значение функции на этом шаге уменьшилось. Теперь из новой точки сделаем спуск по направлению, параллельному оси y, то есть рассмотрим функцию f2( y)= F(х1; y), найдем y1 при котором f2( y) минимальна. Приход в точку (х1; y1) завершает цикл. Далее цикл повторяется. Достоинствами метода покоординатного спуска являются: • Простота вычисления направлений. В результате метод может применяться, в том числе, в пространствах сверхбольшой размерности; • Отсутствие требований к вычислению любых производных функции f. К недостаткам метода следует отнести: • Возможность застревания в промежуточной точке для негладких функций f. • Возможность совершать большое количество очень маленьких шагов даже при оптимизации строго выпуклых функций.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (315)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |