Минимизация функций одной переменной

Для установления границ интервала унимодальности [a, b] обычно используют эвристические процедуры, в которых выбираются некоторые пробные точки функции f, а затем, путем сравнения значений f находится точка, в которой функция начинает возрастать. Рассмотрим основные процедуры алгоритма Свенна.

Алгоритм  Свенна для поиска интервала унимодальности

1. Вычислить f(x⁰), f(x⁰-D), f(x⁰+D), где x⁰-начальная       точка, D-некоторая постоянная.
2. Если f(x⁰-D)£ f(x⁰)£ f(x⁰+D), то D=-D;

иначе перейти  к 5.

3. Вычислить следующую пробную точку x^k+1=x^k+2^(k)×D.
4. Если f(x^k+1) £ f(x^k), перейти к 3;

иначе x^k+1=b, x^k-1=b. Стоп.

5. Положить D=D; перейти к 3.

 

После установления границ интервала унимодальности [a, b] можно применять различные методы поиска точки минимума x*. Прежде чем переходить к методу деления пополам, заметим, что наиболее простым и наименее эффективным является метод равномерного поиска, согласно которому весь интервал [a, b] разбивается на N точек, расположенных на одинаковом расстоянии друг от друга. Затем сравниваются значения функции f в этих пробных точках, и выбирается точка с минимальным значением f. Тогда, очевидно, эта точка является оценкой точки минимума x*.

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

 

• Теорема исключения интервалов. Пусть задана унимодальная функция f на некотором интервале [a, b], и ее минимум достигается в точке x*. Тогда, выбрав x₁ и x₂ так, чтобы a<x₁<x₂<b, и, сравнивая значения функции f в этих точках, можно сделать следующие выводы:

1.если f(x₁)>f(x₂), то точка минимума не лежит в интервале [a, x₁];

    2. если f(x₁)<f(x₂), то точка минимума не лежит в интервале [x₁, b].

 

(Заметим,  что при f(x₁)=f(x₂), то точка минимума лежит в интервале [x₁, x₂]).

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

 Алгоритм деления пополам

Пользователем задается требуемая точность e локализации точки минимума x*.

1. Вычислить x_m=(a+b)/2,  L=b-a

2. Вычислить x₁=a+L/4,  x₂=b-L/4,  f(x₁),  f(x₂);

3. Если f(x₁)<f(x_m), то b=x_m, x_m=x₁; перейти к 6;

     4. Если f(x₂)<f(x_m), то a=x_m, x_m=x₂; перейти к 6;

     5. Положить a=x₁, b=x₂;

6. Вычислить L=(b-a);

        Если ||L|| £ e, то закончить поиск;

        иначе, перейти к 2.

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

 

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

Поскольку местонахождение  искомой точки минимума x* заранее  неизвестно, имеет смысл предположить, что пробные точки x₁ и x₂ нужно выбирать так, чтобы использовать информацию о значении функции на предыдущем шаге поиска. Это означает, что точки нужно выбирать так, чтобы обеспечить уменьшение интервала в одном и том же отношении. Кроме того, в целях повышения скорости сходимости алгоритма необходимо также потребовать, чтобы указанное отношение было максимальным. Такая стратегия поиска называется минимаксной.

Исходя из этих требований, расположим пробные точки x₁ и x₂ так, как показано на рис.1.5а.

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

 

 

 

 

 

                                       (1-t)

 

                                      

          0                                      1

               (1-t)                  t

 

                             a)

 

 

                 (1-t)

          0                                      1

                       t

 

                             б)

 

                           

                           

                            t²

          0                                      1

                 (1-t)

                            в)

 

                      Рис.1.5. Расположение пробных точек

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

Предположим, что  исключается правый интервал [x₂,1]. Тогда для сохранения симметрии поиска расстояние (1-t) должно также составлять t-ю часть длины интервала, которая равна t. При таком выборе t следующая пробная точка размещается на расстоянии, равном t-й части длины интервала (рис.1.5б).

 

Отсюда следует, что t нужно определять из уравнения

 

1-t=t²,                (1.13)

 

решая которое, находим

 

                          t =(-1± ),

 

                          t = 0.6183… .              (1.14)

 

В общем случае, на каждой итерации исключается (1-t)-я часть интервала. Следовательно, после N вычислений функции f, начальный единичный интервал уменьшится до величины t^(N-1).

1.2.3. Сравнение методов исключения  интервалов

Для сравнения  методов исключения интервалов в  качестве критерия сравнения принято  выбирать относительное уменьшение исходного интервала E(N) за N вычислений значений f:

 

E(N)=L_N/L₁,                     (1.15)

 

где L₁ - длина исходного интервала [a, b];

    L_N - длина конечного интервала.

В методе деления пополам  длина текущего интервала L_N равна половине предыдущего, и поэтому можно записать L_N= L₁(0.5)^N/2, тогда

E_МДП(N)=0.5^N/2.                  (1.16)

 

Аналогичные рассуждения  дают для метода золотого сечения  следующие соотношения:

                    L(N)=L₁(0.618)^N-1               (1.17)

и

E_МЗС(N)=0.618^(N-1).              (1.18)

Метод равномерного поиска, в котором сравнивают значения f в N равноотстоящих точках интервала [a, b], локализуют точку x^* в конечном интервале равном

(x^*-L₁/(N+1))£ x* £ (x^*+L₁/(N+1)),

откуда 

                       L_N=2L₁/(N+1)                   (1.19)

и эффективность метода равна

       E_МРП(N)=2/(N+1).                (1.20)

 

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

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

N_МДП = 2×lnE_МДП/ln0.5,              (1.21)

 

N_МЗС = 1 + lnE_МЗС/ln0.618,         (1.22)

 

N_МРП = 2/E_МРП - 1.                 (1.23)

 

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

1.3.  ПОЛИНОМИАЛЬНАЯ  АППРОКСИМАЦИЯ

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

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

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

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

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

Если задана последовательность точек x₁, x₂, x₃ и известны соответствующие этим точкам значения функции f₁, f₂, f₃, то можно определить постоянные величины a₀, a₁ и a₂ таким образом, что значения квадратичной функции

 

              q(x)=a₀ + a₁(x-x₁)+a₂(x-x₁)(x-x₂)          (1.24)

 

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

 

             f₁=f(x₁)=q(x₁)=a₀,              

 

имеем a₀=f₁.

Далее, поскольку

 

                    f₂=f(x₂)=q(x₂)=f₁+ a₁(x₂-x₁),

получаем 

 

                       a₁=(f₂-f₁)/(x₂-x₁).

 

Наконец, при x=x₃

 

         f₃=f(x₃)=q(x₃)=f₁+(f₂-f₁)/(x₂-x₁)(x₃-x₁)+a₂(x₃-x₁)(x₃-x₂).

 

Разрешая последнее  уравнение относительно a₂, получаем

 

          a₂= .

 

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

Если точность аппроксимации исследуемой функции  в интервале [x₁, x₃] c помощью указанного полинома оказывается достаточно высокой, то в соответствии с предложенной стратегией поиска построенный полином можно использовать для оценивания координат точки минимума.

В данном случае, согласно необходимому условию экстремума, найдя первую производную полинома и приравняв ее нулю, получим

 

                q'(x)= a₁+a₂(x-x₂)+a₂(x-x₁)=0,

 

откуда искомая  оценка минимума равна

 

x_a*=(x₂-x₁)/2 - (a₁/2a₂).

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

                   f(x)= 2x² + (16/x)

в интервале 1£x£5.

Пусть пробные  точки равны x₁=1, x₂=3, x₃=5, и соответствующие значения функции равны

 

f₁=18.0,        f₂=23.33,        f₃=53.2.

 

Вычислим коэффициенты квадратичного приближения:

 

a₁=2.67,       a₂=3.07,

 

что дает следующую  оценку точки минимума

 

x_a*=1.565.

 

Точный минимум  исходной функции равен x*=1.5874.

 

Далее рассмотрим метод последовательного оценивания минимума с использованием квадратичной аппроксимации. Идея метода проста и заключается в последовательном применении квадратичной ап-проксимации на сужающемся интервале. Этот метод, разработанный Пауэллом, представляется следующим алгоритмом.

 Алгоритм последовательной квадратичной аппроксимации

Задано: x₁-начальная точка,

        Dx-величина шага по оси x.

1. Вычислить x₂=x₁+Dx.
2. Вычислить f₁=f(x₁) и f₂=f₂(x₂).
3. Если f₁> f₂, то x₃=x₁+2Dx;