5.15. Условие останова

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

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

значения параметров. Иначе, если имеется ряд чисел мы принимаем за решение 0, когда

где компонента Числа могут либо быть выбраны заранее, либо вычислены по программе. В последнем случае, следуя Марквардту [140], рекомендуем

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

Предположим, что на и итерации направление шага было определено. Тогда уравнение справедливо, если для любого т. е. если Следовательно, минимально допустимое значение на итерации равно Как показано на рис. 5.2 а, останов происходит, если алгоритм выбирает

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

В конце концов, можно наложить ограничение сверху на допустимое число итераций. Это следует делать в сочетании с процедурой повторного счета по другому алгоритму.

Когда итерационный процесс заканчивается в точке остается выяснить, достигли ли мы точки минимума на самом деле. Положим, мы знаем вектор-градиент и по крайней мере некоторую аппроксимацию матрицы Гессе . Если мы проведем сечение поверхности осью , то получим кривую, уравнение которой вблизи 0 запишется так:

она имеет стационарную точку при

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

Если матрица Гессе функции в точке 0, то можно легко определить, является ли 0 (если уже известно, что -стационарная точка) действительно точкой минимума. Единственное, что для этого нужно, — это проверить положительную определенность (см. раздел 3.5), т. е. проверить, являются ли положительными все ее собственные значения. При использовании метода Гаусса аппроксимация строится так, что она положительно определена автоматически, независимо от определенности . Поэтому в таких случаях не содержит информации относительно характера точки 0. Единственная возможность ответить на этот вопрос — это исследовать непосредственно поведение в окрестности 0. В методе КРЕ, с другой стороны, матрица на последней итерации может быть хорошей аппроксимацией Мы не можем доказать, что положительно определена (или нет), когда 0 является (или не является) точкой минимума; однако, если не положительно определена, то, вероятно, 0 не будет точкой минимума, и наоборот.

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