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

 0 есть выпуклaя нa множестве U функция.

При _i  0 функции _if _i(х), выпуклы, поэтому для них выполня­ются неравенства (3.17). Складывая эти неравенства, получаем:

, x, y  U ,  [0; 1].

Теорема 3.3 – Пусть g(x) – выпуклaя функция, зaдaннaя в про­стрaнстве Е_n , Тогда множество U точек х, удовлетворяющих не­равенству g(x)  b, выпукло.

Пусть х и y  U и z = х + (1 – )у,   [0; 1]. Из выпуклости функции g(x) следует, что g(z)  g(x) + (l – )g(y) и, следовательно, g(z) b, т.е. точка z U и множество U – выпукло.

Следствие. Пусть g_i(x), i=l, .., m, – выпуклые функции в Е_n .

Тогда множество точек х, удовлетворяющих системе неравенств

g_i(x)  b_i i = 1, …, m, выпукло.

Это следует из теорем 3.1 и 3.3.

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

Теорема 3.4. Пусть f (x) – выпуклaя нa выпуклом множестве U функция. Тогда любой ее локальный минимум нa множестве U яв­ляется одновременно и глобальным.

Предположим противное, т.е. пусть х⁰ – точка локального, а х* – точка глобального минимума f (х) на множестве U, х*х⁰ и f (х⁰) > f (х*). Отсюда с учетом выпуклости функции имеем:

f [x^*+(1–)x⁰] f (x^*) + (1– )f (х⁰)<f (х⁰).

При  +0 точка х = х* + (1–)х⁰ попадет в сколь угодно малую окрестность точки х⁰ . Поэтому полученное неравенство f (х) < f (х⁰) противоречит предположению о том, что х⁰ – точка локального минимума.

Теорема 3.5. Глобальный минимум строго выпуклой функции f (x) нa выпуклом множестве U может достигаться лишь в един­ственной точке.

Предположим, что х¹ и х² – две различные точки глобального минимума. Из строгой выпуклости f (х) следует, что для всех  (0; 1) выполняется строгое неравенство

---

f [x¹+(1–)x²] <f (x¹) + (1–)f (х²) = f ^* =f (x), что противоречит предположению о том, что х¹ и х² –точки глобального минимума.Как уже отмечалось, наличие локальных минимумов функции f (x), не совпадающих с глобальным, сильно затрудняет поиск точки глобального минимума f (х). Поэтому применение многих методов минимизации обосновано только для функций, не имеющих точек локального минимума, отличных от глобального. Согласно теореме 3.4, таким свойством обладают выпуклые функции. Этим объясняется особая роль свойства выпуклости функции во многих вопросах оптимизации.Замечание. Отметим, что не всякая выпуклая в E_n функция достигает минимального значения, даже если она ограничена снизу. Например, функция f (x) = e^xявляется выпуклой в пространстве E₁, но достигает минимума Введем класс функций, для которых минимум вE_n обязательно существует.Определение 3.4. Функция f (х), заданная в E_n, называется сильно выпуклой, если существует такое число l> 0 (константа сильной вы­пуклости), что для всех х и у E_n и любого   [0; 1] выполняется не­равенство: .Очевидно, сильно выпуклая функция является выпуклой и строго выпуклой.Замечание. Можно показать, что у сильно выпуклой функции точка глобального минимума существует и единственна.Следующие утверждения позволяют получить наглядное представление об особенностях графиков функций, обладающих свойством обычной, строгой и сильной выпуклости.Для дифференцируемой в E_n функции f (х) выпуклость эквивалентна выполнению неравенстваf (x)  f (x⁰) + < f  (x⁰), x – x⁰ >, (3.18)строгая выпуклость –f (x) > f (x⁰) + < f  (x⁰), x – x⁰ >, (3.19)сильная выпуклость –f (x)  f (x⁰) + < f  (x⁰), x – x⁰ > + (3.18)для любых х, х⁰  E_nНа рис. 3.1 приведена иллюстрация неравенств (3.18)–(3.20) для пространства E

---

₂. График выпуклой, но не строго выпуклой функции f =f (х) (рис. 3.1,а) расположен не ниже касательной плос­кости z = f (х⁰) + < f '(х⁰), х– х⁰ >, проходящей через произвольную точку поверхности (х⁰, f (х⁰)). График строго выпуклой функции (рис. 3.1,6) имеет единственную общую точку с этой плоскостью. Подобное свойство для выпуклой функции одной переменной было рассмотрено в разд. 2.3.3.Предположим теперь, что f (х) сильно выпукла и х^* – точка ее глобального минимума. Тогда f '(x^*)=0 и неравенство (3.20) принимает вид f (x)  f (x^*) + + .Рис. 3.1. Геометрическая иллюстрация неравенств (3.18) – (3.20) для функции f (x)двух переменных: A – выпуклaя, но не строго выпуклaя; б – строго выпуклaя; в – сильно выпуклaя.Поверхность z=f (x*)+представляет собой параболоид вращения с вершиной в точке (x*, f (х*)). Отсюда видно, что график сильно выпуклой функции (рис.3.1, в) расположен внутри некоторого параболоида вращения.Замечание. Из неравенства (3.18) для выпуклой дифференцируемой функции f (х) следует, что условие f '(x)=0 является не только необходимым, но и достаточным для того, чтобы х* была точкой глобального минимума функции f (х).Приведем критерии строгой и сильной выпуклости для дважды дифференцируемых в Е_n функций. Достаточным условием строгой выпуклости функции f (х) является положительная определенность при x  Е_n ее матрицы Гессе f "(х), а сильной выпуклости – положительная определенность матрицы f "(х) – lЕ, где Е – единичная матрица, а l> 0. Эти критерии в комбинации с критерием Сильвестра (3.5) составляют во многих случаях удобный аппарат для проверки выпуклости функций небольшого числа переменных.

3.2.2. ВЫПУКЛЫЕ КВАДРАТИЧНЫЕ ФУНКЦИИ

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

---

.

Определение 3.5. Функция вида

(3.21)

называется квaдрaтичной функцией п переменных.

Положив _ij= _ij+ _ji, получим симметрическую матрицу A = (_ij), помощью которой выражение (3.21) можно записать в другой форме:

, (3.22)

где b = (b, .., b_n)  Е_n – вектор коэффициентов b_j .

Пример 3.3. Функция

f (x) = 2x²₁ – 2x₁x₂ + 3x₁x₃ + x²₂ – 2x₂x₃ + 4x²₃ + x₁ + 3x₃ + 5

является квадратичной. Запишем ее матрицу A, вектор b и коэффи­циент с из (3.22):

, b = , c = 5.

Перечислим основные свойства квадратичных функций.

1. Для градиента квадратичной функции (3.22) справедлива фор­мула

f  (x) = Ax + b. (3.23)

Запишем k–ю координату вектора f  '(х):



2. Гессиан квадратичной функции (3.22) совпадает с матрицей A:

f  (x) = A. (3.24)

Вычислим элемент матрицы Гессе:

.

3. Квадратичная функция (3.22) с положительно определенной матрицей A сильно выпукла.

Так как мaтрицaf "(x)= A симметрична и положительно опреде­лена, то все ее собственные значения _i положительны и существует ортонормированный базис из собственных векторов этой матрицы (см. разд. 3.1.1). В этом базисе:

, .

Поэтому угловые миноры матрицы A–lЕ равны _k= и положительны при 0< l < min _i . Таким образом, существует число l> 0, при котором матрица A –

---

lЕ положительно определена. А это означает, что f (х) сильно выпукла.Замечание. Для квадратичной функции f (x) из (3.22) с положительно определенной матрицей A точка глобального минимума су­ществует и единственна, так как f (х) сильно выпукла.Пример 3.4. Квадратичная функция f (х) из примера 3.3 сильно выпукла. D Матрица f  "(х) = A – положительно определена, так как₁ = 4 > 0; ₂ = ; ₃ = .Следовательно, f (х) сильно выпукла по свойству 3 квадратичных функций.Выпуклые квадратичные функции играют важную роль в теории одномерной оптимизации. Некоторые алгоритмы, разработанные с учетом свойств таких функций, позволяют найти их точку минимума за кон­ечное число итераций. Во многих случаях эти алгоритмы оказываются эффективными и для неквадратичных выпуклых функций, так как в достаточно малой окрестности точки минимума х* дважды дифференцируемая функция f (х) с положительно определенной матрицей Гессе f (х) хорошо аппроксимируется сильно выпуклой квадратичной функцией (см. (3.4), где f  (x^*) = 0).

---