Презентация - Одномерная оптимизация. Методы классического анализа

Смотреть слайды в полном размере
Презентация Одномерная оптимизация. Методы классического анализа


Вашему вниманию предлагается презентация на тему «Одномерная оптимизация. Методы классического анализа», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 29 слайдов и доступна для скачивания в формате ppt. Размер скачиваемого файла: 1.96 MB

Просмотреть и скачать

Pic.1
2. Одномерная оптимизация 2. 1. Методы классического анализа Рассмотрим задачу минимизации функции о
2. Одномерная оптимизация 2. 1. Методы классического анализа Рассмотрим задачу минимизации функции одной переменной на множестве где - множество действительных чисел одномерного пространства. а) глобальные и локальные минимумы Определение 1. Точка доставляет глобальный минимум функции на множестве , если и для всех
Pic.2
Определение 2. Точка называется точкой строгого глобального минимума функции на множестве , если и д
Определение 2. Точка называется точкой строгого глобального минимума функции на множестве , если и для всех
Pic.3
График функции, имеющей нестрогий минимум, может содержать горизонтальный участок в окрестности точк
График функции, имеющей нестрогий минимум, может содержать горизонтальный участок в окрестности точки минимума. График функции, имеющей нестрогий минимум, может содержать горизонтальный участок в окрестности точки минимума. Под решением в этом случае принимается множество х* = [x* X; f(x) = f(x*)]
Pic.4
Определение 3. Точка называется точкой Определение 3. Точка называется точкой локального минимума фу
Определение 3. Точка называется точкой Определение 3. Точка называется точкой локального минимума функции , если существует такое число , что для всех удовлетворяющих условию выполнено неравенство Если неравенство (2. 1) – строгое, то точку называют точкой строгого локального минимума функции
Pic.5
Выделенные разновидности минимума проиллюстрированы на Выделенные разновидности минимума проиллюстри
Выделенные разновидности минимума проиллюстрированы на Выделенные разновидности минимума проиллюстрированы на рисунке.
Pic.6
в) алгоритм нахождения точки минимума с использованием производной Найти первую производную функции
в) алгоритм нахождения точки минимума с использованием производной Найти первую производную функции Найти критические (стационарные) точки функции, для этого: - найти корни уравнения - найти точки, в которых функция не существует. Исследовать поведение знака в окрестности каждой критической точки: если при переходе слева направо через критическую точку функция меняет знак, то такая критическая точка является точкой экстремума: - точкой максимума, если знак меняется с плюса на минус; - точкой минимума, если знак меняется с минуса на плюс.
Pic.7
г) достаточные условия экстремума Если функция дважды непрерывно дифференцируема, то достаточным усл
г) достаточные условия экстремума Если функция дважды непрерывно дифференцируема, то достаточным условием минимума является положительность, а максимума отрицательность второй производной . Если существует производная и если то функция имеет в точке : - минимум при четном и - максимум при четном и Если нечетно, то функция в точке имеет точку перегиба.
Pic.8
Пример 2. 1. Решить пример 1. 1, используя необходимые Пример 2. 1. Решить пример 1. 1, используя не
Пример 2. 1. Решить пример 1. 1, используя необходимые Пример 2. 1. Решить пример 1. 1, используя необходимые и достаточные условия экстремума. Решение. Целевая функция имеет вид Найдем стационарные точки функции Так как функция дважды непрерывно дифференцируема, то достаточные условия экстремума исследуем с помощью второй производной Так как то в точке достигается минимум целевой функции.
Pic.9
Из условия найдем: Из условия найдем: т. е. высота цилиндрического бака должна быть равна диаметру о
Из условия найдем: Из условия найдем: т. е. высота цилиндрического бака должна быть равна диаметру основания бака.
Pic.10
2. 2. Численные методы поиска экстремума функции одной переменной 2. 2. 1. Постановка задачи. Будем
2. 2. Численные методы поиска экстремума функции одной переменной 2. 2. 1. Постановка задачи. Будем предполагать, что в пределах отрезка функция унимодальна, т. е. на данном отрезке имеет только один минимум. Другими словами, если – единственная точка минимума на отрезке , то является унимодальной на данном отрезке тогда и только тогда, когда для любых двух точек отрезка и взятых по одну сторону от точки минимума соответствует меньшее значение функции, т. е. как при так и при справедливо неравенство
Pic.11
Одномерная оптимизация. Методы классического анализа, слайд 11
Pic.12
Унимодальная функция может быть непрерывной, разрывной Унимодальная функция может быть непрерывной,
Унимодальная функция может быть непрерывной, разрывной Унимодальная функция может быть непрерывной, разрывной или дискретной. Для проверки унимодальной функции на практике обычно используют следующий критерий: если функция дважды дифференцируема на отрезке и в любой точке этого отрезка, то унимодальная функция на отрезке Заметим, что определяет множество точек, на котором функция является выпуклой вниз. Пример 2. 2. Для функции найти отрезок, на котором функция унимодальна.
Pic.13
Решение. Решение. Функция определена при Найдем ее производные: при Следовательно, функция унимодаль
Решение. Решение. Функция определена при Найдем ее производные: при Следовательно, функция унимодальна на интервале Первая производная при Следовательно - точка локального минимума.
Pic.14
2. 2. 2. Стратегии поиска Существуют две принципиально различные стратегии выбора точек, в которых п
2. 2. 2. Стратегии поиска Существуют две принципиально различные стратегии выбора точек, в которых производится вычисление значений целевой функции. Пассивная стратегия - все точки задаются заранее, до начала вычислений. Последовательная стратегия - точки выбираются последовательно в процессе поиска с учетом результатов предыдущих вычислений.
Pic.15
Последовательную стратегию можно Последовательную стратегию можно реализовать двумя способами: постр
Последовательную стратегию можно Последовательную стратегию можно реализовать двумя способами: построением последовательности вложенных в друг друга интервалов, каждый из которых содержит точку минимума; применением квадратичной и кубической интерполяции, где по нескольким вычисленным значениям функции строятся интерполяционный многочлен, а его минимум указывает на очередное приближение искомой точки экстремума.
Pic.16
Алгоритм последовательной стратегии Алгоритм последовательной стратегии Выбор начального интервала и
Алгоритм последовательной стратегии Алгоритм последовательной стратегии Выбор начального интервала изменения параметра , называемого интервалом неопределенности. Границы интервала выбираются таким образом, чтобы функция была унимодальной. Для выбора начального интервала неопределенности можно применить алгоритм Свенна. Уменьшение интервала неопределенности. Проверку условия окончания процесса вычислений. Поиск заканчивается, когда длина текущего интервала неопределенности будет меньше заданной точности вычислений >0, т. е.
Pic.17
Прием уменьшения интервала неопределенности Пусть функция унимодальна на интервале и ее минимум дост
Прием уменьшения интервала неопределенности Пусть функция унимодальна на интервале и ее минимум достигается в точке Возьмем две произвольные точки и , расположенные на интервале таким образом, что . Сравнивая значения функции в этих точках, можно сузить интервал неопределенности следующим образом: если то точка минимума лежит на интервале
Pic.18
если то точка минимума лежит на интервале если то точка минимума лежит на интервале если то точка ми
если то точка минимума лежит на интервале если то точка минимума лежит на интервале если то точка минимума лежит на интервале
Pic.19
Рассмотрим наиболее распространенные в практике следующие приближенные методы поиска минимума: Рассм
Рассмотрим наиболее распространенные в практике следующие приближенные методы поиска минимума: Рассмотрим наиболее распространенные в практике следующие приближенные методы поиска минимума: метод равномерного поиска; метод дихотомии; метод деления интервала пополам; метод золотого сечения; метод Фибоначчи; метод квадратичной интерполяции.
Pic.20
2. 2. 3. Метод равномерного поиска 2. 2. 3. Метод равномерного поиска Метод относится к пассивным ст
2. 2. 3. Метод равномерного поиска 2. 2. 3. Метод равномерного поиска Метод относится к пассивным стратегиям. Задается начальный интервал неопределенности и количество вычислений целевой функции Вычисляются значения целевой функции в равноотстоящих друг от друга точках
Pic.21
Среди точек находится точка , в которой Среди точек находится точка , в которой целевая функция прин
Среди точек находится точка , в которой Среди точек находится точка , в которой целевая функция принимает наименьшее значение Эффективность метода невелика и вычисляется по формуле Например, для достижения точности потребуется вычислить целевую функцию в 199 точках, а при в 1999 точках. Преимущество – возможность определения глобального экстремума.
Pic.22
Одномерная оптимизация. Методы классического анализа, слайд 22
Pic.23
Одномерная оптимизация. Методы классического анализа, слайд 23
Pic.24
2. 2. 4. Метод дихотомии Метод относится к последовательным стратегиям. Задается начальный интервал
2. 2. 4. Метод дихотомии Метод относится к последовательным стратегиям. Задается начальный интервал неопределенности и требуемая точность поиска Делится интервал поиска пополам и вычисляются две абсциссы симметрично расположенные относительно точки где - величина различимости точек
Pic.25
Вычисляются функции и Сравниваются Вычисляются функции и Сравниваются полученные значения и находитс
Вычисляются функции и Сравниваются Вычисляются функции и Сравниваются полученные значения и находится новый уменьшенный интервал неопределенности:
Pic.26
Одномерная оптимизация. Методы классического анализа, слайд 26
Pic.27
Затем снова вычисляются координаты и и продолжается поиск. Затем снова вычисляются координаты и и пр
Затем снова вычисляются координаты и и продолжается поиск. Затем снова вычисляются координаты и и продолжается поиск. За оценку прекращения поиска принимают а за минимальное значение За одну итерацию интервал неопределенности уменьшается примерно в два раза. За итераций длина интервала будет примерно равна
Pic.28
Точность на м шаге вычислений определяется Точность на м шаге вычислений определяется неравенством О
Точность на м шаге вычислений определяется Точность на м шаге вычислений определяется неравенством Отсюда следует, что для достижения точности потребуется итераций. На каждой итерации целевая функция вычисляется дважды.
Pic.29
Одномерная оптимизация. Методы классического анализа, слайд 29


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!