91134

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

Лекция

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

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

Русский

2015-07-13

966 KB

15 чел.

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


 

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

24326. Исследование циклических конструкций Java 183 KB
  Оператор цикла for(цикл со счетчиком). Оператор цикла while (цикл с предусловием). Оператор цикла do...while (цикл с постусловием). Конструкции перехода (прерывания)
24327. Понятие сбыта и сбытовой политики фирмы 46 KB
  Понятие сбыта и сбытовой политики фирмы. комплексность с другими элементами маркетингамикс скоординированность сочетание решений в сфере сбыта ценообразования коммуникаций сервиса и др. системность рассмотрение сбыта и остальных инструментов как элементов вызывающих синергетический эффект от их совместного применения гибкость готовность к пересмотру своих позиций в случае необходимости. Задача сбытовой политики – управление конкурентоспособностью товара путем управлением каналами сбыта планирование длины ширины и...
24328. Поведение потребителей. Факторы, влияющие на поведение потребителя 42.5 KB
  Факторы влияющие на поведение потребителя. потребитель выражая свои симпатии и антипатии покупательские предпочтения может решать судьбу фирмыпроизводителя как продавца фирма стремится в максимальной степени задействовать все свои возможности всестороннего и углубленного изучения потребителя потенциального покупателя включая вопросы мотивации покупательского оповещения потребителей принятие решение о покупке формирование покупательских предпочтений. Рассматривая поведение потребителя экономисты задаются вопросом: каким образом...
24329. Сущность цели и функции маркетинга. 30 KB
  Функции маркетинга: Аналитическая изучение и оценка внешней и внутренней среды фирмы; Продуктовопроизводственная – это создание новых товаров которые соответствуют требованиям потребителей. Функция управления и контроля – сосредоточение всего комплекса маркетинга в руках одного из высших должностных лиц. Концепции маркетинга – это основные подходы на основе которых коммерческие организации ведут свою маркетинговую деятельность.
24330. ПРОФЕССИОНАЛЬНЫЕ ИНТОКСИКАЦИИ 164.5 KB
  Определение и классификация хронических профессиональных интоксикаций; клиника, диагностики и лечение хронических интоксикаций тяжелыми металлами (свинцом, ртутью, мышьяком); клиника, диагностики и лечение хронической интоксикации бензолом и его соединениями; клиника, диагностики и лечение хронических интоксикаций хлор- и фосфорорганическими соединениями; экспертиза трудоспособности и реабилитация при хронических профессиональных интоксикациях.
24331. Особенности маркетинговой деятельности в виртуальной среде 89 KB
  Динамичное развитие информационных технологий в частности технологий коммуникации делает актуальным вопрос использования глобальной сети Интернет в маркетинговой деятельности предприятия. Необходимо понимать что Интернет это не та инновация к которой можно приспособиться подкорректировав традиционную модель бизнеса или создав собственный сайт. Очевидно что использование Интернета в системе маркетинга предприятий благодаря его уникальным маркетинговым характеристикам интерактивность гибкость и масштабируемость а также...
24332. Модель безубыточности производства Точка безубыточности 40 KB
  Модель безубыточности производства Точка безубыточности Материал из Википедии свободной энциклопедии Точка безубыточности минимальный объем производства и реализации продукции при котором расходы будут компенсированы доходами а при производстве и реализации каждой последующей единицы продукции предприятие начинает получать прибыль. Точку безубыточности можно определить в единицах продукции в денежном выражении или с учётом ожидаемого размера прибыли. Точка безубыточности в денежном выражении такая минимальная величина дохода при...
24333. Точечные дефекты кристаллической решетки 1.3 MB
  Монокристалл — отдельный однородный кристалл, имеющий непрерывную кристаллическую решётку и иногда имеющий анизотропию физических свойств. Внешняя форма монокристалла обусловлена его атомно-кристаллической решёткой и условиями (в основном скоростью и однородностью) кристаллизации