Чем отличается локальный минимум от глобального

• [math]\displaystyle< x_0 >[/math] называется точкой глобального (абсолютного) максимума, если [math]\displaystyle< \forall x\in M\quad f(x) \leqslant f(x_0); >[/math]
• [math]\displaystyle< x_0 >[/math] называется точкой глобального (абсолютного) минимума, если [math]\displaystyle< \forall x\in M\quad f(x) \geqslant f(x_0). >[/math]

Если неравенства выше строгие, то [math]\displaystyle< x_0 >[/math] называется точкой строгого локального или глобального максимума или минимума соответственно.

Значение функции [math]\displaystyle< f(x_0) >[/math] называют соответственно (строгим) локальным или глобальным максимумом или минимумом. Точки, являющиеся точками (локального) максимума или минимума, называются точками (локального) экстремума.

Замечание

Функция [math]\displaystyle< f, >[/math] определённая на множестве [math]\displaystyle< M, >[/math] может не иметь на нём ни одного локального или глобального экстремума. Например, [math]\displaystyle< f(x) = x,\; x\in (-1,1). >[/math]

Необходимые условия существования локальных экстремумов

• Из леммы Ферма вытекает следующее [2] :

Эти условия не являются достаточными, так, функция может иметь нуль производной в точке, но эта точка может не быть точкой экстремума, а являться, скажем, точкой перегиба, как точка (0,0) у функции [math]\displaystyle< f(x)=x^3 >[/math] .

Достаточные условия существования локальных экстремумов

• Пусть функция [math]\displaystyle< f\in C(x_0) >[/math] непрерывна в [math]\displaystyle< x_0\in M^0, >[/math] и существуют конечные или бесконечные односторонние производные [math]\displaystyle< f'_+(x_0), f'_-(x_0) >[/math] . Тогда при условии

[math]\displaystyle< x_0 >[/math] является точкой строгого локального максимума. А если

то [math]\displaystyle< x_0 >[/math] является точкой строгого локального минимума.

Заметим, что при этом функция не обязательно дифференцируема в точке [math]\displaystyle< x_0 >[/math] .

• Пусть функция [math]\displaystyle< f >[/math] непрерывна и дважды дифференцируема в точке [math]\displaystyle< x_0 >[/math] . Тогда при условии

[math]\displaystyle< x_0 >[/math] является точкой локального максимума. А если

[math]\displaystyle< f'(x_0)=0 >[/math] и [math]\displaystyle< f''(x_0) \gt 0 >[/math]

то [math]\displaystyle< x_0 >[/math] является точкой локального минимума.

• Пусть функция [math]\displaystyle< f >[/math] дифференцируема [math]\displaystyle< n >[/math] раз в точке [math]\displaystyle< x_0 >[/math] и [math]\displaystyle< f'(x_0)=f''(x_0)=\dots =f^<(n-1)>(x_0)=0 >[/math] , а [math]\displaystyle< f^<(n)>(x_0)\ne 0 >[/math] .

Если [math]\displaystyle< n >[/math] чётно и [math]\displaystyle< f^<(n)>(x_0)\lt 0 >[/math] , то [math]\displaystyle< x_0 >[/math]  — точка локального максимума. Если [math]\displaystyle< n >[/math] чётно и [math]\displaystyle< f^<(n)>(x_0)\gt 0 >[/math] , то [math]\displaystyle< x_0 >[/math]  — точка локального минимума. Если [math]\displaystyle< n >[/math] нечётно, то экстремума нет.

Как найти точку максимума функции?

Поиск точки максимума и минимума функции — довольно распространенная задача в математическом анализе. Иногда требуется экстремум. Многие думают, что под словом «экстремум» подразумевают наибольшее или наименьшее значение функции. Это не совсем верно. Значение может быть наибольшим или минимальным, но не являться экстремумом.

Глобальный и локальный максимум

Максимум бывает локальным или глобальным. Точка локального максимума — это аргумент, который при подстановке в f(x) даёт значение не меньше, чем в других точках из области около этого аргумента. Для глобального максимума эта область расширяется до всей области допустимых аргументов. Для минимума всё наоборот. Экстремум — это локальное экстремальное — минимальное или максимальное — значение.

Как правило, если математиков интересует глобально самое большое значение f(x), то в интервале, не на всей оси аргументов. Подобные задачи обычно сформулированы фразой «найдите точку максимума функции на отрезке». Здесь подразумевается, что надо выявить аргумент, при котором она не меньше, чем на всём остальном указанном отрезке. Поиск локального экстремума является одним из шагов решения такой задачи.

Дано y = f(x). Требуется определить пик функции на указанном отрезке. f(x) может достигать его в точке:

• экстремума, если она попадает в указанный отрезок,
• разрыва,
• ограничивающей заданный отрезок.

Исследование

Пик f(x) на отрезке или в интервале находится путём исследования данной функции. План исследования для нахождения максимума на отрезке (или интервале):

Найти область допустимых аргументов и пересечения этой области с областью исследования.
1. Выявить асимптоты. Они равны пределу при стремлении аргумента к точкам разрыва.
2. Определить первую производную и вычислить экстремальные точки и выяснить поведение функции в окрестности этих точек.
3. Рассчитать значение f(x) в точках, ограничивающих область исследования.
4. Сравнить экстремум со значением функции в точках разрыва и на концах интервала. Определить среди них наибольшее.

Теперь подробно разберем каждый шаг и рассмотрим некоторые примеры.

Область допустимых аргументов

Область допустимых аргументов — это те x, при подстановке которых в f(x) она не престаёт существовать.Область допустимых аргументов ещё называют областью определения. Например, y = x^2 определена на всей оси аргументов. А y = 1/x определена для всех аргументов, кроме x = 0.

Найти пересечение области допустимых аргументов и исследуемого отрезка (интервала) требуется для того, чтобы исключить из рассмотрения ту часть интервала, где функция не определена. Например, требуется найти минимум y = 1/x на отрезке от -2 до 2. На самом деле требуется исследовать два полуинтервала от -2 до 0 и от 0 до 2, так как уравнение у = 1/0 не имеет решения.

Асимптоты

Асимптота — это такая прямая, к которой функция тянется, но не дотягивается. Если f(x) существует на всей числовой прямой и неразрывна на ней, то вертикальной асимптоты у неё нет. Если же она разрывна, то точка разрыва является вертикальной асимптотой. Для y = 1/x асимптота задаётся уравнением x = 0. Эта функция тянется к нулю по оси аргументов, но дотянется до него, только устремившись в бесконечность.

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

Производная и экстремумы

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

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

1) Производная в точке экстремума либо нулевая, либо неопределенная. Это условие необходимое, но недостаточно. Продифференцируем y = x^3, получим уравнение производной: y = 3*x^2. Подставим в последнее уравнение аргумент «0», и производная обратится в нуль. Однако, это не экстремум для y = x^3. У неё не может быть экстремумов, она убывает на всей оси аргументов.

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

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

Концы интервала и сравнение результатов

При поиске максимума на отрезке необходимо проверить значение на концах отрезка. Например, для y = 1/x на отрезке [1; 7] максимум будет в точке x = 1. Даже если внутри отрезка есть локальный максимум, нет никакой гарантии, что значение на одном из концов отрезка не будет больше этого максимума.

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

Для задачи с формулировкой «Найдите точку минимума функции» необходимо выбрать наименьшее из локальных минимумов и значений на концах интервала и в точках разрыва.

Локальные и глобальные экстремумы

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

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

где Хо — произвольно выбранная начальная точка,

А — подбираемая некоторым способом величина шага.

Знак А определяется путем сравнения значений/^), f(x₀+A) и f(x₀ -Л). Если f(xo

A)>f(xo)>f(xo+A), то, согласно предположению об унимодальности, точка минимума должна располагаться правее точки х₀ и величина А выбирается положительной. Если изменить знаки неравенств на противоположные, то А следует выбирать отрицательной. Если же

то точка минимума лежит между х₀ — 1^1 и *о+ 1^1 и поиск граничных точек завершен. Случай, когда

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

Рассмотрим задачу минимизации функции f(x)=( 100-х) 2 при заданной начальной точке *0=30 и величине шага 1Д1=5.

Знак А определяется на основе сравнения значений

то величина А должна быть положительной, а координата точки минимума х* должна быть больше 30. Имеем X/ =х₀ — А = 35. Далее х₂ = Xj + 2 А = 45, /(45) = 3025 исключить интервал (х_т, Ь), положив Ь=Х_т.

Средней точкой нового интервала поиска становится точка X/. Следовательно, необходимо положить х,„ = х/. Перейти к шагу 5.

(2) Если f(x])>f(x_m) перейти к шагу 4.

Шаг 4. Сравнить/^ и f(x_m).

• (1) Если f(x₂) f(x_m), исключить интервалы (а, х/) и (х₂, Ь). Положить а = X/ и Ь=х₂. Заметим, что х_т продолжает оставаться средней точкой нового интервала. Перейти к шагу 5.

Шаг 5. Вычислить L=b-a. Если величина ILI мала, закончить поиск. В противном случае вернуться к шагу 2.

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

• 3. Если проведено п вычислений значения функции, то длина полученного интервала составляет (1/2)» /2 величины исходного интервала.
• 4. Показано, что из всех методов поиска на равных интервалах (двухточечный, трехточечный, четырехточечный и т. д.) трехточечный поиск, или метод деления интервала пополам, отличается наибольшей эффективностью.

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

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

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

Для того чтобы симметрия поискового образца сохранялась, расстояние (1 — т) должно составлять г-ю часть длины интервала (которая равна г). При таком выборе г следующая пробная точка размещается на расстоянии, равном г-й части длины интервала, от правой граничной точки интервала (рис. 7.12 ).

Рис. 7.12. Интервалы, полученные методом золотого сечения

Рис. 7.13. Симметрия золотого сечения интервала

Отсюда следует, что при выборе г в соответствии с условием 1 -r=f симметрия поискового образца, показанного на рис.7.12 сохраняется при переходе к уменьшенному интервалу, который изображен на рис.7.13. Решая это квадратное уравнение, получаем

откуда положительное решение ^=0,61803. . Схема поиска, при которой пробные точки делят интервал в этом отношении, известна под названием поиска с помощью метода золотого сечения. Заметим, что после первых двух вычислений значений функции каждое последующее вычисление позволяет исключить подынтервал, величина которого составляет (1 — г)-ю долю от длины интервала поиска. Следовательно, если исходный интервал имеет единичную длину, то величина интервала, полученного в результате N вычислений значений функции, равна г . Можно показать, что поиск с помощью метода золотого сечения является асимптотически наиболее эффективным способом реализации минимаксной стратегии поиска.

Пример метода золотого сечения

Опять рассмотрим задачу из примера, в которой требуется минимизировать f(x)=( 1 00-jc) 2 в интервале 60 2 при ограничении 0 (o₂=-t=S = 0,382, f(co2) = 31,6

Так как/(аъ) со/ исключается.

Итерация 2. /₂ =(0. 0,618); Ь₂ = 0,618 = г. Следующее вычисление значения функции проводится в точке

со, — т—? — т(1-т) = г ? = 0,236, Дсоз) = 352.

Так как f(co₃) >f(СО2) и со₃ 2 L₃ 0.618 — f(f) = 0.618 — т 4 = 0,472, f(co₄) =

Так как/(со₄) сс>2, интервал со FR(N)=L_n/L_i