Метод циклического покоординатного спуска

 

Метод циклического покоординатного спуска заключается в изменении каждый раз одной переменной, тогда как другие остаются постоянными. Опишем этот метод для задачи (2.1).

Пусть X⁰– некоторое начальное приближение, а a₀–некоторое положительное число, являющееся параметром алгоритма. Допустим, что уже известны точка X^kÎEⁿ и число a_k>0 при некотором k³0. Обозначим e^j=(0,…,0,1,0,…,0)–единичный координатный вектор, у которого j-я координата равна 1, остальные равны нулю, j=1,…,n. Положим

S^k=e^jk, j_k=k-n +1, (2.13)

где - целая часть числа k/n. Условие (2.13) обеспечивает циклический перебор координатных векторов e¹,…,eⁿ, т.е. S⁰=e¹,…, S^n-1=eⁿ, Sⁿ=e¹,…,

S^2n-1=eⁿ, S²ⁿ=e¹….

Вычислим значение функции f(X) в точке X= X^k+ a_kS^k и проверим неравенство

f(X^k+ a_kS^k) < f(X^k). (2.14)

Если оно выполняется, то полагаем

X^k+1= X^k+ a_kS^k, a_k+1=a_k. (2.15)

В случае, если условие (2.14) не выполняется, вычисляем значение функции f(X) в точке X= X^k -a_kS^k и проверяем неравенство

f(X^k - a_kS^k) < f(X^k). (2.16)

При выполнении условия (2.15) полагаем

X^k+1= X^k - a_kS^k, a_k+1=a_k. (2.17)

Будем считать (k+1)–й этап удачным, если выполнилось хотя бы одно из условий (2.14) или (2.16). Если же ни одно из этих условий не выполнено, считаем (k+1)–й этап неудачным и полагаем

Х^k+1=X^k, a_k+1= (2.18)

где lÎ(0;1) –фиксированное число, являющееся параметром алгоритма. Условие (2.18) означает, что если за один цикл из n этапов при переборе направлений всех координатных векторов e¹,…,eⁿ с шагом a_k реализовался хотя бы один удачный этап, то длина шага a_k не дробится и сохраняется на протяжении по крайней мере следующего цикла из n этапов. Если же среди последних n этапов ни одного удачного не оказалось, то шаг a_k дробится.

Скорость сходимости данного метода невысока. Несмотря на это, метод циклического покоординатного спуска широко применяется на практике благодаря простоте реализации.

Заметим, что такой метод работает плохо, если в выражение минимизируемой функции входят произведения x _ix _j, т.е. если имеет место взаимодействие между x _i, i=1,…,n.

Указанного в конце предыдущего пункта недостатка можно избежать с помощью следующей модификации метода покоординатного спуска, известной под названием метода Зейделя.

 

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

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

|f(X^k) - f(X^k-n)|<e или || X^k - X^k-n||<e, (2.19)

где e>0 - заданный параметр точности.

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

min{f(X^k - a×S^k) |aÎR} (2.20)

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

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

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

Решить задачу одномерного поиска (2.20), т.е. определить оптимальную величину шага a_k=arg min{f(X^k+a×S^k)|aÎR}. Найти новую точку последовательности X^k+1= X^k+a_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.1) рассмотренными методами покоординатного спуска можно повысить, если дополнить описанные алгоритмы периодически повторяющимся поиском точки минимума в направлении вектора X^k-X^k-n из точек X^k, k=s×n, где s – количество выполненных внешних итераций. Такой подход и лежит в основе метода Хука-Дживса.

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

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

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

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

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

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

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

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

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

В результате исследующего поиска может оказаться, что =X. Тогда исследующий поиск считается неудачным. Если при этом ||D||£e, где e – заданная точность, то полагают X*=X. Если же заданная точность не достигнута, то полагают D_j=D_jg, где gÎ(0;1)–коэффициент уменьшения шага и повторяют исследующий поиск.

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

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

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

Шаг 2. Проверить условие достижения заданной точности ||D||<e. Если оно выполняется, то перейти к шагу 5, иначе положить D_j=D_jg и перейти к шагу 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).

 

Метод Пауэлла.

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

Пусть задана точка начального приближения X⁰ÎEⁿ. Выполним одну внешнюю итерацию метода покоординатного спуска Зейделя (см. пункт 2.2.2), т.е. найдем точку

Xⁿ= X⁰+

где e^j – единичный координатный вектор, у которого j–я координата равна 1, остальные равны 0, j=1,…,n. При этом величина шага определяется с помощью какой-либо процедуры одномерной оптимизации по a

a _j =arg min {f(X^j-1+a e^j) ½aÎR}.

Далее выполняется “диагональный”шаг в направлении убывания функции f(X) по вектору: Sⁿ⁺¹=Xⁿ-X⁰: Xⁿ⁺¹=Xⁿ+a_n+1Sⁿ⁺¹, где величина шага a_n+1 определяется путем минимизации целевой функции в направлении вектора Sⁿ⁺¹ с помощью одномерного поиска по a:

a _n+1 =arg min {f(Xⁿ+aSⁿ⁺¹) | a>0}.

Полагая X⁰=Xⁿ⁺¹, приступаем к выполнению следующей внешней итерации. Описанная процедура повторяется до тех пор, пока не выполнится одно из условий (2.19).

 

Типовые примеры

 

Пример 1. Решить задачу минимизации функции двух переменных f(X)=5x₁²+5x₂²+8x₁x₂ из начальной точки X⁰= (5;5) ^Т методом покоординатного спуска Зейделя.

Заметим, что линии уровня данной целевой функции - соосные эллипсы с центром в начале координат, большая ось которых наклонена под углом 135° к оси х₁. Результаты расчетов по приведенному в пункте 3 алгоритму приведены в таблице и графически проиллюстрированы на рис.5. При нахождении очередной точки X^к минимизирующей последовательности происходит смещение по прямой, параллельной одной из координатных осей, до точки с наименьшим на этой прямой значением функции f(X). Очевидно, эта точка будет точкой касания рассматриваемой прямой и соответствующей линии уровня.

Таблица 1   K X1 X2 F(x)               -4         -4 3,2 28,8     -2,56 3,2 18,43     -2,56 2,05 11,8     -1,64 2,05 7,55     -1,64 1,31 4,83     -1,05 1,31 3,09     -1,05 0,84 1,98     -0,67 0,84 1,27     -0,67 0,54 0,81                                 Эффективность прямых методов обычно оценивают или по объему вычислений,

Рис.5. Траектория поиска методом

покоординатного спуска Зейделя(к примеру1).

 

Пример 2. Решить задачу минимизации функции f(X)=(x₁+1)²+x₂² методом Хука-Дживса из начальной точки X⁰=(2;3)^T.

Зададим вектор перемещения D=(2;3)^T. Исходное значение функции в начальной точке f(X⁰)=18. В соответствии с алгоритмом, описанным в пункте 4, сначала проводим исследующий поиск из точки X⁰

x₁⁽¹⁾=2+0,5=2,5; f(2,5;3)=21,25 (неудача);

x₁⁽¹⁾=2-0,5=1,5; f(1,5;3)=15,25 (успех);

x₂⁽¹⁾=3+1=4; f(1,5;4)=22,25 (неудача);

x₂⁽¹⁾=3-1=2; f(1,5;2)=10,25 (успех).

Исследующий поиск оказался удачным. Теперь из новой точки X¹=(1,5;2)^T перемещаемся в направлении убывания по вектору X¹-X⁰ в точку X²=2X¹- X⁰:

x₁⁽²⁾=2×1,5-2=1; x₂⁽²⁾=2×2-3=1; f(1;1)=5.

Проводим исследующий поиск в точке X¹=(1,5;2)^T:

x₁⁽³⁾=1+0,5=1,5; f(1,5;1)=7,25 > f(X²) (неудача);

x₁⁽³⁾=1-0,5=0,5; f(0,5;1)=3,25 < f(X²) (успех);

x₂⁽³⁾=1+1=2; f(0,5;2)=6,25 > f(X²) (неудача);

x₂⁽³⁾=1-1=0; f(0,5;0)=2,25 < f(X²) (успех);

Поскольку f(X³)=2,25< f(X¹)=10,25 и перемещение из точки X¹ в точку X²=(1;1)^T успешно, то вновь перемещаемся по направлению убывания из точки X³ в точку

X⁴=2X³- X¹:

x₁⁽⁴⁾=2×0,5-1,5=-0,5; x₂⁽⁴⁾=2×0-2=-2; f(-0,5;-2)=4,25.

После этого проводим исследующий поиск в точке X⁴=(-0,5;-2)^T:

x₁⁽⁵⁾=-0,5+0,5=0; f(0;-2)=5 > f(X⁴) (неудача);

x₁⁽⁵⁾=-0,5-0,5=-1; f(-1;-2)=4 > f(X⁴) (неудача);

x₂⁽⁵⁾=-2+1=-1; f(-0,5;-1)=1,25 < f(X⁴) (успех).

Поскольку f(X⁵)=1,25< f(X³)=2,25 и перемещение из точки X³ в точку X⁴ можно признать успешным, то последовательность поисков по направлению убывания продолжаем до тех пор, пока на очередном этапе в конце исследующего поиска значение f(X) не окажется больше, чем в предыдущей точке. Тогда из последней проводим исследующий поиск для определения нового удачного направления. На рис.6 приведена графическая интерпретация этапов поиска. Линии уровня целевой функции f(X)=(x₁+1)²+x₂²– концентрические окружности с центром в точке X*=(-1;0). Пунктиром на рисунке выделены траектории исследующего поиска, сплошными линиями – перемещения в направлении убывания. Убедитесь в соответствии графической иллюстрации описанному алгоритму.

Рис.6. Минимизация функции Рис.7. Минимизация функции методом

методом Хука-Дживса (к примеру 2). Пауэлла (к примеру 3).

 

Пример 3. Рассмотрим графическую иллюстрацию решения задачи минимизации функции f(X)=2x₁²+x₂²-x₁x₂ методом Пауэлла из начальной точки X⁰=(2;2)^T(рис.7).

Линии уровня функции f(X) – соосные эллипсы с центром в начале координат, большая ось которых наклонена к оси x₁ под углом 67°,5. Первый шаг делается в соответствии с методом покоординатного спуск Зейделя (см. 2.2.2) из точки X⁰ в направлении -e¹=(-1;0), т.е. минимизируется f(X⁰– ae¹) по a>0 с помощью процедуры одномерного поиска. В результате находится точка X¹=X⁰- a₁e¹, где a₁=arg min{f(X⁰– ae¹)|a>0}. Очевидно, эта точка будет точкой касания с соответствующей линией уровня f(X)=const. Аналогично выполняется второй шаг из точки X¹ в направлении -e²=(0;-1) и находится точка X²=X¹-a₂e², где a₂=arg min{f(X¹– ae²)|a>0}. Затем выполняется «диагональный» шаг из точки X² в направлении вектора X²- X⁰. Поскольку целевая функция f(X) квадратичная, точку её минимума удалось найти точно за конечное число шагов.