Квазиньютоновские методы

В методах, которые рассмотрены в этой главе, используются свойства квадратичной аппроксимации минимизируемой функции, однако они не требуют вычисления матрицы вторых производных. Мы здесь обсудим два тина методов — методы сопряженных направлений и методы переменной метрики (квазиньютоновские методы). Последнее название обусловлено следующими причинами. [c.33]

Квазиньютоновские методы минимизации квадратичных функций [c.62]

Рассмотренные выше методы переменной метрики предполагают нахождение точного минимума функции на каждом направлении поиска. Однако поиск с высокой точностью минимума на каждом направлении связан с вычислением значений функции в достаточно большом числе точек, что приводит к значительному увеличению затрат времени ЭВМ на решение задачи. Поэтому в последнее время был развит ряд поисковых методов, не требующих точного линейного поиска. Упомянутые методы можно разделить на две группы. К первой относятся методы, в которых, несмотря на отсутствие точной одномерной минимизации, минимум квадратичной функции достигается за конечное число шагов. Ко второй группе относятся методы, не обладающие указанным свойством. Здесь рассмотрен только один представитель последней группы методов (см. с. 113). Основное же внимание уделено первой группе методов, которую удобно разбить на две подгруппы методы сопряженных направлений без точного линейного поиска и квазиньютоновские методы без точного линейного поиска. [c.102]

Квазиньютоновские методы без точного линейного поиски [c.106]

Таким образом, успех использования квазиньютоновских методов и методов сопряженных направлений для решения задач большой размерности будет существенно зависеть от эффективности вычисления частных производных целевой функции (точности и трудоемкости их нахождения). Отсюда еще большую роль для решения таких задач сыграет применение сопряженного процесса для получения этих производных. [c.260]

Рост сложности и размерности этих задач, особенно задач 2-го класса, требует применения наиболее эффективных (как по быстродействию, так и по надежности определения наилучшего решения) методов оптимизации, позволяющих решать эти задачи в реальное время. Гибкость и универсальность поисковых методов оптимизации, относящихся к классу численных методов нелинейного программирования, сделали их основным средством решения задач 1-го класса и существенной частью алгоритмов решения задач 2-го класса. В последнее время такие методы получили большое развитие, особенно это относится к квазиньютоновским методам, и к методам оптимизации больших систем. Основное внимание в книге уделяется этим методам и опыту их использования для оптимизации ХТС. Вместе с тем комбинаторная природа задач синтеза ХТС требует применения методов дискретной математики, использованию которых также уделено большое внимание. [c.5]

Основной идеей квазиньютоновских методов является объединение этапов сбора информации и поиска. Причем информация, которую получают во время поиска, используется для построения аппроксимации В] матрицы Якоби Jj либо аппроксимации Н] матрицы, обратной к матрице Якоби. По аналогии с соотношениями (I, 15), (II, 16) направление поиска определяется либо решением системы линейных уравнений [c.31]

В дальнейшем соотношения (II, 25), (II, 31) будем называть квазиньютоновскими условиями 1-го рода. Соответствующие методы, в которых матрицы В,-, Я удовлетворяют этим условиям, будут называться квазиньютоновскими методами 1-го рода. Соотношения (11,29), (11,32) будем называть квазиньютоновскими условиями 2-го рода, а соответствующие методы — квазиньютоновскими методами 2-го рода. Будем говорить, что квазиньютоновский метод обладает глубиной памяти q, если в (/г + 1)-й точке матрицы B +i, Яй+i должны удовлетворять квазиньютоновским условиям в q предыдущих точках [c.33]

Таким образом, квазиньютоновские методы 1-го рода являются методами с глубиной памяти, равной 1, и для построения матрицы Якоби (обратной матрицы Якоби) в (/ 4- 1)-й точке они используют только информацию в данной точке [векторы Sj, у в соотношениях (11,25), (11,31)]. В то же время для построения матриц Bj, Н] методы с глубиной памяти q используют и предыдущую информацию. Методы 2-го рода отличаются тем, что глубина памяти q увеличивается в них на 1 на каждом ш аге (при i < п). [c.33]

Для вывода квазиньютоновских методов здесь будут использованы вариационные методы и аппарат псевдообратных матриц. [c.34]

Квазиньютоновские методы 1-го рода [c.34]

Квазиньютоновские методы 2-го рода [c.41]

Отметим еще один очень возможный способ выбора параметров С . Как уже указывалось (см. с. 37) полезным оказался принцип наименьшего изменения аппроксимирующей матрицы, на основе которого были получены выражения для матриц Е и D в квазиньютоновских методах 1-го рода. В данном случае вид матриц и D известен. Его легко получить из формул (И, 101), (II, 103). Произвольные константы с в этих формулах можно попытаться определить, исходя из этого, принципа. [c.45]

Решение этой системы квазиньютоновскими методами (в частности методом QNM) возможно в случае использования в качестве начальной оценки матрицы Якоби его разностной аппроксимации. [c.60]

Последовательный подход. Вначале рассмотрим эту проблему применительно к последовательному подходу. Здесь уменьшение размерности задачи расчета ХТС достигается методами структурного анализа [47]. При этом решаются следующие задачи 1) в схеме выделяются комплексы — совокупности блоков охваченных обратными связями [3, с. 33] 2) определение внутри каждого комплекса оптимальной с точки зрения какого-либо критерия совокупности итерируемых переменных (II, 5). Обычно совокупность итерируемых переменных (II, 5) выбирается из условия, чтобы их суммарная размерность была минимальной. Положительные и отрицательные стороны такого выбора переменных (II, 5) обсуждаются в работе [3, с. 85]. Отметим здесь, что применительно к квазиньютоновским методам это более или менее оправдано, поскольку, как мы уже отмечали, можно считать при применении этих методов, что число итераций растет пропорционально размерности системы нелинейных уравнений. Уменьшаются требования и к размеру памяти, поскольку приходится хранить одну или две матрицы размерности fix/г. При использовании ориентированного на уравнения подхода так же, как и в предыдущем случае определяются комплексы, а внутри комплексов — оптимальные совокупности разрываемых потоков [48 17 18, с. 258]. [c.61]

Параллельный подход. Рассмотрим теперь параллельные методы расчета ХТС применительно к системам (I, 1), (I, 6), или эквивалентной ей системы (II, 4). Непосредственное применение квазиньютоновского метода 2-го рода для решения системы (II, 4) потребует хранения двух (Л/ХЛ )-матриц, а число итераций, когда все модели линейны, будет равно N = тМ. Поскольку обычно N п, на первый взгляд может показаться, что переход к параллельному способу только ухудшит результаты. Однако, как показано ниже, использование особенностей структуры ХТС, а, следовательно, особенностей структуры системы (II, 4) может сделать параллельный метод существенно более эффективным. [c.61]

При построении квазиньютоновских методов желательно учесть как можно больше свойств самой матрицы Якоби. Общим для этих методов является то, что строится аппроксимация самой матрицы Якоби, а не обратной. Это связано с тем, что сама матрица может иметь большое число нулевых и постоянных элементов, в то время как обратная обычно является заполненной, имеющей мало нулевых и постоянных элементов. Идея построения квазиньютоновских методов, учитывающих разреженную структуру систем нелинейных уравнений, состоит в том, чтобы при построении матриц Вг (г = 1, 2,. ..) сохранена была структура самих матриц Якоби, т. е. если некоторый элемент матрицы Якоби равен нулю, то и соответствующий элемент матрицы должен быть равен нулю. То же требование относится к случаю, когда элемент матрицы Якоби является либо легко вычисляемым, либо постоянным. Все дальнейшее изложение будет вестись применительно к параллельному методу расчета ХТС. [c.62]

Квазиньютоновские методы 1 рода для решения разреженных систем нелинейных уравнений [c.62]

Для ХТС с блоками, описываемыми нелинейными моделями, интересно выяснить, что лучше для разреженной системы нелинейных уравнений (I, 1), (I, 6) провести структурный анализ и свести дело к решению системы нелинейных уравнений (П, 8) и далее применять обычные квазиньютоновские методы, или же подойти к ней, как к системе с разреженной структурой и применять специальные квазиньютоновские методы, а структурный анализ применять для сжатия линейной системы (II, 22). [c.66]

Квазиньютоновский метод с памятью для решения неразряженных нелинейных систем был рассмотрен ранее. При этом элементы матрицы Е находились как решение задачи (11,82), (11,83). В данном случае элементы матрицы Е будут находиться так же, но при наличии дополнительных условий (11,162). По аналогии с соотношениями (11,168) введем вектор-строку х ( ) с элементами 5 (О , т, причем сделаем это следующим образом [c.66]

Квазиньютоновский метод с блочной аппроксимацией [c.67]

Используем теперь ту же самую гипотетическую схему, что и при рассмотрении свойства 3, для сравнения последовательного подхода с параллельным, при котором используется квазиньютоновский метод с блочной аппроксимацией. В дальнейшем будем называть этот подход параллельным методом. При использовании последовательного метода в сочетании с любым квазиньютоновским методом 2-го рода потребуется п шагов (здесь п — суммарная размерность разрываемых потоков) для определения решения системы (II, 3), (I, 6) при этом потребуется 2п ячеек памяти для хранения матриц Я, и /С . При параллельном методе, как мы видели, для определения решения системы (II, 3), (I, 6) потребуется т шагов т — размерность одного потока). Это очень интересный факт. В данном случае число итераций определяется не общей размерностью системы, которая может быть очень большой (в данном случае она равна 2Ыт), а максимальной размерностью потока (блока). Причем при усложнении структуры ХТС (увеличение числа обратных связей) величина п может существенно возрасти, что в свою очередь приведет к увеличению числа итераций при использовании последовательного метода. В то же время при параллельном подходе число итераций будет определяться только размерностью т одного потока, независимо от сложности структуры ХТС. Конечно, эти выводы верны только для линейных систем, однако подобное свойство рассмотренных методов может проявиться и при решении систем, близких к линейным. Параллельный метод потребует 2Ыт ячеек памяти, поскольку в каждом блоке для определения необходимо использовать две матрицы см. выражения (II, 103), (II, 104). Отсюда ясно, что при т < п и применении параллельного метода число итераций будет меньше. При этом параллельный метод будет требовать меньшего объема памяти,I если ту 2М < п. [c.70]

Итак, квазиньютоновские методы, как правило, имеют невысокую скорость сходимости, если в качестве начального приближе- [c.71]

В виде примера рассмотрим последовательное применение метода простой итерации и квазиньютоновского метода. Поскольку вначале квазиньютоновский метод часто дает плохую сходимость, в случае, когда метод простой итерации обеспечивает сходимость, может оказаться выгодным вначале на первых п шагах, использовать метод простой итерации, но на каждом шаге векторы и / использовать для преобразования матрицы Я (или в соответствии с той или иной формулой квазиньютоновского метода, например, по формулам (П, 107), (П, 108). При i = п надо переходить на квазиньютоновский метод, причем в качестве начального приближения к матрице Яо (или o) использовать полученную к этому шагу матрицу Я,. Аналогично может оказаться выгодным, применять метод DEM вначале, а затем переходить на квазиньютоновский метод. [c.72]

Метод Вольфа часто обеспечивает быструю скорость сходимости вначале и медленную в конце. В этом случае также может оказаться полезным сначала применять метод Вольфа, а потом переходить на квазиньютоновский метод. Причем поскольку на г-том (г > п) шаге в методе Вольфа [3, с. 35 ] имеются п предыдущих значений fj, [c.72]

Мешков В.И., Синица В.А. Применение квазиньютоновских методов дпя расчёта слсжных химико-технологических процессов / Нефтепереработка и нефтехимия, вып.9,1978, с.213. [c.109]

Приведенная выше теорема (см. с. 81) утверждает, что квазиньютоновские методы минимизации, которые отвечают р = 1 в семействе Хуан, га (П. 174), дают одну и ту же последовательность точек гг при условии, что а, = а с выбором того же самого (локального) минимума на каждом направлении, каждое Я,- определено и HJgi ф О для всех U Тогда доказанный выше результат о сверхлинейной скорости сходимости х, в случае метода D FP справедлив для любого квазиньютоновского метода минимизации из семейства (11,174), в частности, для метода BFS (11,198). [c.283]

Методы решения систем нелинейных уравнений можно р азбить на три группы. К первой относятся метод простой итерации и его модификации, а также методы, ускоряющие сходимость простой итерации (методы DEM [22], GDEM [23]) ко второй — метод Вольфа и его модификации [3, с. 35 1, с. 84] к третьей — квази-ньютоновские методы. Здесь мы рассмотрим только метод Ньютона и квазиньютоновские методы решения систем нелинейных уравнений, идейно очень близкие к методу Ньютона и квазиньютоновским методам оптимизации. В дальнейшем будем говорить, что метод обладает р-шаговым свойством линейного окончания, если он обеспечивает решение системы линейных уравнений при числе шагов, не превышающем р. [c.29]

В этом и следующих разделах приведены результаты численных расчетов на ЭВМ стационарных режимов ряда химико-технологических процессов. При проведении расчетов использовались, в основном, квазиньютоновские методы решения систем нелинейных уравнений ( ЫМ, определяемый преобразованием (II, 101) и Вгоу-кеп [см. преобразование (11,49)1. В соответствующих алгоритмах каждая следующая итерационная точка в пространстве независимых [c.46]

Обсуждение результатов расчета. Для расчета стационарного режима схема приведена к условно разомкнутому виду. Размерность вектора разрываемых потоков равна 9. На рис. 8 места разрыва потоков обозначены римскими цифрами. Элементами вектора для потока I являются покомпонентные расходы и температуры, для потоков II—IV — температуры. Были использованы методы простой итерации (PRIT), доминирующего собственного значения (DEM), модифицированный метод Вольфа (WOLF), квазиньютоновский метод (QNM), обобщенный метод доминирующего собственного значения (GDEM) [23]. [c.58]

Для определения SI- из уравнения (И, 189) мы можем воспользоваться формулами (II, 103), (II, 104), либо любым другим аналогом формул (II, 90), (II, 91), выписанным для определения матрицы fii+i- После того, как на -том шаге будут определены все необходимо найти приращения AjiI , с помощью которых будут определены следующие приближения для х zJ . Это аналог операции определения Axj с помощью уравнения (II, 11) в методе Ньютона и операции определения Pj из уравнения (II, 22) в обычном квазиньютоновском методе. [c.68]

Первыйслучай. Рассмотрим первый режим решения системы (И, 6). В этом случае, как правило, имеется плохое начальное приближение к решению системы (И, 6). В то же время для хорошей работы квазиньютоновских методов необходимо выполнение следующих условий [c.71]

Справочник химика 21

Химия и химическая технология