5.13. размер шага
В предыдущих разделах мы касались выбора направления шага на
итерации, т. е. выбора
Теперь мы остановимся на определении размера шага, т. е. на выборе
Применяемые методы можно разбить на три группы.
1.
. Такое значение
необходимо в методе Ньютона (чтобы обеспечить квадратичную сходимость вблизи точки минимума) и в методе Марквардта. В последнем размер шага определяется выбором
2.
В этом случае мы двигаемся вдоль выбранного направления к точке, в которой
перестает уменьшаться, как в методе
Методы поиска
предложены Флетчером и Пауэллом [813, Бардом [13], Голдфарбом и Лапидусом [861 и др.
3. Метод, основанный на интерполяции — экстраполяции совместно с методами Гаусса и
Здесь можно сделать попытку пайти хорошее допустимое значение
не заботясь о точном вычислении
В целом очевидно, что, чем ближе
тем меньше будет требуемое общее число итераций. С другой стороны, чем точнее мы хотим определить значение тем большим будет число обращений к вычислению целевой функции на каждой итерации. Разница между случаями 2 и 3 заключается в том, что в первом из них
определяется со значительно большей точностью, чем это потребуется впоследствии. В следующем разделе мы приведем простой алгоритм определения
для случая 3. Он работает достаточно успешно, но не очевидно, что он является самым эффективным. Степень изобретательности при создании таких алгоритмов бесконечна.
Во всех случаях поиск
не связан с расчетом производных. Было бы весьма расточительным вычислять в каждой точке
функций
компонент ее градиента) для проведения одномерного поиска. Знание градиента требуется лишь на основных итерациях
В алгоритме следующего раздела предполагается, что мы имеем ограничение сверху
на возможные значения
на каждой итерации. Если нужно удовлетворить ограничениям типа неравенств (см. раздел 6.1), то
наименьшее положительное значение
для которого
лежит на границе допустимой области. Если отсутствуют ограничения типа неравенств, в качестве
может быть выбрано любое большое число. Мы имеем также ограничение снизу
(см. раздел 5.15). Если нельзя найти допустимого
поиск заканчивается.