ВУЗ:
Составители:
Рубрика:
8
Из предположения теоремы [∇f(x)−∇f(x
1
)]
T
(x−x
1
), то есть (1 − λ)[∇f(x)−∇f(x
1
)]
T
(x
2
−x
1
) ≥ 0.
Отсюда ∇f
T
(x)(x
2
− x
1
) ≥∇f
T
(x
1
)(x
2
− x
1
). Тогда из (∗) имеем, что
f(x
2
) ≥ f (x
1
)+∇f
T
(x
1
)(x
2
− x
1
)
Тогда f(x) по предыдущей теореме выпукла.
Эти теоремы дают необходимы и достаточные условия выпуклости дифференцируемой функ-
ции. Однако с вычислительной точки зрения проверка этих условий сложна. Просто и легко про-
веряемое, по крайней мере для квадратичных функций, условие может быть получено дважды
дифференцируемой функцией.
Теорема. Пусть M — непустое открытое выпуклое множество в R
n
, f(x) — дважды дифферен-
цируемая на M функция. Для того, чтобы функция f(x) была выпуклой, необходимо и достаточно,
чтобы матрица Гессе была неотрицательно-определенной в каждой точке M.
Для вогнутости f(x) на M требуется неположительная определенность матрицы вторых про-
изводных. Эта теорема широко используется при проверке на выпуклость или вогнутость дважды
дифференцируемых функций. В частности, если f(x) — квадратичная функция, то матрица Гессе
не зависит от точки, в которой она вычисляется. Следовательно, проверка на выпуклость сводится
к проверке неотрицательной определенности матрицы или, что то же самое, на неотрицательность
ее собственных значений.
Пример. Пусть f(x
1
,x
2
)=2x
1
+6x
2
− 2x
2
1
− 3x
2
2
+4x
1
x
2
. Матрица Гессе равна
H =
−44
4 −6
Находим ее собственное значение, решая уравнение
det(H − λI)=
−4 − λ 4
4 −6 − λ
= λ
2
+10λ +8=0
λ
1
= −5+
√
17 < 0,λ
2
= −5 −
√
17 ≤ 0
f(x) — вогнутая функция.
При использовании теоремы студенту необходимо вспомнить известные из алгебры критерии
знакоопределенности и полуопределенности матриц. Пусть имеется знакосимметричная матрица
A =
a
11
a
12
... a
1n
a
21
a
22
... a
2n
... ... ...
a
n1
a
n2
... a
nn
Критерий положительной определенности матрицы (критерий Сильвестра).
Для того, чтобы матрица была положительно определенной (то есть для любых x =0выполня-
лось соотношение (Ax, x) > 0) необходимо и достаточно, чтобы все угловые миноры этой матрицы
были строго положительны:
1
= a
11
> 0,
2
=
a
11
a
12
a
21
a
22
> 0, ...,
n
= det A>0
Поскольку любой главный минор (то есть минор, построенный на элементах, стоящих на пересече-
нии строк и столбцов с одинаковыми номерами) матрицы A может при соответствующей перену-
мерации переменных помещен в левый верхний угол, то имеет место следствие.
Следствие. У положительно определенной матрицы не только угловые, но и все главные миноры
строго положительны.
Критерий неотрицательной определенной матрицы: Для того, чтобы матрица A была
неотрицательно-определена (то есть для любых x ∈ R
n
выполнялось соотношение (Ax, x) ≥ 0)
необходимо и достаточно, чтобы все ее главные миноры были неотрицательны.
8
Из предположения теоремы [∇f (x)−∇f (x1 )]T (x−x1 ), то есть (1 − λ)[∇f (x)−∇f (x1 )]T (x2 −x1 ) ≥ 0.
Отсюда ∇f T (x)(x2 − x1 ) ≥ ∇f T (x1 )(x2 − x1 ). Тогда из (∗) имеем, что
f (x2 ) ≥ f (x1 ) + ∇fT (x1 )(x2 − x1 )
Тогда f (x) по предыдущей теореме выпукла.
Эти теоремы дают необходимы и достаточные условия выпуклости дифференцируемой функ-
ции. Однако с вычислительной точки зрения проверка этих условий сложна. Просто и легко про-
веряемое, по крайней мере для квадратичных функций, условие может быть получено дважды
дифференцируемой функцией.
Теорема. Пусть M — непустое открытое выпуклое множество в Rn , f (x) — дважды дифферен-
цируемая на M функция. Для того, чтобы функция f (x) была выпуклой, необходимо и достаточно,
чтобы матрица Гессе была неотрицательно-определенной в каждой точке M .
Для вогнутости f (x) на M требуется неположительная определенность матрицы вторых про-
изводных. Эта теорема широко используется при проверке на выпуклость или вогнутость дважды
дифференцируемых функций. В частности, если f (x) — квадратичная функция, то матрица Гессе
не зависит от точки, в которой она вычисляется. Следовательно, проверка на выпуклость сводится
к проверке неотрицательной определенности матрицы или, что то же самое, на неотрицательность
ее собственных значений.
Пример. Пусть f (x1 , x2 ) = 2x1 + 6x2 − 2x21 − 3x22 + 4x1 x2 . Матрица Гессе равна
−4 4
H=
4 −6
Находим ее собственное значение, решая уравнение
−4 − λ 4
det(H − λI) =
= λ2 + 10λ + 8 = 0
4 −6 − λ
√ √
λ1 = −5 + 17 < 0, λ2 = −5 − 17 ≤ 0
f (x) — вогнутая функция.
При использовании теоремы студенту необходимо вспомнить известные из алгебры критерии
знакоопределенности и полуопределенности матриц. Пусть имеется знакосимметричная матрица
a11 a12 . . . a1n
a21 a22 . . . a2n
A= ... ...
...
an1 an2 . . . ann
Критерий положительной определенности матрицы (критерий Сильвестра).
Для того, чтобы матрица была положительно определенной (то есть для любых x = 0 выполня-
лось соотношение (Ax, x) > 0) необходимо и достаточно, чтобы все угловые миноры этой матрицы
были строго положительны:
a11 a12
1 = a11 > 0,
2 =
> 0, . . . , n = det A > 0
a21 a22
Поскольку любой главный минор (то есть минор, построенный на элементах, стоящих на пересече-
нии строк и столбцов с одинаковыми номерами) матрицы A может при соответствующей перену-
мерации переменных помещен в левый верхний угол, то имеет место следствие.
Следствие. У положительно определенной матрицы не только угловые, но и все главные миноры
строго положительны.
Критерий неотрицательной определенной матрицы: Для того, чтобы матрица A была
неотрицательно-определена (то есть для любых x ∈ Rn выполнялось соотношение (Ax, x) ≥ 0)
необходимо и достаточно, чтобы все ее главные миноры были неотрицательны.
