18. Одномерная задача оптимизации. Решение и решение методом Фибоначчи.
Одномерная задача оптимизации в общем случае формулируется следующим образом. Найти наименьшее (или наибольшее) значение целевой функции y=f(x), заданной на множестве , и определить значение проектного параметра x, при котором целевая функция принимает экстремальное значение.
Будем рассматривать методы оптимизации для разных классов целевых функций. Простейшим из них является случай дифференцируемой функции f(x) на отрезке [a,b], причем функция задана в виде аналитической зависимости y=f(x), и может быть найдено явное выражение для ее производной f(x). Нахождение экстремумов таких функций можно проводить известными из курса высшей математики методами дифференциального исчисления.
В других случаях, когда целевая функция задана в табличном виде или может быть вычислена при некоторых дискретных значениях аргумента, используются различные методы поиска.
метод чисел Фибоначчи
В силу того, что в
асимптотике
,
метод золотого сечения может быть
трансформирован в так называемый метод
чисел Фибоначчи. Однако при этом в силу
свойств чисел Фибоначчи количество
итераций строго ограничено. Это удобно,
если сразу задано количество возможных
обращений к функции.
Алгоритм
Шаг 1.
Задаются начальные границы отрезка a,b
и число итерацийn
, рассчитывают начальные точки деления:
и значения в них целевой функции:
Шаг 2. n=n-1.
Если
, тоa=x1,
x1=x2, x2=b-(x1-a), y1=y2, y2=f(x2)Иначеb=x2, x2=x1, x1=a+(b-x2), y2=y1, y1=f(x1)
Шаг 3.
Еслиn=1 , тоx=x1=x2 и остановка
Иначе возврат к шагу 2.
Одномерная задача оптимизации. Решение методом Пауэлла
Одномерная задача оптимизации в общем случае формулируется следующим образом. Найти наименьшее (или наибольшее) значение целевой функции y=f(x), заданной на множестве , и определить значение проектного параметра x, при котором целевая функция принимает экстремальное значение.
Будем рассматривать методы оптимизации для разных классов целевых функций. Простейшим из них является случай дифференцируемой функции f(x) на отрезке [a,b], причем функция задана в виде аналитической зависимости y=f(x), и может быть найдено явное выражение для ее производной f(x). Нахождение экстремумов таких функций можно проводить известными из курса высшей математики методами дифференциального исчисления.
В других случаях, когда целевая функция задана в табличном виде или может быть вычислена при некоторых дискретных значениях аргумента, используются различные методы поиска.
Метод пауэлла
Пусть известны значения функции f(x) в трех разных точкахx1,x2,x3 , равные соответственноf(x1),f(x2),f(x3) , тогда функция f(x) может быть аппроксимирована квадратичной функцией :q(x)=a0+a1(x-x1)+a2(x-x1)(x-x2)
где коэффициенты a0 a1 a2 определяются из условия, что значения функции в этих точках равны значениям полинома q(x) в этих же точках.
Имеем
f(x1)=q(x1)=a0
f(x2)=q(x2)=f(x1)+a1(x2-x1)
Отсюда получаем
a1=(f(x2)-f(x1))/(x2-x1)
Аналогично получаем
Квадратичная функция q(x) достигает минимума в точке .
Поскольку функция f(x) на рассматриваемом интервале обладает свойством унимодальности, а аппроксимирующий квадратичный полином также является унимодальной функцией, то можно ожидать, что величина окажется приемлемой оценкой координаты точки истинного оптимума функции f(x).
Стратегия поиска.
Метод Пауэлла относится к последовательным стратегиям. Задается начальная точка и с помощью пробного шага находится три точки так, чтобы они были как можно ближе к искомой точке минимума. В полученных точках вычисляются значения функции. Затем строится интерполяционный полином второй степени, проходящий через эти точки. В качестве приближения точки минимума берется точка минимума полинома. Поиск заканчивается, когда полученная точка отличается от лучшей из трех опорных точек не более чем на заданную величину.