91135

Метод Хука и Дживса

Лекция

Информатика, кибернетика и программирование

Рассмотрим простейшую модификацию метода Хука и Дживса на примере функции F=fx1x2=x1x22x212 Метод вращающихся координат Розенброка Идея Розенброка устранить ограничения покоординатного поиска и метода ХукаДживса на возможные изменения переменных которые в этих методах могли изменяться только в направлениях параллельных осям координат. Если первоначальный шаг был неудачен то длина шага уменьшается и попытка повторятся до тех пор пока не будет получено улучшение функции. Как только будет выявлена ситуация когда значение функции...

Русский

2015-07-13

1.12 MB

10 чел.

Лекция 6

Метод Хука и Дживса

Этот метод можно рассматривать как модификацию метода Гаусса-

Зейделя.

Рассмотрим простейшую модификацию метода Хука и Дживса на примере функции F=f(x1,x2)=(x1+x2)2+(x2-1)2

Метод вращающихся координат Розенброка

Идея Розенброка - устранить ограничения покоординатного поиска и метода Хука-Дживса на возможные изменения переменных, которые в этих методах могли изменяться только в направлениях, параллельных осям координат. В методе Розенброка шаги поиска могут производиться вдоль направлений координатных осей, которые могут вращаться в пространстве. (т.е.движение может быть и по диагонали).

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

Однако имеется дополнительный недостаток - процедура ортогонализации очень дорого стоит и в смысле количества операций, производимых с системой координат, и в смысле необходимой памяти, которой требуется уже порядка n2, а не n, как в методе Хука-Дживса. Это значит, что даже в случае относительно “дешевой” целевой функции вычислительные затраты на ортогонализацию оказываются значительными в сравнении с общими затратами. Кроме того, размерность решаемых задач ограничивается требуемым объемом памяти. 

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

Поиск экстремума методом Нелдера-Мида

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

Рассмотрим эти правила на примере двумерной задачи оптимизации. Так как количество переменных две то многогранник имеет 2+1 три вершины, т.е. это треугольник. Выбраны вершины исходного треугольника: , ,  Новая вершина находится на луче, проведенном из худшей вершины (из вершины с наибольшим значением целевой функции) через центр тяжести многогранника, причем рекомендуется выбирать на расстоянии от , равном . Новая вершина заменяет худшую вершину . Если оказывается, что имеет лучшее значение целевой функции среди вершин многогранника, то расстояние увеличивают. На рисунке именно эта ситуация имеет место и увеличение дает точку . В новом многограннике с вершинами , , худшей является вершина , аналогично получают вершину , затем вершину и т.д. Если новая вершина окажется худшей, то в многограннике нужно сохранить лучшую вершину, а длины всех ребер уменьшить, например вдвое (стягивание многогранника к лучшей вершине). Поиск прекращается при выполнении условия уменьшения размеров многогранника до некоторого предела.

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

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

В природе мы нередко наблюдаем явления, сходные с решением задачи на нахождение минимума. К ним относится, в частности, стекание воды с берега котлована на дно. Упростим ситуацию, считая, что берега котлована “унимодальны”, т.е. они гладкие и не содержат локальных углублений или выступов. Тогда вода устремится вниз в направлении наибольшей крутизны берега в каждой точке.

Переходя на математический язык, заключаем, что направление наискорейшего спуска соответствует направлению наибольшего убывания функции. Из курса математики известно, что направление наибольшего возрастания функции двух переменных u=f(x,y) характеризуется ее градиентом 

,

где e1, e2 - единичные векторы (орты) в направлении координатных осей. Следовательно, направление, противоположное градиентному, укажет путь, ведущий вниз вдоль наиболее крутой линии. Методы, основанные на выборе пути оптимизации с помощью градиента, называются градиентными.

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

Формально поиск новой точки приближения к минимальной точке можно представить как

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

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

 

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

Метод наискорейшего спуска.

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

Проиллюстрирую метод наискорейшего спуска на рисунке для случая функции двух переменных z = f(x,y) и отметим некоторые его геометрические особенности.

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

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

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

Исследование оврагов

Все рассмотренные методы, как прямые, так и методы первого порядка страдают существенным недостатком – они слабо применимы при наличии оврага на поверхности.

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

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

Проблема многоэкстремальности

Достаточно часто на практике имеются функции имеющие несколько минимумов.

На рисунке приведены линии уровня функции с двумя локальными минимумами в точках O1 и O2. Такие функции принято называть многоэкстремальными. Сравнивая между собой значения функции в точках O1 и O2 f1=3, f2=1, находим, что наименьшее значение функция достигает в точке O2.

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

Как бороться с многоэкстремальностью? Универсального ответа на этот вопрос нет. Самый простой прием состоит в том, что проводят поиск несколько раз, начиная его с разных точек. Если при этом получаются разные ответы, то сравнивают в них значения целевой функции и выбирают наименьшее. Расчеты останавливают после того, как несколько новых поисков не меняют полученного ранее результата. Выбор начальных точек поиска, обоснованность прекращения расчетов в значительной степени зависят от опыта и интуиции специалистов, решающих задачу.

Решение задач условной оптимизации методом Лагранжа

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

Решение задач условной оптимизации методом Лагранжа. 

Пусть задана задача математического программирования: максимизировать функцию

Z = f(х1х2, ..., хn)   при ограничениях

gi(х1х2, ..., хn) = 0, i=1, 2. ..., m

Основная идея метода заключается в переходе от задачи на условный экстремум исходной функции f (x) к задаче на безусловный экстремум некоторой специально построенной функции Лагранжа F.

С этой целью составим функцию

(2.7)

Где  множитель Лагранжа.

Определим частные производные 

и приравняем их нулю. В результате получим систему уравнений

Функция (2.7) называется функцией Лагранжа, а числа - множителями Лагранжа. Решая систему находим точки x1(0)x2(0), ..., xn(0)λ1(0)λ2(0), ..., λm(0) которые и определяют точки экстремума (в общем случае таких точек может быть несколько). Однако для того чтобы определить какой экстремум (мах или мин) нужно дополнительное исследование связанное с анализом значения функции в найденной точке.

Пример 1. Найти точку условного экстремума функции Z=x1x2+x2x3 при ограничениях

Решение. Составим функцию Лагранжа 

F(х1,х2,х3,λ1,λ2)=х1х2+х2х3+λ1(х1+х2-2)+λ2(х2+х3-2) 

и продифференцируем ее по переменным х1х2х3λ1 и λ2. Приравнивая полученные выражения нулю, получим следующую систему уравнений:

Из первого и третьего уравнения следует, что λ1=λ2= -х2; тогда

Решая данную систему, получим: ххх= 1, Z=2.

Для определения характера экстремума исследуем окрестность точки Z=2. С этой целью дадим приращения h1, h2, h3 для точек х1, х2, х3.

Т.е новые точки имеют координаты 1+h1, 1+h2, 1+h3

Подставим эти значения в ограничения.

1+h1+1+h2=2

1+h2+1+h3=2

Т.е.

h1+h2=0

h2+h3=0

Или h1=-h2 и h2=-h3

Подставим значения новых точек в функцию

Ф=(1+h1)*(1+h2)+(1+h2)*(1+h3)

С учетом найденных значений h

Ф=2-2h12

Т.е окрестность точки экстремума меньше значения функции в этой точке, что свидетельствует, что это максимум.

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


 

А также другие работы, которые могут Вас заинтересовать

21786. Управление финансовыми рисками 174.5 KB
  Сущность и классификация финансовых рисков 2. Сущность и классификация финансовых рисков Финансовая деятельность предприятия во всех ее формах сопряжена с многочисленными рисками степень влияния которых на результаты этой деятельности существенно возрастает с переходом к рыночной экономике. Риски сопровождающие эту деятельность выделяются в особую группу финансовых рисков играющих наиболее значимую роль в общем портфеле рисков предприятия. Возрастание степени влияния финансовых рисков на результаты финансовой деятельности предприятия...
21787. Риск как экономическая категория 80 KB
  Понятие риска его основные элементы 2. Причины возникновения риска 3. Общие принципы классификации риска 4. Факторы влияющие на уровень экономического риска 1.
21788. Система количественных оценок риска 94 KB
  Как отмечалось ранее тема 2 одним из наиболее распространенных методов количественной оценки риска является статистический метод. Главными инструментами статистического метода расчета риска являются: среднее значение х изучаемой случайной величины последствий какоголибо действия например дохода прибыли и т. как случайные величины подчиняются закону близкому к нормальному широко используется в литературе по проблеме количественной оценки экономического риска.
21789. Теоретические аспекты риск-менеджмента 70 KB
  Основные принципы управления рисками 3. Анализ риска 4. Методы количественного анализа риска 1. Содержание рискменеджмента Рискменеджмент – система управления рисками на предприятии которая представляет собой совокупность методов приемов и мероприятий позволяющих в определенной степени прогнозировать наступление рисковых событий и принимать меры к исключению или снижению отрицательных последствий наступления таких событий.
21790. Риск и доход 72 KB
  Величина FV показывает будущую стоимость сегодняшней величины PV при заданном уровне доходности. Концепция риска и доходности в финансовом менеджменте Риск и доходность в финансовом менеджменте и анализе рассматриваются как две взаимосвязанные категории. Активы с которыми ассоциируется относительно больший размер возможных потерь рассматриваются как более рисковые; вполне естественно что к таким активам предъявляются и большие требования в отношении доходности.
21791. Управление рисками и антикризисное управление 81 KB
  Главная задача антикризисного управления обеспечение такого положения предприятия на рынке когда оно может преодолеть временные трудности в том числе и финансовые посредством использования всех возможностей современного менеджмента. главной целью его является обеспечение стабильного положения на рынке компании при любых экономических политических и социальных изменениях в стране; в его рамках применяются в основном те управленческие инструменты которые наиболее эффективны в устранении временных финансовых затруднений и решении других...
21792. Санитарные требования к транспортированию, приему, хранению, механической кулинарной обработке пищевых продуктов 75 KB
  ПЛАН ЛЕКЦИИ : Санитарные требования к транспортированию пищевых продуктов. Санитарные требования к приему и хранению пищевых продуктов. Санитарные требования к механической кулинарной обработке пищевых продуктов.
21793. Санитпрные требования к содержанию предприятий общественного питания 110.5 KB
  Санитарные требования к содержанию территории и помещений предприятий общественного питания. Цель способы и средства дезинфекции в предприятиях общественного питания. Гигиена и санитария общественного питания: Учебник для техн.
21794. Санитарные требования к тепловой обработке пищевых продуктов, хранению и раздаче готовой пищи 91 KB
  Санитарные требования к изготовлению кремовых изделий и пирожков во фритюре. Органолептическими признаками готовности мясных изделий являются выделение бесцветного сока в месте прокола и серый цвет на разрезе продукта при этом температура в центре готовых изделий должна быть не ниже 85 град. C для натуральных рубленых изделий и не ниже 90 град. C для изделий из котлетной массы.