Спуск по координатам
Может показаться, что для поиска минимума функции F(x,y) достаточно решить нелинейную систему уравнений, обычными для этого случая итерационными методами и, отбросив точки максимума и седловые точки, получить минимумы. Однако на практике оказывается, что области сходимости итераций весьма малы и выбрать подходящее нулевое приближение не всегда удается. В этой ситуации может оказаться более эффективным метод спуска по координатам.
Процедуру спуска по координатам можно представить в виде набора циклов спуска. Пусть задано некоторое начальное приближение x0, y0. Фиксируем значение координаты y = y0 и рассматриваем функцию F(x,y0) как функцию f1 переменной x, т.е. f1(x) = F(x,y0). Используя методы поиска минимума функции одной переменной f1(x), рассмотренные ранее, находим точку минимума x1. Далее фиксируем переменную x = x1 и рассматриваем функцию F(x1,y) как функцию g1 переменной y, т.е. g1(y) = F(x1,y). Применяя к функции g1(y) методы поиска минимума, находим точку минимума y1. На этом завершается первый цикл спуска. Следующий цикл спуска начинается с фиксации координаты y = y1 и рассмотрения функции F(x,y1) как функции f2 одной переменной x, т.е. f2(x) = F(x,y1). Минимум функции f2(x) реализуется при x = x2. Далее можно продолжить по аналогии с предыдущим циклом спуска.
На каждом цикле спуска функция F не возрастает, и она ограничена снизу своим значением минимума 
. Поэтому итерации сойдутся к некоторому пределу 
. Необходимо разобраться будет ли иметь место знак равенства и если да, то, как быстро итерации сойдутся.
Сходимость метода спуска зависит от вида функции и от начального приближения. Приведем два примера, первый из которых демонстрирует сходимость метода спуска, а второй — отсутствие сходимости.
На рис.6,а приведена геометрическая интерпретация сходимости покоординатного спуска. Начинаем двигаться от начального приближения (x0, y0) по координате x (координата y фиксирована). Направление движения определяет стрелка. Движемся вправо до тех пор, пока не коснемся соответствующей линии уровня, после чего движение вправо приводит к возрастанию функции F. В точке касания фиксируем переменную x и двигаемся по переменной y вниз до касания с соответствующей линией уровня. На этом заканчивается первый цикл спуска. Далее цикл спуска повторяем столько раз, сколько необходимо для достижения требуемой точности. Видно, что данная процедура действительно приближает нас к точке минимума функции F.
На рис.6,б линии уровня образуют истинный овраг. В этом случае существуют ситуации, одна из которых приведена на рис.6,б, когда с помощью метода покоординатного спуска на некотором этапе мы приходим на “дно” оврага, из которого движение в перпендикулярном направлении заблокировано, т.к. функция F растет в обоих направлениях. Другими словами, дальнейший покоординатный спуск невозможен, но минимум еще не достигнут. Это пример того, что метод покоординатного спуска не сходится к минимуму.
| 
|
| Рис.6,а. Демонстрация сходимости метода покоординатного спуска | Рис.6,б. Пример отсутствия сходимости метода покоординатного спуска к точке минимума |
Докажем сходимость метода покоординатного спуска, выбрав для простоты функцию двух переменных F(x,y), у которой вторые производные непрерывны и минимум которой не вырожден. Пусть выбрано нулевое приближение (x0,y0). Проведем линию уровня через эту точку, она ограничивает некоторую область G. Пусть в области G выполнены условия положительной определенности квадратичной формы (16), т.е.
. (17)
Поскольку значения функции не возрастают вдоль траектории спуска, постольку траектория не может выйти за пределы области G и поэтому неравенства (17) останутся верными на всех этапах спуска.
Представим процедуру перехода от i-го цикла к i+1-циклу спуска:
(18)
Согласно (18), точка A построена после спуска по координате y, т.е. 
и 
. После первого шага i-го цикла получим: 
и 
. В силу непрерывности вторых производных функции F, применяя теорему о среднем, находим
(19)
где 
— расстояние между точками A и B. Комбинируя пару неравенств (19), находим 
.
Применяем аналогичные рассуждения ко второму шагу цикла спуска, т.е., считая 
и 
, находим
(20)
где 
— расстояние между точками B и C. Комбинируя пару неравенств (20), находим 
. Учитывая пару неравенства и , находим
. (21)
Согласно оценке (21), Fx уменьшается в q-1 раз за один шаг цикла. Аналогичная оценка имеет место применительно к Fy, она получается, если цикл рассматривать сдвинутым на один шаг, т.е. начиная с точки B далее к C и D. Таким образом, при неограниченном увеличении числа циклов первые производные функции F стремятся к нулю, согласно выражениям:
и 
, n ® ¥. (22)
Итак, доказано, что при условии положительной определенности квадратичной формы (17) в окрестности невырожденного минимума метод покоординатного спуска сходится, причем его сходимость линейна.
| 
|
| Рис.7,а. Форма линий уровня, обеспечивающая быструю сходимость метода спуска | Рис.7,б. Форма линий уровня, при которой метод спуска медленно сходится |
Скорость сходимости будет неплохой при малом q, когда линии уровня являются эллипсами, оси которых параллельны осям координат. И, наоборот, сходимость будет медленной при q » 1, когда линии уровня являются сильно вытянутыми эллипсами, оси которых находятся под значительным углом к координатным осям. Покажем это на примере поиска минимума функции
. (23)
Можно проверить, что для функции (23) a = b = 1, q = c2. На рис.7 приведены соответствующие линии уровня функции (23) для двух случаев: q =0,25 на рис.7,а и q = 0,99 на рис.7,б.
На листинге_№5 приведен код программы, иллюстрирующей метод покоординатного спуска к минимуму функции 
. Результат работы кода программы листинга_№5 приведен на рис.8, где представлены линии уровня функции F и траектория спуска к минимуму функции F.
Листинг_№5
%Программа, иллюстрирующая поиск минимума
%функции F(x,y)=(y-sin(x))^2+0.1x^2
%методом покоординатного спуска
%очищаем рабочее пространство
clear all
%задаем точность близости частных производных
%функции F к нулю
eps=1e-3;
%определяем функцию и ее частные производные
F=@(x,y)(y-sin(x))^2+0.1*x^2;
Fx=@(x,y)-2*cos(x)*(y-sin(x))+0.2*x;
Fxx=@(x,y)2*y*sin(x)+2*cos(2*x)+0.2;
Fy=@(x,y)2*(y-sin(x));
Fyy=@(x,y)2;
%задаем начальное приближение
x(1)=4.5; y(1)=-1;
%задаем счетчик числа шагов в методе спуска и
%максимальное число шагов
k=1; iterm=200;
%организуем цикл покоординатного спуска
while ((abs(Fx(x(k),y(k)))>eps)|...
(abs(Fy(x(k),y(k)))>eps))&(k<iterm)
%цикл спуска по координате x осуществим с
%помощью метода Ньютона
xs=x(k);
for i=1:2
xs=xs-Fx(xs,y(k))/Fxx(xs,y(k));
end
k=k+1;
x(k)=xs; y(k)=y(k-1);
%цикл спуска по координате y осуществим с
%помощью метода Ньютона
ys=y(k);
for i=1:2
ys=ys-Fy(x(k),ys)/Fyy(x(k),ys);
end
k=k+1;
x(k)=x(k-1); y(k)=ys;
end
%подготовительные мероприятия к построению
%линий уровня
[u v]=meshgrid(-2*pi:0.1:2*pi,-pi:0.1:pi);
Func=(v-sin(u)).^2+0.1*u.^2;
%определяем значения функции, линии уровня
%которых будут построены
for i=1:5
s(i)=F(x(i),y(i));
end
%построение линий уровня
contour(u,v,Func,s);
hold on
%построение траектории спуска к минимуму
%функции F
line(x,y,'Color','black');
Рис.8. Линии уровня минимизируемой функции и траектория
спуска к минимуму