2.2.2. Метод Зейделя.

Этот метод заключается в последовательной минимизации функции f(X) по направлению каждого из координатных векторов e^j, j=1,…,n всегда начиная из самой последней точки построенной последовательности. После завершения минимизации по направлению последнего координатного вектора eⁿ цикл, называемый внешней итерацией, повторяется до тех пор, пока не выполнится одно из возможных условий окончания поиска:

|f(X^k)  f(X^kn)| или || X^k  X^k-n||, (2.19)

где 0  заданный параметр точности.

Для приближенного решения вспомогательной задачи минимизации

min{f(X^k  S^k) |R} (2.20)

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

Шаг 0. Задать параметр точности 0, выбрать точку начального приближения X⁰ÎEⁿ, вычислить значение функции f(X⁰), положить k=0.

Шаг 1. Положить j=kn +1, S^k=e^j, где –целая часть числа k/n.

Решить задачу одномерного поиска (2.20), т.е. определить оптимальную величину шага _k=arg min{f(X^k+S^k)|R}. Найти новую точку последовательности X^k+1= X^k+_kS^k и вычислить значение функции f(X^k+1).

Шаг 2. Если jn , то положить k=k+1 и перейти к шагу 1, иначе – перейти к шагу 3.

Шаг 3. Проверить условие достижения заданной точности (2.19). Если оно выполняется, то перейти к шагу 4, иначе – к шагу 1, положив k=k+1.

Шаг 4. Завершить вычисления, положив X* X^k+1, f*f(X^k+1).

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

2.2.3. Метод Хука-Дживса

Эффективность решения задачи (2.1) рассмотренными методами покоординатного спуска можно повысить, если дополнить описанные алгоритмы периодически повторяющимся поиском точки минимума в направлении вектора X^kX^k-n из точек X^k, k=sn, где s – количество выполненных внешних итераций. Такой подход и лежит в основе метода ХукаДживса.

Алгоритм метода ХукаДживса содержит две основные процедуры:

1) Исследующий покоординатный поиск в окрестности данной точки с целью определения направления убывания функции f(X);

2) Перемещение в направлении убывания.

Опишем вначале алгоритм исследующего покоординатного поиска из заданной точки X с приращениями по каждой координате _j, j=1,…,n.

Шаг 1. Положить =X, j=1.

Шаг 2. Сделать пробный шаг Y=  _je^j,где e^j  j-й координатный вектор. Если f(Y)f( ), то перейти к шагу 3, иначе – к шагу 4.

Шаг 3. Сделать пробный шаг Y= +_je^j. Если f(Y)f( ), то перейти к шагу 5, иначе – к шагу 4.

Шаг 4. Положить =Y.

Шаг 5. Положить j=j+1. Если jn, то перейти к шагу 2. В противном случае исследующий поиск окончен, т.е. получена точка , для которой f( )f(X), если X.

В результате исследующего поиска может оказаться, что =X. Тогда исследующий поиск считается неудачным. Если при этом |||| , где  – заданная точность, то полагают X*=X. Если же заданная точность не достигнута, то полагают _j=_j, где (0;1)–коэффициент уменьшения шага и повторяют исследующий поиск.

Опишем теперь полный алгоритм ХукаДживса.

Шаг 0. Выбрать начальную точку X⁰ÎEⁿ, вектор приращений =(₁,…, _n), коэффициент уменьшения (0;1), параметр точности 0, положить k=0.

Шаг 1. Провести исследующий покоординатный поиск из точки X^k и найти точку ^k. Если ^k X^k, то перейти к шагу 3, иначе – к шагу 2.

Шаг 2. Проверить условие достижения заданной точности ||||. Если оно выполняется , то перейти к шагу 5, иначе положить _j=_j и перейти к шагу 1.

Шаг 3. Сделать “диагональный ” шаг из точки ^k в направлении вектора ^kX^k в точку X= ^k+( ^kX^k )=2 ^kX^k.

Шаг 4. Провести исследующий поиск в точке X и найти точку . Если f( )f( ^k), то положить X^k= ^k, ^k =X и перейти к шагу 3. Иначе положить k=k+1, X^k=X и перейти к шагу 1.

Шаг 5. Завершить вычисления, положив X^*=X^k, f ^*=f(X^k).