Реферат на тему Методы недифференцируемой оптимизации

Содержание:

Введение. 3

1.   Недифференцируемая оптимизация. 4

2.   Классификация методов оптимизации. 7

3.   Методы недифференцируемой оптимизации. 10

Заключение. 17

Список
использованной литературы.. 18

Введение:

Среди
существующих методов поиска глобального экстремума перспективны
рандомизированные подходы. Они чаще всего построены на сочетании случайного
просмотра области поиска Х и локальных детерминированных алгоритмов поиска
минимума.

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

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

Цель работы
– теоретически обосновать методы недифференцируемой оптимизации.

Задачи:

—
изучить недифференцируемую оптимизацию;

—
проанализировать методы недифференцируемой оптимизации.

Заключение:

В
ходе исследования данной темы, можно сделать такие выводы:

· Методы обобщенного градиентного спуска
(ОГС). Они положили начало новому направлению математического программирования
– численным методам негладкой оптимизации, которому в настоящее время посвящены
многочисленные научные статьи и монографии.

· Субградиентные методы с растяжением
пространства в направлении субградиента, которые имеют ускоренную сходимость в
сравнении с методами ОГС. Эти методы дали теории оптимизации уникальный в своем
роде алгоритм – метод эллипсоидов, скорость сходимости которого зависит лишь от
размерности пространства.

· Субградиентные методы с растяжением
пространства в направлении разности двух последовательных субградиентов –
r-алгоритмы. В рамках этого семейства методов получены достаточно эффективные
реализации r-алгоритмов.

· Недифференцируемая оптимизация решает
класс задач, которые неразрешимы для классических методов
оптимизации. Большая часть теории такова на основе понятия
субградиентов и делается большая часть работы для выпуклого случая. Она
имеет обилие применений в реальной жизни, потому что аспект
недифференцируемости отражает некоторую внутреннюю сложность реальных
проблем.

· Хорошо
известно, что недифференцируемые функции не могут быть использованы для
градиентной оптимизации, поскольку алгоритмы оптимизации предполагают плавное
изменение градиентов. Чтобы справиться с недифференцируемыми функциями в
оптимизации, инженеры часто аппроксимируют недифференцируемую функцию,
используя гладкую дифференцируемую функцию. Однако процесс аппроксимации
делает функцию сильно нелинейной, что затрудняет оптимизацию.

Фрагмент текста работы:

1. Недифференцируемая
оптимизация Оптимизация
в широком смысле слова находит применение в науке, технике и в любой другой
области человеческой деятельности. Оптимизация – целенаправленная
деятельность, заключающаяся в получении наилучших результатов при
соответствующих условиях. Поиски оптимальных решений привели к созданию
специальных математических методов и уже в 18 веке были заложены математические
основы оптимизации (вариационное исчисление, численные методы и др.). Однако до
второй половины 20 века методы оптимизации во многих областях науки и
техники применялись очень редко, поскольку практическое использование
математических методов оптимизации требовало огромной вычислительной работы,
которую без ЭВМ реализовать было крайне трудно, а в ряде случаев –
невозможно. Особенно большие трудности возникали при решении задач оптимизации
из-за большого числа параметров и их сложной взаимосвязи между собой. При
наличии ЭВМ ряд задач оптимизации поддается решению. Обычно
оптимизируемая величина связана с экономичностью работы рассматриваемого
объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта
должен оцениваться какой-то количественной мерой – критерием оптимальности. Критерием
оптимальности называется количественная оценка оптимизируемого качества объекта
[5, c.
62].

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

Наиболее
общей постановкой оптимальной задачи является выражение критерия
оптимальности в виде экономической оценки (производительность, себестоимость продукции,
прибыль, рентабельность). Однако в частных задачах оптимизации, когда
объект является частью технологического процесса, не всегда удается или не
всегда целесообразно выделять прямой экономический показатель, который бы
полностью характеризовал эффективность работы рассматриваемого объекта. В таких
случаях критерием оптимальности может служить технологическая
характеристика, косвенно оценивающая экономичность работы агрегата (время
контакта, выход продукта, степень превращения, температура). Например,
устанавливается оптимальный температурный профиль, длительность цикла
«реакция–регенерация».

Недифференцируемая
оптимизация-это категория оптимизации, которая имеет дело с целью, которая по
целому ряду причин является недифференцируемой и, следовательно,
невыпуклой. Функции в этом классе оптимизации, как правило,
негладкие. Эти функции, хотя и непрерывные, часто содержат острые точки
или углы, которые не допускают решения касательной и, следовательно,
недифференцируемы. На практике недифференцируемая оптимизация охватывает
большое разнообразие задач, и единственное универсальное решение неприменимо,
однако решение часто достигается путем реализации субградиентного метода [1, c. 102].

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

Недифференцируемая
оптимизация имеет дело с задачами, в которых предположение о
гладкости функций ослаблено, а это означает, что градиенты не обязательно
существуют. В недифференцируемой оптимизации функции могут иметь перегибы
или угловые точки, поэтому они не могут быть аппроксимированы локально
касательной гиперплоскостью или квадратичной
аппроксимацией. Недифференцируемые оптимизационные задачи возникают в
различных контекстах, таких как приложения при прямолинейной подгонке данных,
задачи, включающие ℓ1ℓ1 (Евклидово) или ℓ∞ℓ∞ (Чебычев)
нормы и алгоритмы, такие как точные штрафные методы, которые превращают
ограниченные задачи в неограниченные задачи. Поскольку негладкость
проявляется многими различными способами, не существует методов решения"
черного ящика", которые должны быть применены; вместо этого методы решения
разрабатываются для обработки конкретной структуры проблемы.

Простым примером недифференцируемой
оптимизации является аппроксимация Кинка, возникающего из функции абсолютного
значения. Простая функция это
пример функции, которая, будучи непрерывной для бесконечной области, является
недифференцируемой из-за
наличия "излома" или точки, которая не допускает решения
касательной. Поскольку недифференцируемая точка функции известна,
аппроксимация может быть добавлена для расслабления и сглаживания функции с
параметром . Это новое
приближение может быть смоделировано При
недифференцируемой оптимизации весь субдифференцированный набор никогда не
вычисляется. Субградиенты вычисляются, когда это необходимо, и часто
достаточно одного элемента. Общепринятой практикой является выделение
процедур вычисления субградиентов в оракул. Количество обращений к оракулу
может служить основой для сравнения различных методов NDO [9, c. 79].