Симплексный и градиентный методы оптимизации.

Симплексный и градиентный методы оптимизации.

Симплексный метод.

Симплекс – многогранник, число сторон которого на одну больше мерности пространства.

Для поиска новой вершины применяется способ отражения.

Если , то процесс удачный.

- оптимальное значение

Если ,

то возвращаемся назад и берем х₂.

Градиентный метод.

Упрощенно принцип работы градиентных методов минимизации функций полно представить следующим образом:

1) в исходной точке поиске с координатой х₀ определяется нап­равление аитиградиента;

2) вдоль этого направления выполняется шаг заданной длины;

3) в полученной таким образом новой точке опять определяется
направление антиградиента и т.д.

Процесс проводится до тех пор, пока происходит улучшение ре­зультата, т.е. идет убывание функции F(x).

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

Наиболее простым методом является тот, в которой движение вдоль направления антиградиента осуществляется с постоянным шагом:

где и - номера предыдущей и последующей итерации поиска.

- модуль градиента.

Если значение целевой функции в новой точке оказывается больше значения в предыдущей точке, т.е. F_k+1 > F_k , то производится возвращение в предыдущую точку, потом шаг делится пополам и процесс продолжается с уменьшенным шагом. Решение останавливается тогда, когда величина шага оказывается меньше некоторого заданно­го малого числа или модуль градиента становится меньше другого заданного числа .

В некоторых случаях более эффективна является движение с шагом, пропорциональным модулю градиента;

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