Презентация Лекция1Классификациямногомерных и одномерные. ppt онлайн

Содержание слайда: Раздел II. Методы оптимизации

Содержание слайда: Тема1. Основные понятия и классификация методов многомерной оптимизации Постановка задачи Рельеф функции Классификация методов многомерной оптимизации Методы нахождения минимума функции одной переменной

Содержание слайда: Задачи Главной целью большинства выполняемых на компьютере расчетов является принятие оптимального в конкретной ситуации решения или, что тоже самое, сделать наилучший выбор из множества допустимых вариантов: сколько и куда вложить денег, чтобы получить наибольшую прибыль по какой дороге поехать, чтобы сэкономить бензин, время и при этом обеспечить безопасность как выбрать параметры прибора, что бы при его минимальной стоимости изготовления достигался максимум КПД.

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

Содержание слайда: Критерии вышеприведенных примеров: Критерии вышеприведенных примеров: - величина прибыли при вложениях x1..xn - длина дороги через пункты x1..xk - величина КПД при значениях x1..xn В результате, задача принятия оптимального решения приводит к нахождению оптимального (максимального или минимального) значения Следует отметить, что нахождение максимума эквивалентно нахождению минимума поэтому стандартные программы разрабатываются, как правило, для нахождения

Содержание слайда: Постановка задачи о локальном минимуме Пусть в Евклидовом пространстве задана функция Говорят, что имеет локальный минимум в точке если существует некоторая -окрестность точки , в которой выполняется Будем полагать, что непрерывная дважды дифференцируемая функция.

Содержание слайда: Локальный минимум

Содержание слайда: Рельеф функции

Содержание слайда:

Содержание слайда: Типы рельефов

Содержание слайда: Общая характеристика методов многомерной оптимизации Практически все методы минимизации функции n переменных основаны на многократном повторении следующих двух действий: выбор в области параметров некоторого направления спуска; спуск к минимуму вдоль выбранного направления.

Содержание слайда:

Содержание слайда: Спуск по выбранному направлению Если - единичный вектор выбранного направления в точке , то уравнение прямой, проходящей через эту точку в направлении , записывается в виде где параметр z , соответствующий точкам на прямой (модуль z есть расстояние от текущей точки до ). Значения функции вдоль этой прямой можно описать функцией одной переменной Изменяя z двигаемся вдоль этой прямой, находим точку , в которой функция имеет меньшее значение, чем в точке Обычно находим минимум функции одной переменной

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

Содержание слайда: Все многообразие методов минимизации функции n переменных определяется множеством способов выбора направлений и методов спуска в выбранном направлении. Все многообразие методов минимизации функции n переменных определяется множеством способов выбора направлений и методов спуска в выбранном направлении.

Содержание слайда: Классификация методов многомерной оптимизации МЕТОДЫ НУЛЕВОГО ПОРЯДКА - при выборе направления спуска требуют вычисления только значений функции (методы: Гаусса-Зейделя, Пауэлла, ДСК, Розенброка, Хука-Дживса, Нелдера-Мида). МЕТОДЫ ПЕРВОГО ПОРЯДКА - требуют вычисления (точного или приближенного) градиента функции (методы: градиентный, сопряженных градиентов, Давидона-Флетчера-Пауэлла (ДФП), Флетчера-Ривса и др.). МЕТОДЫ ВТОРОГО ПОРЯДКА - требуют вычисления как градиента, так и матрицы вторых производных (методы: Ньютона, Ньютона-Рафсона). МЕТОДЫ С ПЕРЕМЕННОЙ МЕТРИКОЙ – занимают промежуточное место между методами 1-го и 2-го порядка.

Содержание слайда: МЕТОДЫ НАХОЖДЕНИЯ МИНИМУМА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ Наиболее часто используемые методы можно разбить на два класса: 1) методы уточнения минимума на заданном интервале [a, b] (метод деления пополам, метод золотого сечения); 2) методы спуска к минимуму из некоторой начальной точки x0 (метод последовательного перебора, метод квадратичной параболы, метод кубической параболы). Ниже рассмотрим только методы спуска

Содержание слайда: Метод последовательного перебора (MPP) Идея этого метода состоит в том, что, спускаясь из точки x0 с заданным шагом h в направлении уменьшения функции, устанавливают интервал длиной h, на котором находится минимум, и затем его уточняют. Уточнение можно осуществить либо методом золотого сечения, либо повторяя спуск с последней точки, уменьшив шаг и изменив его знак. Алгоритм последнего варианта приведен ниже

Содержание слайда: Метод последовательного перебора (MPP)

Содержание слайда: Метод последовательного перебора Задаются x0, некоторый шаг h и погрешность  . 1. В точке x0 вычисляется x1=x0 и y1=f(x1). 2. x0=x1, y0=y1 - запоминается удачная точка. 3. x1=x0+h, y1=f(x1) - делаем следующий шаг в удачном направлении. 4. Если функция убывает, y1<y0, то повторить с п.2, иначе п.5. 5. h=-h/4. В точке x1 функция оказалась большей, чем в x0, следовательно, мы перешагнули точку минимума и организуем спуск в обратном направлении. 6. Если , тогда повторить с п.2, иначе перейти к п.7. 7. конец.

Содержание слайда: Метод последовательного перебора

Содержание слайда: Метод квадратичной параболы (MP2) Для ускорения спуска к минимуму из некоторой точки x0 используют локальные свойства функции вблизи этой точки. Так, скорость и направление убывания можно определить по величине и знаку первой производной. Вторая производная характеризует направление выпуклости: если f''>0, то функция имеет выпуклость вниз, иначе - вверх. Вблизи локального безусловного минимума дважды дифференцируемая функция всегда выпукла вниз. Поэтому, если вблизи точки минимума функцию аппроксимировать квадратичной параболой, то она будет иметь минимум. Это свойство и используется в методе квадратичной параболы

Содержание слайда: Вблизи точки x0 выбираются три точки x1, x2, x3. Вычисляются значения y1, y2, y3. Вблизи точки x0 выбираются три точки x1, x2, x3. Вычисляются значения y1, y2, y3. Через эти точки проводится квадратичная парабола Находится ее минимум xm1

Содержание слайда:

Содержание слайда: Конец