–PAGE_BREAK–
Вывод: метод является эффективным для измерения оптимума унимодальной функции, причем изменение шага поиска или кратности уменьшения шага ( при неизменной погрешности вычисления на результат практически не влияет).
Одномерная оптимизация методом квадратичной интерполяции.
В предыдущих методах была сделана попытка найти малый интервал, в котором находится оптимум функции f(х). В этом методе применяется иной подход. Он заключается в построении аппроксимирующей модели оптимизируемой функции (х). Функция может аппроксимирована полиномом второго порядка:
(х) = ах2 + Ьх + с
по крайней мере в небольшой области значений, в том числе в области оптимума. При этом положении экстремума (х)определяется по положению экстремума полинома, поскольку последний вычислить проще.
Экстремум функции fап(х)как известно расположен в точке: = -Ь/2а.
Положим, что окрестность некоторой исходной точки х=х1 области определения f(х) аппроксимирована полиномом fап (х).Задача поиска заключается в определении смещения
= х°ап – х1
Которое приводит из исходного состояния х = х1, ближе к экстремуму х = х°. Если f(х) строго квадратичная функция, то смещение после первого шага сразу приведет к. В противном случае достижение х° требует выполнения итерационной процедуры. Для определения смещения нужно определить коэффициенты параболы. Для этого необходимо вычислить значение f(х)в трех точках. Пусть вычисление производится в исходном состоянии х = х1 и в точках, , и при этом получено три значения этой функции
,
гдеh— полуинтервал интерполяции, малая постоянная величина. Подставляя эти значения в уравнение (х), получаем систему из трех линейных уравнений с тремя неизвестнымиа, Ь, с:
а(х1 —
h)2 + Ь(х1 —
h) + с =а(х1 —
h)2 + Ь(х1 —
h) + с =
а*х12 + Ь*х1 + с =
а(х1 +
h)2 + Ь(х1 +
h) + с =
Для того, чтобы система имела решение, необходимо чтобы ее определитель не был равен нулю. Это условие выполняется, так как определитель равен: = — 2
h3так как . Решая систему уравнений, получаем интересующие нас значения параметров а, Ь, с подставляя их в формулу находим положение экстремума параболы
х°ап= х1 +
h(-)/2(— 2+)
Зная коэффициенты а, Ь, с можно определить и экстремальное значение функции по формуле, которая является оценкой экстремума критерия (х).
Теперь следует проверить, действительно ли найден экстремум. Для этого достаточно вычислить значение функции цели (х)в предполагаемом экстремуме х=х1+Δх — х°апи сопоставить его с оценкой. Если эти величины отличаются не более чем на ɛт. е:
|
(х°ап
)-(х°ап
)|
, гдеɛзаданная погрешность определения экстремума. При этом = х1. Если условие не выполняется, тогда следует процесс поиска; т.е. выполнить следующий цикл, но уже построение
аппроксимирующей модели производится в окрестности точки х1=х°ап. Процедура будет повторяться пока не выполнится условие.
Алгоритм расчета
.
Результаты расчета.
Целевая функция имеет вид :
Нач. знач.
X=-100,H=0.5
Погрешность Е
Значение Х
Значение F
Кол-во итераций
Кол-во вычислений
1
(-)2,19360741
(-)919,076558
10
30
0.1
0,8912446
22,8921666
14
45
0.01
0,79728604
22,27161267
16
48
0.001
0,7960595
22,2612358
17
51
Нач. знач. Х=-100, Е=0.1
ШагН
ЗначХ
Знач F
Кол-во итераций
Кол-во вычислений
Увеличение шага
0,3
0,901465
22,93463
25
75
0,5
0,797286
22,27161
16
48
0,8
0,6115913
20,33949
35
105
Уменьшение шага
0.5
0,79728604
22,27161267
16
48
0.4
0,8540667
22,69232
20
60
0.3
0,901465
22,934634
25
75
0.2
0,936694
23,034198
41
123
0.1
0,961479
23,056109
31
93
0.02
0,961661
23,05611
25
75
Вывод: расчеты показали, что изменение погрешности определения экстремума ɛ, практически не влияет на точность вычисления в то время, как изменение шага поиска hоказывает значительное влияние. При уменьшении шага точность вычислений улучшается и наоборот, при увеличении шага уменьшается. И в конечном итоге, когда шаг поиска слишком велик для того, чтобы с помощью итерационной процедуры уточнения значений получить результат с заданной погрешностью, программа отказывается производить вычисления.
Оптимизация
методом наискорейшего спуска.
Метод наискорейшего спуска предназначен для поиска минимума. Данный метод отличается от метода градиента правилом определения коэффициента шага. Сначала выделяется начальная точка. В пространстве Xмогут быть выделены области притяжения каждого из локальных минимумов.
Если алгоритм начинает поиск из начальной точки, лежащей в области притяжения некоторого минимума функции против направления градиента. Таким образом, в каждом цикле решается одномерная задача минимизации , после чего шаг находится как
–PAGE_BREAK–