91134

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

Лекция

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

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

Русский

2015-07-13

966 KB

16 чел.

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г. Хуком и Дживсом, но и до настоящего времени широко используется на практике.


 

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

8248. Штучні джерела оптичного випромінювання 582.63 KB
  Штучні джерела оптичного випромінювання. Основні закони теплового випромінювання. Лампи розжарювання. Будова принципи дії, структура позначень, переваги та недоліки. Галогенні лампи розжарювання. Будова,пр...
8249. Газорозрядні лампи низького тиску 1.03 MB
  Газорозрядні лампи низького тиску Будова,принцип дії, структура позначень Вплив виду баластного опору на роботу газорозрядної лампи Схеми вмикання ЛЛ в мережу. Світлотехнічні, енергетичні, експлуатаційні...
8250. Газорозрядні лампи високого тиску 1.19 MB
  Газорозрядні лампи високого тиску Будова, принцип дії, схеми вмикання, переваги і недоліки ртутної лампи високого тиску ДРЛ. Дугова метало галогенна лампа високого тиску ДРИ. Будова, принцип дії, схеми вмика...
8251. Освітлювальні установки для сільського господарства 121.5 KB
  Освітлювальні установки для сільського господарства. Освітлювальні прилади. Загальні відомості Загальні принципи нормування освітленості Види і системи освітлювання Вибір типу джерела світла і світильника Розміщення сві...
8252. Електрична частина освітлювальних установок 93 KB
  Електрична частина освітлювальних установок Вибір системи напруги живлення освітлювальної установки. Компоновка електричної освітлювальної мережі. Вибір марок проводів і способу їх прокладки. Розрахунок перерізу проводів осві...
8253. Джерела і установки УФ опромінення в С.Г 78.5 KB
  Джерела і установки УФ опромінення в С.Г. Розприділення енергії УФ опромінення по спектру. Джерела УФ опромінення в області УФ-С, УФ-В, УФ-А і області застосування в с.г. УФ- випромінювання невидиме і не викликає зорового відчуття у люди...
8254. Джерела установки інфрачервоного (ІЧ) опромінення 64 KB
  Джерела установки ІЧ опромінення. Розподілення іч опромінення по спектру. Джерела і установки іч опромінення в області ІЧ-А, ІЧ-В, ІЧ-С. Автоматизовані установки ІЧ-обігріву і УФ опромінення Діапазон ІЧ опромінення поділяється на 3 групи...
8255. Використання в доказуванні матеріалів оперативно-розшукової діяльності 100 KB
  Використання в доказуванні матеріалів оперативно-розшукової діяльності Проблема використання матеріалів оперативно-розшукової діяльності (далі – ОРД), з допомогою яких можна отримати докази по кримінальній справі існує ще з XIX ст. до прийняття...
8256. Застосування технічних засобів при збиранні та перевірці доказів 252.99 KB
  Застосування спеціальних знань і технічних засобів субєктами кримінально-процесуального провадження при збиранні і перевірці доказів. Види науково-технічних засобів, які використовуються при збиранні та перевірці доказів...