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

 

Постановка: требуется оптимизировать х (формальная постановка)

 

 

- функция одной переменной

- целевая функция.

 

Решение: найти х, при котором принимает оптимальное значение.

2 варианта:

- минимизировать – задача минимизации;

- максимизировать – задача максимизации.

 

Рассмотрим случай минимизации

 

 

2 способа:

- аналитический

- численный

 

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

 

Пусть функция определена в некоторой области S (), в случае одномерной оптимизации S – интервал :

1. точка называется глобальным минимумом, если для
2. точка называется строгим глобальным минимумом, если для
3. точка называется локальным минимумом, если для
4. точка называется строгим локальным минимумом, если для

 

Следствие: любая точка глобального минимума является локальным минимумом, обратное не верно.

 

Аналитический способ нахождения локального минимума.

 

- дифференцируема

- необходимое условие точки локального минимума.

 

 

 

Численные методы.

Пусть функция задана на интервале , при этом существует такая точка , что на – монотонно убывает, а на – монотонно возрастает, то функция унимодальная.

 

 

а b

 

Если из того что следует, что , то функция называется монотонно возрастающей. Если из того что следует, что , то функция называется монотонно убывающей.

 

Методы одномерного поиска.

 

Разобьем и вычислим значение функции в каждой точке.

 

искомый минимум

 

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

 

Интервал неопределенности – интервал, в котором заведомо находится точка минимума. Наиболее эффективное разбиение – двумя точками на 3 равных отрезка.

 

 

 

1)

2)

 

- после выполнения n шагов сокращение исходного интервала

- точность с которой надо найти решение задачи.

 

 

N=2n, где n – число шагов, N – число вычислений (мера эффективности данного решения).

 

Метод золотого сечения.

 

Точки должны быть расположены на равном расстоянии.

 

а b

; ; ;

; - золотое сечение.

 

а

 

 

- величина сокращения на каждом шаге

число итераций растет как логарифм функции.

 

Одномерная оптимизация с использованием производных.

 

. Пусть целевая функция дифференцируема .

 

точка локального минимума	точка локального максимума	точка перегиба