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

(х⁰) = df (х⁰) + ( ),

где – первый дифференциал f (х) в точке х⁰ .

2. Вектор f  '(х⁰)= – называется градиентом функции f (х) в точке х⁰. В малой окрестности точки х⁰ градиент ука­зывает направление наискорейшего возрастания функции f (х), а его норма характеризует скорость этого возрастания. Градиент в точке х перпендикулярен линии (поверхности) уровня f (х) = с, проходящей че­рез эту точку. Очевидно, df (х⁰) = < f  '(х⁰), x > , поэтому

 f (х⁰) = < f  '(х⁰), x > +( ).

3. Если функция f (x) дважды дифференцируема в точке х⁰ E_n , то

 f (х⁰) = df (х⁰) + d²f (х⁰) + ( ²) , где d²f (х⁰) =

второй дифференциал f (x) в точке х⁰ .

Используя матрицу вторых производных (мaтрицу Гессе, гессиaн)

, второй дифференциал можно записать так:

d²f (х⁰) = < f  (х⁰) x, x > , поэтому

 f (х⁰) = < f  (х⁰), x > + < f  (х⁰) x, x > + ( ²). (3.9)
4. Из формул (3.8) и (3.9) следует, что для малых ||x ||
f (x)  f (х⁰) + < f  (х⁰), x > (3.10)

или

f (x)  f (х⁰) + < f  (х⁰), x > + < f  (х⁰) x

---

, x > ,(3.11)

т.е. в малой окрестности точки х⁰ поведение дифференцируемой функции f (x) приближенно описывается формулой (3.10), а дважды диф­ференцируемой – формулой (3.11), причем представление (3.11) яв­ляется более точным.

3.1.4. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ

МИНИМУМА ДИФФЕРЕНЦИРУЕМОЙ ФУНКЦИИ

Из курса математического анализа известны следующие условия минимума функции n переменных.1. Если в точке х⁰ E_nфункция f (x) дифференцируема и достига­ет локального минимума, тоf (х⁰) = 0 или , j = 1,…, n (3.12)(необходимое условие минимумa). Точки, в которых выполнено усло­вие (3.12), называются стaционaрными точкaми дифференцируемой функции f (x).2. Если в стационарной точке х⁰ E_n , функция f (x) дважды дифференцируема и матрица ее вторых производныхf (х⁰) положительно определена, то х⁰ есть точка локального минимума f (x) (достаточное условие минимумa).Условия 1 и 2 лежат в основе классического метода минимизации функций, дифференцируемых во всем пространстве E_n . Приведем алгоритм этого метода.Шаг 1. Решив систему уравнений (3.12), найти все стационарные точки функции f (x).Шаг 2. Используя достаточные условия минимума, среди стаци­онарных точек функцииf (x) найти точки локального минимума и, срав­нивая значения функции в них, определить точки глобального мини­мума.Пример 3.1. Классический метод минимизации.Решить задачу f (x) = x²₁ + x²₂ + x²₃ +x₁ – x₃ – x₂x₃  min.Шаг 1. Запишем систему (3.12): ;  ;  . Решив ее, получим стационарную точку Шаг 2. Находим гессиан f  "(х⁰ ) =

---

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

Минимальное значение f  ^* f (х⁰ )= –19/12.

Замечание. Классический метод минимизации функций многих переменных имеет ограниченное практическое применение в основном из–за трудностей в аналитическом решении системы уравнений (3.12). Кроме того, на практике часто аналитическое за­дание функции неизвестно, а ее значения получают в результате измерений.

---

УПРАЖНЕНИЯ

1. Проверить справедливость равенств для данных числовых матриц:

1. 
   ;
   
2. 
   ;
   
3. 
   ;
   
4. 
   , то .
   

2. Установить, какая из приведенных ниже квадратичных форм положительно определена:

1. 
   Q(h) = h²₁ + 2h²₂ – 3h²₃ – 6h₁h₂ + 8h₁h₃ – 4h₂h₃ ;
   
2. 
   Q(h) = h²₁ + 5h²₂ – 3h²₃ – 4h₁h₂ – 2h₁h₃ – 2h₂h₃ ;
   
3. 
   Q(h) = h²₁ + h²₂ – h²₃ – h₁h₂ + 2h₁h₃ – 2h₂h₃ .
   

3. Проверить, что матрицаимеет собственные значения ₁ = 7, ₂ = ₃ = 1. Найти ее собственные векторы. Построить ортонормированный базис в E₃ из собственных векторов матрицы 1. Оценить норму матрицы,4. Проверить, что точки (0, 3, 1), (О, 1, –1), (1, 2, 0), (2, 1, 1), и (2, 3, –1) являются стационарными точками функции f (x) = x²₁ + x²₂ + x²₃ + 2x₁x₂x₃ – 4x₁x₃ – 2x₂x₃ – 2x₁ – 4x₂ + 4x₃ .Найти точки минимума этой функции, используя достаточное условие минимума.5. С помощью классического метода найти точки минимума функций:

1. 
   f (x) = x² ₁ + x² ₂ – 3x₁x₂ ; 
   
2. 
   f (x) = 2x² ₁ + x² ₂ + x² ₃ + 2x₁x₂x₃ + 6x₁ + 6x₂ + 4x₃ .
   

3.2. ВЫПУКЛЫЕ МНОЖЕСТВА И ВЫПУКЛЫЕ ФУНКЦИИ

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

---

выпуклых целевых функций.

3.2.1. СВОЙСТВА ВЫПУКЛЫХ ФУНКЦИЙ

Определение 3.1. Пусть х,у  Е_n . Множество {z}  Е_n точек видаz = x + (1 – )y , [0; 1] (3.16)называется отрезком, соединяющим точки х и у. В пространстве Е_n, п  3 соотношение (3.16) определяет обычный отрезок, соединяющий точки х и у. В самом деле, вектор х–у является направляющим вектором прямой, проходящей через точки х и у, поэтому для любой точки z этой прямой справедливо представление z = у + (х – у), которое отличается от (3.16) лишь формой записи. При  = 0 точка z совпадает с одним из концов отрезка (z=y), а при  = 1 – другим (z=x). При изменении  от 0 до 1 точка z пробегает отрезок от точки у до точки х.Определение 3.2. Множество U  Е_n называется выпуклым, если с любыми точками х и у U оно содержит и весь отрезок (3.16). Очевидно, Е_n – выпуклое множество.Теорема 3.1.Пересечение выпуклых множествU_i ,i=1,.., m, есть выпуклое множество, если оно содержит более одной точки.Пусть U= . Рассмотрим произвольные точки х¹ и x²U.Очевидно, х¹ и x²U₂при любом i = 1, .., т и, так как все U_i – выпуклы, отрезок [х¹, x²] U_i для всех i. Следовательно, он целиком принадлежит и множеству U.Определение 3.3. Функция f (х), заданная на выпуклом множестве U Е_n называется выпуклой, если для любых точек x, y U любого   [0; 1] выполняется неравенствоf [x + (1– )y]  f (x) + (1–)f (y). (3.17)Функция f (х) называется строго выпуклой, если для всех   (0; 1) неравенство (3.17) выполняется как строгое.Теорема 3.2. Линейнaя комбинaция выпуклых нa выпуклом мно­жестве U функцийf _i(х), i = 1, .., т, с неотрицaтельными коэффициентами _i , т.е. , _i

---