Градиентный метод с дроблением шага

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

                         (2.2)

Методы построения таких последовательностей называют методами спуска. Пусть  Поставим задачу отыскания последовательности ., сходящейся к .

Выберем произвольным образом точку , направление  и сконструируем луч

.                                       (2.3)

Рассмотрим вопрос о выборе направления , обеспечивающего (2.2). Для этого изучим поведение вдоль луча  . Имеем

Введем

                          (2.4)

Здесь

В соответствии с (2.3)

Тогда

Вычислим                            (2.5)

Теперь, чтобы для любого  обеспечить отрицательность (2.5), достаточно положить , где  произвольная положительно определенная  матрица. Тогда

При этом                         (2.6)

Выбрав каким-либо образом  , получим Затем аналогично рассчитаем

Общее рекуррентное соотношение имеет вид :

                           (2.7)

Различные варианты градиентных процедур отличаются друг от друга способом выбора .

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

                             (2.8)

                                     (2.9)

где  и  -некоторые достаточно малые числа .

Понятно, что критерий (2.8) хорош в тех случаях, когда функция  в окрестности минимума, используя ранее введенную классификацию, имеет характер «глубокой» впадины. С другой стороны, если функция  ведет себя как «пологое плато», то более предпочтительным является критерий (2.9). Аналогом критерия (2.8) является другое часто применяемое правило останова :

,                                  (2.10)

использующее необходимое условие экстремума функции. Очевидным недостатком критериев (2.8)-(2.10) является то, что их качество существенно зависит от абсолютных значений величины  и компонентов векторов , . Более универсальными являются относительные критерии :

                          (2.11)

                                   (2.12)

            (2.13)

Заметим, что очень часто на практике используются составные критерии, представляющие собой линейную комбинацию критериев (2.11)-(2.13), например,

Иногда применяют другой вариант построения составного критерия :

При реализации градиентного метода с дроблением шагав качестве  выбирают единичную матрицу, то есть

а длину шага определяют путем проверки некоторого неравенства. При этом основное рекуррентное соотношение (2.7) приобретает вид :

Ясно, то если , выбирать достаточно малым, то это обеспечит убывание , но потребуется весьма большое число шагов. Если же неосторожно выбрать  большим , то можно проскочить минимум, а это опасно в связи с возможным осциллированием. Для выбора шага используется правило Голдстейна-Армийо :

а)            (2.14)

б)           (2.15)

Выполнение условия а) обеспечивает выбор  не слишком большим. Выполнение условия б) не дает возможность выбрать  слишком малым.

Практическая процедура строится следующим образом. Выбирается начальная точка  и некоторое начальное значение , проверяется (2.14) и, если оно выполняется, то делается шаг в направлении  В новой точке  вычисляется градиент  и вновь проверяется условие (2.14). В случае его удовлетворения продвижение к минимуму продолжается с тем же шагом. Если же оно не удовлетворяется, то параметр , определяющий длину шага, делят пополам до тех пор, пока это неравенство не будет выполнено. Затем выполняется очередной шаг. Процедура продолжается до выполнения критерия останова.