Первый вариант

Начальный этап. Задать начальную точку , – параметр окончания счета, – первоначальная величина шага, – коэффициент уменьшения шага, положить , .

Основной этап.

1. Вычислить .

2. Если , то перейти к шагу 5.

3. Вычислить .

4. Если , то перейти к шагу 5, иначе положить .

5. Если , то положить и перейти к шагу 1.

6. Положить .

7. Если , то перейти к шагу 9, иначе перейти к шагу 8.

8. Если , то положить и остановиться, иначе положить , , и перейти к шагу 1.

9. Если , то положить и остановиться, иначе положить , , и перейти к шагу 1.

Второй вариант

Начальный этап. Такой же, как в первом варианте.

Основной этап.

1. Вычислить .

2. Если , то перейти к шагу 6.

3. Вычислить .

4. Если , то перейти к шагу 6.

5. Если , то перейти к шагу 6, иначе положить и перейти к шагу 1.

6. Если , то положить и перейти к шагу 1.

7. Положить .

8. Если , то положить и остановиться, иначе положить , , и перейти к шагу 1.

Если пользоваться терминологией Хука-Дживса, то метод покоординатного спуска, не использующий одномерной оптимизации, состоит из последовательности ИП вокруг текущей (базисной) точки и не предполагает поиска по образцу, что во многих случаях замедляет сходимость. ИП вокруг текущей точки состоит из n-итераций, каждая из которых состоит из поиска точки на соответствующей координатной оси . Величина шага вдоль оси определяется так называемым методом удвоения (название метода соответствует случаю, когда ; ). В первом варианте алгоритма величина шага вдоль оси остается постоянной при проведении ИП вокруг текущей точки и уменьшается лишь тогда, когда ИП не приводит к уменьшению значения функции . Во втором варианте алгоритма величина шага может меняться при поиске вдоль каждой из координатных осей, причем как в сторону уменьшения шага ( ), если значение функции не уменьшилось, так и в сторону увеличения шага ( ), если значение функции уменьшилось, причем процесс увеличения продолжается до тех пор, пока убывание функции не прекратится.

Пример 12.4. Решить задачу из примера 12.1 методом покоординатного спуска (второй вариант).

Начальный этап. Положить , , , , , .

Основной этап.

1. Вычислить .

2. Так как , то переходим к шагу 6.

6. Так как , то и переходим к шагу 1

1. .

2. Так как , то переходим к шагу 6.

6. Так как , то переходим к шагу 7.

7. Вычислим .

8. Так как , то полагаем , и переходим к шагу 1.

1. Вычислить .

2. Так как , то переходим к шагу 6.

6. Так как , то и переходим к шагу 1

1. .

2. Так как , то переходим к шагу 6.

6. Так как , то переходим к шагу 7.

7. Положим .

8. Так как , то полагаем , и переходим к шагу 1.

1. Вычислить .

2. Так как , то переходим к шагу 6.

6. Так как , то и переходим к шагу 1

1. .

2. Так как , то переходим к шагу 6.

6. Так как , то переходим к шагу 7.

7. Положим .

8. Так как , то полагаем , и переходим к шагу 1.

1. Вычислить .

2. Так как , то переходим к шагу 3.

3. Вычислим .

4. Так как , то переходим к шагу 5.

5. Так как , полагаем и переходим к шагу 1.

1. Вычислить .

2. Так как , то переходим к шагу 6.

6. Так как , то переходим к шагу 1

1. Вычислить .

2. Так как , то переходим к шагу 3.

3. Вычислим .

4. Так как , то переходим к шагу 5.

5. Так как , полагаем и переходим к шагу 1.

1. Вычислить .

2. Так как , то переходим к шагу 3.

3. Вычислим .

4. Так как , то переходим к шагу 7.

6. Положим .

7. Так как , то полагаем , и переходим к шагу 1.

1. Вычислить .

2. Так как , то переходим к шагу 3.

3. Вычислим .

4. Так как , то переходим к шагу 5.

5. Так как , полагаем и переходим к шагу 1.

1. Вычислить .

2. Так как , то переходим к шагу 3.

3. Вычислим .

4. Так как , то переходим к шагу 7.

7. Положим .

8. Так как , то положим , и остановимся.

Итак, после пяти итераций получена точка . На рис. 12.6 представлены соответствующие шаги алгоритма. Пунктирная линия соответствует неудачным шагам поиска.