Необходимые и достаточные условия оптимальности

МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

[ Одномерная оптимизация.] [ Необходимые и достаточные условия оптимальности.]
[ Методы половинного деления], [ "золотого" сечения], [ Фибоначчи.]
[ Методы с использованием производных ]. [ Mетоды полиномиальной аппроксимации ]

Методы безусловной оптимизации делятся на методы одномерной и многомерной оптимизации.

МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

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

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

o методы исключения интервалов:

§ метод половинного деления;

§ метод "золотого" сечения;

§ метод Фибоначчи;

• методы полиномиальной аппроксимации;
• методы с использованием производных.

Необходимые и достаточные условия оптимальности.

МЕТОДЫ ИСКЛЮЧЕНИЯ ИНТЕРВАЛОВ

Методы поиска, которые позволяют определить оптимум функции одной переменной путем уменьшения интервала поиска, носят название методов исключения интервалов.

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

Правило исключения интервалов. Пусть W(x) унимодальна на отрезке [a,b], а ее минимум достигается в точке x*. Рассмотрим x₁ и x₂, расположенные a<x₁<x₂<b.

o Если W(x₁)>W(x₂), то точка минимума W(x) не лежит в интервале (a,x₁), т.е. x*Є (x₁,b).

• Если W(x₁)<W(x₂), то точка минимума W(x) не лежит в интервале (x₂,b), т.е. x*Є (a,x₂).

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

Главное достоинство поисковых методов - основаны на вычислении только значений функции и, следовательно, не требуют выполнения условия дифференцируемости и записи в аналитическом виде. Последнее свойство особенно ценно при имитационном моделировании.

Процесс применения методов поиска на основе исключения интервалов включает два этапа:

o этап установления границ интервала;

o этап уменьшения интервала.