Cтраница 1
Квазиньютоновские методы могут оказаться здесь предпочтительнее в силу их значительно более быстрой сходимости. При этом они требуют вычислений функции не больше, чем градиентные методы, а добавляется только процедура обращения матрицы, которую легко осуществить, решая систему уравнений. [1]
Квазиньютоновские методы можно применять для решения задач безусловной минимизации функций, аналитические значения градиентов которых не поддаются вычислению. [2]
Квазиньютоновские методы называют также методами переменной метрики. Это название объясняется тем, что любая симметрическая положительно определенная матрица Hf - задает скалярное произведение ( и, v) k ( Н и, v) и связанную с ним метрику. [3]
Квазиньютоновские методы являются эффективным средством решения задач безусловной оптимизации. Их отличает высокая скорость сходимости, в то же время при реализации квазиньютоновских алгоритмов не приходится выполнять такие трудоемкие операции, как вычисление матрицы вторых производных или обращение матрицы. Однако при большой размерности пространства необходимость хранения и пересчета на каждом шаге матриц Hk обусловливает высокие требования к объему занимаемой памяти ЭВМ. Этот недостаток не присущ изучаемому в следующем параграфе методу сопряженных градиентов. [4]
Решение этой системы квазиньютоновскими методами ( в частности методом QNM) возможно в случае использования в качестве начальной оценки матрицы Якоби его разностной аппроксимации. [5]
С нашей точки зрения, квазиньютоновские методы с применением стратегии активного набора эффективнее при решении общих задач с линейными ограничениями, чем методы, рассмотренные в этом разделе. Причина в том, что из-за частой смены активных ограничений не удается построить хорошую квадратичную аппроксимацию целевой функции. [6]
На практике поэтому используют так называемые квазиньютоновские методы, в которых на основе имеющейся информации о значениях функции, или также и о значениях производных, определяется приближенная матрица G или G 1, или же используется алгоритм, который позволяет за конечное число шагов минимизировать квадратичную функцию. При этом обычно используются процедуры, которые позволяют строить так называемые сопряженные направления. Можно показать, что последовательная минимизация выпуклой квадратичной формы вдоль последовательности К линейно независимых сопряженных направлений ( где К - размерность пространства координат q) определяет точный минимум квадратичной формы. Таким образом, К шагов подобных алгоритмов имитируют один шаг метода Ньютона - Рафсона. [7]
Ко второй группе относятся: метод Ньютона, методы оптимизации с разреженными матрицами Гессе, квазиньютоновские методы, метод Гаусса-Ньютона, метод Левенберга-Маркардта. [8]
Аналогично тому, как было сделано при разработке квазиньютоновских методов решения систем нелинейных уравнений, рассмотрим квазиньютоновские методы 1-го рода, в которых матрицы Bt, Hj будут удовлетворять соотношениям ( II, 25) ( II, 31) соответственно, и квазиньютоновские методы 2-го рода, в которых матрицы BI, HI будут удовлетворять соотношениям ( II, 29), ( II, 32) соответственно. [9]
Поскольку трудно предположить, что такие программы будут созданы в ближайшие годы, основное применение найдут квазиньютоновские методы первого порядка. Как мы уже отмечали, эффективность этих методов с увеличением размерности задач должна уменьшаться. Однако, есть обстоятельство, которое позволяет существенно повысить эффективность квазиньютоновских методов: при оптимизации больших систем либо сама структура ХТС приводит к тому, что гессиан целевой функции имеет сильно разреженную структуру ( большое число нулевых элементов), либо же с помощью специального приема удается получить модифицированный критерий, гессиан которого будет иметь сильно разреженную структуру. В связи с этим рассмотрим квазиньютоновские методы минимизации функций, имеющих сильно разреженные гессианы. [10]
Трудности, связанные с применением метода Ньютона, привели к разработке группы методов, которые называются квазиньютоновскими методами переменной метрики или градиентными методами с большим шагом. Сущность их заключается в аппроксимации матрицы Гессе или обратной к ней матрицы таким образом, чтобы ограничиться только использованием первых производных. [11]
В связи с этим, если методы простой итерации DEM, GDEM сходятся меньше, чем за п итераций, переходить к квазиньютоновским методам невыгодно. С другой стороны, интересно рассмотреть возможность и целесообразность совместной работы различных методов. При этом, конечно, соединение методов не должно быть чисто механическим, но при их соединении информация, накопленная в результате работы одного метода, должна использоваться в другом методе. [12]
Аналогично тому, как было сделано при разработке квазиньютоновских методов решения систем нелинейных уравнений, рассмотрим квазиньютоновские методы 1-го рода, в которых матрицы Bt, Hj будут удовлетворять соотношениям ( II, 25) ( II, 31) соответственно, и квазиньютоновские методы 2-го рода, в которых матрицы BI, HI будут удовлетворять соотношениям ( II, 29), ( II, 32) соответственно. [13]
А - симметрическая положительно определенная матрица размера п х п, за один шаг. Квазиньютоновские методы позволяют найти минимум квадратичной функции за п шагов. На стремлении минимизировать квадратичную функцию за конечное число шагов основана идея методов сопряженных направлений. [14]
Приведенные в таблице методы позволяют решить широкий ряд задач для взаимосвязанных систем разделения, в том числе для систем, приведенных на рис. 5.2, однако при этом авторы не выделяют те задачи, для которых предлагаемые ими методы не работают. Общеизвестно, что метод Ньютона и квазиньютоновские методы могут не сходиться при решении задач разделения из-за сильных неидеальностей температурного профиля или равновесных соотношений. Поэтому в [16] ( см. табл. 5.1) предпринята попытка объединить стратегию блочной релаксации с методом Ньютона для увеличения области сходимости, что однако не позволило решить все проблемы. [15]