Cтраница 2
Если в более ранних работах некоторые авторы использовали в расчетах равновесных геометрий и переходных структур достаточно кустарные методики или такие малоэффективные процедуры, как циклический спуск или симплексный метод, то начиная примерно с 1971 г. градиентные методы и, в первую очередь, методы переменной метрики начали интенсивно внедряться в квантовохимическую практику. [16]
Формула ( IV, 102) лежит в основе метода проектирования градиента [ 88, с. Ясно, что по скорости сходимости этот метод эквивалентен методам градиента и наискорейшего спуска для случая отсутствия ограничений. Поэтому методы переменной метрики, дающие большую скорость сходимости, интересно распространить на данный случай. [17]
Матрица D в формуле (12.111) носит название метрики. Методы поиска вдоль направлений, определяемых этой формулой, называются методами переменной метрики, поскольку матрица Djt изменяется на каждой итерации. Так как методы переменной метрики не используют вторых производных целевой функции, то они относятся к методам первого порядка. [18]
Формула ( IV, 103) лежит в основе метода проектирования градиента [ 31, с. Ясно, что этот метод по скорости сходимости эквивалентен методам градиента и наискорейшего спуска при отсутствии ограничений. Поэтому интересно обобщить на данный случай методы переменной метрики, дающие большую скорость сходимости. [19]
В то же самое время, когда был введен метод переменной метрики, было показано, что он разрешает задачу min ( z, d) -) - ( 2, Hz / 2 z e R j ( где Я - симметрическая положительно определенная матрица) не более чем за п итераций. Однако и через десять лет после появления метода переменной метрики не было опубликовано ни одного доказательства сходимости для более общего случая. Совсем недавно Пауэлл доказал сходимость и оценил скорость сходимости для метода переменной метрики в случае минимизации строго выпуклых функций. Пауэлл был столь любезен, что позволил автору ознакомиться с его еше не опубликованной рукописью [ Ш ], и сейчас мы приведем некоторые из этих новых результатов. [20]
Примером этого является рассматриваемый в следующем разделе метод сопряженных градиентов, где сопряженные векторы образуются из вектор-градиентов. Если функция и ее градиенты определены только численно так, что нет возможности построить матрицу Q, то задача построения множества ( - сопряженных векторов становится более трудной. Этот случай позже в данной главе будет рассмотрен подробно при описании метода сопряженных градиентов и метода переменной метрики. В случав неквадратичной функции метод сопряженных направлений становится итеративным и обычно не заканчивается за п шагов. Неквадратичные функции локально аппроксимируют последовательность квадратичных функций, р-векторы определяются в соответствии с квадратичными аппроксимациями этих неквадратичных функций. Поэтому при функциях, локальные квадратичные аппроксимации которых быстро изменяются от итерации к итерации или для которых матрица Гессе перестает быть положительно определенной, метод сопряженных направлений может не сходиться. [21]
Оптимум имеет место при х1 10, x 2i, z 3 - i. Однако прп х 0 61 п х3 - 1 32 минимум относительно хг не существует, и по этой причине метод Дэвпса, Сваина п Кэмин ( С в а и н, 1964) и метод Пауолла ( 1964) оказываются nejiaooTO - способнымп. Предположите, что положение минимума на выбранном направлении не определяется точно. Как это повлияет на поведение метода Ньютона - Рафсона, метода сопряженных градиентов и метода переменной метрики. [22]
Поскольку методы сопряженных направлений за / С шагов имитируют один шаг метода Ньютона - Рафсона, они, вообще говоря, обладают квадратичной скоростью сходимости. Однако это их свойство проявляется лишь в достаточной близости к экстремальной точке. В случае расчета стабильных структур использование известной структурной информации позволяет достаточно хорошо выбирать начальное приближение. Интересной особенностью градиентных методов сопряженных направлений является их эквивалентность в случае выпуклой квадратичной функции [234], когда они приводят к одной и той же последовательности сопряженных направлений. Но для произвольных функций, особенно вблизи точек перегиба, разные методы приводят к разным результатам. Наибольшей устойчивостью, по-видимому, обладают методы переменной метрики, но в задачах с очень большим числом переменных необходимость работы с матрицей высокого порядка может приводить к затруднениям; тогда следует пользоваться более простыми методами параллельных касательных или сопряженных градиентов. Предварительно полезно улучшить начальное приближение с помощью метода скорейшего спуска. [23]