Градиентный метод с оврагом

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

Существует большое число модификаций градиентного метода поиска экстремума функций многих переменных, учитывающих искривление поверхности градиента или то, что при попадании на гребень ( овраг ) движение по градиенту оказывается медленным и неустойчивым. Данные о применении этих методов для расчетов равновесных составов имеются в обзорных работах [15—-17]. [c.110]

Метод градиента и его модификации. Как известно, направление наискорейшего убывания функции противоположно вектору градиента в данной точке. На этом основан классический метод градиента в текущей точке поиска вычисляется антиградиент функции и осуществляется продвижение вдоль этого направления с некоторым шагом. Затем снова осуществляется вычисление вектора антиградиента и т.д. Если функция имеет несколько локальных минимумов, то метод градиента обеспечивает сходимость к одному из них. Метод градиента имеет наибольшую скорость сходимости в случае, когда линии уровней минимизируемого функционала имеют вид, близкий к окружностям. В случае "овражного" рельефа метод градиента малоэффективен, так как происходит спуск в овраг и блуждание от одного его склона к другому без существенного продвижения по дну оврага. Вариант градиентного метода, когда на каждом шаге поиска производится одномерная минимизация вдоль выбранного направления, называется методом наискорейшего спуска [7]. [c.163]

Нелокальные методы. Градиентные методы и методы прямого поиска обеспечивают сходимость к одному из минимумов поверхности минимизируемого функционала, однако сравнительно часто возникает ситуация, когда таких минимумов оказывается несколько или поверхность имеет сильно выраженный "овражный" характер. В этом случае минимизация может быть осуществлена методом оврагов [36, 38] или методом случайного поиска [56, 162]. [c.165]

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

Градиентный метод приводит к зацикливанию в овраге. В данной ситуации эффективным оказывается метод оврагов. Из двух исходных точек (д о, Уо) и (дгь уг) определяются два локальных минимума I и 2, т. е. точки, в которых градиентные методы привели к зацикливанию. На прямой, соединяющей локальные минимумы I и 2 на расстоянии, равном расстоянию между ними, определяется точка (л 2, Уг), из нее градиентным методом определяется новый локальный минимум 3. Затем определяется точка (л з, уз) и локальный минимум и т. д. [c.29]

Метод оврагов имеет ряд модификаций. Иногда берут несколько начальных точек a°, a%. .. и проводят экстраполирующий вектор так, чтобы он проходил через наибольшее число точек й, . .., лежащих в овраге . В других вариантах градиентный спуск осуществляют не после каждого овражного шага, а при нарушении неравенства Ф(а ,)<Ф(а ). Этот прием целесообразно применять при слабо искривленных линиях уровня. Все модификации имеют примерно такую же скорость поиска, как и основной метод. [c.228]

Поиск минимума, функции Ф[/г2(7 ), 4(7)] осуществлялся методом оврагов . Вначале производился градиентный спуск из начальных точек а = = [c.267]

Поиск минимума функции Ф по переменным ка, Е осуществлялся градиентным методом. В процессе решения задачи было установлено, что Ф имеет овраги . Для движения по их дну применялся метод оврагов . Частные производные Ф(йо,, Ё) находились по разностной схеме. Решение системы дифференциальных уравнений (XI, 36), (XI. 37) производилось методом Рунге — Кутта с шагом, равным Vie объема реактора. Затраты машинного времени ЦВМ типа М-20 на поиск минимума составляли не менее 1,5—2 ч при достаточно хороших начальных приближениях. Минимальное значение Ф при использовании данных табл. XI. 4 и XI. 5 равно 4,2. [c.306]

Максимум функции Z можно определить градиентным методом с оврагом . Поиск максимума проводился многократно из разных начальных точек с точностью до 5° С. Наибольший локальный максимум был взят в качестве глобального. Наиболее важные данные поиска максимума приведены в табл. 28. [c.206]

Задача решалась градиентным методом с оврагом. Взяты следую-ш,ие исходные данные [c.237]

Выбор шага спуска производится автоматически, в зависимости от угла между последовательными направлениями движения (см. [58], а также стр. 103). Эта модификация метода градиента была использована для определения констант скоростей изомеризации и окислительного дегидрирования бутенов в дивинил [59, 60]. Она применялась также для осуществления градиентных спусков при изучении методом оврагов кинетики радиационного изотопного обмена дейтерия с гидроксильными группами силикагеля [c.95]

Хотя описываемый метод известен сравнительно давно [78] и для простых в кинетическом отношении задач использовался еще в 1950 г. [79[, но вследствие вычислительных трудностей он не находил широкого применения. Лишь с появлением ЭВМ метод нелинейных оценок получил распространение при решении разнообразных задач, в том числе и задач нахождения кинетических параметров [73]. Описанным методом была изучена кинетика целого ряда процессов окисления нафталина [28], изомеризации / -гексапа [80], синтеза аммиака [81], окисления метана [82, 83] и др. [12, 26, 27, 53, 84—88]. Программа этого метода применялась также для замены градиентных спусков в методе оврагов (см. стр. 107). [c.99]

Из приведенных данных видно, что для локализации минимума суммы квадратов отклонений обычным методом оврагов потребовалось три градиентных спуска с общим числом итераций N == = 25. Применяя модифицированный метод оврагов, удалось найти минимум всего за четыре итерации, причем положение минимума определялось несколько точнее. Это легко понять, поскольку в методе нелинейных оценок сумма квадратов отклонений нред- [c.107]

Из точки х +1 производится локальный спуск градиентным методом. Он продолжается до тех пор, пока величина 1 — АШи будет меньше некоторой заранее заданной величины Д, называемой пробой на отношение. В результате спуска получим очередную точку после чего процесс повторяется. Успех поиска во многом зависит от выбора значений /г и А. Пробу на отношение Л обычно берут близкой к 0,9 (при А = 1 происходит спуск в локальный минимум), овражный шаг к должен быть значительно больше градиентного спуска. При больших Л траектория поиска переваливает через большие хребты и горы, при малых к она огибает их большие к приводят к быстрому перемещению по потенциальной поверхности, но при этом возрастает вероятность прозевать глобальный минимум. Игра вычислителя с машиной, заключающаяся в подборе значений /г и А на разных этапах поиска, может привести к нахождению глобального минимума. Примеры применения метода оврагов .--г в конформационном анализе приве-дены в гл. 7. [c.139]

Прямыми поисковыми называют методы, не требующие вычисления частных производных (355(0)/( 05. Градиентные методы основываются на вычислении градиента функции 55(0). Среди прямых поисковых методов укажем прежде всего метод оврагов [122, 123], методы Розепброка [124] и Пауэлла [125, 126]. Метод оврагов , хорошо зарекомендовал себя при решении задач, связанных с оценкой кинетических параметров [107]. Эффективным оказывается также метод случайного поиска [127]. Кстати, методом случайного поиска пользовались при уточнении оценок параметров скорости зародышеобразования и роста кристаллов (см. выше). [c.324]

Все эти трудности резко возрастают при нелинейной зависимости модели от К. В этом случае вопрос о сравнительной простоте минимизации суммы квадратов очень проблематичен. Используя, например, градиентные методы, мы сравнительно быстро приходим к значениям К, достаточно хорошо описывающим эксперимент, т. е. точность описания не превышает погрешности эксперимента. Но в окрестности минимума мы обычно сталкиваемся с оврагом, и начинается медленное движение около минимума, при этом на каждом шагу итерации получаются параметры, которые могут существенно различаться, описывая тем не менее эксперимент. При движении вдоль оврага обычные методы становятся неэффективными, следует привлекать стохастические методы, методы типа с.тучайного поиска [11]. Необходимо, чтобы программы, испо.тьзуемые при поиске минимума, сочетали различные методы. А решение задачи на ЭВМ наиболее целесообразно вести в диалоге человек — машина , что допускает в процессе минимизации переход от одного критерия к другому, от одного алгоритма к другому. Это очень важно, ибо геометрические формы различных критериев могут существенно различаться, и в одной области целесообразнее минимизировать один критерий, в следующей — другой и т. д. [c.87]

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

Опишем здесь еще овражный метод, предложенный И. М. Гель-фандом и М. Л. Цетлиным Вначале выбирают две точки 11° и и , из которых производят спуск на дно оврага градиентным методом (рис. 25), в результате чего находят две точки Л и А . Затем проводят прямую A A в сторону убывания функции 2 в некоторую точку и . [c.74]

Процедура поиска минимума методом оврагов вкратце заключается в следующем из начальной точки поиска осуществляется спуск (обычно каким-либо из градиентных методов) ко дну ближайшего оврага. При этом не требуется особой точности. Затем из какой-либо другой точки в области поиска проводится еще один спуск. Через полученные в результате спусков точки проводится прямая (предполагается, что она аппроксимирует геометрическую форму дна оврага), вдоль которой осуществляется шаг в направлении убывания минимизируемого функционала. Из полученной точки делается еще один градиентный спуск, и через полученную и предыдущую точки опять проводится прямая, вдоль которой также осуществляется продвижение, и т.д. В случае удачного выЬора величины шага при продвижении по оврагу и шага градиентного спуска метод оврагов может быть весьма эффективен при решении ОКЗ [36]. [c.165]

В начале поиска. мини.мальной точки х задаются два начальных приближения х и i , из которых производят спуск с помощью какого-либо градиентного метода, и получают две точки х - на "дне оврага". Пусть, напри.мер. f x " ) < /(х . Тогда следующее Г1риближение находят по формуле [c.25]

Из точки x , которая, вообще говоря, находится на "склоне оврага", производят спуск с помоп1ью градиентного метода и опреде.ляют следуюш ю точку на "дне оврага". Если уже известны приближения х- -, . .., x и /(х - -) < , то из точки [c.25]

Разработано много вариантов градиентного метода, обеспечивающих более быструю сходимость к оптимуму. Можно не определять направление градиента на каждом шаге, а перемещаться вдоль направления г° до тех пор, пока. функция Ф не начнет убывать, или до границы области. Этот вариант носит название метода наискорейшего спуска. Перемещение в пространстве переменных Х], хг,. .., х. может происходить не строго в направлении градиента, а вдоль любого допустимого направления, составляющего с градиентом острый угол (метод Гаусса — Зейделя, метод возможных направлений Зойтендей-ка). Сходимость на поверхностях сложных конфигураций (с хребтами, оврагами и седловыми точками) обеспечивается с помощью специальных алгоритмов [c.23]

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

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