Алгоритмы покоординатного спуска

f(x) ®  min, xÎR² 

выбирая в качестве начального приближения  произвольную точку из R².

      Шаг в градиентном методе следует  выбирать из условия монотонности функции. 
 

. 

Алгоритмы покоординатного  спуска.

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

      Алгоритм  состоит из циклов, каждый из которых  содержит n итераций и характеризуется тем, что величина шага в течение всех n итераций остаётся постоянной.

      Предположим, что начальное приближение и положительное значение шага выбраны. Опишем цикл метода.

      В цикле вычисляются точки  . Обозначим через -  i-ый единичный координатный вектор, , т.е. вектор, у которого i-ый элемент равен единице, а остальные элементы равны нулю. Пусть в результата предыдущего цикла получен некоторый шаг .

      (i+1)-я итерация цикла заключается в следующем.

1). Если  , то положим и перейдём к следующей итерации.

2).Если  , то вычислим .

3).Если  , то положим и перейдём к следующей итерации.

4)Если  , то положим и перейдём к следующей итерации.

      В случае, когда неравенства в п.2) и в п.4) выполняются одновременно для всех i = 0,1,….,n – 1, т.е. при переборе направлений всех координатных осей цикл оказался нерезультативным, уменьшим величину и повторим все процедуры цикла, но уже с меньшим шагом.

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

Пример 2.  Найти минимум функции методом покоординатного спуска, заканчивая вычисления при .

Решение.   Выберем  ,  ,   тогда

1). Т.к.  ,    , то вычислим ,   . Следовательно . Перейдём к следующей итерации первого цикла.

2). . Т.к. , то определим , . Отсюда . Перейдём к следующему циклу.

3). Т.к.  и , то положим и перейдём к следующей итерации второго цикла.

4). Т.к.  , то вычислим . Итак, цикл оказался нерезультативным и, следовательно, необходимо положить и уменьшить шаг . Пусть = 0.05. Перейдём к новому циклу.

5). ,  . Вычислим теперь ,  . Следовательно, положим и перейдём к следующей итерации.

6). ,  . Тогда определим ,  . Следовательно, цикл снова оказался нерезультативным и т.к. , то вычисления прекращаем и в качестве приблизительного решения полагаем ,  .