91134

Методы поиска экстремума функций нескольких переменных

Лекция

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

Следует отметить что в многомерных задачах оптимизации где число проектных параметров достигает пяти десяти и более этот метод потребовал бы слишком большого объема вычислений. Поэтому необходимы специальные численные методы основанные на целенаправленном поиске. Исторически первыми подходами были прямые обобщения одномерных методов например поиск Фибоначчи или интерполяционные методы на многомерные задачи.

Русский

2015-07-13

966 KB

11 чел.

PAGE  9

Лекция 5

Методы поиска экстремума функций нескольких переменных.

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

Минимум дифференцируемой функции многих переменных u = f(x1,x2,…,xn) можно найти, исследуя ее значения в критических точках, которые определяются из решения системы дифференциальных уравнений

. (1)

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

Для решения подобной задачи в области проектирования G, в которой ищется минимум целевой функции u = f(x1,x2,…,xn), можно ввести дискретное множество точек (узлов) путем разбиения интервалов изменения параметров x1,x2,…,xn на части с шагами h1,h2,…,hn. В полученных узлах можно вычислить значения целевой функции и среди этих значений найти наименьшее.

Следует отметить, что в многомерных задачах оптимизации, где число проектных параметров достигает пяти, десяти и более, этот метод потребовал бы слишком большого объема вычислений. Допустим возьмем область (для простоты, “прямоугольной” формы) и по каждой координате возьмем 100 точек, то можно вычислить функцию на образовавшейся сетке из 100n точек и выяснить координаты точки с экстремальным значением. Однако при n>3 ни о каком реальном расчете говорить не приходится даже при наличии самых быстродействующих компьютеров. Это заставляет искать более эффективные способы минимизации. Поэтому необходимы специальные численные методы, основанные на целенаправленном поиске. Рассмотрим некоторые из них.

Линии уровня

На рис. 7.8 изображен график функции двух переменных f(x, у), унимодальной (имеющей одну точку экстремума) в некоторой области координатной плоскости (напомним, что графиком функции двух переменных является поверхность в трехмерном пространстве). Минимум функции достигается в точке (x0, y0) на плоскости ху, которая является проекцией точки M, «наинизшей» на графике. На том же рисунке изображен ряд сечений поверхности плоскостями, параллельными плоскости ху, и проекции этих сечения на указанную плоскость. Эти проекции, которые можно изображать в отрыве от трехмерного рисунка, являются удобным способом создания наглядного представления о поверхности с помощью двумерного рисунка. Совокупность таких плоских сечений составляет так называемое семейство линий уровня поверхности.

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

Исторически первыми подходами были прямые обобщения одномерных методов (например, поиск Фибоначчи или интерполяционные методы) на многомерные задачи. Эти подходы не были особенно удачными в связи с тем, что их трудоемкость росла экспоненциально с ростом размерности задачи ("проклятие размерности" по Беллману). 

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

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

Общая идея методов спуска такова. Взяв за начало некоторую произвольную точку области, в которой функция f(x,y) унимодальна (см. рис. 7.8) и вычислив в ней значение этой функции, будем смещаться по некоторому алгоритму в другую точку, в которой значение функции меньше, чем в начальной, и т.д. На рис. 7.8 это будет движением вниз (по оси z), т. е. «спуском», откуда и пошло название группы методов.

В качестве начальной точки x[0] может быть выбрана произвольная точка, однако стремятся использовать всю имеющуюся информацию о поведении функции f(x), чтобы точка x[0] располагалась как можно ближе к точке минимума. Переход (итерация) от точки х [k] к точке х [k+1], k = 0, 1, 2, ..., состоит из двух этапов:

выбор направления движения из точки х [k]; 

определение шага вдоль этого направления.

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

методы прямого поиска (методы нулевого порядка), которым нужны только значения целевой функции;

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

ньютоновские методы (методы второго порядка), которые используют и частные производные второго порядка. 

Общие методы (методы нелинейного программирования):

Методы одномерной оптимизации:

Метод золотого сечения (Метод чисел Фибоначчи) • Метод деления пополам • Метод дихотомии • Метод парабол • Метод равномерного поиска (перебора) • Метод равномерного блочного поиска • Метод троичного поиска

Методы многомерной оптимизации:

Прямые методы:
(требуют только значения функции в точках приближений)
Метод Гаусса • Метод деформируемого многогранника (метод Нелдера — Мида, симплексный метод) • Метод конфигураций • Метод Розенброка • Метод сопряжённых направлений • Метод Хука — Дживса

Методы первого порядка:
(помимо значений функции требуют значения частных производных)
Метод наискорейшего спуска •
Метод сопряжённых градиентов

Методы второго порядка:
(требуют значения первой и второй частных производных):
Метод Ньютона • Метод Ньютона-Рафсона

Методы линейного программирования:

Метод эллипсоидов • Симплекс-метод • Метод потенциалов

Прямые методы спуска

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

Выбираем в данном случае произвольно начальную точку х(0)=2 и у(0)=3

Подставим значение Х в уравнение

Находим первую производную от функции

=2y+2

Приравниваем ее нулю и находим У(1)

У(1)=-1

Y(1) - Точка претендент на экстремум

Находим вторую производную от функции

=2

Так как вторая производная не равна нулю и число к четное (вторая производная), то в точке У(1) =-1 минимум.

Подставляем У=-1 в уравнение и получаем

f(X, Y(1))=1/4X2-1/2X+2

Находим первую производную от функции

f(X, Y(1))=1/2X-1/2

Приравниваем ее нулю и находим X(1)

X(1)=1

X(1) - Точка претендент на экстремум

Находим вторую производную от функции

f(X, Y(1))=1/2

Так как вторая производная не равна нулю и число к четное, то в точке X(1)=1 минимум.

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

Данный метод легко проиллюстрировать геометрически для случая функции двух переменных z=f(x,y), описывающей некоторую поверхность в трехмерном пространстве. На рисунке нанесены линии уровня этой поверхности. Процесс оптимизации в этом случае проходит следующим образом. Точка M0(x0,y0) описывает начальное приближение. Проводя спуск по координате х, попадем в точку M1(x1,y0). Далее, двигаясь параллельно оси ординат, придем в точку M2(x1,y1) и т.д.

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

Метод Гаусса прост, но не очень эффективен. Проблемы могут воз-никнуть, когда линии уровня сильно вытянуты и "эллипсоиды" ориентиро-ваны, например, вдоль прямых (ОВРАГ).

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

Дифференцируем

4(0,5+а)+1

4(0,5+а)+1=0

Откуда

Для машинной реализации метод Гаусса получил название метода Гаусса_Зейделя.

Пример использования метода Гаусса-Зейделя

Найти минимальное значение функции F=f(x1,x2)=(x1+x2)2+(x2-1)2

Построение линий уровня.

Рисунок 3

Реализация метода Гаусса_Зейделя

Развитием метода покоодинатного спуска является поиск по образцу.

Этот метод впервые предложен еще в 1960г. Хуком и Дживсом, но и до настоящего времени широко используется на практике.


 

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

40402. Гражданская война в США 78.84 KB
  Первый период войны апрель 1861 апрель 1863 Сражения 1861 года Боевые действия начались 12 апреля 1861 года сражением за форт Самтер в бухте Чарлстон который после 34часового обстрела был вынужден сдаться. Первое серьёзное сражение произошло в Вирджинии у железнодорожной станции Манассас 21 июля 1861 года когда плохо обученные войска северян перейдя ручей БуллРан атаковали южан но были вынуждены начать отступление превратившееся в бегство. В ходе этого самого кровавого дня войны известного как Сражение при Энтитеме обе стороны...
40403. Эпоха Бурбонов (XVIII век) 30.32 KB
  В 1609 году начинается выселение из Испании морисков однако доходы от конфискации их имущества не компенсировали последующий упадок торговли и запустение многих городов во главе с Валенсией. Вступление в войну католической Франции лишило конфликт религиозной почвы и привело к катастрофическим последствиям для Испании. На долгие десятилетия политическую жизнь Испании начали определять интересы её северного соседа. Экономическая и политическая слабость привели Испанию к подписанию крайне невыгодного договора в СанИльдефонсо 1796 который...
40404. Италия во времена испанского господства и возрастающего влияния Франции (1559—1700) 141.87 KB
  Наибольшее значение для будущего имело восстановление Савойи и Пьемонта которые прежде всего должны были служить испанскому господству в верхней Италии оплотом против Франции. Незадолго до того прекратило своё существование ещё одно из небольших владений в Италии Урбино которое в 1623 году слилось с Церковной областью. Франция уже ранее воздвигла на северной границе Италии преграду дальнейшему развитию испанской власти тем что воспрепятствовала соединению габсбургских земель в Граубюндене и Вальтеллине. Она пыталась утвердиться и в...
40405. Конституция США 95.53 KB
  Состоит из семи статей за время действия Конституции были приняты двадцать семь поправок которые являются её неотъемлемой частью. В основе Конституции США лежит принцип разделения властей между законодательной конгресс исполнительной президент и судебной верховный суди нижестоящие суды ветвями. Хотя первоначальной целью Конвента был именно пересмотр Статей Конфедерации и вопрос о выработке нового документа не ставился постепенно делегаты пришли к заключению о необходимости создания новой Конституции которая бы утвердила...
40406. Война Первой коалиции 193.28 KB
  союзные войска в общем до 250 тыс. Французская регулярная армия не превышала тогда 125 тыс. Он издал грозную прокламацию которая имела целью устрашить французов но произвела обратное действие: её вызывающий тон возбудил сильнейшее негодование; всякий кто мог взялся за оружие и менее чем через 2 месяца численность французских войск превзошла уже 400 тыс. капитулировал имея в распоряжении 18 тыс.
40407. Предыстория объединения 77.04 KB
  под эгидой Пруссии был заключенТаможенный союз куда вошли Пруссия Бавария Саксония и другие государства. Королевство Пруссия Ядром Пруссии стало Маркграфство Бранденбург которое образовалось в XII веке на славянских землях бодричей и лютичей между Эльбой и Одером в результате экспансии немецких рыцарей на восток. В 1618 году в результате династического брака сына маркграфа Бранденбурга и дочери герцога Пруссии из другой ветви Гогенцоллернов образовалось наследственное владение БранденбургПруссия. ВТридцатилетней войне относительно...
40408. Австро-венгерское соглашение 1867 года (Австро-венгерский компромисс) 34.97 KB
  kiegyezés договор заключённый 15 марта 1867 годамежду австрийским императором ФранцемИосифом I и представителями венгерского национального движения во главе с Ференцем Деаком в соответствии с которым Австрийская империя преобразовывалась в дуалистическую монархию АвстроВенгрия. Создание АвстроВенгрии было способом преодоления затяжного кризиса империи вызванного подъёмом национальных движений народов страны укреплением национальных элит военными поражениями в австроиталофранцузской 1859 года и австропрусской 1866 года войнах...
40409. Зависимость от Испании 1580—1640 456.5 KB
  Иберийская или пиренейская уния современное обозначение династической унии корон Испании и Португалии в 1580 1640 годах. Приход к власти Габсбургов в Португалии После того как в 1578 году молодой португальский король Себастьян I сложил голову при ЭльКсарэльКебире правящая Ависская династия оказалась на грани угасания. Он обеспечил португальское представительство в управлении единым государством позволил Португалии сохранить собственные законы и денежную единицу; одно время даже обсуждалась идея переноса столицы в Лиссабон. Династия...
40410. Венский конгресс 1814—1815 гг. 24.67 KB
  Гумбольдт Францию Шарль Морис де ТалейранПеригор Португалию Педро де Соуза Гольштейн де Палмела Решения Европа после Венского конгресса Все решения Венского Конгресса были собраны в Заключительном акте Венского Конгресса. В результате конгресса сложилась Венская система международных отношений и был создан Священный союз европейских государств имевший целью обеспечение незыблемости европейских монархий.