Общий отчёт по МО
.pdfМинистерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра комплексной информационной безопасности электронно-
вычислительных систем (КИБЭВС)
Применение методов оптимизации для различных задач Общий отчёт по лабораторным работам по дисциплине «Методы оптимизации»
Студент гр. 711-2
_______ Е. П. Толстолес
_______
Принял:
Ст. преподаватель кафедры КИБЕВС
_______ А. Ю. Якимук
_______
Томск 2022
1 Введение
Необходимо для функций 4(х-9)*(х-3)*(х-1), х/4+7*sin(3*pi*x+1), и
функции 4-7*e^-((x-3)^2) вычислить точки минимума методами: золотого сечения, дихотомии и Фибоначчи. Составить теоретическое описание методов, описать процесс выбора отрезка, список границ отрезка при каждой итерации и построить график функций.
Атакже для функций 4*(X1 - 7)^2 + 3*(X2 - 1)^2 и функции (X1 - 4)^2
+(X2 - 7)^2 + 30*(X2 + X1 - 6)^2 + 7,1 вычислить точки минимума методами:
Нелдера-Мида, наискорейшего спуска и овражным. Составить теоретическое описание методов, описать процесс выбора отрезка, список границ отрезка при каждой итерации и построить график функций.
2
2 Ход работы:
2.1Одномерная оптимизация без ограничений
2.1.1Метод золотого сечения
Пусть функция ( ) унимодальна на отрезке [ 1, 1]. Нужно найти минимум данной функции на заданном отрезке с некоторой точностью .
Принцип золотого сечения заключается в следующем: на каждом шаге
отрезок |
, длиной |
|
делится на две части так, чтобы отношение всего |
|
|
|
отрезка длиной к большей его части длиной |
было равно отношению |
|||||
большей части к меньшей части длиной (1 - ) |
: |
|
||||
|
|
= |
Δ |
., где 0.5<a<1 |
|
|
|
|
|
|
|||
|
Δ |
(1− )Δ |
|
|
||
Получим значение . Для этого сократим пропорцию на |
: |
= 1 −
Перемножим части по правилу пропорции и получим уравнение:
2 + − 1 = 0
Корни у этого уравнения, следующие:
|
|
|
|
|
|
|
|
= − |
1 |
± √ |
1 |
+ 1 = |
−1 ± √5 |
|
|
|
|
|
|||||
1,2 |
2 |
4 |
2 |
|
|
||
|
|
|
Для наших вычислений нужен положительный корень, обозначим его:
= √5 − 1 ≈ 0.618 2
Также введем
3
= 1 − ≈ 0.382.
Опишем k –й шаг метода.
Известны , , и вычислены значения функции ( ), ( ).
Вычисляем две симметричные относительно середины отрезка точки
|
[ ] = |
+ |
|
, |
β |
|
|
|
|
|
[ ] = |
+ |
|
, |
α |
|
|
|
и значения функции в этих точках ( α[ ]), (xβ[ ]).
Сокращаем интервал неопределенности следующим образом:
если ( β[ ]) ≥ (xα[ ]), то +1 = β[ ], +1 = ;
если ( β[ ]) ≤ ( α[ ]), то +1= , +1 = ,
Обратите внимание, что за один раз меняется только одна граница отрезка. Длина интервала неопределенности становится
+1 = = 1,
то есть на k –й итерации интервал неопределенности сокращается меньше,
чем в 2 раза.
Условие останова:
< ,
точкой минимума является аргумент меньшего из значений ( α [ +
1]) и (xβ [ + 1]).
2.1.2 Метод дихотомии
4
Пусть функция ( ) унимодальна на отрезке [ 1, 1]. Нужно найти минимум данной функции на заданном отрезке с некоторой точностью .
Вычислим 2 точки по следующим соотношениям:
|
= |
1+ 1−δ |
, |
= |
1+ 1+δ |
, где 0 < < . |
|
|
|||||
1 |
|
2 |
2 |
2 |
|
|
|
|
|
|
В каждой найденной точке вычисляем ( 1), ( 2).
Дальше сокращаем интервал неопределенности и получаем интервал
[ 1, 2] следующим образом:
если ( 1) ≤ ( 2), то 2 = 1, 2 = 2;
если ( 1) ≥ ( 2), то 2 = 1, 2 = 1,
опять же за один раз меняется только одна граница отрезка.
Далее по аналогичным формулам на этом интервале вычисляем следующую пару точек 1 и 2. С помощью найденных точек определяем новый интервал неопределенности.
Условие останова: длина интервала неопределенности [ , ] на текущей итерации k становится меньше заданной точности:
| - | < ,
точкой минимума является середина последнего отрезка [ , ]. В
данном методе на каждой итерации минимизируемая функция f(x)
вычисляется дважды, интервал неопределенности сокращается почти в 2 раза
(при малых < ).
2.1.3 Метод Фибоначчи
Последовательность Фибоначчи подчиняется соотношению:
5
+2= +1+ ,
где n =1,2, ... , и начальные значения 1 = 2 = 1.
Она имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,…
С помощью метода математической индукции можно показать, что n -е число Фибоначчи вычисляется по формуле Бинэ:
[1+√5] −[1−√5]
= 2 √5 2 ,
где = 1, 2, 3, ...
Из данной формулы видно, что при больших значениях выполняется соотношение:
[1+√5]
≈ 2 5 ,
√
так что числа Фибоначчи с увеличением n растут очень быстро. Сам метод Фибоначчи очень похож на метод золотого сечения и дихотомии. На k -ой итерации промежуточные точки вычисляются по формулам:
[ ] = |
|
+ |
− +1 |
( |
- |
) = |
|
+ |
− +1 |
|
( |
- ), |
|||
|
|
||||||||||||||
1 |
|
|
− +3 |
|
|
|
|
|
|
|
1 |
1 |
|||
|
|
|
|
|
|
|
|
|
|
|
+2 |
|
|
||
[ ] = + |
− +2 |
|
( - ) = + |
− +1 |
( - ) |
||||||||||
|
|
|
|
||||||||||||
2 |
|
|
− +3 |
|
|
|
|
|
|
|
1 |
1 |
|||
|
|
|
|
|
|
|
|
|
|
|
+2 |
|
|
и расположены на отрезке [ , ] симметрично относительно его середины.
Интервал неопределенности сокращается точно так же, как в методе золотого сечения:
если ( 1[ ]) ≥ ( 2[ ]), то +1 = 1[ ], +1 = , .
если ( 1[ ]) ≤ ( 2[ ]), то +1 = , , +1= 2[ ].
Можно заметить, что при = точки
1[ ] = + 1 ( 1 - 1)
+2
6
2[ ] = + 2 ( 1 - 1)
+2
совпадают и делят отрезок [ , ] пополам.
Следовательно,
− = 1−1< ,
2 +2
и, значит, можно выбрать n из условия
1−1< +2.
ε
Таким образом, это условие позволяет до начала работы определить число итераций, нужное для определения минимума с заданной точностью при начальной величине интервала [ 1, 1].
Условие останова:
< ,
точкой минимума является аргумент меньшего из значений ( 1[k + 1]) и
( 2[k + 1]).
С ростом n из-за того, что – бесконечная десятичная дробь, возникает
+2
погрешность метода и возможна потеря интервала с точкой минимума.
Следует отметить также, что при практическом применении метод золотого сечения по скорости сходимости и точности получаемого решения почти не уступает методу Фибоначчи, а алгоритмически реализация метода золотого сечения является более простой.
7
2.2 Вывод программы для вычисления точек минимума
На рисунках 2.1–2.6 показаны выводы программы для трёх заданных вариантом функций.
Рисунок 2.1 – Вывод программы для функции 4*(x-7)*(x-3)*(x-1)
8
Рисунок 2.2 – Продолжение вывода программы для функции 4*(x-7)*(x- 3)*(x-1)
9
Рисунок 2.3 – Вывод программы для функции x/4+7*sin(3*pi*x+1)
10