Локальные методы спуска

ЛОКАЛЬНЫЕ МЕТОДЫ СПУСКА [c.65]

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

Интересным с практической точки зрения является, очевидно, отыскание не любого, а наиболее глубокого из локальных минимумов, называемого глобальным. Легко понять, что если в качестве начального приближения выбрана точка то процесс спуска, приведет нас в точку локального минимума. Поскольку в окрестности точки локального минимума значение функции возрастает при движении в любую сторону, то метод спуска не позволяет улучшить полученное решение. [c.308]

Клименко и Каневец [79] высказали соображение, что в таком случае метод спуска можно применять не ко всей области изменения независимых переменных, а к отдельным подобластям, в каждой из которых содержится лишь по одному локальному минимуму. Однако разбить многомерное пространство на такие подобласти чрезвычайно сложно и какие-либо универсальные рекомендации на этот счет отсутствуют. [c.310]

Важное достоинство метода наискорейшего спуска — его абсолютная сходимость. Этот метод рекомендуется применять для уточнения решения тогда, когда вычисления по другим итерационным методам расходятся. Рассматриваемый метод можно использовать и для первоначального отыскания корней уравнений (III.I), взяв в качестве исходных данных произвольные числа. Однако в этом случае вместо решения системы могут получиться значения, при которых функция Ф (х) имеет относительный экстремум. Отметим, что это может случиться при использовании любого локального метода оптимизации. [c.72]

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

Описанные выше локальные методы градиента и наискорейшего спуска малоприменимы для минимизации функций, имеющих овраги . Действительно, рассмотрим, например, использование метода градиента для минимизации функции, линии уровня которой изображены на рис. 23. Пусть закон изменения коэффициента пропорциональности Ш дается формулой (111,13) и спуск привел в точку Л1- Направление вектора-градиента перпендикулярно касательной к линии уровня в данной точке. Поэтому в результате шага по направлению антиградиента следующей точкой спуска может оказаться точка А а, расположенная на другом склоне оврага , в которой функция принимает большее значение, чем в точке А х- Вследствие этого [см. формулу (П1,13)] коэффициент Ш поделится на два, хотя изображающая точка находится далеко от минимума. Такая ситуация может повториться несколько раз в результате шаг сделается достаточно малым и поиск либо остановится в соответствии с критерием (П1,12) далеко от минимума, либо продолжится с очень малой скоростью. [c.73]

При решении задачи (VI, 17) необходимо искать глобальный минимум. Область G выбирается так, чтобы решение задачи (VI, 17) было в каком-то смысле проще решения задачи (V,15). Так например, если G — невыпуклая область, то задача (VI, 15) может иметь несколько минимумов и для ее решения необходимо использовать сложные нелокальные методы спуска. Если в качестве G взять выпуклую область, то для решения задачи (VI, 17) можно воспользоваться хорошо разработанными методами локального спуска. [c.197]

Поиск точки локального экстремума (минимизация) целевой функции <р( ,а,Р) реализуется методом спуска по координатам. [c.107]

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

Преимущества градиентного метода оптимизации по сравнению с методом случайного поиска возрастают в случае организации процесса спуска с переменным рабочим шагом. Для этого случая в процессе случайного поиска среднее приращение функции 3(Х) на один расчет в 2л/(и + 1) раз меньше, чем при градиентном методе. Напомним, что п — число оптимизируемых параметров X. Указанные результаты сопоставления детерминированного и случайного способов поиска, естественно, полностью справедливы только для условий выполнения расчетов [56]. Тем не менее, они позволяют сделать вывод о нецелесообразности применения метода случайного поиска для оптимизации непрерывно изменяющихся параметров адсорбционных установок, т. е. там, где возможно использование детерминированных методов направленного поиска (градиентного и др.). Вместе с тем принцип случайного поиска обладает важными преимуществами во-первых, алгоритмы, его реализующие, менее чувствительны, чем детерминированные методы, к наличию неглубоких локальных минимумов, и, во-вторых, некоторые алгоритмы случайного поиска позволяют определить точку абсолютного минимума. [c.136]

Для преодоления неглубоких локальных минимумов может быть использована одна из модификаций градиентного метода — метод тяжелого шарика [61], в котором при определении координат очередной точки в процессе спуска кроме вектора текущей точки и градиента минимизируемой функции в ней учитываются также значения этих величин в одной или нескольких предшествующих точках. Аналогичный результат обеспечивает применение метода сглаживания . В этом методе выражение минимизируемой функции 3 сглаживается таким образом, чтобы процесс дальнейшего поиска минимума функции 3 одним из обычных методов оказался малочувствительным к неглубоким локальным минимумам. Отыскание абсолютного минимума возможно также путем применения несколько видоизмененного метода покоординатного спуска. Модернизация состоит в том, что спуск по каждой координате производится не до локального, а до абсолютного минимума. Заметим, что определение абсолютного минимума одномерной функции — задача разрешимая. [c.154]

Если применить для минимизации таких многоэкстремальных функций метод градиента или наибыстрейшего спуска, то поиск может окончиться в одном пз локальных минимумов, если начальная точка не лежит в области притяжения [c.71]

Система дифференциальных уравнений (3.128) решается численно с использованием метода локальной линеаризации [140] по процедуре, предложенной в работе [21]. Очевидно, что на каждом шаге линеаризации движение происходит не по траектории наискорейшего спуска, а по близкой к ней траектории. Поэтому при решении линейной системы дифференциальных уравнений можно следить не за аппроксимацией правой части исходного уравнения дифференциального спуска, а лишь за убыванием функционала. [c.87]

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

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

При решении обратной кинетической задачи использовался метод поиска экстремума, основанный на линейной аппроксимации системы уравнений градиентного спуска, развитый в работе [21]. Для расчета производных по параметрам с использованием метода локальной линеаризации решалась расширенная система уравнений химической кинетики (5.64), (5.66). [c.168]

Все остальные методы локальны и уточняют положение какого-то минимума, который иногда может не быть глобальным. Их успешно применяют лишь в случае, когда известно достаточно хорошее приближение к структуре исследуемой молекулы. Это методы поочередного уточнения параметров, наибыстрейшего спуска и др. Наиболее распространен среди них метод минимизации функционала (6.15) по схемам Ньютона—Гаусса и Ньютона—Рафсона. При этом после разложения в ряд Тейлора выражения (6.15) для 8М(з) и пренебрежения всеми членами, начиная с квадратичного, возникает система линейных уравнений относительно искомых параметров. Эту систему решают известными методами, что позволяет, применяя итерационную процедуру, уточнять значения структурных параметров. Достоинством данного метода наряду с уточнением геометрических параметров является возможность оценить величину случайной ошибки при их определении. [c.150]

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

Для решения системы уравнений (IX, 146) можно использовать любой метод локального спуска, если с помощью уравнений (IX, 146) составить целевую функцию вида [c.528]

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

Достоинство метода покоординатного спуска — простота реализации. Сходимость процесса зависит от вида целевой функции и от выбора стартовой точки. Недостаток — медленная сходимость процесса при неудачном выборе стартовой точки и возможность получить локальный экстремум. Последнее обстоятельство относится к большинству методов оптимизации. Поэтому рекомендуется выполнить решение задачи оптимизации несколько раз из разных стартовых точек. [c.404]

Использование методов быстрейшего спуска в задачах оптимизации ректификационных установок, затруднено из-за наличия функциональных ограничений а переменные. Кроме того, эти методы обеспечивают определение только локального оптимума. Для проверки того, что найденный оптимум является глобальным, необходимо проводить специальное расчетное исследование. [c.126]

Для нахождения локальных минимумов ф и ф2 предлагается релаксационная модификация метода быстрейшего спуска. Сущность метода заключается в последовательном движении по отдельным независимым переменным с некоторым шагом А (в обоих направлениях — положительном и отрицательном) до нарушения условий (У,16) — (У,20) или до получения положительного приращения функции ф. Когда указанные нарушения возникают по всем переменным, производится дробление шага движения А. Поиск оптимума заканчивается после достижения достаточно малого шага. Логическая схема поиска приведена на рис. 28. [c.144]

Ввиду того, что методом быстрейшего спуска находят только локальный минимум, в задачах подобного типа необходимо осуществлять проверку на наличие нескольких локальных минимумов. В данном случае эта проверка осуществлялась двумя способами [c.156]

Приведем некоторые соображения о сходимости метода. Хотя в предлагаемой схеме производится сравнение большого числа вариантов, сохраняется возможность попадания в какую-нибудь точку локального минимума, если таковые существуют и обладают достаточно большой областью притяжения. Однако эта опасность значительно меньше, чем в схемах быстрейшего спуска. [c.207]

Если критерий в допустимой области и обладает одним максимумом, в общем случае трудно сказать, имеет ли один из этих методов преимущество перед другим с точки зрения скорости сходимости. По-видимому, дело обстоит иначе, когда критерий Q имеет в допустимой области несколько локальных максимумов. Здесь преимущество может оказаться на стороне метода Черноусько и Крылова. Действительно, если в методе спуска использовать какой-либо локальный метод, то он может застрять в локальном максимуме. Поэтому здесь надо применять глобальный метод. Таким образом, в данном случае приходится искать глобальный максимум функции Нг переменных. [c.114]

Локальные методы поиска можно организовать так, чтобы дви- я епие изображающей точки М на плоскости (х , х ) совершалось по некоторой кривой Мд, Afj, М .. . (рис. П-32, д). Такие усовершенствованные методы (методы наискореишего спуска и метода градиента) были описаны выше. [c.174]

Этот метод, предложенный Дэвидоном [146] и затем развитый в работе Флетчера и Поуэлла [151], является итерационным методом спуска для нахождения локального минимума функции нескольких переменных в виде квадратичного полинома. При этом оптимум функции ищется в направлении, которое не является направлением наискорейшего спуска (за исключением первой итерации), а является направлением, параметры которого вычисляются с использованием информации о характере поверхности, получаемой на предыдущей итерации. Метод заключается в следующем. [c.175]

Локальные методы поиска можно организовать так, чтобы движение изображающей точки М на плоскости (xi, Х2) совершалось по некоторой кривой Mo,Mi, M ,. .. (рис. П-20, (9). Такие усовершенствованные методы (методы наискорейшего спуска и метод градиента) были описаны выше. Методы оптимизации химических реакторов изложены в книге Г. М. Островского и Ю. М. Волина [c.146]

Из методов этого класса наилучшим образом себя зарекомендовали некоторые модификации случайного поиска и метод Розенброка, хотя последний значительно уступает градиентным методам, например методу Ньютона или Дэвидона — Флетчера — Пауэлла [82, 95]. Самый большой недостаток прямых методов — их исключительная чувствительность к заданию начальных условий. Удачное задание начального приближения — это и есть такое задание, которое ведет к спуску именно в инфинум (3.157), а не к одному из локальных минимумов (3.156). В принципе это обстоятельство является отрицательным, затрудняя практическое решение, однако в методе случайного поиска именно оно используется для суждения о характере минимума. [c.221]

Следующим достаточно эффективным методом направленного поиска оптимума функции (со. Го, Ию,. . . , с, Т, к f, v , Р,. . .) является метод покоординатного спуска (метод Гаусса—Зейделя). Суть этого метода заключается в минимизации (максимизации) функции сначала по одному параметру, затем по второму и т. д. Основное преимущество перечисленных методов направленного поиска заключается в направленности поиска оптимума, что позволяет заметно снизить число вариаптов перебора по сравнению с перебором вариантов в методах слепого поиска. Среди недостатков методов направленного поиска следует выделить один — основной— возможность нахождения только локального оптимума или особой точки типа седловой. [c.362]

Химическая очистка сточных вод производится перед их подачей в систему оборотного водоснабжения, а также перед спуском их в водоем или городскую канализащюнную сеть. Кроме того, указанный метод применяется для пр арительной очистки сточных вод перед биологической или физико-химической очисткой, а также в системах локальной очистки производственных сточных вод. Химическая обработка находит применение и как метод глубокой очистки сточных вод с целью их дезинфекции или обесцвечивания. [c.111]

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

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