Спуск по координатам

Может показаться, что для поиска минимума функции 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. Линии уровня минимизируемой функции и траектория
спуска к минимуму