ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ

Все методы оптимизации могут искать и минимум, и максимум при незначительных изменениях в алгоритмах.

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

Для того, чтобы найти максимум (минимум) функции нужно искать минимум (максимум) целевой функции с противоположным знаком.

МЕТОД ЗОЛОТОГО СЕЧЕНИЯ

Метод основан на делении текущего отрезка [a, b], где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу Золотого сечения, для определения следующего отрезка, содержащего максимум.

Многомерная оптимизация. Метод покоординатного спуска.

Многомерная оптимизация - оптимизация при нескольких управляющих переменных

Методы, использующие только значения функции:

ü Метод покоординатного спуска (метод Гаусса);

ü Метод деформируемого многогранника (симплексный метод);

ü Метод Хука–Дживса;

ü Алгоритм Розенброка;

ü Метод Пауэлла и сопряженные направления.

Методы, требующие вычисления первых производных функции (градиента):

ü Метод градиентного спуска;

ü Метод Ньютена;

ü Метод сопряженных градиентов;

ü Многопараметрический поиск.

Линии постоянного уровня. «Рельеф функции» удобно рассмотреть на примере функции двух переменных z= F( x, y). Это функция описывает некоторую поверхность в трехмерном пространстве с координатами z, x, y. Задача F( x, y)→ min означает поиск низшей точки этой поверхности. Проведем сечения поверхности равно отстоящими плоскостями, которые параллельны плоскости изменения

переменных x и y. Линии этих сечений проецируем на плоскость изменения переменных. Получим концентрические окружности.

    Эти линии называются линиями постоянного уровня. Основная характеристика любой из линий это то, что в любой точке этой линии значение функции постоянно.

Метод покоординатного спуска (метод Гаусса)

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

Алгоритм расчета:

1) Задается начальное приближение;

2) Фиксируются все координаты, кроме одной, ищется минимум одномерным поиском;

3) Предыдущий шаг повторяется для всех координат.

Алгоритм расчета:

Выберем нулевое приближение (начальные значения) х₀, y₀  Фиксируем значение координаты y= y₀ , тогда функция будет зависеть только от одной переменной х ; обозначим ее через f₁( x)= F( x; y₀). Используя какой-либо способ одномерной оптимизации, найдем х₁ при котором f₁( x) минимальна. Получился шаг из точки (х₀; y₀) в точку (х₁; y₀) по направлению, параллельному оси х. Значение функции на этом шаге уменьшилось.

Теперь из новой точки сделаем спуск по направлению, параллельному оси y, то есть рассмотрим функцию f₂( y)= F(х₁; y), найдем y₁ при котором f₂( y) минимальна. Приход в точку (х₁; y₁) завершает цикл. Далее цикл повторяется.

Достоинствами метода покоординатного спуска являются:

• Простота вычисления направлений. В результате метод может применяться, в том числе, в пространствах сверхбольшой размерности;

• Отсутствие требований к вычислению любых производных функции f.

К недостаткам метода следует отнести:

• Возможность застревания в промежуточной точке для негладких функций f.

• Возможность совершать большое количество очень маленьких шагов даже при оптимизации строго выпуклых функций.