Файл: Сахарова Людмила Викторовна, Лукьянова Галина Викторовна Методы оптиизации для машинного обучения учебное пособие.doc

; b] ограничена некоторым числом, од­ним и тем же для всех участков. В этом случае говорят, что f (х) удов­летворяет на [а; b] условию Липшица. Целевые функции большинства практических задач оптимизации указанным свойством обладают.

Определение 2.3. Функция f (х) удовлетворяет на отрезке [а; b] ус­ловию Липшица, если существует такое число L > 0 (константа Липшица), что

(2.7)

для всех х' и х", принадлежащих [а; b].

Замечания:

1. Если неравенство (2.7) выполняется с константой L, то оно справедливо и при всех . Поэтому для функции, удовлетворяю­щей условию Липшица, существует бесконечное множество констант L из (2.7).

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

2. Из условия (2.7) непосредственно следует непрерывность f (х) на отрезке [а; b]. Поэтому, согласно теореме Вейерштрасса, функция f (х), удовлетворяющая на отрезке [а; b] условию Липшица, имеет на нем хотя бы одну точку минимума.

3 . Условие (2.7) означает, что модуль углового коэффициента любой хорды графика f (х) не превосходит L.

Переходя в (2.7) к пределу при , убеждаемся, что если в не­которой точке существует касательная к графику функции f (х), то модуль ее уг­лового коэффициента также не может превышать L. Так, функция f (х)= на отрезке [0; 1] условию Липшица не удовлетворяет, потому что при угловой коэффициент касательной к ее графику k

---

неограниченно возрастает (рис. 2.5).


Рис. 2.5. График функции , не удовлетворяющей условию Липшица

4. Если функция f (х) имеет на отрезке [а; b] непрерывную произ­водную, то она удовлетворяет на этом отрезке условию Липшица с константой

По формуле конечных приращений для произвольных точек х', х" [а; b] имеем: , где – некоторая точка, лежащая между х' и х". Отсюда с учетом условия получаем неравенство (2.7) для f (х).

5. Если a=x₀ <x₁<…<x_n =b, а функцияf (х) непрерывна на [а; b] и удовлетворяет условию (2.7) на каждом из отрезков [x_i, x_i+1], i= 0, 1,..,п – 1, с константой L_i, то она удовлетворяет условию Липшица и на всем отрезке [а; b] с константой

2.1.5. КЛАССИЧЕСКАЯ МИНИМИЗАЦИЯ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

Из математического анализа известны следующие условия ло­кального экстремума функции f (х), дифференцируемой достаточное число раз.1. Если функция f (х) дифференцируема в точке и достигает в этой точке локального экстремума, то (необходимое условие экстремума).2. Пусть функция f (х) п раз дифференцируема в точке и в этой точке все производные f (х) до п – 1–го порядка включительно равны нулю, . Тогда, если n – нечетно, то не является точкой локального экстремума функцииf (х). Если же n – четное число, то:а) при

---

– точка локального минимума f (х);б) при – точка локального максимума f (х) (доста­точное условие экстремума).Перечисленные условия позволяют предложить следующий путь решения задачи минимизации (2.1):1) с помощью условия 1 находим все точки возможного экстрему­ма функции f (х) на интервале (а; b), т.е. корни уравнения (2.8)(стационарные точки), принадлежащие интервалу (а; b);2) найденные стационарные точки исследуем в соответствии с условием 2, выделяя из них только точки локальных минимумов f (х);3) значения f (х) в точках локальных минимумов и на концах отрезка [а; b] сравниваем между собой. Наименьшему из этих значений соответствует точка глобального минимума f (х) на [а; b].3амечание. Применение условия 2 требует вычисления высших производных функцииf (х), поэтому в большинстве случаев бывает проще сравнить значения f (х) во всех стационарных точках, не интересуясь их характером. С учетом этого можно предложить следующий алгоритм минимизации f (х) на отрезке [а; b] (классический метод).Шаг 1. Решить уравнение (2.8) на интервале х  (а; b), т.е. найти все стационарные точки x₁, .., x_k–1 (а; b). Положить x₀ = а, x_k= b.Шаг 2. Вычислить значения f (х) функции f (х) в точках x_i, i= 0, .., k.Шаг 3. Найти . Положить х* = x_m.Пример 2.2. Классический метод минимизации. Решить задачуf (х) =х³ – Зх +1  min, х  [–2; 2].Шаг 1. Находим корни уравнения f '(х) = Зx² – 3 = 0 из интервала (–2; 2): x₁ = –1, x₂ = 1. Полагаем x₀= –2, x₃ = 2.Шаг 2. Вычисляем значения f (х) в точках x_i, i = 0, .., 3: f (х₀) = –17, f (х₁) = 3, f (х₂) = –1, f (х₃

---

) = 1.

Шаг 3. Находим f *= min(–l 7, 3, –1, 1) = – 17 =f (х₀). Поэтому x* = х₀ = –2, f *=–17.

При решении практических задач оптимизации классический метод имеет ограниченное применение. Это объясняется тем, что, во–первых, во многих случаях значения целевой функции f (х) находятся из измерений или экспериментов, а измерение производной f '(х) затруднительно или невозможно и, во–вторых, даже когда производная f '(х) задана аналитически или поддается измере­нию, решение уравнения (2.8) зачастую вызывает затруднения.

---

2.2. ПРЯМЫЕ МЕТОДЫ

Для решения задачи минимизации функции f (х) на отрезке [а; b] на практике, как правило, применяют приближенные методы. Они позволяют найти решение этой задачи с необходимой точностью в результате определения конечного числа значений функции f (х) и ее производных в некоторых точках отрезка [а; b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f (х) в заданных точках.Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функ­цию f (х), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f (х) унимодальной на отрезке [а; b].

2.2.1. МЕТОД ПЕРЕБОРА

Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем.Разобьем отрезок [а; b] на п равных частей точками деления x_i= а + i(b – а)/п,i = 0, .., n. Вычислив значения f (х) в точках x_i, путем сравнения найдем точку x_m ,0  т  п, для которой (2.9)Далее, положим .Замечания:1. Погрешность определения точки минимумах x* функции f (х) ме­тодом перебора не превосходит величины .Предположим, что x_m, из (2.9) является внутренней точкой разбиения отрезка [а;b], т.е. (случаи m = 0 и т = n рассматри­ваются аналогично). Тогда из соотношения (2.9) с учетом свойства (2.3) унимодальных функций следует что:а) т.е.

---