5.4. Сходимость
В любом случае желательно иметь возможность доказать, что избранный метод оценивания параметров сходится к истинному минимуму целевой функции. К сожалению, доказательства сходимости обычно связаны с введением некоторых предположений о природе целевой функции. В задачах рассматриваемого класса проверка справедливости этих предположений оказывается весьма сложной. Еще более важным является то обстоятельство, что даже в тех случаях, когда сходимость доказана, это еще не является гарантией ее осуществления на практике. Метод может сходиться теоретически и в то же время приводить к чрезмерно большому числу итераций или требовать выполнения расчетов с нереализуемым числом значащих цифр. По этим причинам мы лишь кратко остановимся на рассмотрении теорем сходимости.
Обозначим через
значение
. Если на каждой итерации выбирается допустимая точка, то последовательность
является монотонно убывающей. Если значения целевой функции имеют нижнюю границу, то такая последовательность должна сходиться к пределу
Наконец, если последовательность
ограничена (т. е. существует число
такое, что для любого
будет
то она имеет по крайней мере одну предельную точку. Из непрерывности функции
следует, что
где 0, — некоторая предельная точка последовательности
Вследствие этого последовательность
может иметьболее чем одну предельную точку только в случае исключительного совпадения. Во всех практических случаях последовательность
является либо неограниченной, либо сходящейся к точке Впрочем, скорость сходимости может быть настолько малой, что последовательность будет казаться несходящейся.
Точка, в которой
является стационарной тонкой целевой функции. Если точка
стационарная, т. е.
то из равенства
следует, что все
совпадают с 0. Следовательно, самое большее, что мы можем доказать для любого градиентного метода, — это то, что он сходится к стационарной точке. Сходимость к истинному минимуму гарантируется лишь в том случае, если удается показать, что целевая функция не имеет других стационарных точек. На практике сходимость к локальному максимуму, или седловой точке, почти невероятна. Обычно достигают точки минимума, по крайней мере локального.
При доказательствах сходимости требуется выбирать достаточно большие
и матрицы
являющиеся в достаточной мере положительно-определенными. Типичной является следующая теорема, доказательство которой приводится в приложении
Теорема. Пусть множество всех 0, таких, что
обозначено 3). Предположим, что выполнены следующие условия:
1) функция
имеет на множестве
непрерывные первые и ограниченные вторые производные;
2) пусть
— это наименьшее неотрицательное значение
при котором
достигает локального минимума, где
и пусть а и
положительные числа, причем
Будем выбирать каждое
так, чтобы выполнялось либо условие а
либо условие
3) пусть
константы, удовлетворяющие условиям
Будем выбирать каждую матрицу
так, чтобы все ее собственные значения лежали между
Тогда все предельные точки последовательности
являются стационарными точками функции
Приведенные здесь условия являются необходимыми, но не достаточными. В алгоритмах, которые мы будем рассматривать, матрицы
обычно выбираются в соответствии с условием 3. Однако на практике вряд ли есть необходимость стремиться точно выполнить условие 2. Условие 1 принципиально выполняется почти всегда, однако в некоторых случаях здесь возникают затруднения из-за ограниченной точности вычислений.