Методы одномерной минимизации.

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

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

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

1. Унимодальные функции. Рассмотрим методы минимизации так называемых унимодальных функций. Пусть Х = [ a, b ].

Определение 2.1. Функция f называется унимодальной на Х, если существует такая точка х* Î Х, что для любых x ₁, x ₂ Î X

f (x ₁) > f (x ₂) если х ₁ < x ₂ < x *,

f (x ₁) < f (x ₂) если х * < x ₁ < x ₂.

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

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

Теорема 2.3. Пусть функция f унимодальна на Х, х ₁ < x ₂. Тогда, если f (x ₁) £ f (x ₂), то х* £ х ₂, если же f (x ₁) ³ f (x ₂), то х* ³ х ₁.

Предположение о том, что Х = [ a, b ], не является слишком ограничительным. В самом деле, если предположить, что множество Х не ограничено (является прямой или полупрямой), то с помощью теоремы 2.3. легко построить алгоритм, позволяющий найти отрезок, в котором содержится точка х*. Этот алгоритм называется методом сканирования (см., например [5]).

Зададим для этого некоторое число h ₁> 0 и вычислим значение f в точках х ₁ и х ₂ = x ₁ + h ₁ множества Х. Пусть, например, f (x ₁) > f (x ₂). Если Х = (-¥, с ], где с - действительное число, то х *Î [ x _1, c ]. Если же Х = (-¥, +¥), то следует вычислять значения f (x_i) (x_i = x_{i -1} + h_i, i = 3, 4, …) до тех пор, пока не будет найдена такая точка х_i, что f (x_{i -1}) £ f (х_i), причём f (x_{i -2}) > f (x_{i -1}). Тогда согласно теореме 2.3 х *Î [ x_{i -2,} х_i ]. Шаг h_i можно выбирать постоянным или же h_{i +1} = 2 h_i (i ³ 1) и т.д. Если f (x ₁) < f (x ₂), то значения функции следует вычислять в точках x_i = x_{i -1} - h_i. Если f (x ₁) = f (x ₂), то х *Î [ х ₁, х ₂].

Если известен какой-либо отрезок [ х_k, х_m ], которому принадлежит х *, мы будем говорить, что точка минимума х * локализована в отрезке [ х_k, х_m ]. Сам отрезок при этом будем называть о трезком локализации минимума. В литературе интервал (х_k, х_m) называется интервалом неопределённости.

Приступим к описанию алгоритмов минимизации унимодальных функций. Будем предполагать, если не оговорено противное, что используется информация лишь о значениях минимизируемой функции. Будем также считать, что функция унимодальна на отрезке [ a, b ].

2. Метод дихотомии. Пусть количество допустимых вычислений функции N =2 k. Положим где d - некоторое положительное число, d< (a+b)/2 ^k. Вычислим f (x ₁) и f (x ₂). Тогда согласно теореме 2.3:

1) если f (x ₁) < f (x ₂), то х* Î [ а, х ₂], т.е. новым отрезком локализации минимума является [ a, x ₂];

2) если f (x ₁) > f (x ₂), то х * [ x ₁, b ], т.е. новым отрезком локализации минимума является [ x ₁, b ];

3) если f (x ₁) = f (x ₂), то х * [ x ₁, x ₂], т.е. новым отрезком локализации минимума является [ x ₁, x ₂].

Для единообразия в случае f (x ₁) = f (x ₂) будем рассматривать в качестве нового отрезка локализации минимума, например, [ a, x ₂]. Так что длина отрезка локализации после первой пары вычислений функции равна Вторая пара значений f вычисляется в точках х ₃, х ₄, отстоящих на расстоянии d по обе стороны от середины нового отрезка локализации. Если, например, этим отрезком оказался [ a, x ₂], то

Используя снова теорему 2.3, мы определяем новый отрезок локализации минимума длиной В нашем примере это будет [ a, x ₄] при f (x ₃) £ f (x ₄) и [ x ₃, x ₂] при f (x ₃) > f (x ₄). После третьей пары вычислений длина отрезка локализации становится равной , …, после k -й -

Итак после N вычислений функции мы нашли отрезок локализации минимума [ x_{N -1}, x_N ] длиной

на котором расположена точка х *. Величину l называют прогрешностью метода дихотомии. Соответсвующим выбором d величину l можно сделать сколь угодно близкой к (b - a)/2 ^{N /2}. Приняв приближёно х * (x_{N -1}+ x_N)/2, получим, что погрешность вычисления х * не будет превышать величины l /2. Число f ((x_{N -1} + x_N)/2) принимается за минимальное значение f (x) на [ a, b ].

3. Метод Фибоначчи. Предположим, что нужно определить минимум х * как можно точнее, т.е. с наименьшим возможным отрезком локализации, но при этом можно выполнить только N вычислений функции.

Пусть известно значение функции f (x ₁) в некоторой точке х ₁ внутри отрезка [ a, b ] (см. рис. 2.1). Выясним, где следует поместить следующую точку х ₂ (N = 2), чтобы получить наименьший возможный отрезок локализации.

Положим х ₁ - а = L и b - х ₁ = R. Причём L < R, как показано на рис. 2.1. Тогда согласно теореме 2.3

1) если f (х ₁) < f (x ₂), то новым отрезком локализации будет [ a, x ₂] длиной x ₂ - a;

2) если f (x ₁) > f (x ₂), то новым отрезком локализации будет [ x ₁, b ] длиной L.

Поскольку не известно, какая из этих ситуаций будет иметь место, выберем x ₂ таким образом, чтобы минимизировать наибольшую из длин x ₂ - a и b - x ₁. Достигнуть этого можно, сделав эти длины равными, то есть поместив х ₂ внутри интервала (a, b) симметрично относительно точки x ₁, уже лежащей внутри интервала.

Если N > 2 и можно выполнить еще одно вычисление функции, то следует применить описанную процедуру к отрезку [ a, x ₂], в котором ужеесть значение функции, вычисленное в точке x ₁, или к отрезку [ x ₁, b ], в котором уже есть значение функции, вычисленное в точке x ₂. Итак, стратегия поиска ясна. Нужно поместить следующую точку внутри отрезка локализации симметрично относительно уже находящейся там точки. Теперь остается найти положение начальной точки х₃.

На N -м вычислении N -ю точку нужно поместить симметрично по отношению к (N -1)-й точке (см. рис. 2.1). Отрезок локализации будет иметь наименьшую длину на

данном этапе, если мы поместим точку х ₁ так, чтобы после соответствующих построений точка Х_{N- 1}оказалась посередине N- 1-го отрезка ([ х_{N- 2}, х_{N- 3}] на рис. 2.1). В этом случае точка Х_N будет совпадать с точкой Х_{N- 1.} Обозначим длину N -го отрезка локализации через L_N. Тогда длина N- 1-го отрезка локализации

L_{N- 1} = 2 L_N. (2.3)

Согласно стратегии поиска, точки х_{N- 1}, х_{N- 2} должны быть помещены симметрично внутри предыдущего отрезка локализации длиной L_{N- 2} на расстоянии L_{N- 1} от концов этого отрезка (см. рис.2.2 при j = n - 1), т. е. L_{N- 2} = L_{N- 1} + L_N = 3 L_N. В общем случае (рис.2.2)

L_{j- 1} = L_j + L_{j+ 1}при 2 £ j £ N- 1.(2.4)

Определим последовательность чисел Фибоначчи следующим образом: F ₀ = 1, F ₁ = 1 и F_k = F_{k -1} + F_{k -2} для k ³ 2.

Из (2.3) и (2.4) вытекает, что

L_N-j = F_{j+ 1} L_N, j= 1, 2, …, n - 1. (2.5)

Если начальный отрезок имеет длину L ₁ = b - a, тo

.

Теперь мы можем найти положение точки x ₁, которая помещается на расстоянии L ₂ от одного из концов начального отрезка [ a, b ], причем не важно, от какого конца. Согласно (2.5)

.

Тогда можно считать, что

(2.6)

Таким образом, метод Фибоначчи, названный так ввиду появления при поиске чисел Фибоначчи, является итерационной процедурой. В процессе поиска очередного отрезка локализации следующая точка x ₂ на отрезке [ a, b ] с точкой x ₁, уже лежащей внутри отрезка, всегда выбирается такой, что

x ₂ = a + b - x ₁ (2.7)

Приведем алгоритм нахождения точки локального минимума методом Фибоначчи.

1. Задаем а, b, N (N ³ 2).

2. Вычисляем x ₁ по формуле (2.6). Полагаем j = 2.

3. Вычисляем x ₂по формуле (2.7). Вычисляем e = f (x ₁) - f (x ₂).

4. Если x ₁ > x ₂и е £ 0, то полагаем a = x _2. Если x ₁ > x ₂ и e > 0, то полагаем b = x ₁, x ₁ = x ₂. Если x ₁ < x ₂ и е £ 0, то полагаем b = x ₂. Если x ₁ < x ₂ и е > 0, то полагаем a = x ₁, x ₁= x ₂.

5. Увеличиваем j: j = j + 1.

6. Если j £ N, то переходим к пункту 3. В противном случае полагаем x*» x ₁, f _min» f (x*).

Модуль абсолютной погрешности метода Фибоначчи, как следует из построений, не превосходит длины N -го отрезка, т.е.

(2.8)

Заметим, что на каждом шаге метода Фибоначчи точка, лежащая внутри отрезка локализации, делит его в отношении двух последовательных чисел Фибоначчи. Так после i шагов

.

Из формулы, выражающей числа Фибоначчи в явном виде

(2.9)

где t» 1, 618034, вытекает, что F_{j +1}/ F_j ®t при j ® ¥.

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

4. Метод золотого сечения. Алгоритм определяется той же стратегией, что и метод Фибоначчи: на каждом шаге точка очередного вычисления выбирается симметрично относительно середины отрезка локализации к лежащей внутри этого отрезка точке, в которой уже проведено вычисление. Разница состоит лишь в выборе точки х ₃.

Пусть снова f унимодальна на [ a, b ] и L ₁ = b- a. Положим

(2.10)

где t - величина из (2.9). Тогда

Легко проверить, что t - 1 = 1/t. Следовательно,

Деление отрезка в таком отношении носит название золотого сечения.

Точку х ₂ выберем симметрично точке х ₁ относительно середины отрезка [ a, b ],

(2.11)

Сравнив значения f (x ₁) и f (x ₂), находим новый отрезок локализации минимума с помощью теоремы 2.3. Если f (х ₁) < f (x ₂), то новым отрезком локализации будет отрезок [ x ₂, b ]. При f (х ₁) ³ f (x ₂) новый отрезок локализации - [ a, x ₁]. Длина полученного отрезка L ₂ = L ₁/t. Нетрудно видеть, что лежащая внутри отрезка локализации точка, где вычисление уже проведено, делит отрезок снова в отношении золотого сечения. Так что отношение L ₂ к длине следующего отрезка локализации L ₃снова будет равно t, а L ₃ = (b- a)/t². Причем L ₁ =L ₂ +L ₃ так же как и в методе Фибоначчи. Повторяя описанную процедуру, мы получим после N вычислений, что

N -й отрезок локализации минимума будет иметь длину

Алгоритм нахождения точки локального минимума методом золотого сечения отличается от поиска методом Фибоначчи, приведенного в предыдущем пункте, только тем, что точки х ₁и х ₂ вычисляются по формулам (2.10) и (2.11) соответственно.

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

(2.12)

5. Сравнение методов. При практическом использовании описанных выше методов надо иметь в виду, что каждый из них имеет свои достоинства и недостатки. Метод дихотомии (его еще называют метод деления отрезка пополам) – самый простой, но и самый трудоемкий из них. На каждом шаге данного метода нужно вычислять значение функции f (х) дважды, тогда как в методе Фибоначчи и золотого сечения это делается на каждом шаге только один раз, что и определяет большую трудоемкость вычисления значения х* с заданной точностью. А именно, если N раз вычислить значение функции f (х), то, например, методом золотого сечения значение х* может быть найдено в 1, 44 ^N раз точнее, чем методом дихотомии.

Сравним теперь погрешности (2.8) и (2.12) методов Фибоначчи и золотого сечения после N вычислений значений целевой функции, то есть длины N -ых отрезков локализации минимума. Как видно, оба метода обеспечивают экспоненциальное уменьшение длины исходного отрезка [ a, b ]. С учетом (2.9) мы получаем, что при N ® ¥

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

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

Пусть a ₁ < c ₁ < b ₁, f (c ₁) £ f (a ₁), f (c ₁) £ f (b ₁), то есть [ a ₁, b ₁] - отрезок локализации минимума f. Тройку чисел a ₁, c ₁, b ₁ можно найти, сделав несколько шагов, например, по методу золотого сечения (если, конечно, точка минимума не совпадает ни с одним из концов отрезка [ a, b ], на котором определена функция f). Построим квадратный трехчлен j₁, график которого проходит через точки (a ₁, f (a ₁)), (c ₁, f (c ₁)), (b ₁, f (b ₁)):

Поскольку f - унимодальная функция, то хотя бы одно из неравенств f (с ₁) £ f (a ₁) или f (с ₁) £ f (b ₁) строгое и, следовательно, коэффициент при старшем члене квадратного трехчлена j₁ положителен. Нетрудно видеть, что j₁ достигает минимума в точке

причем (a ₁ + c ₁)/2 £ s ₁ £ (c ₁ + b ₁)/2. Эта точка и выбирается в качестве точки очередного вычисления значения функции f (если оказалось, что s ₁ = c ₁, условимся в качестве точки очередного вычисления выбирать точку (a ₁ + c ₁)/2). Итак, следующее вычисление проводится в точке

Как и в методах Фибоначчи и золотого сечения, определим новый отрезок локализации [ a ₂, b ₂] c лежащей внутри него точкой c ₂, в которой значение функции f уже вычислено. Ясно, что c ₂ = c ₁ или c ₂ = t ₁. Далее строится квадратный трехчлен j₂, график которого проходит через точки (a ₂, f (a ₂)), (c ₂, f (c ₂)), (b ₂, f (b ₂)), определяется точка его минимума и т. д.

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