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

 

 

 

 

 

 

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

На тему

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

 

Содержание

 

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] и алгоритм локализации точки минимума.