Cтраница 2
В этом разделе речь пойдет о задачах двух типов; когда градиент целевой функции трудно вычислить и когда его просто нет. Задачи малой размерности, относящиеся к первому типу, лучше всего решать дискретными квазиньютоновскими методами ( разд. Однако в силу причин, рассмотренных в разд. [16]
Соответствующие методы, в которых матрицы Blt HI удовлетворяют этим условиям, будут называться квазиньютоновскими методами 1-го рода. [17]
Обратное распространение ошибки позволяет во много раз сократить вычислительные затраты на расчет градиента по сравнению с расчетом по определению градиента. Применимы также квазиньютоновские методы, в которых строится матрица вторых производных Н ( гессиан) на основе нескольких последовательных значений градиента. [18]
Наибольшей эффективностью поиска характеризуются методы второго порядка. Однако они требуют вычисления матрицы Гессе, что значительно затрудняет или даже делает невозможным их использование для решения конкретных задач оптимизации. В связи связи были разработаны квазиньютоновские методы, в которых осуществляется аппроксимация матрицы Гессе. [19]
Из них следует, что на практике скорости сходимости этих методов почти не зависят от значений h и близки к идеальным, если, конечно, эти значения выбираются не совсем бестолковым образом. Вообще же упомянутые результаты позволяют утверждать, что ньютоновские методы с аппроксимацией матрицы Гессе надежнее, чем квазиньютоновские алгоритмы, и будут сходиться в более широком классе задач, в частности в задачах с очень плохой обусловленностью матрицы Гессе. Правда, по отношению к квазиньютоновским методам у них есть один недостаток: для построения оценок вторых производных в них требуется на вычислений градиента больше; однако, если матрица Gft слабо заполнена и имеет специальную структуру, количество вычислений градиента можно существенно сократить ( см. гл. [20]
К первой относятся метод простой итерации и его модификации, а также методы, ускоряющие сходимость простой итерации ( методы DEM [22], GDEM [23]); ко второй - метод Вольфа и его модификации [ 3, с. Здесь мы рассмотрим только метод Ньютона и квазиньютоновские методы решения систем нелинейных уравнений, идейно очень близкие к методу Ньютона и квазиньютоновским методам оптимизации. [21]
Если схема корректировки в (5.2.19) излишне сложна, то способ выбора направления спуска слишком прост. Значительно более совершенные алгоритмы получаются с использованием приведенных градиентов в комбинации с квазиньютоновскими методами и методами сопряженных направлений. Два из них, рассчитанные на задачи с линейными ограничениями, представлены в предыдущей главе. Оба опираются на метод Флетчера - Ривза. Аналогичный алгоритм, но для задач с нелинейными ограничениями подробно описан в цитированной выше работе Абади и Кар-пентье. [22]
Рост сложности и размерности этих задач, особенно задач 2-го класса, требует применения наиболее эффективных ( как по быстродействию, так и по надежности определения наилучшего решения) методов оптимизации, позволяющих решать эти задачи в реальное время. В последнее время такие методы получили большое развитие, особенно это относится к квазиньютоновским методам, и к методам оптимизации больших систем. Основное внимание в книге уделяется этим методам и опыту их использования для оптимизации ХТС. Вместе с тем комбинаторная природа задач синтеза ХТС требует применения методов дискретной математики, использованию которых также уделено большое внимание. [23]
К первой относятся метод простой итерации и его модификации, а также методы, ускоряющие сходимость простой итерации ( методы DEM [22], GDEM [23]); ко второй - метод Вольфа и его модификации [ 3, с. Здесь мы рассмотрим только метод Ньютона и квазиньютоновские методы решения систем нелинейных уравнений, идейно очень близкие к методу Ньютона и квазиньютоновским методам оптимизации. [24]
Поскольку трудно предположить, что такие программы будут созданы в ближайшие годы, основное применение найдут квазиньютоновские методы первого порядка. Как мы уже отмечали, эффективность этих методов с увеличением размерности задач должна уменьшаться. Однако, есть обстоятельство, которое позволяет существенно повысить эффективность квазиньютоновских методов: при оптимизации больших систем либо сама структура ХТС приводит к тому, что гессиан целевой функции имеет сильно разреженную структуру ( большое число нулевых элементов), либо же с помощью специального приема удается получить модифицированный критерий, гессиан которого будет иметь сильно разреженную структуру. В связи с этим рассмотрим квазиньютоновские методы минимизации функций, имеющих сильно разреженные гессианы. [25]
При этом решаются следующие задачи: 1) в схеме выделяются комплексы - совокупности блоков охваченных обратными связями [ 3, с. Обычно совокупность итерируемых переменных ( II, 5) выбирается из условия, чтобы их суммарная размерность была минимальной. Положительные и отрицательные стороны такого выбора переменных ( II, 5) обсуждаются в работе [ 3, с. Отметим здесь, что применительно к квазиньютоновским методам это более или менее оправдано, поскольку, как мы уже отмечали, можно считать при применении этих методов, что число итераций растет пропорционально размерности системы нелинейных уравнений. [26]
Заметим, что, может быть, даже не надо будет улучшать точность этих оценок - достаточно, чтобы тип ошибки был приемлем. Тут есть некая аналогия с аппроксимацией матрицы Гессе в квазиньютоновских методах: при заданной величине ошибки надо, чтобы аппроксимация матрицы Гессе была положительно определена. Заметим, что, если спроектированная матрица Гессе функции Лагранжа положительно определена, но почти вырождена, методы функции Лагранжа особенно чувствительны к ошибкам в множителях Лагранжа, поскольку эти ошибки могут привести к неопределенности спроектированной матрицы Гессе. [27]
Существует ( Шуберт ( 1970)) квазиньютоновский метод решения систем нелинейных уравнений со слабо заполненными матрицами Якоби, в котором пересчитывается только часть элементов аппроксимирующих матриц, а остальные тождественно равны нулю. Поправки в его формуле пересчета имеют полный ранг. Мы, однако, до сих пор не встретили ни одной работы на эту тему и сами считаем, что методы такого сорта были бы слишком громоздкими, чтобы сохранить превосходство, которым обладают обычные квазиньютоновские методы в случае малой размерности. [28]
Таким образом, метод сопряженных градиентов обладает высокой скоростью сходимости. В то же время его трудоемкость сравнительно невелика. Так, например, метод (3.22) по трудоемкости и памяти лишь незначительно превосходит метод наискорейшего спуска. Все это позволяет отнести метод сопряженных градиентов к числу наиболее эффективных алгоритмов первого порядка. Вычислительная практика показывает, что этот метод незначительно уступает по эффективности квазиньютоновским методам; в то же время он предъявляет меньшие требования к объему занимаемой памяти ЭВМ. Следует отметить, что в настоящее время построено и применяется много различных вариантов метода сопряженных градиентов. [29]
Поскольку трудно предположить, что такие программы будут созданы в ближайшие годы, основное применение найдут квазиньютоновские методы первого порядка. Как мы уже отмечали, эффективность этих методов с увеличением размерности задач должна уменьшаться. Однако, есть обстоятельство, которое позволяет существенно повысить эффективность квазиньютоновских методов: при оптимизации больших систем либо сама структура ХТС приводит к тому, что гессиан целевой функции имеет сильно разреженную структуру ( большое число нулевых элементов), либо же с помощью специального приема удается получить модифицированный критерий, гессиан которого будет иметь сильно разреженную структуру. В связи с этим рассмотрим квазиньютоновские методы минимизации функций, имеющих сильно разреженные гессианы. Также как и в главе III мы здесь рассмотрим квазиньютоновские методы 1-го и 2-го рода. [30]