назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [ 79 ] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


79

Определение. Гессианом функции /(jci,...,x„), называется матрица размером пхп, на пересечении /-й строки и у-го столбца которой находится значение соответствующей смешанной производной второго порядка в точке X =, а именно:

dxdxj

Эта матрица обозначается как H(xi,..,,x).

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

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

Теорема. Пусть функция/х), х = (х][,...,х) есть функция, определенная на некотором множестве S и имеющая на этом множестве непрерывные частные производные второго порядка. Тогда Дх) есть выпуклая функция на множестве S тогда и только тогда, когда все главные миноры Гессиана функцииДх) неотрицательны во всех точках множества S.

Теорема. Пусть функция/х), x = (xi,...,x) есть функция, определенная на некотором множестве S и имеющая на этом множестве непрерывные частные производные второго порядка. Тогда/х) есть вогнутая функция на множестве S тогда и только тогда, когда знак любого главного минора -го порядка Гессиана функции /х) совпадает со знаком выражения (-1) во всех точках множества 5.

Рассмотрим некоторые примеры применения данных теорем.

Пример. Докажите, что функция

/(Х1,х2,хз) = х + х + 2X3 -12 -23 ~13

является выпуклой функцией на всей области определения. Решение.

Построим Гессиан данной функции

(Ь2з) =

2 -1 -1 -1 2 -1 -1 -1 4



Вычислим все главные миноры данной матрицы. Первоначально рассмотрим главные миноры первого порядка. После удаления рядов (и столбцов) 1 и 2 остается один единственный элемент 4 > 0. После удаления рядов (и столбцов) 1 и 3 остается один единственный элемент 2 > 0. После удаления рядов (и столбцов) 2 и 3 остается один единственный элемент 2 > 0.

Вычислим все главные миноры второго порядка.

Удаляя строку 1 и столбец 1, получаем

2 -1 -1 4

= 7 >0.

Удаляя строку 2 и столбец 2, получаем

2 -1

-1 4

= 7 >0.

Удаляя строку 3 и столбец 3, получаем

2 -1

-1 2

= 3 >0.

Вычислим главные миноры третьего порядка. Таковым единственным минором является сам Гессиан. Вычислим его определитель путем разложения по первой строке, а именно:

2.(2-4-(Ч).(-1))-(-1)-((-1)-4-(-1).(-1)) + + (-1).((-1)-(~1)-(-1)-2) = 6>0.

Поскольку все главные миноры Гессиана являются неотрицательными на всей области определения функции, функция /(х1,л:2,хз) , согласно приведенному критерию, является выпуклой.

2 2

Пример. Докажите, что функция f{x\,X2)~-x\ -2x2 "12 является вогнутой функцией на всей области определения.

Решение. Как легко заметить, главные миноры первого порядка имеют значения (совпадающие со значениями диагональных элементов) -2 и -4, т.е. являются отрицательными.

Единственным главным минором второго порядка является сама матрица. Ее определитель равен (-2) • (-4) - (~1) • (-1) = 7 > 0.

Поэтому согласно вышеприведенному критерию, функция f(xi,X2) является вогнутой на всей области определения.



Заметим, что для случая функции одной переменной приведенные теоремы принимают следующий вид.

Теорема. Пусть функция J{x) имеет вторую производную во всех точках некоторого выпуклого множества S, Тогда функция/х) является выпуклой функцией на множестве S тогда и только тогда, когда / (х) > О для всех точек х множества S.

Теорема. Пусть функция/х) имеет вторую производную во всех точках некоторого выпуклого множества S, Тогда функция Дх) является вогнутой функцией на множестве S тогда и только тогда, когда / (х) < О для всех точек х множества S.

Основная идея градиентного метода состоит в замене максимизируемой (минимизируемой) функции в окрестности конкретной точки ее линейным приближением.

В методе наискорейшего спуска длина шага выбирается из условия минимизации функции вдоль направления антиградиента.

9.3. Градиентный метод

Данный метод применим для задач безусловной оптимизации. В общем виде такая задача может быть записана как max (min) /(xj,х„),

x = (xi,...,x„)g7?.

Основная идея метода состоит в замене максимизируемой (минимизируемой) функции в окрестности конкретной точки ее линейным приближением, получаемым из разложения данной функции в ряд Тейлора в данной точке.

Общая схема метода состоит в построении последовательности приближений х,х\...,х" исходя из соотношения

x=xЧaЛ

где h - направление убывания функции/х) вдоль h .

В градиентном методе h берется равным антиградиенту функции /х) в точке х, а именно = -/ (х). Что касается выбора длины шага

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

Опишем коротко еще один способ выбора параметров градиентного метода, называемый дроблением шага. Выбираются некоторые кон-246

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [ 79 ] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]