Краткие выводы к первому разделу.

1. Изучен метод Эйлера – классический, аналитико-численный метод безусловной оптимизации. Основа метода: необходимое и достаточное условие для точки локального минимума (максимума) целевой функции .

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

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

2. Изучены методы решения классической задачи условной оптимизации:

а) метод исключения (подстановки);

б) ММЛ;

в) графо-аналитический метод.

3. Вышеуказанные методы перестают быть эффективными при увеличении размерности пространства . При целесообразно использовать прямые численные методы оптимизации, ориентированные на применение высокопроизводит. ЭВМ.

 

ЛК №10

17.04.2003

 

Раздел 2

Численные методы безусловной оптимизации.

Цель всех вычислений – не числа, а понимание.

 

Численные методы одномерной оптимизации.

К числу этих методов относятся:

а) метод дихотомии;

б) метод золотого сечения;

в) метод Фибоначчи.

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

 

Метод дихотомии (МД) (метод деления отрезка пополам).

Сущность МД легко понять, рисуя следующую графическую иллюстрацию.

На отрезке задана функция с одним минимумом ( унимодальная ).

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

; ; .

Если , то , .

Если , то , .

Вычисляем до тех пор, пока ,

 

.

На каждой итерации МД отрезок локализации минимума уменьшается в два раза. После -той итерации он будет равен: . На каждой итерации метода дихотомии функция вычисляется два раза. Поэтому число вычислений функции и число итераций и связано отношением: .

Тогда при .

 

Метод золотого сечения (МЗС).

Этот метод основан на свойствах золотого сечения отрезка .

Точка будет точкой золотого сечения отрезка , если выполняется условие:

; .

Точка симметрична относительно середины отрезка точке . Будем представлять золотое сечение :

; .

Точка является золотым сечением не только , но и отрезка . Соответственно, точка является точкой золотого сечения не только , но и отрезка .

, ;

, .

Даже необходимо найти и значение координат точек и .

; ;

;

;

;

; ; ; ; ;

 

 

; ; ;

; .

Изучив свойства золотого сечения отрезка целесообразно перейти к МЗС поиска точки унимодальной функции , заданной на отрезке .

Поиск необходимо произвести с заданной точностью .

Характерной особенностью МЗС является меньшее по сравнению с МД число вычислений функции на каждой итерации кроме первой.

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

Рассмотрим графическую иллюстрацию, позволяющую легко понять суть МЗС – метода поиска точки минимума унимодальной функции .

Точка вычисляется по формуле:

.

 

Соответственно находятся значения функции в этой точке .

Но самое главное то, что точка является точкой золотого сечения отрезка и соответственно это подтверждает правомерность операции присвоения:

и .

Если , то ; ; , вычисляется.

Если - присвоение, а вычисляется.

Если , то ; ; , а вычисляется по формуле: .

Соответственно , а вычисляется.

Из рисунка и соответствующих формул видно, что , т.е. подтверждаются все ранее упомянутые достоинства МЗС.

Приведем формулы для оценки эффективности МД и МЗС.

Введем коэффициент вида: . Этот коэффициент характеризует скорость сходимости МД, его можно представить в форме: , .

, учитывая что: .

.

Предположим, что (точность вычисления) задана и одинакова для каждого из методов, тогда и , .

; .

 

Метод Фибоначчи.

Этот метод использует последовательность чисел Фибоначчи, представляемого рекуррентным соотношением:

 

ЛК №12

15.05.2003

 

Алгоритм МФ сходен с алгоритмом МЗС.

МФ лишь немного эффективнее МД.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: