91134

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

Лекция

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

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

Русский

2015-07-13

966 KB

10 чел.

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


 

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

48560. Основные аспекты компьютерных технологий, которые служат платформой, обеспечивающей целостное представление о современной сфере ИКТ 1.24 MB
  Принципы и проблемы физической передачи данных по линиям связи Даже при рассмотрении простейшей сети состоящей всего из двух машин можно увидеть многие проблемы присущие любой вычислительной сети в том числе проблемы связанные с физической передачей сигналов по линиям связи без решения которой невозможен любой вид связи. По степени территориальной рассосредоточенности элементов сети абонентских систем узлов связи различают глобальные региональные и локальные вычислительные сети. К классу ЛВС относятся сети предприятий фирм банков...
48561. Хімічний склад продуктів харчування 42 KB
  Хімічний склад продуктів харчування Урок №: Поняття про сировину напівфабрикати готову страву МЕТА УРОКУ: Ознайомити учнів з поняттям про сировину напівфабрикат готову страву. Харчування – одна із основних життєво необхідних умов існування людини. Здоров’я людини її працездатність і настрій нормальний розвиток значною мірою залежать від харчування. Поняття про сировину напівфабрикати готову страву Виробництво кулінарної продукції здійснюється на сучасних підприємствах масового харчування.
48562. Основные конструкционные стали, применяемые в автомобилестроении и авторемонтном производстве и их характеристики 29.5 KB
  Конструкционные стали предназначены для изготовления деталей машин машиностроительные стали. К этой группе относятся углеродистые и легированные стали с содержанием не более 0708 углерода. Низкоуглеродистые стали до 03 углерода пластичны хорошо свариваются и деформируются.
48563. Основные этапы конструирования 28.5 KB
  Составляется заказчиком изделия и устанавливается наиболее общие требования к изделию о его разработке и изготовлении. задание содержит: 1 наименование и область применения изделия; 2 основание для разработки; 3 источники для разработки; 4технические требования включая: требования к составлению и конструкции изделия; к надежности и технологичности; 5порядок контроля и приемки. Техническое предложение – это совокупность конструкторских документаций содержащих технические и техникоэкономические обоснования целесообразности разработки и...
48564. ОСНОВЫ АЛГОРИТМИЗАЦИИ 825 KB
  ОСНОВЫ АЛГОРИТМИЗАЦИИ Понятие алгоритма Основы алгоритмического языка Паскаль
48565. Будова та функції ядра 50.5 KB
  Методи та методичні прийоми: словесні інтелектуальна розминка розповідь з елементами бесіди пояснення фронтальне опитування практичні самостійна робота наочнографічні демонстрація схем будови мітохондрії хлоропласта взаємоперетворення пластид будови метафазної хромосоми і нитки хромосоми. Базові поняття і терміни: еукаріоти прокаріоти клітина цитоплазма поверхневий апарат ядро хромосоми гени. Засоби навчання: схема Будова мітохондріїâ€ схема Будова хлоропласта†схема Взаємоперетворення пластид схема Будова...
48566. ОСНОВНЫЕ БИЗНЕС-ПРОЦЕССЫ В ОРГАНИЗАЦИИ 75.5 KB
  Субъектами предпринимательства могут быть как отдельные частные лица, так и объединения партнеров. Частные лица как субъекты предпринимательства выступают в этом качестве, как правило, путем организации единоличного или семейного предприятия. Такие предприниматели могут ограничиваться затратами собственного труда или использовать наемный труд.
48567. Конспект лекцій. Економіка підприємства 1.92 MB
  УДК Конспект лекцій по дисципліні “Економіка підприємства†Укл. Містить конспект лекцій по дисципліні “Економіка підприємства†для студентів економічних спеціальностей усіх форм навчання. ЗМІСТ Тема1: Організаційно правові аспекти діяльності підприємства 1.
48568. Коммерческое (предпринимательское) право 3.26 MB
  Понятие коммерческого права Принципы коммерческого права История коммерческого права Очерк истории науки и преподавания коммерческого торгового права в России