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

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

На тему

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

 

Содержание

 

1.  МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ

1.1. Необходимые сведения из математики

1.1.1. Постановка  задачи одномерной минимизации

Под одномерной минимизацией понимается раздел численных методов, связанных с вычислением (или оценкой) минимума одномерной функции действительной переменной, заданной, как правило, на некотором ограниченном отрезке найти min f(x)=f(x*),               (1.1)

                                 a£x£b

где x*-искомая точка минимума на [a, b].

Заметим, что max f(x)= min f(-x),                 (1.2)

и поэтому при  дальнейшем изложении мы будем говорить о задачах минимизации (если не оговорено особо).

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

 

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

 

 

 

 

1.1.2. Классификация одномерных функций

Одномерные  функции принято классифицировать на непрерывные, разрывные и дискретные (рис.1.1).

 

     f(x)                    f(x)                      f(x)

  a) непрерывная           б) разрывная             г) дискретная

Рис.1.1. Примеры одномерных функций

 

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

• монотонные функции;
• унимодальные функции.

Введем некоторые  определения, которые нам понадобятся  в дальнейшем.

 

• Определение. Функция f(x) монотонно возрастает (убывает), если для произвольных x₁ и x₂, таких что x₁ £ x₂ выполняется неравенство

                     f(x₁)£ f(x₂)

      (или, соответственно, f(x₁)³f(x₂) для убывающей    функции).

 

Особый и  весьма важный класс составляют унимодальные функции.

• Определение. Функция f(x) называется унимодальной на отрезке a£x£b тогда и только тогда, когда для некоторой точки a£x*£b найдутся такие x₁ и x₂, для которых из неравенств x*£x₁£x₂ следует

                   f(x*)£f(x₁)£f(x₂)

     

и, из неравенств x*³x₁³x₂ следует

 

                       f(x*)³f(x₁)³f(x₂).

 

Другими словами можно  сказать, что функция унимодальна  на отрезке [a, b], если найдется такая точка x* на этом отрезке, по обе стороны от которой функция f монотонно возрастает (рис.1.2).

 

 

Заметим, что именно унимодальные функции являются целью одномерной минимизации.

         f(x)                                            f(x)

 

                 

а)                                     б)

Рис.1.2. Примеры унимодальных функций

а) непрерывная  унимодальная функция;

б) разрывная  унимодальная функция.

1.1.3. Ряд Тейлора

Любую непрерывную  функцию f можно разложить в окрестности некоторой точки x⁰ в степенной ряд, называемый рядом Тейлора¹:

 

   ,  (1.3)

 

где О_n+1(x-x⁰)ⁿ⁺¹ – сумма остаточных членов, степень приращения в           которых равна (n+1) и выше.

Вводя соответствующие  обозначения, ряд (1.3) будем записывать компактнее:

 

   .  (1.4)

 

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

 

1.1.4. Необходимые  и достаточные условия экстремума функции одной переменной

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

    

 

f(x)

          

 

 

           0 a    b     c    d        e      f    g         h      x  

     

Рис.1.3. Классификация стационарных точек

a,h)глобальный максимум и минимум на отрезке [a,h]; b)-локальный минимум; с,g)-локальный максимум; d-e)-отрезок слабого минимума; f)-точка перегиба.

 

 

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

• Теорема. Для того, чтобы точка x* была точкой локального минимума (максимума) дважды дифференцируемой на [a, b] функции f(x) необходимо, чтобы df(x*)/dx = 0,                  (1.5)

                       и

                         d²f(x*)/dx² ³ 0 (£ 0).           (1.6)

 

   Доказательство. Предположим вначале, что x*-внутренняя точка минимума на [a, b], а e=Dx-малая величина (отрицательная или положительная).

Запишем с помощью  ряда Тейлора изменение функции f в окрестности анализируемой точки x*:

  .  (1.7)

Тогда очевидно, что

                         f(x)³f(x*).                    (1.8)

 

Из неравенства (1.8) следует, что

 

             .  (1.9)

 

При достаточно малом e первое слагаемое доминирует над остальными, а так как e можно выбрать и положительным, и отрицательным, то неравенство (1.9) будет выполняться только в том случае, если

 

                          f’(x*)=0.                    (1.10)

 

Рассуждая аналогичным  образом, нетрудно установить, что неравенство (1.10) будет справедливым только тогда, когда

 

                          f”(x*)³0.                    (1.11)

 

Замечание. Эта же схема доказательства применима и в случае локального максимума, с той лишь разницей, что знак неравенства (1.9) требуется заменить на противоположный.

 

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

 

Введем следующие  важные определения:

• Стационарной точкой называется точка x*, в которой f’(x*)=0.
• Стационарная точка x* называется седловой точкой или точкой перегиба, если она не соответствует локальному экстремуму (минимуму или максимуму).

 

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

• Теорема. Пусть в точке x* первые (n-1) производные функции f(x) обращаются в нуль, а производная порядка n отлична от нуля. Тогда

      (1) если n–нечетное, то x*-точка перегиба;

      (2) если  n–четное, то x*-точка локального оптимума,

причем,

(а) если эта производная  положительная, то x*-точка локального минимума;

   (б) если эта  производная отрицательная, то x*-точка локального максимума.

 

Доказательство. Используем снова разложение f(x) в ряд Тейлора в окрестности стационарной точки x* (2.4). Поскольку порядок первой отличной от нуля производной равен n, формулу (1 f(x).4) можно переписать в следующем виде:

             .           (1.12)

Если n – нечетное число, то правая часть (1.12) может принимать как положительные, так и отрицательные значения в зависимости от того, является ли величина e положительной или отрицательной. Это означает, что в зависимости от знака e разность f(x*+e)-f(x*) либо положительная, либо отрицательная. Следовательно, функция не достигает в точке x* своего минимального или максимального значения, т.е. x* - точка перегиба.

Если n – четное число, то величина eⁿ всегда положительная, а знак правой части (1.12) определяется первым слагаемым т.к.   e - достаточно малая величина. Таким образом, если величина f⁽ⁿ⁾(x*) положительная, то f(x*+e)-f(x*)>0 и точка x* соответствует локальному минимуму. Аналогичные рассуждения нетрудно провести также для случая локального максимума.

 

• Пример. Классифицировать² стационарные точки функции

 

                f(x)=5x⁶-36x⁵+(165/2)x⁴-60x³+36,

 

      определенной на всей действительной  оси.  

 

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

 

                f’(x)=30x²(x-1)(x-2)(x-3),

 

обращаясь в  нуль в точках x*=0,1,2,3, и, следовательно, эти точки являются стационарными.

Вторая производная  функции равна

 

              f”(x)=150x⁴-720x³+990x²-360x.

 

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

 

                

 

Таблица 1.1.

x	f(x)	f”(x)
0 1 2 3	36.0   27.5   44.0    5.5	0    60 -120   540

 

Отсюда следует вывод, что x=1,3 – точки локальных минимумов, а x=2 – точка локального максимума. Чтобы идентифицировать точку x=0, необходимо вычислить третью производную в этой точке:

 

            f”’(x*)=(600x³-2160x²+1980x-360)|_x=0 = -360.

 

Так как эта  производная отлична от нуля и  имеет нечетный порядок, то точка x=0 является не точкой оптимума, а точкой перегиба (рис.1.4)

 

Рис.1.4. График исследуемой в примере функции

f(x)=5x⁶-36x⁵+(165/2)x⁴-60x³+36

1.1.5. Замечания относительно глобального минимума

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

Итак, пусть  требуется:

 

минимизировать f(x)

при ограничении a£x£b,

 

где a и b – установленные границы изменения значений переменной x.

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

Шаг 1. Приравнять df/dx=0 и найти все стационарные точки.

Шаг 2. Выбрать  все стационарные точки, которые  расположены в интервале [a,b],  обозначив их как x_i*, i=1,2,…,K.

Шаг 3. Найти  наименьшее значение f(x) из множества:

         f(a), f(x₁), f(x₂), …, f(x_K), f(b),

т.е. к множеству  всех стационарных точек мы добавили и граничные точки.

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

1.2. Методы исключения интервалов

1.2.1. Метод деления  пополам

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

Для установления границ интервала унимодальности [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;