Существуют модификации алгоритма, в которых в процессе исследующего поиска ищется минимум по каждой переменной или в процессе поиска по образцу ищется не минимум функции, а просто делается шаг в заданном найденном направлении с фиксированным значением параметра λ.

Алгоритм Розенброка

Критерии останова алгоритма могут быть стандартными (т.е. описанными в предыдущих алгоритмах прямых методов).

Симплексный метод Нелдера-Мида или поиск по деформируемому многограннику

где: ; ; t – расстояние между вершинами.

В самом простом виде симплексный алгоритм заключается в следующем. Строится регулярный симплекс. Из вершины, в которой максимальна (т.1) проводится проектирующая прямая через центр тяжести симплекса. Затем т.1 исключается и строится новый отраженный симплекс из оставшихся старых точек и одной новой, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести.

Продолжение этой процедуры, в которой каждый раз исключается вершина, где целевая функция максимальна, а также использование правил уменьшения размера симплекса и предотвращение циклического движения в окрестности экстремума позволяет достаточно эффективно определять минимум для «хороших» функций. Но для «овражных» функций такой поиск неэффективен.

В симплексном алгоритме Нелдера и Мида минимизация функций n переменных осуществляется с использованием деформируемого многогранника.

В качестве критерия останова могут быть взяты те же критерии, что и в остальных алгоритмах. Можно также использовать критерий останова следующего вида:

Выбор коэффициентов α, β, γ обычно осуществляется эмпирически. После того как многогранник подходящим образом промасштабирован, его размеры должны поддерживаться неизменными пока изменения в топологии задачи не потребуют многогранника другой формы. Чаще всего выбирают α = 1, 0.4 ≤ β ≤ 0.6, 2 ≤ γ ≤ 3.

Источник

Методы безусловной оптимизации

Автор работы: Пользователь скрыл имя, 13 Июня 2013 в 14:58, реферат

Краткое описание

Задачи отыскания экстремумов в многомерном случае существенно осложняются. Возникают следующие качественно новые стороны рассматриваемой задачи:
Функция F(X) может иметь сложную форму. Для графической интерпретации поверхности принято изображать ее с помощью линий уровня. Линия уровня – это кривая в 2-х мерном сечении пространства параметров, значение функции, на которой константа. Поверхность, соответствующая зависимости F(X) может иметь: «овраги» или «гребни» (поверхности уровня имеют структуру, сильно отличающуюся от сферической); «плато» (плоские горизонтальные участки); особые точки типа «седло». Это не имеет себе аналогий в классе одномерных функций. («Седло» – точка гладкой поверхности, вблизи которой поверхность лежит по разные стороны от своей касательной плоскости. В окрестности седла имеются 4 интегральные кривые, которые входят в особую точку. Между ними располагаются интегральные кривые типа гипербол).

Вложенные файлы: 1 файл

Задачи отыскания экстремумов в многомерном случае существенно ос.doc

Г.И.Шкатова, Методы оптимизации

Методы безусловной оптимизации

Особенности поиска экстремума функции многих переменных

Задачи отыскания экстремумов в многомерном случае существенно осложняются. Возникают следующие качественно новые стороны рассматриваемой задачи:

Стратегия методов безусловной оптимизации

Все методы решения задач математического программирования можно разбить на прямые и непрямые. Непрямые методы основаны на использовании необходимых и достаточных условий экстремумов и сводятся к решению системы нелинейных уравнений

Методы, не связанные с использованием необходимых и достаточных условий экстремумов относят к прямым.

Большинство применяемых на практике прямых методов решения задач математического программирования являются итеративными.

В основу этих методов положен механизм порождения последовательности точек по правилам, которые определены в соответствии с выбранным методом решения и обладают следующими свойствами:

Общее правило построения последовательности численными методами безусловной оптимизации записывается в виде:

Стратегия предполагает на очередной итерации следующие шаги:

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

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

Критерии для завершения поиска

На основании сравнения результатов расчетов двух или нескольких последовательных итераций. Наиболее распространены:

(1) – недостаточна, т.к. функция может иметь поведение типа скачка (резкое изменение критерия оптимальности).

(3) – характеризует скорость убывания критерия оптимальности и обращается в нуль в точке локального минимума. Поэтому по этой скорости можно судить о приближении к оптимуму.

Оценка эффективности методов оптимизации

Большое разнообразие итерационных алгоритмов ставит перед пользователем задачу выбора. Для этого следует выставить критерии, на основании которых один алгоритм будет считаться более предпочтительным, нежели другой. С этой целью обычно используют следующие оценки:

Для сравнения алгоритмов по этим критериям следует производить расчеты в одинаковых или близких условиях.

Классификация методов на основании порядка производных при выборе направления

Классификация методов на основании выбора метода аппроксимации целевой функции

Методы нулевого порядка

Представляет собой группу методов, у которых величина шага и направление к оптимуму формируются однозначно в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных. Методы различаются выбором направления, начальных условий (начальной точки).

В методах покоординатного спуска осуществляется поиск из заданной точки в направлении, параллельном одной из осей, до точки минимума в данном направлении.

Затем поиск производится в направлении, параллельном другой оси и т.д.

Направления, конечно, фиксированы. Все многообразие этой группы методов определяется стратегией выбора очередной оси поиска и методом поиска (любым из методов одномерной минимизации) экстремума вдоль выбранной оси. Пример траектории поиска методом покоординатного спуска приведен на рис.1.

Достоинством метода является его простота, невысокие требования к памяти и сходимость практически с любых начальных приближений, если не попадет в овраг (может остановиться на дне оврага далеко от минимума). А основным недостатком – медленная сходимость. Установлено, что методом покоординатного спуска задача минимизации ф-ии будет решена за n шагов. Для общего вида – процесс бесконечный. Кажется разумным попытаться модифицировать этот метод т.о., чтобы на каждой итерации поиск производился не просто вдоль координатной оси, а вдоль наилучшего направления.

Метод Розенброка направлен на ликвидацию одного из недостатков метода покоординатного спуска — высокую чувствительность к выбору системы координат. Метод сводится по сути к отысканию «удачной» системы координат путем поворота исходных осей координат. После чего осуществляется поиск поочередно по всем переменным последовательно. Первый цикл поиска совпадает с Г.-З. А далее поворот в зависимости от вектора смещения точки поиска.

Симплексом в n- мерном пространстве называют фигуру, содержащую n+1 вершину. На плоскости – треугольник, в трехмерном пространстве – тетраэдр и т.д. Если все вершины симплекса равно удалены друг от друга, то такой симплекс называется регулярным.

В организации алгоритма поиска используется важное свойство симплекса: против каждой вершины находится одна грань.

Суть метода: в окрестности точки Х₀ строится симплекс, затем находится самая плохая вершина, и на противоположной стороне строится новый симплекс, отличающийся только одной другая вершиной. Эта вершина получается симметричным отражением выбрасываемой вершины относительно центра противоположной грани. При выходе в район оптимума процесс обычно зацикливается, в этом случае нужно сжимать симплекс, откладывая вершину от грани на расстоянии вдвое меньше, чем необходимо. Процесс сжатия происходит многократно, до тех пор, пока размеры симплекса не будут меньше заданной величины. Недостаток – невозможность ускорения вдали от оптимума.

Методы градиентного спуска основываются на известном факте, что направление градиента показывает направление наискорейшего возрастания функции, а направление антиградиента, соответственно, показывает направление наискорейшего убывания функции. Модуль же градиента – характеризует скорость этого возрастания. Вектор градиента может быть получен через свои проекции на оси координат, которые равны соответствующим частным производным:

Градиент всегда перпендикулярен линии уровня, проходящей через ту точку, в которой вычислен градиент. Пример траектории поиска методом градиентного спуска приведен на рис..

Величина рабочего шага в направлении градиента зависит от величины градиента, которую заранее трудно учесть, поэтому, как правило, вводится коэффициент пропорциональности шага, с помощью которого можно управлять эффективностью (число повторов вычисления функции) метода.

Показано, что значение a можно определять по некоторым характеристикам функции f(x). Например, если существует такая константа R, что для любых точек

Однако, значения R и M обычно заранее неизвестны.

Разработаны различные методы, относящиеся к группе градиентного спуска. Среди них: с постоянным шагом, с дробным шагом и наискорейшег о спуска.

Основным недостатком градиентного метода является необходимость частого вычисления производных. Этого недостатка лишен метод наискорейшего спуска.

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

Источник

Что такое пассивная стратегия поиска при численном решении задач многомерной безусловной оптимизации