Многомерный поиск безусловного минимума
Метод Гаусса-Зейделя (покоординатного спуска)
Процедура поиска сводится к решению последовательности задач одномерной минимизации по каждой переменной.
Начальная точка . Зафиксируем все переменные, кроме первой, на начальных значениях и решаем задачу одним из одномерных методов, находим x1’. Приходим к очередной одномерной задаче . Аналогично строятся и решаются последующие одномерные задачи. Эти n задач составляют один цикл. Его результатом является точка X1. Она принимается за начальную точку для следующего аналогичного цикла. Условия окончания поиска: .
Недостатки. Эффективность зависит от направления осей координат относительно линий уровня. Метод неэффективен в условиях оврага. Если функция не дифференцируема в отдельных точках, поиск может остановиться, не достигнув окрестности минимума.
Метод Хука-Дживса (метод конфигураций)
В этом методе каждая итерация состоит из двух фаз:
1) исследующий поиск; 2) движение по образцу (ускоряющий шаг). Исследующий поиск аналогичен одному циклу покоординатного спуска. Конечную точку цикла называют базовой. Две последовательные базовые точки определяют направление поиска на 2-й фазе. Точка, получаемая в результате ускоряющего шага, называется временной. Начальная точка одновременно является базовой и временной. Модификация метода Хука-Дживса заключается в замене дискретных шагов одномерной минимизацией.
|