Численные методы оптимизации - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Численные методы оптимизации. Доклад-сообщение содержит 24 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ Константин Ловецкий lovetskiy@gmail.com Сентябрь 2012

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

Постановка задачи оптимизации Постановка задачи оптимизации начинается с определения набора независимых переменных и обычно включает условия, которые характеризуют их приемлемые значения. Эти условия называют ограничениями задачи. Еще одной обязательной компонентой описания является скалярная мера «качества», именуемая целевой функцией и зависящая каким-то образом от переменных. Решение оптимизационной задачи — это приемлемый набор значений переменных, которому отвечает оптимальное значение целевой функции. Под оптимальностью обычно понимают максимальность или минимальность; например, речь может идти о максимизации прибыли или минимизации массы.

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

Классификация оптимизационных задач Подавляющее большинство оптимизационных задач, возникающих на практике, приводятся к стандартному виду. Даже те задачи, которые сами по себе в эти рамки не укладываются, часто могут быть сведены к последовательности стандартных. Однако существование столь универсальной формы представления вовсе не означает, что различиями между отдельными задачами следует пренебрегать. Наоборот, имея дело с конкретной постановкой, всегда надо постараться использовать ее особенности для того, чтобы организовать поиск решения самым эффективным образом. К примеру, усилия можно сэкономить, отказавшись от каких-то проверок, необходимых в общем случае, но лишних в конкретном, или избежав повторных вычислений величин, являющихся константами. Рассмотрим классификацию разнообразных задач по тем их особенностям, которые наиболее существенны для выбора алгоритма решения.

Слайд 8

Описание слайда:

Постановка задачи оптимизации Вначале обсудим весьма широкий класс задач, именуемых нелинейными непрерывными задачами условной оптимизации (NCP). Ставятся они следующим образом:

Слайд 9

Описание слайда:

Класс задач NCP разбивают на подклассы, и делается это по ряду признаков, существенных для выбора алгоритма и метода решения. Класс задач NCP разбивают на подклассы, и делается это по ряду признаков, существенных для выбора алгоритма и метода решения.

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Классификация оптимизационных задач

Слайд 12

Описание слайда:

В соответствии с данными определениями х* не будет точкой локального минимума, если в любой ее окрестности найдется допустимая точка с меньшим значением F. В соответствии с данными определениями х* не будет точкой локального минимума, если в любой ее окрестности найдется допустимая точка с меньшим значением F. Определение решения задачи NCP как точки локального минимума на первый взгляд может показаться довольно искусственным — ведь ясно, что наибольший интерес, как правило, представляет глобальный минимум, т. е. точка, в которой значение целевой функции не хуже, чем в любой допустимой, а не только в близлежащих. Однако если мы хотим называть рассматриваемые в дальнейшем процедуры методами решения задач NCP, то решение надо определять именно так, поскольку все они являются методами локальной минимизации. Конечно, с их помощью можно искать и точки глобальных минимумов, но, за исключением ряда специальных случаев, когда локальное решение автоматически оказывается глобальным, успеха здесь гарантировать нельзя. Что же касается других методов, которые надежно сходились бы к точкам глобальных минимумов в мало-мальски интересных многоэкстремальных задачах, то их просто не существует. Последнее, впрочем, не должно удручать практиков, поскольку для большинства прикладных задач удовлетворительные решения все-таки находятся.

Слайд 13

Описание слайда:

БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ Мы начнем изучение условий оптимальности с простейшей задачи о безусловной минимизации функции одной переменной: найти Если всюду дважды непрерывно дифференцируема и х*— точка ее локального минимума, то должны выполняться следующие соотношения:

Слайд 14

Описание слайда:

Слайд 15

Описание слайда:

Функции одной переменной Метод золотого сечения. Пусть задана функция Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки такие, что:

Слайд 16

Описание слайда:

Формализация метода золотого сечения

Слайд 17

Описание слайда:

Троичный поиск

Слайд 18

Описание слайда:

Троичный поиск

Слайд 19

Описание слайда:

Бассейны Ньютона

Слайд 20

Описание слайда:

Метод Ньютона

Слайд 21

Описание слайда:

Метод Ньютона

Слайд 22

Описание слайда:

Интернет – наше ВСЕ! Опыт – это то, что ты получаешь только тогда, когда в нем нуждаешься … Справочник по проблемам оптимизации Decision Tree for Optimization Software

Слайд 23

Описание слайда:

История

Слайд 24

Описание слайда:

История Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; советский академик, лауреат Нобелевской премии (1975 г.) Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший (1939 г.) метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.