Презентация Методы поиска экстремума онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Методы поиска экстремума абсолютно бесплатно. Урок-презентация на эту тему содержит всего 47 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Методы поиска экстремума
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:47 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.17 MB
- Просмотров:72
- Скачиваний:1
- Автор:неизвестен
Слайды и текст к этой презентации:
№8 слайд
![В зависимости от числа](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img7.jpg)
Содержание слайда: В зависимости от числа управляемых параметров различают методы одномерной (управляемый параметр единственный) и многомерной (размер вектора X не менее двух) оптимизации.
В зависимости от числа управляемых параметров различают методы одномерной (управляемый параметр единственный) и многомерной (размер вектора X не менее двух) оптимизации.
Реальные задачи в САПР многомерны,
методы одномерной оптимизации играют вспомогательную роль на отдельных этапах многомерного поиска.
№9 слайд
![Различают методы условной и](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img8.jpg)
Содержание слайда: Различают методы условной и безусловной оптимизации по наличию или отсутствию ограничений.
Различают методы условной и безусловной оптимизации по наличию или отсутствию ограничений.
Для реальных задач характерно наличие ограничений.
Однако задачи условной оптимизации с помощью специальных методов могут быть сведены к задачам без ограничений
(к безусловной оптимизации).
№10 слайд
![В зависимости от числа](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img9.jpg)
Содержание слайда: В зависимости от числа экстремумов различают задачи одно- и многоэкстремальные.
В зависимости от числа экстремумов различают задачи одно- и многоэкстремальные.
Локальный метод ориентирован на определение какого-либо локального экстремума.
Метод глобального поиска – метод, результатом которого является глобальный экстремум.
Удовлетворительные по вычислительной эффективности методы глобального поиска для общего случая отсутствуют и потому на практике в САПР используют методы поиска локальных экстремумов.
№11 слайд
![Методы нескольких порядков](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img10.jpg)
Содержание слайда: Методы нескольких порядков различают по использованию при поиске производных целевой функции по управляемым параметрам.
Методы нескольких порядков различают по использованию при поиске производных целевой функции по управляемым параметрам.
Если производные не используются, то имеет место метод нулевого порядка, если используются первые или вторые производные, то соответственно метод первого или второго порядка.
№13 слайд
![Конкретные методы](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img12.jpg)
Содержание слайда: Конкретные методы определяются следующими факторами:
Конкретные методы определяются следующими факторами:
1) способом вычисления направления поиска g(Xk) в формуле ;
2) способом выбора шага h;
3) способом определения окончания поиска.
Определяющим фактором является первый.
№14 слайд
![Шаг может быть постоянным или](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img13.jpg)
Содержание слайда: Шаг может быть постоянным или выбираться исходя из одномерной оптимизации — поиска минимума целевой функции в выбранном направлении g(Xk).
Шаг может быть постоянным или выбираться исходя из одномерной оптимизации — поиска минимума целевой функции в выбранном направлении g(Xk).
В последнем случае шаг будем называть оптимальным.
№18 слайд
![Базовая общая задача](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img17.jpg)
Содержание слайда: Базовая (общая) задача оптимизации ставится как задача математического программирования:
Базовая (общая) задача оптимизации ставится как задача математического программирования:
где F(X) — целевая функция, X — вектор управляемых (проектных) параметров, φ(X) и ψ(X) — функции-ограничения,
Dx —допустимая область в пространстве управляемых параметров.
№19 слайд
![В общей задаче](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img18.jpg)
Содержание слайда: В общей задаче математического программирования необходимые условия экстремума (условия Куна-Таккера) формулируются:
В общей задаче математического программирования необходимые условия экстремума (условия Куна-Таккера) формулируются:
для того, чтобы точка Q была экстремальной точкой выпуклой задачи математического программирования (ЗМП), необходимо наличие неотрицательных коэффициентов ui, таких, что
и при этом соблюдались ограничения задачи, а также выполнялось условие
где m — число ограничений типа неравенств, L— то же равенств, коэффициенты aj>0.
№21 слайд
![Рассмотрим случай с](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img20.jpg)
Содержание слайда: Рассмотрим случай с ограничениями только типа неравенств.
Рассмотрим случай с ограничениями только типа неравенств.
Если максимум находится внутри допустимой области R, то, выбирая все ui=0, добиваемся выполнения
если же точка максимума Q лежит на границе области R, то, как видно из левой части рисунка, эту точку всегда соответствующим подбором неотрицательных ui можно поместить внутрь оболочки, натянутой на градиенты целевой функции F(X) и
функций-ограничений φi(X).
№22 слайд
![Наоборот, если точка не](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img21.jpg)
Содержание слайда: Наоборот, если точка не является экстремальной, то условие
Наоборот, если точка не является экстремальной, то условие
нельзя выполнить при любом выборе положительных коэффициентов ui
(см. правую часть рисунка, где рассматриваемая точка N лежит вне выпуклой оболочки, натянутой на градиенты).
Учет ограничений типа равенств очевиден, если добавляется сумма
№26 слайд
![Необходимые условия](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img25.jpg)
Содержание слайда: Необходимые условия экстремума функции :
Необходимые условия экстремума функции :
Система содержит n+L алгебраических уравнений, где
n - размерность пространства управляемых параметров. Её решение - искомые координаты экстремальной точки и значения множителей Лагранжа.
При численном решении системы (алгоритмические модели) возникают трудности. Поэтому в САПР основными методами решения ЗМП являются методы штрафных функций и проекции градиента.
№27 слайд
![Основная идея методов](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img26.jpg)
Содержание слайда: Основная идея методов штрафных функций — преобразование задачи условной оптимизации в задачу безусловной оптимизации путем формирования новой целевой функции Ф(N) введением в исходную целевую функцию F(X) специальным образом выбранной функции штрафа S(X):
Основная идея методов штрафных функций — преобразование задачи условной оптимизации в задачу безусловной оптимизации путем формирования новой целевой функции Ф(N) введением в исходную целевую функцию F(X) специальным образом выбранной функции штрафа S(X):
где r - множитель, значения которого можно изменять в процессе оптимизации.
№28 слайд
![Среди методов штрафных](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img27.jpg)
Содержание слайда: Среди методов штрафных функций различают методы внутренней и внешней точки.
Среди методов штрафных функций различают методы внутренней и внешней точки.
Согласно методам внутренней точки (методам барьерных функций) исходную для поиска точку можно выбирать только внутри допустимой области, а для методов внешней точки как внутри, так и вне допустимой области (в ней функции целевая и ограничений должны быть определены).
№29 слайд
![Ситуация появления барьера у](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img28.jpg)
Содержание слайда: Ситуация появления барьера у целевой функции Ф(х) и соотношение между условным в точке х2 и безусловным в точке х1 минимумами F(x) в простейшем одномерном случае иллюстрируется рисунком
Ситуация появления барьера у целевой функции Ф(х) и соотношение между условным в точке х2 и безусловным в точке х1 минимумами F(x) в простейшем одномерном случае иллюстрируется рисунком
№30 слайд
![Примеры штрафных функций](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img29.jpg)
Содержание слайда: Примеры штрафных функций:
Примеры штрафных функций:
для метода внутренней точки при ограничениях
где m - число ограничений типа неравенств;
для метода внешней точки при таких же ограничениях
здесь штраф сводится к включению в Ф(N) суммы квадратов активных (т.е. нарушенных) ограничений;
3) в случае ограничений типа равенств
№31 слайд
![Чем больше коэффициент r, тем](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img30.jpg)
Содержание слайда: Чем больше коэффициент r, тем точнее решение задачи, однако при больших r может ухудшаться ее обусловленность.
Чем больше коэффициент r, тем точнее решение задачи, однако при больших r может ухудшаться ее обусловленность.
Поэтому в начале поиска обычно выбирают умеренные значения r, увеличивая их в окрестностях экстремума.
№33 слайд
![Поиск при выполнении](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img32.jpg)
Содержание слайда: Поиск при выполнении ограничений осуществляется в подпространстве
Поиск при выполнении ограничений осуществляется в подпространстве
(n-m) измерений,
где n - число управляемых параметров, m - число ограничений.
При этом движение осуществляется в направлении проекции градиента целевой функции F(X) на гиперплоскость, касательную к гиперповерхности ограничений (точнее к гиперповерхности пересечения гиперповерхностей ограничений).
№34 слайд
![Поиск минимума начинают со](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img33.jpg)
Содержание слайда: Поиск минимума начинают со спуска из исходной точки на гиперповерхность ограничений. Далее выполняют шаг в указанном выше направлении (шаг вдоль гиперповерхности ограничений).
Поиск минимума начинают со спуска из исходной точки на гиперповерхность ограничений. Далее выполняют шаг в указанном выше направлении (шаг вдоль гиперповерхности ограничений).
Поскольку этот шаг может привести к заметному нарушению ограничений, вновь повторяют спуск на гиперповерхность ограничений и т.д.
№36 слайд
![На рисунке это ограничение](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img35.jpg)
Содержание слайда: На рисунке это ограничение представлено жирной линией, а целевая функция — совокупностью более тонких линий равного уровня.
На рисунке это ограничение представлено жирной линией, а целевая функция — совокупностью более тонких линий равного уровня.
Спуск обычно осуществляют по нормали к гиперповерхности ограничений (в данном случае к линии ограничения).
Условие окончания поиска основано на сопоставлении значений целевой функции в двух последовательных точках, получаемых после спуска на гиперповерхность ограничений.
№39 слайд
![Используем метод множителей](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img38.jpg)
Содержание слайда: Используем метод множителей Лагранжа, обозначая А-В=U и учитывая, что минимизация расстояния равнозначна минимизации скалярного произведения U на U, получаем
Используем метод множителей Лагранжа, обозначая А-В=U и учитывая, что минимизация расстояния равнозначна минимизации скалярного произведения U на U, получаем
тогда из второго выражения получаем
подставляя его в третье выражение, имеем
откуда
Подставляя λ во второе выражение, находим
№40 слайд
![Движение вдоль](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img39.jpg)
Содержание слайда: Движение вдоль гиперповерхности ограничений
Движение вдоль гиперповерхности ограничений
Шаг в гиперплоскости D, касательной к гиперповерхности ограничений, следует сделать в направлении вектора S, на котором целевая функция уменьшается в наибольшей мере при заданном шаге h.
№41 слайд
![Уменьшение целевой функции](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img40.jpg)
Содержание слайда: Уменьшение целевой функции при переходе из точки А в новую точку С подсчитывают, используя формулу линеаризации F(X) в окрестностях точки А:
Уменьшение целевой функции при переходе из точки А в новую точку С подсчитывают, используя формулу линеаризации F(X) в окрестностях точки А:
где - приращение F(X),
которое нужно минимизировать, варьируя направления S.
№42 слайд
![где вариация S осуществляется](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img41.jpg)
Содержание слайда: где вариация S осуществляется в пределах гиперплоскости D; grad ψ(A) и S — ортогональные векторы.
Следовательно, минимизацию этого выражения необходимо выполнять при ограничениях
Последнее ограничение говорит о том, что при поиске направления движения, вектор S должен лишь указывать это направление, т.е. его длина несущественна (пусть S — единичный вектор).
№45 слайд
![Частным случаем применения](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img44.jpg)
Содержание слайда: Частным случаем применения метода проекции градиента являются задачи оптимизации с максиминным критерием. Для поиска экстремума функции минимума
Частным случаем применения метода проекции градиента являются задачи оптимизации с максиминным критерием. Для поиска экстремума функции минимума
где Zj — нормированная величина
j-го выходного параметра yj,
удобно применять метод проекции градиента.
№46 слайд
![В качестве ограничений задачи](/documents_6/3e8f699864ccbf0842a6ae7bcd98b374/img45.jpg)
Содержание слайда: В качестве ограничений задачи в исходной постановке фигурируют только прямые ограничения
В качестве ограничений задачи в исходной постановке фигурируют только прямые ограничения
Здесь хmaxi и xmini — граничные значения допустимого диапазона варьирования параметра хi.
В процессе поиска, если минимальной является функция Zq(X) и траектория поиска пересекает гребень
то поиск продолжается в направлении проекции градиента функции Zq(X) на гиперповерхность этого гребня.
Скачать все slide презентации Методы поиска экстремума одним архивом:
Похожие презентации
-
Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ
-
Экспертные системы. Методы поиска решений
-
Методы программирования. Алгоритмы поиска. (Лекция 5)
-
Методы программирования. Поиск в тексте. (Лекция 6)
-
Лекция 13. Сортировка и поиск информации. Методы внутренней сортировки
-
Методика решения заданий типа «Робот в лабиринте»
-
Методика решения графических тестов
-
Методы улучшения алгоритмов сортировок. Лекция 7
-
Метод сортировки пирамидой
-
Решение простейших задач линейного программирования графическим методом