Методы одномерного поиска

Рис. 1Х-17. Одномерный поиск методом золотого сечения .

Метод Гаусса — Зейделя (МГЗ) прост и удобен. В нем многомерный поиск превращается в последовательность одномерных и не делается никаких прощупываний с целью выбора таких одномерных движений, а только перебираются по очереди все направления коорди ат 1Ь Х осей. Ему свойственны недостатки, присущие другим методам спуска. [c.289]

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

Кратко рассмотрим два метода одномерного поиска и три — многомерного. [c.264]

У.3.1. Методы одномерного поиска [c.199]

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

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

Рис, IX-16. Одномерный поиск методом локализации экстремума. [c.505]

Метод Фибоначчи служит для повышения эффективности одномерного поиска. Пусть область поиска экстремума определяется неравенством Ао 0- Для применения метода Фибоначчи должно быть зафиксировано N точек, в которых производится вычисление критерия оптимальности. [c.199]

Методы детерминированного прямого поиска. Методы оптимизации этого класса позволяют определять направление поиска непосредственно по одному или нескольким значениям целевой функции. Самые простые алгоритмы этих методов — прямое обобщение алгоритмов одномерного поиска на многомерный случай. Например, в основе метода покоординатного спуска лежит последовательная минимизация целевой функции по каждой координатной оси с помощью одного из методов, изложенных в разд. У.3.1. [c.204]

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

В табл. 7 приведены результаты сравнения различных методов решения систем уравнений и вариантов модульного подхода к расчету отделения синтеза аммиака. Сравнивались трехуровневый и двухуровневый подходы. В первом случае итерации производились по пяти переменным на верхнем и по пяти переменным на среднем уровне (итерации в итерации). Во втором случае итерации проводились по всем десяти переменным совместно. В обоих случаях итерации на уровне расчета отдельных аппаратов не учитывались. Методы сравнивались по числу направлений одномерного поиска и числу обращений к модели — расчету аппаратов схемы. В случае, когда [c.78]

Изложенные методы одномерной минимизации являются по существу методами нулевого порядка, т. е. веточках прямой pi вьшолняется расчет лишь значений минимизируемой функции. Если же в каждой точке известны и значения градиента данной функции, то могут быть использованы теоретически - более эффективные алгоритмы одномерного поиска, основанные на применении так называемых критериев сходимости. При этом автоматически обеспечивается выполнение условия (И1, 163), связанного с устойчивостью алгоритма минимизации. Для обеспечения критерия сходимости в случае его невыполнения на первом шаге обычно используются методы линейной экстраполяции совместно с кубической интерполяцией (см. Приложение 2). По данным решения тестовых задач методы первого порядка требуют в среднем 1,1—1,5 вычислений функции (вместе с градиентом) на направлении по сравнению с 2,5—4 вычислениями при методах нулевого порядка. [c.99]

Тогда можно записать рис- 1Х.17< Одномерный поиск методом j (3) — jt = [c.503]

Основная особенность рассматриваемой группы методов — отсутствие вычисления градиента критерия оптимальности. Ряд методов прямого поиска базируется на последовательном применении одномерного поиска по переменным или по другим задаваемым направлениям, что облегчает их алгоритмизацию и применение. [c.385]

Для определения порядка реакции проведен одномерный поиск методом золотого сечения [9] на интервале варьирования п от О до 2. При каждом фиксированном значении порядка реакции константу скорости определяли по методу наименьших квадратов. Целевой функцией поиска был минимум среднеквадратичного отклонения экспериментальных и расчетных данных. [c.124]

Еще одно важное свойство функции Р, учитываемое при выборе метода поиска, — это число факторов. Здесь различаются два ос-новых случая. Первый, когда Р зависит только от одного фактора, Р = Р х) тогда говорят об одномерном поиске. Второй, когда факторов больше одного — многомерный поиск. Причем почти все методы многомерного поиска принципиально применимы при любом числе факторов А>1, тогда как при к—1 применяются иные, одномерные методы. Лишь немногие методы, как например, сканирование, применимы и в одномерном, и в многомерном случаях. [c.264]

Одномерный поиск методом золотого сечения [c.280]

В табл. 2.8 приведены результаты испытаний различных методов минимизации на этих функциях. Во всех случаях при поиске минимумов на прямых для начального шага т (который в дальнейшем удваивался) было принято значение 0,00005 приращения аргументов при вычислении производных принимались равными 0,0001. Одномерный поиск проводился с параболической интерполяцией (2.119). [c.136]

Последовательность L поисков называется итерацией и приводит к конформации a J, х, . . ., xi), исходя из которой начинают новую серию одномерных поисков. На рис. 1-3 приведен пример (L=2), из которого видно, что одной итерации, как правило, недостаточно, и что бывают случаи, когда их требуется бесконечно много. В этом существенный дефект изложенного метода, называемого методом координатной релаксации. [c.35]

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

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

Поиск локального экстремума. Опыт решения высокоразмерных задач синтеза ХТС N > 20) при наличии существенного количества ограничений М 30) показал, что наиболее эффективным алгоритмом является одна из модификаций алгоритма случайного поиска с обратным шагом. В качестве метода одномерного поиска используется метод Дэвиса—Свенна—Кемпи. [c.604]

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

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

В алгоритме также используют специальную логику движения вдоль границы и метод Кифера — Джонсона для поиска экстремума одномерных унимодальных функций. Блок-схема приведена иа рис. IV-9. [c.159]

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

В некоторых случаях метод SSVM применялся в сочетании с несколько иным методом одномерного поиска. Величина начального шага вдоль направления pi зависела от интервала на числовой прямой, в котором оказывалось текущее значение p l. Если параболическая интерполяция выполнялась в окрестности начальной точки вектора pt, то учитывалось значение производной минимизируемой функции по направлению pi в этой точке gi, Рг) интерполяция в этом случае проводилась по двум точкам. Это вело к сокращению числа вычислений функции в процессе поиска. Если же интерполяция выполнялась по трем точкам, то в случае близости найденного положения минимума параболы и средней из узловых точек последняя принималась за точку минимума данной функции в направлении Pi. Это также способствовало уменьшению объема вычислений. В приводимых далее табл. 8—16 соответствующие результаты (с двойной точностью) даны в фигурных скобках. [c.99]

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

Следует заметить, что Дэвидон [791 разработал новый алгоритм оптимизации, который работает без одномерного поиска и имеет те же преимущества методов переменной метрикц. [c.212]

Однако вычисление с высокой точностью минимума F [х) по направлению р требует многократного расчета функции F (а ). Поэтому целесообразно воспользоваться процедурой экономного одномерного поиска (см. с. 105), менее трудоемкой по сравнению с (111,20). Поскольку направление равно произведению отрицательно определенной симметрической матрицы — BlBh) на градиент функции F [х), полученный в результате метод будет сходиться при некоторых дополнительных предложениях (30, с. 61-62]. [c.135]

Алгоритм одномерного поиска первого порядка входит как составная часть в Swit h-метод Флетчера [65], в котором используются преобразования матриц (III, 80) с прямой аппроксимацией гессиана, представленных в факторизованном виде. Результаты тестовых испытаний этого метода даны в табл. 8—17 (строка SW). Следует отметить, что при работе с алгоритмами оптимизации, использующими две матрицы для построения обратного гессиана, например выражения (II, 101), и (II, 102), техника работы с матрицами должна быть аналогична изложенной в главе II. Здесь рассматриваются алгоритмы, использующие одну матрицу преобразования, причем [c.99]

В заключение остановимся на поиске оптимального варианта конструкции теплообменника. В рассматриваемой задаче варьируют два параметра dl и гзкв (в программе — переменные В1 и 02). Соответственно поиск оптимума ведут по двум переменным. Одним из простейших методов многомерной оптимизации является метод покоординатного спуска. Его идея заключается в последовательном применении одномерного поиска для [c.222]

Ту же задачу решает более сложно обосновываемый, но более простой в реализации метод сопряженных градиентов [116— 119]. Идею метода поясняет тот же рис. 1-3 придя после Ь одномерных координатных поисков из исходной точки а , х, . . ., XI, в точку х, х1,. . ., х ), выполняют еще один одномерный поиск — в диагональном направлении, соединяющем эти две точки. Так завершается итерация. Каждая следующая итера- [c.36]

II — минимизации (4.19), III — минимизации полного отклонения но обоим экспериментам, приведены в табл. 4.5 вместе с потерями на поиск — числом итераций (под итерацией подразумевается одномерная минимизапия в ква-зиньютоновском методе Флетчера, обычно 2—3 вычисления целевой функции вместе с градиентом). [c.211]

Существует ряд методов решения задач одномерной оптимизации общий поиск (метод сканирования), деление интервала пополам, дихотамии, золотого сечения, метод Фибоначчи [83]. [c.232]

В методе Дэвиса - Свена - Кэмпи поиск производится также вдоль ортогональных направлений, но вдоль каждого из направлений проводится одномерная минимизация. [c.165]

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

Приведем еще один пример несистемного подхода в практическом применении математической модели. В конце 80-х годов осуществлялось технико-экономическое обоснование противопаводковых мероприятий на большом протяжении рек Читинка, Амга, Перча, Селенга и др. в Читинской области. Научной основой такого обоснования служат гидравлические расчеты неустановившегося медленно изменяющегося движения воды в естественном русле и пойме с выбором основных параметров обвалования территорий, подвергающихся затоплениям. Высокие половодья на этих реках происходят, как правило, в конце весны — начале лета в соответствии с их снеговым питанием и имеют достаточно большую продолжительность (от трех недель до двух месяцев). На реках расположено большое число городов и поселков, подвергающихся периодическим затоплениям, а также значительные площади ценных для сельскохозяйственного использования земель. Проводить сплошное обвалование этих рек не предполагалось. Однако анализ выборочного обвалования потребовал рассмотреть участки рек на большом протяжении (80-200 км для каждой из них). К тому времени уже была создана компьютерная программа расчета неустановившегося медленно изменяющегося движения воды в естественном русле. Численный алгоритм обеспечивал строгое решение одномерных уравнений Сен-Венана методом прогонки, который основывался на достаточно детальном делении реки на расчетные участки по длине и сравнительно малых интервалах времени. Однако такая высокая детализация не соответствовала той проблемной постановке задачи, которая требовалась в данном случае. В результате многочасового расчета на ЭВМ удалось лишь провести расчет единственного варианта планового расположения дамб по реке Читинка. Использовать компьютерную программу для других рек и для вариантного поиска планового расположения дамб оказалось невозможно. Для выполнения задания по проекту пришлось составить новую специальную программу расчета кривой свободной поверхности (т. е. установившегося движения воды), оценивающую оперативные изменения информации о положении дамб. Расчеты проводились для расходов, близких к максимальным половодным расходам, хотя формально в данном случае это не вполне корректно. Однако эти расчеты достаточны для оценок стоимости дамб на предпроект-ной стадии. В работе [Левит-Гуревич, 1996] показано, что необходимо установление соответствий между классификацией методов решения гидравлических задач и классификацией их проблемных постановок. Несоответствия между методом расчета и изложенной постановкой задачи устраняются посредством различных модификаций метода мгновенных режимов, которые отвечают необходимым расчетным параметрам и удобно вписываются в технические условия [Грушевский, 1982] [c.21]

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

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