Матстат. Семинар 1 Матричновекторное дифференцирование
 Скачать 0.54 Mb.
|
|
Методы оптимизации, ВМК, осень 2018 Семинар 1: Матрично-векторное дифференцирование 1 Матрично-векторное дифференцирование 1.1 Теория Для вычисления большинства производных, которые возникают на практике, достаточно лишь небольшой таблицы стандартных производных и правил преобразования. Удобнее всего оказывается работать в терминах «дифференциала» — с ним можно не задумываться о промежуточных размерно- стях, а просто применять стандартные правила. Замечание: В этом разделе описана сама техника матрично-векторного дифференцирования. Для более подробного описания математической теории, лежащей в основе этой техники, см. раздел A. Правила преобразования dA = 0 d(αX) = α(dX) d(AXB) = A(dX)B d(X + Y ) = dX + dY d(X T ) = (dX) T d(XY ) = (dX)Y + X(dY ) dhX, Y i = hdX, Y i + hX, dY i d X φ = φdX − (dφ)X φ 2 Таблица стандартных производных dhA, Xi = hA, dXi dhAx, xi = h(A + A T )x, dxi dhAx, xi = 2hAx, dxi (если A = A T ) d(Det(X)) = Det(X)hX −T , dXi d(X −1 ) = −X −1 (dX)X −1 Здесь A, B — фиксированные матрицы; α — фиксированный скаляр; X, Y — произвольные дифферен- цируемые матричные функции (согласованные по размерностям, чтобы все операции имели смысл); φ — произвольная дифференцируемая скалярная функция. Одним из самых важных является правило производной композиции. Пусть g(Y ) и f (X) — две дифференцирумые функции, и мы знаем выражения для их дифференциалов: dg(Y ) и df (X). Чтобы посчитать производную композиции φ(X) := g(f (X)), как и в скалярном случае, нужно: • взять выражение посчитанного дифференциала dg(Y ); • подставить в него вместо Y значение f (X), а вместо dY значение df (X). Пример Рассмотрим функцию φ(x) := lnhAx, xi, где A ∈ S n ++ . В данном случае g(y) := ln(y), dg(y) = dy y ; f (x) := hAx, xi, df (x) = 2hAx, dxi. Подставляем формально в dg(y) вместо y выражение для f (x) = hAx, xi, a вместо dy выражение для df (x) = 2hAx, dxi: dφ(x) = 2hAx, dxi hAx, xi (В нотации с «D»-большим: Dφ(x)[h] = 2hAx, hi hAx, xi ). Обычно, все возникающие на практике матрично-векторные функции составлены с помощью таб- личных функций и стандартных операций над ними. Благодаря универсальности приведённых правил, 1 дифференцировать сколь угодно сложные функции такого типа становится настолько же просто, как и дифференцировать одномерные функции. Полученное в конце концов выражение нужно привести к одному из канонических видов: Вход Выход Скаляр Вектор Матрица Скаляр df (x) = f 0 (x)dx − − (f 0 (x): скаляр; dx: скаляр) Вектор df (x) = h∇f (x), dxi df (x) = J f (x)dx − (∇f (x): вектор; dx: вектор) (J f (x): матрица; dx: вектор) Матрица df (X) = h∇f (X), dXi − − (∇f (X): матрица; dX: матрица) Случаи, отмеченные «−», нас интересовать не будут. Объект ∇f (x) (вектор для функции векторного аргумента и матрица для функции матричного аргумента) называется градиентом. Матрица J f (x) называется матрицей Якоби. Найти вторую производную функции f (X) можно по следующему «алгоритму»: ◦ посчитать первую производную функции; зафиксировать в выражениии для df (X) приращение dX — обозначить его как dX 1 ; ◦ посчитать производную для функции g(X) = df (X), считая dX 1 фиксированным (константа). Новое приращение обозначать dX 2 Пример Ввернёмся к функции φ(x) = lnhAx, xi, где A ∈ S n ++ . Мы уже посчитали её первую производную: dφ(x) = 2hAx,dxi hAx,xi . Обозначим dx за dx 1 и рассмотрим новую функцию: g(x) = 2hAx, dx 1 i hAx, xi Найдём производную g(x), считая, что dx 1 — константный вектор: d 2 φ(x) = d 2hAx, dx 1 i hAx, xi = d(2hAx, dx 1 i)hAx, xi − 2hAx, dx 1 idhAx, xi hAx, xi 2 = 2hAdx 1 , dx 2 ihAx, xi − 2hAx, dx 1 i2hAx, dx 2 i hAx, xi 2 = 2A hAx, xi − 4Axx T A hAx, xi 2 dx 1 , dx 2 (В нотации с D-большим: D 2 φ(x)[h 1 , h 2 ] = D 2A hAx,xi − 4Axx T A hAx,xi 2 h 1 , h 2 E .) Для второй производной каноническая форма для скалярной функции векторного аргумента d 2 f (x) = h∇ 2 f (x)dx 1 , dx 2 i. Матрица ∇ 2 f (x) называется гессианом. Для дважды непрерывно дифференцируемых функций гес- сиан является симметричной матрицей. 1.2 Задачи Задача 1 (Квадратичная функция). Найти первую и вторую производные df (x) и d 2 f (x), а также градиент ∇f (x) и гессиан ∇ 2 f (x) функции f (x) := 1 2 hAx, xi − hb, xi + c, x ∈ R n , 2 где A ∈ S n , b ∈ R n , c ∈ R. Решение. Найдем первую производную: df (x) = d 1 2 hAx, xi − hb, xi + c = 1 2 dhAx, xi − dhb, xi = 1 2 2hAx, dxi − hb, dxi = hAx − b, dxi . Заметим, что df (x) уже записан в канонической форме df (x) = h∇f (x), dxi, поэтому ∇f (x) = Ax − b . Теперь найдём вторую производную: d 2 f (x) = dhAx − b, dx 1 i = hd(Ax − b), dx 1 i = hd(Ax), dx 1 i = hAdx 2 , dx 1 i . Чтобы найти гессиан, приведем d 2 f (x) к канонической форме d 2 f (x) = h∇ 2 f (x)dx 1 , dx 2 i: d 2 f (x) = hAdx 1 , dx 2 i ⇒ ∇ 2 f (x) = A . Задача 2. Найти первую и вторую производные df (x) и d 2 f (x), а также градиент ∇f (x) и гессиан ∇ 2 f (x) функции f (x) := 1 2 kAx − bk 2 2 , x ∈ R n , где A ∈ R m×n , b ∈ R n Решение. Найдем первую производную: df (x) = d 1 2 kAx − bk 2 2 = {d(kxk 2 2 ) = dhx, xi = 2hx, dxi} = 1 2 2hAx − b, d(Ax − b)i = hAx − b, Adxi . Чтобы найти градиент, приведем df (x) к канонической форме df (x) = h∇f (x), dxi: df (x) = hA T (Ax − b), dxi ⇒ ∇f (x) = A T (Ax − b) . Теперь найдём вторую производную: d 2 f (x) = dhAx − b, Adx 1 i = hd(Ax − b), Adx 1 i = hAdx 2 , Adx 1 i = hdx 2 , A T Adx 1 i . Чтобы найти гессиан, приведем d 2 f (x) к канонической форме d 2 f (x) = h∇ 2 f (x)dx 1 , dx 2 i: d 2 f (x) = hA T Adx 1 , dx 2 i ⇒ ∇ 2 f (x) = A T A . Задача 3 (Куб евклидовой нормы). Найти первую и вторую производные df (x) и d 2 f (x), а также градиент ∇f (x) и гессиан ∇ 2 f (x) функции f (x) := 1 3 kxk 3 2 , x ∈ R n 3 Решение. Найдем первую производную: df (x) = d 1 3 kxk 3 2 = 1 3 dhx, xi 3/2 = 1 3 3 2 hx, xi 1/2 dhx, xi = 1 2 kxk 2 ( 2hx, dxi) = kxk 2 hx, dxi . Чтобы найти градиент, приведем df (x) к канонической форме df (x) = h∇f (x), dxi: df (x) = hkxk 2 x, dxi ⇒ ∇f (x) = kxk 2 x . Теперь найдем вторую производную: d 2 f (x) = d(kxk 2 hx, dx 1 i) = d(kxk 2 ) | {z } =d(hx,xi 1/2 ) hx, dx 1 i + kxk 2 dhx, dx 1 i = 1 2 hx, xi −1/2 ( 2hx, dx 2 i hx, dx 1 i + kxk 2 hdx 2 , dx 1 i = kxk −1 2 hx, dx 2 ihx, dx 1 i + kxk 2 hdx 2 , dx 1 i . Чтобы найти гессиан, приведем d 2 f (x) к канонической форме d 2 f (x) = h∇ 2 f (x)dx 1 , dx 2 i: d 2 f (x) = kxk −1 2 hdx 1 , xihx, dx 2 i + kxk 2 hdx 1 , dx 2 i = h(kxk −1 2 xx T + kxk 2 I n )dx 1 , dx 2 i ⇒ ∇ 2 f (x) = kxk −1 2 xx T + kxk 2 I n Отметим, что полученная формула для гессиана (и второй производной) верна только при x 6= 0, поскольку значение kxk −1 2 не определено для x = 0. Такое ограничение возникло из-за того, что в самом начале мы воспользовались правилом произведения, и у нас возникла производная d(kxk 2 ), которая не существует в точке x = 0. Тем не менее, можно показать, что рассматриваемая функция f является всюду дважды непрерывно дифференцируемой, и ее вторая производная в точке x = 0 равна нулю. Таким образом, можно сказать, что полученная формула, на самом деле, верна для любых значений x, с оговоркой, что в точке x = 0 значение kxk −1 2 xx T надо понимать как 0 (предел при x → 0). Задача 4 (Евклидова норма). Найти первую и вторую производные df (x) и d 2 f (x), а также градиент ∇f (x) и гессиан ∇ 2 f (x) функции f (x) := kxk 2 , x ∈ R n \ {0}. Решение. Найдем первую производную: df (x) = d(kxk 2 ) = d(hx, xi 1/2 ) = 1 2 hx, xi −1/2 dhx, xi = 1 2 kxk −1 2 2hx, dxi = kxk −1 2 hx, dxi . Чтобы найти градиент, приведем df (x) к канонической форме df (x) = h∇f (x), dxi: df (x) = hkxk −1 2 x, dxi ⇒ ∇f (x) = kxk −1 2 x . Теперь найдем вторую производную: d 2 f (x) = d(kxk −1 2 hx, dx 1 i) = d(kxk −1 2 )hx, dx 1 i + kxk −1 2 dhx, dx 1 i = −kxk −2 2 d(kxk 2 )hx, dx 1 i + kxk −1 2 hdx 2 , dx 1 i = −kxk −2 2 (kxk −1 2 hx, dx 2 i)hx, dx 1 i + kxk −1 2 hdx 2 , dx 1 i = kxk −1 2 hdx 2 , dx 1 i − kxk −3 2 hx, dx 2 ihx, dx 1 i . 4 Чтобы найти гессиан, приведем d 2 f (x) к канонической форме d 2 f (x) = h∇ 2 f (x)dx 1 , dx 2 i: d 2 f (x) = kxk −1 2 (hdx 1 , dx 2 i − kxk −2 2 hdx 1 , xihx, dx 2 i) = hkxk −1 2 (I n − kxk −2 2 xx T )dx 1 , dx 2 i ⇒ ∇ 2 f (x) = kxk −1 2 (I n − kxk −2 2 xx T ) . Задача 5 (Логистическая функция). Найти первую и вторую производные df (x) и d 2 f (x), а также градиент ∇f (x) и гессиан ∇ 2 f (x) функции f (x) := ln(1 + exp(ha, xi)), x ∈ R n , где a ∈ R n Решение. Найдем первую производную: df (x) = d(ln(1 + exp(ha, xi))) = d(ln(x)) = dx x = d(1 + exp(ha, xi)) 1 + exp(ha, xi) = d(exp(ha, xi)) 1 + exp(ha, xi) = {d(exp(x)) = exp(x)dx} = exp(ha, xi)dha, xi 1 + exp(ha, xi) = exp(ha, xi)ha, dxi 1 + exp(ha, xi) = ha, dxi 1 + exp(−ha, xi) = σ(ha, xi)ha, dxi . Здесь введено обозначение σ : R → R для сигмоидной функции: σ(x) := 1 1 + exp(−x) Чтобы найти градиент, приведем df (x) к канонической форме df (x) = h∇f (x), dxi: df (x) = hσ(ha, xi)a, dxi ⇒ ∇f (x) = σ(ha, xi)a . Таким образом, градиент ∇f (x) — это вектор, коллинеарный вектору a с коэффициентом σ(ha, xi) ∈ (0, 1). В зависимости от точки x меняется лишь длина вектора ∇f (x), но не его направление. Теперь найдем вторую производную: d 2 f (x) = d(σ(ha, xi)ha, dx 1 i) = d(σ(ha, xi))ha, dx 1 i = {d(σ(x)) = σ 0 (x)dx} = (σ 0 (ha, xi)dha, xi)ha, dx 1 i = σ 0 (ha, xi)ha, dx 2 iha, dx 1 i = {σ 0 (x) = σ(x)(1 − σ(x))} = σ(ha, xi)(1 − σ(ha, xi))ha, dx 2 iha, dx 1 i . Чтобы найти гессиан, приведем d 2 f (x) к канонической форме d 2 f (x) = h∇ 2 f (x)dx 1 , dx 2 i: d 2 f (x) = σ(ha, xi)(1 − σ(ha, xi))hdx 1 , aiha, dx 2 i = h(σ(ha, xi)(1 − σ(ha, xi))aa T )dx 1 , dx 2 i ⇒ ∇ 2 f (x) = σ(ha, xi)(1 − σ(ha, xi))aa T Заметим, что гессиан ∇ 2 f (x) — это одноранговая матрица, пропорциональная матрице aa T с коэффициентом σ(ha, xi)(1 − σ(ha, xi)) ∈ (0, 0.25). Точка x влияет лишь на коэффициент пропорциональности. Задача 6 (Логарифм определителя). Найти первую и вторую производные df (X) и d 2 f (X), а также градиент ∇f (X) функции f (X) := ln(Det(X)), заданной на множестве S n ++ в пространстве S n 5 Решение. Найдём первую производную: df (X) = d(ln Det(X)) = d(ln(x)) = dx x = d(Det(X)) Det(X) = Det(X) hX −1 , dXi Det(X) = hX −1 , dXi . Заметим, что df (X) уже и так записан в канонической форме df (X) = h∇f (X), dXi. 1 Поэтому, ∇f (X) = X −1 Теперь найдем вторую производную: d 2 f (X) = dhX −1 , dX 1 i = hd(X −1 ), dX 1 i = h−X −1 (dX 2 )X −1 , dX 1 i = −hX −1 (dX 2 )X −1 , dX 1 i . В итоге получилась билинейная форма от приращений dX 1 и dX 2 в пространстве матриц. Рассмотрим D 2 f (X)[H, H] = −hX −1 HX −1 , Hi. Покажем, что D 2 f (X)[H, H] имеет отрицательный знак для всех X ∈ S n ++ и H ∈ S n , т. е. что функ- ция f является вогнутой функцией. Действительно, раскладывая X −1 = X −1/2 X −1/2 , перепишем D 2 f (X)[H, H] в следующем виде: D 2 f (X)[H, H] = −hX −1/2 HX −1/2 , X −1/2 HX −1/2 i = −kX −1/2 HX −1/2 k 2 F Отсюда видно, что D 2 f (X)[H, H], действительно, имеет отрицательный знак. Задача 7. Найти производную df (X) и градиент ∇f (X) функции f (X) := kAX − Bk F , X ∈ R k×n , где A ∈ R m×k , B ∈ R m×n Решение. Вычислим отдельно d(kXk F ): d(kXk F ) = d(hX, Xi 1/2 ) = d(x 1/2 ) = 1 2 x −1/2 dx = 1 2 hX, Xi −1/2 dhX, Xi = 1 2 kXk −1 F 2hX, dXi = kXk −1 F hX, dXi. Теперь используем полученную формулу, чтобы найти df (X): df (X) = d(kAX − Bk F ) = kAX − Bk −1 F hAX − B, d(AX − B)i = kAX − Bk −1 F hAX − B, AdXi . Чтобы найти градиент, приведем df (X) к канонической форме df (X) = h∇f (X), dXi: df (X) = hkAX − Bk −1 F A T (AX − B), dXi ⇒ ∇f (X) = kAX − Bk −1 F A T (AX − B) . 1 В этом примере мы работаем в пространстве симметричных матриц S n , поэтому знак транспонирования можно опустить. 6 Задача 8. Найти производную df (X) и градиент ∇f (X) функции f (X) := Tr(AXBX −1 ), X ∈ R n×n , Det(X) 6= 0, где A, B ∈ R n×n Решение. Для удобства перепишем след через скалярное произведение: f (X) = hI n , AXBX −1 i. Найдем первую производную: df (X) = dhI n , AXBX −1 i = hI n , d(AXBX −1 )i = hI n , (d(AXB))X −1 + (AXB)d(X −1 )i = hI n , (A(dX)B)X −1 + (AXB)(−X −1 (dX)X −1 )i = hI n , A(dX)BX −1 − AXBX −1 (dX)X −1 i . Чтобы найти градиент, приведем df (X) к канонической форме df (X) = h∇f (X), dXi: df (X) = hI n , A(dX)BX −1 i − hI n , AXBX −1 (dX)X −1 i = = hA T X −T B T , dXi − hX −T B T X T A T X −T , dXi = hA T X −T B T − X −T B T X T A T X −T , dXi ⇒ ∇f (X) = A T X −T B T − X −T B T X T A T X −T Задача 9. Рассмотрим функцию скалярного аргумента φ(α) := f (x + αp), α ∈ R, где x, p ∈ R n , f : R n → R — дважды непрерывно дифференцируемая функция. Найдите первую и вторую производные φ 0 (α) и φ 00 (α) и выразите их через градиент ∇f (·) и гессиан ∇ 2 f (·). Решение. В этой задаче нужно постоянно помнить, что дифференцирование выполняется по α, а x — постоянный вектор. Найдем первую производную: dφ(α) = d α (f (x + αp)) = {df (x) = h∇f (x), dxi} = h∇f (x + αp), d α (x + αp)i = h∇f (x + αp), (dα)pi = h∇f (x + αp), pidα. Здесь последнее равенство следует из того, что dα — это скаляр. Заметим, что мы представили dφ(α) в канонической форме dφ(α) = φ 0 (α)dα. Значит, φ 0 (α) = h∇f (x + αp), pi . Теперь найдем вторую производную: d 2 φ(α) = d α (h∇f (x + αp), pidα 1 ) = hd α ∇f (x + αp), pidα 1 = {d∇f (x) = ∇ 2 f (x)dx} = h∇ 2 f (x + αp)d α (x + αp), pidα 1 = h∇ 2 f (x + αp)(dα 2 )p, pidα 1 = h∇ 2 f (x + αp)p, pidα 1 dα 2 Таким образом, из канонической формы d 2 φ(α) = φ 00 (α)α 1 α 2 , получаем φ 00 (α) = h∇ 2 f (x + αp)p, pi . 7 Задача 10. Рассмотрим функцию скалярного аргумента φ(α) := kr(x + αp)k 2 , α ∈ R + , r(x + αp) 6= 0, где x, p ∈ R n , r : R n → R m — дифференцируемое отображение. Найдите производную φ 0 (α) и выразите ее через матрицу Якоби J r (·). Решение. В этой задаче, как и в предыдущей, нужно постоянно помнить, что дифференцирование выполняется по α, а x — постоянный вектор. Найдем первую производную: dφ(α) = d α (kr(x + αp)k 2 ) = dkxk 2 = hx, dxi kxk 2 = hr(x + αp), d α r(x + αp)i kr(x + αp)k 2 = {dr(x) = J r (x)dx} = hr(x + αp), J r (x + αp)d α (x + αp)i kr(x + αp)k 2 = hr(x + αp), J r (x + αp)(dα)pi kr(x + αp)k 2 = hr(x + αp), J r (x + αp)pi kr(x + αp)k 2 dα. Отсюда φ 0 (α) = hr(x + αp), J r (x + αp)pi kr(x + αp)k 2 2 Условия оптимальности 2.1 Теория Рассмотрим функцию f : X → R, где X ⊆ U — подмножество нормированного линейного простран- ства, например, U = R n — векторы или U = R n×m — матрицы. Определение 2.1 (Локальные экстремумы). Точка x ∈ X называется точкой локального минимума функции f , если существует шар некоторого радиуса r > 0, с центром в этой точке: W = {z ∈ U : kz − xk < r}, и выполнено: f (x) ≤ f (z) для любого z ∈ W ∩ X. Если для всех z ∈ W кроме z = x в определении выполняется строгое неравенство, то локальный минимум называется строгим локальным минимумом. Если неравенство выполнено в другую сторону, то точка x называется локальным максимумом. Локальные минимумы и максимумы вместе называются локальными экстремумами. Если функция является дифференцируемой, то отыскать её локальные экстремумы иногда удаётся с помощью следующих утверждений. Утверждение 2.2 (условие оптимальности первого порядка). Пусть для функции f : X → R точка x является точкой локального экстремума. Тогда если функция непрерывно-дифференцируема в окрестности этой точки, то её производная в этой точке равна нулю: df (x) = 0. Замечание 2.3. Равенство df (x) = 0 означает, что Df (x)[h] = 0 для любого h ∈ U . Замечание 2.4. Напомним, что для функции векторного аргумента f : R n → R ее производную всегда можно представить с помощью градиента: Df (x)[h] = h∇f (x), hi. В этом случае равенство производной нулю эквивалентно равенству нулю градиента: df (x) = 0 ⇔ h∇f (x), hi = 0 для любого h ∈ R n ⇔ ∇f (x) = 0. 8 Рис. 1: Пример экстремумов из Википедии. Рис. 2: Примеры седловых точек (слева — красная точка, справа — белая) из Википедии. Замечание 2.5. Важно понимать, что утверждение 2.2 является лишь необходимым условием ло- кального минимума. Например, для функции f (x) = x 2 производная равна нулю в единственной точке x = 0, и эта точка действительно является локальным минимумом функции (в данном случае и гло- бальным). Но для f (x) = x 3 , в той же точке x = 0 — производная равна нулю, но сама точка не является ни локальным минимумом, ни локальным максимумом. Определение 2.6. Точка x называется стационарной точкой, если производная в ней обращается в ноль: df (x) = 0. Стационарная точка, которая не является ни локальным минимумом, ни локальным максимумом, называется седловой точкой. В случае функции двух переменных «седловая точка» действительно напоминает седло. Но мы используем это понятие для произвольных функций, в значении, указанном выше. Для классификации стационарных точек удобным оказывается следующее утверждение. Утверждение 2.7 (условия оптимальности второго порядка). Пусть функции f : X → R дважды непрерывно дифференцируема в окрестности стационарной точки x ∈ X. Тогда: 9 • если D 2 f (x)[h, h] > 0 для всех h ∈ U, h 6= 0, то x — строгий локальный минимум; • если D 2 f (x)[h, h] < 0 для всех h ∈ U, h 6= 0, то x — строгий локальный максимум; • если существует h, h 0 ∈ U такие, что: D 2 f (x)[h, h] > 0 и D 2 f (x)[h 0 , h 0 ] < 0, то x — седловая точка. Также, справедливы и необходимые условия оптимальности второго порядка: • если x — локальный минимум, то D 2 f (x)[h, h] ≥ 0 для всех h ∈ U ; • если x — локальный максимум, то D 2 f (x)[h, h] ≤ 0 для всех h ∈ U . Замечание 2.8. Напомним, что для функции векторного аргумета f : R n → R её вторую производную всегда можно представить с помощью матрицы — гессиана: D 2 f (x)[h, h] = h∇ 2 f (x)h, hi. В этом случае утверждение 2.7 можно переписать в терминах знакоопределённости гессиана: • если ∇ 2 f (x) 0, то x — строгий локальный минимум; • если ∇ 2 f (x) ≺ 0, то x — строгий локальный максимум; • если ∇ 2 f (x) — неопределённая матрица (т.е. не выполнено ни ∇ 2 f (x) 0 ни ∇ 2 f (x) 0), то x — седловая точка. • если x — локальный минимум, то ∇ 2 f (x) 0; • если x — локальный максимум, то ∇ 2 f (x) 0. Итак, в общем случае условие оптимальности первого порядка (Df (x) = 0) является только необ- ходимым условием глобального минимума — точка x может быть не глобальным, а лишь локальным минимумом, или вообще локальным максимумом или седловой точкой. Тем не менее, для определенно- го класса функций — класса выпуклых функций — условие оптимальности первого порядка является не просто необходимым, но также и достаточным условием глобального минимума. Утверждение 2.9 (Условие оптимальности первого порядка для выпуклой функции). Пусть X яв- ляется открытым множеством, и пусть f : X → R — выпуклая дифференцируемая функция. Точка x ∗ ∈ X является глобальным минимумом функции f тогда и только тогда, когда ∇f (x ∗ ) = 0. Дру- гими словами, любая стационарная точка выпуклой функции автоматически является глобальным минимумом. 2.2 Задачи Задача 11. Рассмотрим фунцию f (x 1 , x 2 ) = x 2 1 − x 2 2 + 2x 1 . Найти все ее стационарные точки. Решение. Найдем градиент и гессиан: ∇f (x 1 , x 2 ) = " 2x 1 + 2 −2x 2 # ∇ 2 f (x 1 , x 2 ) = 2 0 0 −2 — всюду постоянная матрица. Градиент обращается в ноль в единственной точке: (−1, 0). Гессиан — неопределённая матрица, значит стационарная точка (−1, 0) — седловая. Локальных экстремумов нет, функция неограниченная: inf x∈R 2 f (x) = −∞, sup x∈R 2 f (x) = +∞. 10 Задача 12 (Регрессия наименьших квадратов). Рассмотрим следующую задачу оптимизации: min x∈R n kAx − bk 2 , где A ∈ R m×n , b ∈ R m , Rank(A) = n. Найдите множество ее решений и оптимальное значение целевой функции. Решение. Прежде всего, перейдем от исходной негладкой задачи к эквивалентной ей гладкой: min x∈R n kAx − bk 2 2 (2.1) Заметим, что при таком переходе меняется лишь оптимальное значение целевой функции, а множество оптимальных решений остается неизменным. Чтобы найти решения (2.1), воспользуемся условием оптимальности первого порядка: ∇(kAx − bk 2 2 ) = 2A T (Ax − b) = 0. Заметим, что целевая функция в задаче (2.1) является выпуклой (как композиция выпуклой функции x 7→ kxk 2 и аффинного преобразования x 7→ Ax − b). Поэтому условие оптимальности первого порядка является не только необходимым, но также и достаточным условием того, что точка x является гло- бальным решением задачи (2.1). Итак, все решения задачи (2.1) — это решения следующей системы линейных уравнений, и только они: A T Ax = A T b. (2.2) Уравнения (2.2) называются нормальными уравнениями. Заметим, что матрица A T A является обра- тимой, поскольку она имеет полный ранг: согласно условию, Rank(A) = n, и из линейной алгебры известно, что Rank(A T A) = Rank(A). Отсюда заключаем, что нормальные уравнения (2.2) имеют единственное решение x ∗ = (A T A) −1 A T b . Таким образом, найденная точка x ∗ является единственным решением исходной задачи. Оптимальное значение целевой функции при этом равно Opt := kAx ∗ − bk 2 = kA(A T A) −1 A T b − bk 2 Матрица (A T A) −1 A T называется псевдообратной (по Муру-Пенроузу) и обозначается A + . Это прямое обоб- щение понятия обратной матрицы для неквадратных матриц. Если A квадратная и обратимая, то псевдооб- ратная матрица A + совпадает с обратной матрицей A −1 Матрица Π := A A T A −1 A T называется проекционной матрицей и проектирует заданный вектор b на линейную оболочку, натянутую на столбцы матрицы A. Отметим, что задача (2.1) имеет решения всегда, даже если Rank(A) < n. Действительно, как было показано выше, задача (2.1) разрешима тогда и только тогда, когда разрешимы нормальные уравнения (2.2). Нормальные уравнения (2.2) разрешимы тогда и только тогда, когда A T b ∈ Im(A T A), где Im(A T A) — образ матрицы A T A. Из линейной алгебры известно, что Im(A T A) = Im(A T ). Значит, условие A T b ∈ Im(A T A) всегда выполняется. Итак, задача (2.1) всегда разрешима, и в случае Rank(A) < n имеет бесконечное множество решений. (Одно из возможных решений записывается через псевдообратную матрицу.) Задача 13. Для следующей задачи оптимизации найдите ее множество решений и оптимальное зна- чение целевой функции: min X∈S n ++ {hS, Xi − ln Det(X)}, где S ∈ S n ++ 11 Решение. Введем обозначение f (X) := hS, Xi − ln Det(X). Запишем условие оптимальности первого порядка: ∇f (X) = S − X −1 = 0. Заметим, что в нашем случае целевая функция f является выпуклой на рассматриваемом множестве S n ++ как сумма двух выпуклых функций: X 7→ hS, Xi и X 7→ − ln Det(X). Поэтому условие оптимально- сти первого порядка является не только необходимым, но также и достаточным условием глобального минимума. Из уравнения оптимальности находим X = S −1 . Итак, оптимальное решение единственное — это X ∗ = S −1 Соответствующее оптимальное значение целевой функции равно Opt := f (X ∗ ) = hS, S −1 i − ln Det(S −1 ) = n + ln Det(S) . 12 A Производные: теория A.1 Определение Начнём с напоминания понятия производной. Для функции одной переменной f : R → R её производная в точке x обозначается f 0 (x) и опреде- ляется из равенства: f (x + h) = f (x) + f 0 (x)h + o(h) для всех достаточно малых h. Другими словами, зафиксировав некоторую точку x, мы хотим приблизить изменение функции f (x + h) − f (x) в окрестности этой точки с помощью линейной функции по h, и f 0 (x)h — наилучший способ это сделать. Рассмотрим теперь более общую ситуацию. Пусть U и V суть конечномерные линейные пространства с нормами. Основными примерами таких пространств для нас будут служить числа: R, векторы: R n и матрицы: R n×m , а также их комбинации (декартовы произведения). Рассмотрим функцию f : X → V , где X ⊆ U . Определение A.1 (Дифференцируемость). Пусть x ∈ X — внутренняя точка множества X, и пусть L : U → V — линейный оператор. Будем говорить, что функция f дифференцируема в точке x с производной L, если для всех достаточно малых h ∈ U справедливо следующее разложение: f (x + h) = f (x) + L[h] + o(khk). (A.1) Если для любого линейного оператора L : U → V функция f не является дифференцируемой в точке x с производной L, то будем говорить, что f не является дифференцируемой в точке x. Если точка x не является внутренней точкой множества X, то оставим понятие дифференцируемости функции f в точке x неопределенным. Замечание A.2. Выражение o(khk) имеет стандартное значение: f (x + h) − f (x) − L[h] = o(khk) def ⇐⇒ lim h→0 kf (x + h) − f (x) − L[h]k khk = 0. Замечание A.3. Поскольку рассматриваемые пространства U и V являются конечномерными (а в конечномерном пространстве все нормы топологически эквивалентны), то не имеет значения, какие конкретно нормы используются в данном выше определении: если функция f является дифференци- руемой в точке x с производной L для одного выбора норм, то f также будет дифференцируемой в точке x с производной L для любого другого выбора норм. Утверждение A.4. Предположим, что функция f дифференцируема в точке x с производной L 1 и также дифференцируема в точке x с производной L 2 . Тогда L 1 = L 2 Таким образом, если функция f является дифференцируемой в точке x, то ее производная L опре- деляется единственным образом. Будем обозначать ее символом df (x). Замечание A.5. Объект df зависит от двух параметров: точка x ∈ X, в которой мы аппроксимируем функцию, и приращение h ∈ U , которое откладывается от зафиксированной точки: df : X × U → V, линейный по второму аргументу — по «h». Замечание A.6. Встречаются разные обозначения производной фунции f в точке x: Df (x)[h] ≡ df (x)[h] ≡ Df (x)[∆x] ≡ df (x)[∆x]. Все они обозначают одно и то же. При работе с определением производной, удобно явным образом указывать приращение (h или ∆x) в квадратных скобках. При вычислении производных на практи- ке, пользуясь уже известными посчитанными производными и свойствами пересчёта, приращение в квадратных скобках обычно не пишут: df (x) или даже просто df , когда понятно, о чём идёт речь. 13 Итак, производная функции в точке x — это линейный оператор df (x) который лучше всего ап- проксимирует приращение функции: f (x + h) − f (x) ≈ Df (x)[h]. Ещё одним известным и важным понятием является производная функции по направлению. Ока- зывается, зная производную функции f мы можем легко посчитать её производную вдоль любого направления h. Утверждение A.7. Пусть f дифференцируема в точке x. Выберем произвольное направление h. Тогда: Df (x)[h] = ∂f (x) ∂h := lim t→+0 f (x + th) − f (x) t То есть, чтобы посчитать ∂f (x) ∂h — производную функции f вдоль направления h, достаточно при- менить df (x)[·] к этому направлению. Набор векторов e i = (0, . . . , 0, 1 i , 0, . . . , 0) ∈ R n , i = 1, . . . , n называется стандартным базисом в R n Если для некоторого i у функции существует (двусторонняя) производная вдоль направления e i , то eё называют частной производной по i-ой координате: ∂f (x) ∂x i := lim t→0 f (x + te i ) − f (x) t = Df (x)[e i ]. Обратите внимание, что функция может быть недифференцируемой, даже если у неё существуют производные по всем направлениям. Пример A.8. Рассмотрим функцию f (x) = kxk 2 . Найдём её производную по направлению h в точке x = 0: ∂kxk 2 ∂h x=0 = lim t→+0 k0 + thk 2 − k0k 2 t = lim t→+0 tkhk 2 t = khk 2 Если бы функция f (x) = kxk 2 была дифференцируема в нуле, то по утверждению 2: Df (0)[h] = ∂f (0) ∂h = khk 2 , но функция khk 2 не является линейной, что противоречит тому, что производная — линейный оператор. Значит kxk 2 не дифференцируема в нуле, хотя и имеет производные вдоль всех направлений. Градиент функции, матрица Якоби. • В случае U = R n , V = R линейную функцию Df (x)[h] всегда можно представить с помощью скалярного произведения с некоторым вектором: Df (x)[h] = ha x , hi где a x ∈ R n — разный для каждого x. Вектор a x называется градиентом функции f в точке x и обозначается ∇f (x). В стандартном базисе градиент функции представляется в виде вектора из частных производных: ∇f (x) = ∂f ∂x 1 (x), . . . , ∂f ∂x n (x) ! ∈ R n Как и все векторы у нас, этот вектор — вектор-столбец. 14 • В случае U = R n×m , V = R линейную функцию df (x)[H] всегда можно представить с помощью скалярного произведения с некоторой матрицей: df (x)[H] = hA x , Hi, A x , H ∈ R n×m Эта матрица также называется градиентом функции в точке x: ∇f (x) = A x и в стандартном базисе (из матриц, у которых все нули, кроме одной единички) записывается в виде матрицы частных производных: ∇f (x) = ∂f ∂x ij (x) ! n,m i=1,j=1 • В случае U = R m , V = R n , линейный оператор df (x)[·], зафиксировав базисы, всегда можно представить матрицей: Df (x)[h] = J x h, J x ∈ R n×m Матрица J x называется матрицей Якоби функции f . В стандартном базисе она состоит из част- ных производных: J x = ∂f i ∂x j (x) ! n,m i=1,j=1 Утверждение A.9 (Дифференциальное исчисление). Пусть U и V — векторные пространства, X — подмножество U , x ∈ X — внутренняя точка X. Справедливы следующие свойства: (a) (Производная константы) Пусть f : X → V — постоянная функция, т. е. найдется v ∈ V , что f (x 0 ) = v для всех x 0 ∈ X. Тогда f дифференцируема в точке x, и df (x) = 0. (b) (Производная тождественной функции) Пусть f : X → V — тождественная функция, т. е. f (x 0 ) = x 0 для всех x 0 ∈ X. Тогда f дифференцируема в точке x, и ее производная — также тождественная функция: Df (x)[h] = h для всех h ∈ U . (c) (Линейность) Пусть f : X → V и g : X → V — функции. Если f и g дифференцируемы в точке x, а c 1 , c 2 ∈ R — числа, то функция (c 1 f + c 2 g) также дифференцируема в точке x, и d(c 1 f + c 2 g)(x) = c 1 df (x) + c 2 dg(x). (d) (Правило произведения) Пусть α : X → R и f : X → V — функции. Если α и f дифференцируемы в точке x, то функция αf также дифференцируема в точке x, и D(αf )(x)[h] = (Dα(x)[h])f (x) + α(x)(Df (x)[h]) для всех h ∈ U . (e) (Правило композиции) Пусть Y — подмножество V , f : X → Y — функция. Также пусть W — векторное пространство, g : Y → W — функция. Если f дифференцируема в точке x, и g дифференцируема в точке f (x), то их композиция (g ◦ f ) : X → W (определенная как (g ◦ f )(x) = g(f (x))) также будет дифференцируема в точке x, и D(g◦f )(x) = Dg(f (x)) h df (x) i или, более подробно, D(g◦f )(x)[h] = Dg(f (x)) h Df (x)[h] i (f ) (Правило частного) Пусть α : X → R и f : X → V — функции. Если α и f дифференцируемы в точке x, и если α не обращается в ноль на X, то функция (1/α)f также дифференцируема в точке x, и D 1 α f (x)[h] = α(x)(Df (x)[h]) − (Dα(x)[h])f (x) α(x) 2 для всех h ∈ U . 15 Доказательство. Первые четыре свойства доказываются по определению, а последнее выводится из правил произведения и композиции. Заметим, что правило произведения в утверждении A.9 установлено только в случае, когда одна из функций является скалярной. Это понятно, поскольку в векторных пространствах определено лишь умножение на скаляр, а не на произвольный элемент векторного пространства. Тем не менее, в неко- торых частных случаях правило произведения остается верным даже если обе функции являются не скалярными. Например, справедливо следующее утверждение. Утверждение A.10. Пусть U — векторное пространство, X — подмножество U , x ∈ X — внут- ренняя точка X. Пусть f : X → R m×n и g : X → R n×k — матрично-значные функции. Предположим, что f и g дифференцируемы в точке x. Тогда функция f g также дифференцируема в точке x, и D(f g)(x)[h] = (Df (x)[h])g(x) + f (x)(Dg(x)[h]). для всех h ∈ U . (Здесь под операцией умножения подразумевается матричное умножение, поэтому порядок множителей имеет значение.) A.2 Вторая производная Пусть функция f : X → V дифференцируема в каждой точке x ∈ X ⊆ U . Рассмотрим производную функции f при фиксированном приращении h 1 ∈ U как функцию от x: g(x) = Df (x)[h 1 ]. Определение A.11. Если для функции g в некоторой точке x существует производная, то она назы- вается второй производной функции f в точке x: D 2 f (x)[h 1 , h 2 ] := Dg(x)[h 2 ]. Можно показать, что D 2 f (x)[h 1 , h 2 ] является билинейной функцией по h 1 и h 2 По аналогии определяются третья: D 3 f (x)[h 1 , h 2 , h 3 ], четвёртая и производные более высоких по- рядков. Если производная df (x) является непрерывной функцией по x, то говорят, что f — непрерывно дифференцируема. Если вторая производная D 2 f (x) непрерывна по x, то тогда f — дважды непрерывно дифференцируема. Для функций f : R n → R вторую производную, как и любую билинейную форму, можно предста- вить с помощью матрицы: D 2 f (x)[h 1 , h 2 ] = hH x h 1 , h 2 i, H x ∈ R n×n Матрица H x называется гессианом функции f в точке x и обозначается обычно ∇ 2 f (x). В стан- дартном базисе эта матрица состоит из вторых частных производных: ∇ 2 f (x) = ∂ 2 f ∂x i ∂x j (x) ! n,n i=1,j=1 Для дважды непрерывно дифференцируемой функции её гессиан — симметричная матрица: ∇ 2 f (x) ∈ S n 16 A.3 Формула Тейлора Для дважды непрерывно-дифференцируемой функции справедлива формула Тейлора: f (x + h) = f (x) + Df (x)[h] + 1 2 D 2 f (x)[h, h] + o(khk 2 ). Для функции f : R n → R её можно записать, используя градиент и гессиан: f (x + h) = f (x) + h∇f (x), hi + 1 2 h∇ 2 f (x)h, hi + o(khk 2 ). Если функция имеет непрерывные производные до порядка k включительно, то формулу Тейлора можно записать до k-ой производной: f (x + h) = f (x) + Df (x)[h] + 1 2! D 2 f (x)[h, h] + 1 3! D 3 f (x)[h, h, h] + · · · + 1 k! D k f (x)[h, . . . , h] + o(khk k ). A.4 Подсчет табличных производных Замечание: всюду в дальнейшем k · k обозначает (для краткости) евклидову норму для векторов и спектральную (операторную) норму для матриц. Пример A.12 (Линейная функция). Пусть c ∈ R n , и пусть f : R n → R — функция f(x) := hc, xi. Покажем, что f является дифференцируемой в произвольной точке x ∈ R n и найдем ее производную df (x) : R n → R. Для этого зафиксируем произвольное приращение аргумента h ∈ R n и вычислим соответствующее приращение функции: f (x + h) − f (x) = hc, x + hi − hc, xi = hc, hi. Заметим, что отображение h 7→ hc, hi является линейным. Значит, для функции f справедливо разложе- ние (A.1) с Df (x)[h] := hc, hi. Таким образом, функция f является дифференцируемой в произвольной точке x ∈ R n с производной Df (x)[h] = hc, hi. Пример A.13 (Квадратичная форма). Пусть A ∈ R n×n , и пусть f : R n → R — функция f(x) := hAx, xi. Зафиксируем произвольную точку x ∈ R n и произвольное приращение аргумента h ∈ R n и вычислим соответствующее приращение функции: f (x + h) − f (x) = hA(x + h), x + hi − hAx, xi = h(A + A T )x, hi + hAh, hi. Заметим, что отображение h 7→ h(A + A T )x, hi является линейным, а hAh, hi = o(khk), поскольку для всех h ∈ R n справедлива следующая цепочка неравентв: |hAh, hi| ≤ khkkAhk ≤ kAkkhk 2 Здесь первое неравенство следует из неравенства Коши-Буняковского; второе неравенство следует из согласованности матричной и векторной норм. Таким образом, функция f дифференцируема в произ- вольной точке x ∈ R n с производной Df (x)[h] = h(A + A T )x, hi. Пример A.14 (Обратная матрица). Пусть S := {X ∈ R n×n : Det(X) 6= 0} — множество всех квад- ратных невырожденных матриц размера n. Рассмотрим функцию f : S → S, которая для каждой матрицы X ∈ S возвращает ее обратную: f (X) := X −1 . Покажем, что f является дифференцируемой в любой точке X ∈ S. Для этого зафиксируем произвольное достаточно малое приращение аргумента H ∈ R n×n (удовлетворяющее X +H ∈ S и kHk < 1/kX −1 k) и рассмотрим соответствующее приращение функции: f (X + H) − f (X) = (X + H) −1 − X −1 = (X(I n + X −1 H)) −1 − X −1 = ((I n + X −1 H) −1 − I n )X −1 17 Оценим отдельно (I n + X −1 H) −1 . Для этого разложим эту матрицу в ряд Неймана: 2 (I n + X −1 H) −1 = I n − X −1 H + ∞ X k=2 (−X −1 H) k Заметим, что ряд, стоящий в правой части последнего равенства, является абсолютно сходящимся, поскольку kX −1 Hk < 1 в силу достаточной малости H. Покажем, что сумма этого ряда есть o(kHk): ∞ X k=2 (−X −1 H) k ≤ ∞ X k=2 k(−X −1 H) k k ≤ ∞ X k=2 kX −1 k k kHk k = kX −1 k 2 kHk 2 1 − kX −1 k · kHk Здесь первое неравенство следует из неравенства треугольника для нормы; второе неравенство следует из субмультипликативности нормы; далее вычисляется сумма геометрического ряда. Таким образом, (I n + X −1 H) −1 = I n − X −1 H + o(kHk). Подставляя это выражение в полученную выше формулу для приращения функции, получаем f (X + H) − f (X) = −X −1 HX −1 + o(kHk). Таким образом, функция f дифференцируема в произвольной точке X ∈ S с производной df (X)[H] = −X −1 HX −1 Замечание A.15. Выведенную формулу для производной функции X −1 можно очень просто полу- чить с помощью следующего трюка. Рассмотрим дифференциал единичной матрицы d(I n ). С одной стороны, поскольку матрица постоянная, d(I n ) = 0. С другой стороны, по правилу произведения, dI n = d XX −1 = (dX)X −1 + Xd(X −1 ). Приравняв выражения, получим d(X −1 ) = −X −1 (dX)X −1 , или, в другой форме, d(X −1 )[H] = −X −1 HX −1 . Заметим, однако, что приведённое рассуждение не является полным доказательством тождества, так как предполагает, но не доказывает существование дифференциала d(X −1 ). Пример A.16 (Определитель матрицы). Пусть f : R n×n → R — функция f(X) := Det(X). Рассмотрим произвольную точку X ∈ R n×n и произвольное приращение аргумента H ∈ R n×n . Будем предполагать, что матрица X обратима. Выпишем соответветствующее приращение функции: f (X +H)−f (X) = Det(X +H)−Det(X) = Det(X(I n +X −1 H))−Det(X) = Det(X)(Det(I n +X −1 H)−1). Оценим отдельно Det(I n + X −1 H). Для этого воспользуемся тем, что определитель матрицы равен произведению ее собственных значений. Пусть λ 1 (X −1 H), . . . , λ n (X −1 H) — собственные значения мат- рицы X −1 H (пронумерованные в произвольном порядке и, возможно, комплексные). Заметим, что собственными значениями матрицы I n + X −1 H будут 1 + λ 1 (X −1 H), . . . , 1 + λ n (X −1 H). Поэтому Det(I n + X −1 H) = n Y i=1 [1 + λ i (X −1 H)] = 1 + n X i=1 λ i (X −1 H) + X 1≤i≤j≤n λ i (X −1 H)λ j (X −1 H) + . . . , где многоточие скрывает сумму всевозможных троек λ i (X −1 H)λ j (X −1 H)λ k (X −1 H), всевозможных четверок и т. д. Заметим, что выражение, стоящее скобках, представляет из себя величину o(kHk). Это следует из неравенства треугольника и того факта, что для произвольной матрицы A ∈ R n×n все 2 Имеется в виду разложение (I n − A) −1 = ∞ P k=0 A k , справедливое для любой матрицы A ∈ R n×n , такой, что kAk < 1. Эта формула является обобщением известной формулы для суммы геометрического ряда: (1 − q) −1 = ∞ P k=0 q k для любого |q| < 1. 18 ее собственные значения не превосходят по модулю ее нормы kAk. (Действительно, пусть λ ∈ C — собственное значение матрицы A, и пусть x ∈ C n \ {0} — соответствующий собственный вектор: Ax = λx. Тогда |λ|kxk = kAxk ≤ kAkkxk.) Таким образом, Det(I n − X −1 H) = 1 + n X i=1 λ i (X −1 H) + o(kHk) = 1 + Tr(X −1 H) + o(kHk). Подставляя полученное выражение в полученную выше формулу для приращения функции, получаем f (X + H) − f (X) = Det(X) Tr(X −1 H) + o(kHk). Таким образом, для любой обратимой матрицы X ∈ R n×n функция f дифференцируема в точке X с производной df (x)[H] = Det(X) Tr(X −1 H) = Det(X)hX −T , Hi. Замечание A.17. Можно показать, что рассматриваемая функция f (X) = Det(X) будет диффе- ренцируемой всюду на R n×n , а не только на подмножестве обратимых матриц. Общая формула для производной в этом случае называется формулой Якоби и выглядит следующим образом: df (X)[H] = Tr(Adj(X)H), где Adj(X) — присоединенная матрица к X. Заметим, что если X — невырожденная матрица, тогда Adj(X) = Det(X)X −1 и формула Якоби переходит в доказанную формулу df (X)[H] = Det(X) Tr(X −1 H). 19 |