Сравнение методов одномерной оптимизации: метод золотого сечения и метод квадратичной параболы

Сравнение методов одномерной оптимизации: метод золотого сечения и метод квадратичной параболы

Введение

Задача в виде, пригодном для решения методом оптимизации, состоит в минимизации (максимизации) вещественнозначной функции f(x) N-мерного аргумента x. Такая задача называется задачей условной оптимизации. Если задача не содержит ограничения и рассматривается на всем пространстве, то это задача безусловной оптимизации. Задачи без ограничений с N = 1 называются задачами одномерной оптимизации, с N 2 - многомерной оптимизации.

Задачей одномерной оптимизации является поиск локального минимума целевой функции f(х) вдоль заданного направления.

Задача нахождения минимума функции одной переменной min f(x) нередко возникает в практических приложениях. Кроме того, многие методы решения задачи минимизации функции многих переменных сводятся к многократному поиску одномерного минимума. Поэтому разработка все новых, более эффективных одномерных методов оптимизации продолжается и сейчас, несмотря на кажущуюся простоту задачи.

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

Введем некоторые определения:

Монотонность функции. Функция f(x) является монотонной на интервале, если для любых x₁ и x₂ из этого интервала, таких, что x₁ < x₂, выполняется неравенство:

f(x₁)<f(x₂), если функция монотонно возрастающая, или f(x₁)>f(x₂), если функция монотонно убывающая.

Унимодальность. Функция f(x) является унимодальной на отрезке, если она монотонна по обе стороны от единственной на отрезке точки х₀, то есть функция f(x) в полуинтервале [а,х₀) убывает, а в полуинтервале (х₀,b] возрастает. Примеры графиков унимодальных функций приведены на рис. 1.

Точка х₀ может быть внутренней точкой отрезка [а, b] или совпадать с одним из его концов. Унимодальная функция не обязательно непрерывна на отрезке [а, b].

Рис. 1. Графики унимодальных функций

Определение глобального минимума. Функция f(x), определённая на множестве D, достигает глобального минимума в точке x*  D, если f(x*)<f(x) для всех x  D.

Определение локального минимума. Функция f(x), определённая на множестве D, имеет локальный минимум в точке x*  D, если существует такая е-окрестность точки x*, что для всех x из этой е-окрестности выполняется неравенство f(x*)<f(x).

Если функция f(x) не унимодальна, то наименьший из локальных минимумов будет глобальным минимумом. Для нахождения аналитического оптимума необходимо найти стационарные или критические точки функции, использовать какое-либо из достаточных условий экстремума (изменение знака первой производной или определенного знака четной производной) и сравнить значения функции в точках локальных экстремумов и граничных значениях. Однако в прикладных задачах нередки ситуации, когда трудно вычислить производные функции (например, если функция не задана в аналитическом виде). Более того, не исключено, что значения функции известны или могут быть вычислены только в отдельных точках. В таких ситуациях использование необходимого и достаточного условий локального минимума невозможно и следует применять другие методы решения задачи оптимизации. Методы минимизации функции одной переменной, в которых используют значения функции в точках рассматриваемого промежутка и не используют значения ее производных, называют методами прямого поиска.

Можно выделить две группы методов прямого поиска, соответствующие двум принципиально различным ситуациям:

.        все N точек х_k, k = 1,…, N, в которых будут вычислены значения функции, выбирают заранее (до вычисления функции в этих точках);

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

В первом случае поиск наименьшего значения называют пассивным, а во втором - последовательным.

Так как в прикладных задачах вычисление каждого значения функции может быть достаточно трудоемким, то целесообразно выбрать такую стратегию поиска, чтобы значение целевой функции f(x*) с заданной точностью было найдено наиболее экономным путем.

Будем считать, что стратегия поиска определена, если:

.        определен алгоритм выбора точек x_k, k = 1, …, N;

.        определено условие прекращения поиска, т.е. условие, при выполнении которого значение f(x*) считают найденным с заданной точностью.

Оптимальный пассивный поиск состоит в выборе точек, равномерно расположенных на отрезке [a,b], координаты которых:

При этом длина интервала, содержащего минимум  дает оценку скорости сходимости пассивного поиска с ростом числа N точек, так как скорость сходимости любого метода прямого поиска можно характеризовать скоростью уменьшения интервала неопределенности с возрастанием N. Вычисляя значения целевой функции в каждой точке f_k = f(x_k), найдем наименьшее значение f_j, и тогда точка оптимума x* (x_j-1, x_j+1), и можно считать, что x*  x_j ± е с точностью е.

1. Обзор существующих методов решения задачи

1.1 Методы последовательного поиска

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

Метод деления отрезка пополам

Задается интервал [a,b] и погрешность . В алгоритме деления пополам или алгоритме равномерного дихотомического поиска испытания проводятся парами. Координаты каждой последующей пары испытаний разнесены между собой на величину . Испытания производятся в середине текущего интервала неопределенности (ТИН). По значениям f(x), полученным в этих точках, одна половина ТИН в силу унимодальности функции f(x) исключается из дальнейшего рассмотрения. Величина  определяется требуемой точностью решения. Алгоритм относится к классу методов последовательного поиска.

Расчет происходит до тех пор, пока длина интервала не станет меньше заданной погрешности . В среднем за одно вычисление функции отрезок, на котором находится x, уменьшается примерно в 1.33 раза. Этот метод прост в реализации, позволяет находить минимум разрывной функции, однако требует большого числа вычислений функции для обеспечения заданной точности.

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

Золотое сечение - это такое деление отрезка [a,b] на две неравные части [a,x] и [x,b], при котором имеет место следующее соотношение:

xb/ab=ax/xb=1-,

 = 2/(3+)  0.381966011.

Алгоритм поиска минимума аналогичен вышеописанному методу деления отрезка пополам и отличается тем, что в начале точки x₁ и x₂ выбираются так, чтобы выполнялось золотое отношение, и вычисляются значения функции в этих точках.

За одно вычисление функции отрезок, на котором находится x_m, уменьшается в 1-  1.61 раза, т.е. быстрее, чем метод деления отрезка пополам.

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

Метод аналогичен методу золотого сечения. Отличие состоит в том, что коэффициент сжатия интервала неопределенности меняется от итерации к итерации согласно последовательности Фибоначчи. Последовательность чисел определяется следующим образом:

F₀ = F₁ = 1,

F_k+1 = F_k + F_k-1,

k = 1, 2, …

Пробные точки _k и м_k вычисляют по формулам:

При этом число итераций выбирается до начала вычислений и обусловлено требуемой точностью:

1.2 Методы аппроксимации

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

.        увеличением степени полинома;

.        уменьшением интервала аппроксимации.

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

Метод квадратичной аппроксимации

Чтобы функция имела минимум внутри отрезка она должна быть, по крайней мере, квадратичной. Для построения квадратичной функции достаточно трех точек:

M₁(x₁,y₁), M₂(x₂,y₂), M₃(x₃,y₃).

Можно задать аппроксимацию функции полиномом вида:

P₂(x) = a₀ + a₁(x-x₁) + a₂(x-x₁)(x-x₂)

и выбрать a₀, a₁, a₀ так, чтобы:

P₂(x₁) = y₁

P₂(x₂) = y₂

P₂(x₃) = y₃

Отсюда следует, что

a₀ = y₁,

Найдем стационарную точку x* полинома P₂(x):

Так как функция унимодальна на рассматриваемом интервале и полином P₂(x) тоже унимодальная функция, то x* является приемлемой оценкой истинного оптимума.

Метод квадратичной аппроксимации удобно применять после локализации точки минимума методом золотого сечения или методом Фибоначчи. Это объясняется тем, что для дважды дифференцируемой функции многочлен второго порядка достаточно хорошо аппроксимирует функцию в окрестности точки минимума.

В методах прямого поиска при вычислении значений минимизируемой функции f(x) неизбежно возникают погрешности, к которым чувствительны алгоритмы прямого поиска, основанные на сравнении значений функции в отдельных точках. Если унимодальная функция f(x) непрерывно дифференцируема на отрезке минимизации, то точку х* наименьшего значения функции можно вычислять как корень уравнения:

f’(x)=0

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

Метод средней точки

Будем искать минимум функции f(x) непрерывно дифференцируемой и строго унимодальной на отрезке [a,b]. В этом случае единственной точкой x*  [a,b] минимума будет стационарная точка, в которой f’(x*)=0. Отметим, что непрерывно дифференцируемая унимодальная на отрезке функция может иметь на нем более одной стационарной точки. На отрезке определяются две точки a_k, b_k, в которых производные имеют разные знаки, f’(a_k)f’(b_k)<0. Искомый оптимум находится между ними. Делим интервал пополам: , если f’(x_k)>0(<0), то из двух интервалов оставляем тот, на концах которого производная имеет разные знаки.

Метод средней точки напоминает метод дихотомии, но сходится к искомому значению х* быстрее. Поскольку для метода средней точки после вычисления n значений производной минимизируемой на отрезке [0, 1] функции f(x) для длины интервала неопределенности получаем .

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

Метод Ньютона (метод касательных)

Если строго унимодальная на отрезке [a,b] функция f(x) дважды непрерывно дифференцируема на этом отрезке, то точку x*  минимума этой функции можно найти путем решения уравнения f’(x) = 0 методом Ньютона, иногда называемым методом касательных. Выбираем x₀ - начальное приближение, называемое обычно начальной точкой. Линеаризуем функцию f’(x) в окрестности начальной точки, приближенно заменив дугу графика этой функции касательной в точке (x₀,f’(x₀)). Выберем в качестве следующего приближения к х* точку x₁ пересечения касательной с осью абсцисс.

В общем случае сходимость метода Ньютона существенно зависит от выбора начальной точки x₀. Поэтому говорят, что метод Ньютона обладает локальной сходимостью в том смысле, что надо выбрать хорошее начальное приближение, попадающее в такую окрестность точки х*, где f’’(x)>0. Однако проверка выполнения этого условия не всегда возможна. Достаточным условием монотонной сходимости метода Ньютона будут постоянство в интервале между точками x₀ и х* знака производной f’’’(x) и совпадение его со знаком f’(x). Оказывается, что в этом случае метод Ньютона обладает квадратичной скоростью сходимости в некоторой окрестности точки х*.

Метод секущих

Метод секущих похож на метод Ньютона, но строится не касательная к графику производной, а секущая. Геометрическая интерпретация этого метода состоит в том, что в качестве очередного приближения x_k+1 выбирают точку пересечения с осью абсцисс секущей к графику функции f’(x).

Этот метод имеет сверхлинейную скорость сходимости. Модификации метода Ньютона обладают только локальной сходимостью, т.е. сходятся, если начальная точка выбрана в некоторой окрестности точки минимума функции. Если же начальная точка расположена слишком далеко от точки минимума, то подобный метод может расходиться или «зацикливаться». В отличие от метода средней точки метод секущих использует информацию не только о знаке производной, но и о значениях в пробных точках.

Метод кубической аппроксимации

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

Пусть для непрерывно дифференцируемой функции f(x), строго выпуклой на отрезке [x₁, x₂], известны значения y₁ = f(x₁), y₂ = f(x₂) функции и значения ее производной y₁₁ = f’(x₁), y₁₂ = f’(x₂). Если y₁₁*y₁₂ < 0, то рассматриваемая функция строго унимодальна на этом отрезке.

При условии y₁₁*y₁₂ < 0 на отрезке [х₁, х₂] можно построить единственный многочлен третьей степени, располагая значениями функции и производных на концах этого отрезка. Этот многочлен называется кубическим интерполяционным многочленом Эрмита.

2. Детальное описание используемых методов

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

сечение аппроксимация ньютон производная

Рассмотрим следующую задачу условной оптимизации: найти минимум одномерной унимодальной функции f(x), определенной в замкнутой области допустимых значений D=[a,b],

Свойства золотого сечения:

Рассмотрим интервал [a,b] (рис. 2). Говорят, что точка c выполняет золотое сечение интервала [a,b], если:

 (1)

где  0,618- решение квадратного уравнения:

²+-1=0 (2)

Рис. 2. Золотое сечение отрезка.

Из определения золотого сечения следует, что .
Действительно,

Алгоритм золотого сечения.

Алгоритм золотого сечения относится к классу последовательных методов поиска.

.        Выполняем присваивания:

r = 1, a¹ = a, b¹ = b,

ТИН₁ = [a¹,b¹].

.        Вычисляем величины (Рис. 3)

,  (3)

3.      Вычисляем значения f(), f() функции f(x).

.        Если f() < f(), то выполняем присваивания:

a^r+1 = a^r, b^r+1 = ,

ТИН_r+1 = [a^r+1, b^r+1]

Иначе - выполняем присваивания

a^r+1 = , b^r+1 = ^r,

ТИН_r+1 = [a^r+1, b^r+1].

5.      Если , то заканчиваем вычисления. Иначе - выполняем присваивание r=r+1 и переходим на п.2. Здесь  - требуемая точность решения

.       

Рис. 3. Определение величин ,

В качестве приближенного значения точки минимума x* с равными основаниями может быть принята любая точка последнего текущего интервала неопределенности.

Некоторые свойства алгоритма золотого сечения:

Утверждение 1.

Точки ,  расположены симметрично относительно концов текущего интервала неопределенности.

Действительно, из (3) следует, что точка отстоит от точки b^r на величину (b^r-a^r); точка  отстоит от точки a^r на ту же величину.

Утверждение 2.

Для любого r≥1 алгоритм золотого сечения обладает следующим свойством: одна из точек , совпадает с одной из точек ,.

Доказательство.

Пусть на r-й итерации f() < f(). В соответствии с алгоритмом золотого сечения ТИН_r+1 = [a^r,] причем, очевидно,  ТИН_r+1. Для того, чтобы доказать справедливость утверждения достаточно показать, что верно отношение:

 (4)

Из соотношений (3) следует, что

(b^r - ) = (b^r - a^r)

b^r -  - a^r + a^r = (b^r - a^r)

(b^r - a^r)-(-a^r)=(b^r - a^r)

 - a^r = (b^r - a^r)(1-)

 - a^r = (b^r - a^r)

Разделив первый из этих результатов на второй, получим

 (5)

Из уравнения (2) следует, что 1- =². Отсюда и из (5) следует справедливость (4). Аналогично проводится доказательство для случая f() > f().

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

Утверждение 3.

Поэтому количество итераций N, необходимых для нахождения минимума функции с точностью _x, находится из условия _x ≤ (b-a)^N

2.2 Метод квадратичной параболы

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

Рассмотрим квадратичную аппроксимацию (рис. 4). Пусть в процессе решения задачи поиска минимума функции f(x) тем или иным образом получены попарно не совпадающие точки x₁, x₂, x₃, принадлежащие области допустимых значений D (не обязательно упорядоченные слева направо).

Рис. 4. Квадратичная аппроксимация

Построим квадратичную функцию

y=ax²+bx+c, (6)

проходящую через точки (x_i,f_i), i = 1,2,3, где f_i = f(x_i).

Коэффициенты a,b,c функции (6) удовлетворяют системе линейных алгебраических уравнений (СЛАУ)

 (7)

Определитель СЛАУ (7) является определителем Вандермонда, который отличен от нуля, если величины x₁,x₂,x₃ попарно различны.

Таким образом, в сделанных предположениях СЛАУ (7) имеет решение и притом единственное. Поскольку определитель СЛАУ (7) равен ), это решение имеет вид:

Подставим найденные значения коэффициентов a,b,c в необходимое условие y’=2ax+b=0 минимума квадратичной функции (6), получим стационарную точку этой функции:

 (8)

где .

Метод квадратичной аппроксимации.

Рассмотрим следующую задачу условной оптимизации: найти минимум одномерной унимодальной функции f(x), определенной в замкнутой области допустимых значений D=[a,b],

 (9)

Метод квадратичной аппроксимации относится к классу методов сокращения текущего интервала неопределенности. Пусть при решении задачи (8) каким-либо методом получены три точки x₁ < x₂ < x₃, принадлежащие области допустимых значений, такие, что f(x₁) > f(x₂) < f(x₃).

Схема метода квадратичной аппроксимации:

.        Выполняем присваивания

r=1

 x₁

₂

₃

ТИН_r = [,]

. Вычисляем значения  функции f(x) в точках ,,  соответственно.

. По формуле (8) вычисляем величину ^r и находим значение функции f(x) в этой точке ^r = f(^r)

. Находим следующие три точки:

случай (а) - если ^r [, ], то  = , =^r, =  (рис. 5а);

случай (б) - если ^r  [, ], то  = , =^r, =  (рис. 5б).

. В качестве следующего текущего интервала неопределенности принимаем

ТИН_r+1 = [,  ].

. Если , то заканчиваем вычисления. Иначе - выполняем присваивание r=r+1 и переходим на п.2. Здесь  - требуемая точность решения.

Рис. 5. Метод квадратичной аппроксимации:

В качестве приближенного значения точки минимума x* с равными основаниями может быть принята любая точка последнего текущего интервала неопределенности.

Замечание.

В силу условий ,  точка ^r всегда принадлежит текущему интервалу неопределенности ТИН_r = [].

Текст программы метода квадратичной параболы размещен в Приложении 1. Блок-схема алгоритма представлена в Приложении 2.

3. Полученные результаты

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

Пример.

Минимизировать функцию f(x)=x²+2x на интервале (-3,5). Допустимая погрешность  = 0,2.

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

Первая итерация:

a=-3, b = 5, b-a = 8;

x₁= -3 + 0.382∙8 = 0.056;

x₂ = 5 - 0.382∙8 = 1.944;

f(x₁)= 0.056² +2∙0.056 =0.115;

f(x₂)= 1.944² + 2∙1.944=7.667;

f(x₁)<f(x₂). Новый отрезок [-3; 1.944].

Дальнейшие вычисления оформим в виде таблицы (Таблица 1). Значения функции f(x), вычисленные на каждом шаге, помечены звездочкой.

Таблица 1

Результат:

Кол-во итераций: 8

Интервал неопределенности: (-1,112; -0,936), его длина: 0,176 < .

Точка минимума: x_min = -1.024

Точка точного минимума: -1.

Метод квадратичной параболы

Начальное приближение x₀ = 0;

Шаг h = 1;

Первая итерация:

x₁ = x₀ - h = 0 - 1 = 1;

x₂ = x₀ = 0;₃ = x₀ + h = 0 + 1 = 1;(x₁) = f(-1) = (-1)² + 2*(-1) = -1;(x₂) = f(0) = 0;(x₃) = f(1) = 1² + 2 = 3;₁ = x₁ - x₃ = -1 - 1 = -2;₂ = x₂ - x₃ = 0 - 1 = -1;=  = 1;=  = 4;

zm = -  = -2;

, переход ко второй итерации

Дальнейшие вычисления оформим в виде таблицы (Таблица 2). Значения функции f(x), вычисленные на каждом шаге, помечены звездочкой.

Таблица 2

Результат:

Кол-во итераций: 2

Кол-во вычислений функции: 5

Точка минимума: x_min = -1.

Точка точного минимума: -1.

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

Вывод

В данной работе были рассмотрены методы решения задач безусловной оптимизации с целевой функцией одной переменной.

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

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

Для оценки эффективности методов обычно используются три характеристики:

.        время, затраченное на получение решения;

.        точность решения;

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

Таким образом, можно утверждать:

.        Если необходимо получить решение с очень высокой степенью точности, то лучшими оказываются методы на основе полиномиальной аппроксимации.

.        Если важно добиться надежной работы алгоритма, то целесообразно выбрать метод золотого сечения.

.        Поисковые методы типа метода квадратичной аппроксимации следует использовать совместно с методом золотого сечения, когда возникают затруднения с реализацией соответствующих итераций на ЭВМ.

Литература

1.      Алгоритмы вычислительной математики: учебно-метод. пособие по курсу «Основы алгоритмизации и программирования» / А.К. Синицын, А.А. Навроцкий. - Минск: БГУИР, 2007. - 80 с.

2.      Методические указания по дисциплине «Методы оптимизации» / сост. Т.М. Попова. - Хабаровск: Изд-во Тихоокеан. гос. ун-та, 2011 - 26 с.

.        Мицель А.А., Шелестов А.А. Методы оптимизации. Часть 1: Учебное пособие. - Томск: Томский межвузовский центр дистанционного образования, 2002. - 192 с.

.        Методы оптимизации (базовый курс) [Электронный ресурс] - Режим доступа:://bigor.bmstu.ru/?cnt/?doc=MO/base.cou