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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



 

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

 

 

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

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

 

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

2 варианта:

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

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

 

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

 

 

2 способа:

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

- численный

 

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

 

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

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

 

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

 

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

 

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

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

       
 
   
 

 


 

 
 



 

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

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

 
 

 

 


а b

 

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

 

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

 

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

 
 

 


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

 

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

 

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

 

               
   
     

 


 

1)

2)

 

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

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

 

 

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

 

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

 

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

 

а b

 
 


; ; ;

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

 

а

 
 

 


 

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

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

 

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

 

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

 

 
 

 

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

 



Поделиться:


Последнее изменение этой страницы: 2017-02-07; просмотров: 98; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.192.73.68 (0.011 с.)