91134

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

Лекция

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

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

Русский

2015-07-13

966 KB

12 чел.

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


 

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

21441. Замечания по поводу классификации точек покоя 340.5 KB
  Следовательно при достаточно большом t точки траекторий начальные значения которых находятся в любой окрестности начала координат попадают в сколь угодно малую окрестность начала координат а при неограниченно приближаются к началу координат т. точки расположенные в начальный момент в окрестности начала координат при возрастании t покидают любую заданную окрестность начала координат т. Если существует дифференцируемая функция называемая функцией Ляпунова удовлетворяющая в окрестности начала координат условиям: 1 причем...
21442. Исследование на устойчивость по первому приближению 209.5 KB
  Напомним что исследование на устойчивость точки покоя системы 1 эквивалентно исследованию на устойчивость некоторого решения системы дифференциальных уравнений 2 т. при правые части системы 1 обращаются в нуль:. Будем исследовать на устойчивость точку покоя линейной системы 5 называемой системой уравнений первого приближения для системы 4. система 1 стационарна в первом приближении то исследование на...
21443. Дифференциальные уравнения с частными производными первого порядка 170 KB
  Линейным неоднородным уравнением или квазилинейным уравнением I порядка в частных производных называется уравнение вида: . 2 Это уравнение линейно относительно производных но может быть нелинейным относительно неизвестной функции Z. Если а коэффициенты Xi не зависят от z то уравнение 2 называется линейным однородным.
21444. Дифференциальные уравнения векторных линий 218 KB
  Выделим из двухпараметрического семейства векторных линий называемых характеристиками уравнения 3 или 6 предыдущей лекции PxyzQxyz=Rxyz3 6 произвольным способом однопараметрическое семейство устанавливая какуюнибудь произвольную непрерывную зависимость между параметрами С1 и С2 . Тем самым найден интеграл квазилинейного уравнения 3 предыдущей лекции зависящий от произвольной функции. Если требуется найти не произвольную векторную поверхность поля а поверхность проходящую через заданную линию...
21445. Приведение матрицы линейного оператора к канонической (жордановой) форме 623.5 KB
  Вектор называется присоединенным вектором оператора соответствующим собственному значению если для некоторого целого выполняются соотношения . Иными словами если присоединенный вектор порядка то вектор является собственным вектором оператора . Существует базис 1 образованный из собственных и присоединенных векторов оператора в котором действие оператора дается следующими соотношениями:...
21446. Обыкновенные дифференциальные уравнения 438.5 KB
  Функция называется решением (или интегралом) д.у., если она раз непрерывно дифференцируема на некотором интервале и при удовлетворяет уравнению. Процесс нахождения решения д.у. называется его интегрированием...
21447. Линейные дифференциальные уравнения I порядка 299.5 KB
  Линейным дифференциальным уравнением I порядка называется уравнение I порядка линейное относительно неизвестной функции и её производной. Если то уравнение 1 называется линейным однородным. В соответствии с этим методом в формуле 2 полагают тогда: Подставляем полученное соотношение в уравнение 1 будем иметь: или откуда интегрируя находим следовательно . Интегрируем соответствующее однородное уравнение т.
21448. Нормальные системы дифференциальных уравнений. Условие Липшица 267 KB
  Условие Липшица. Говорят что функция удовлетворяет условию Липшица в некотором интервале [b] если существует такое число 0 что для. Так функция удовлетворяет условию Липшица в окрестности x=0 но её производная в точке x=0 имеет разрыв. Если функция нескольких переменных удовлетворяет условию Липшица по каждой из этих переменных в соответствующем диапазоне их изменения т.
21449. Теорема о дифференцируемости решений дифференциальных уравнений. Особые точки 463.5 KB
  Особые точки. Теорема: если в окрестности точки функция имеет непрерывные производные до mого порядка включительно то решение уравнения 1 удовлетворяющее начальному условию в некоторой окрестности точки имеет непрерывные производные до m1 порядка включительно. Подставляя в уравнение 1 получим тождество...