Выпуклость и гессиан

Гессиан

Для скалярных функций R→R\RR \to \RR показателем выпуклости и скорости роста служила вторая производная. Этот показатель легко обобщается на случай функций многих переменных Rn→R\RR^n \to \RR. Однако у многомерных функций, переменные могут убывать или возрастать по разным направлениям, поэтому для полноценного анализа нам нужно рассмотреть вторые частные производные всех комбинаций переменных, для этого в математике используется гессиан

Гессиан

Пусть f ⁣:Rn→Rf \colon \RR^n \to \RR — функция nn переменных.

Гессиан функции ff — матрица её вторых частных производных

H⁡f   ⁣=def   ⁣(∂2f∂x12∂2f∂x1 ∂x2⋯∂2f∂x1 ∂xn∂2f∂x2 ∂x1∂2f∂x22⋯∂2f∂x2 ∂xn⋮⋮⋱⋮∂2f∂xn ∂x1∂2f∂xn ∂x2⋯∂2f∂xn2 )\hess f \defeq \pmatrix{ \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1 \, \partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1 \, \partial x_n}\\[0.8em]\dfrac{\partial^2 f}{\partial x_2 \, \partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2 \, \partial x_n}\\[0.8em]\vdots & \vdots & \ddots & \vdots\\[0.8em]\dfrac{\partial^2 f}{\partial x_n \, \partial x_1} & \dfrac{\partial^2 f}{\partial x_n \, \partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \ }

Симметрия

Давайте воспользуемся данным определением и посчитаем гессиан для функции f(x,y,z)=x2+y2zf(x, y, z) = x^2 + y^2z, выглядит он следующим образом:

H⁡f=( 200 02z2y 02y0)\hess f = \pmatrix{ \, 2 & 0 & 0\\[0.8em]\, 0 & 2z & 2y\\[0.8em]\, 0 & 2y & 0\\[0.8em]}

Как можно заметить, перед нами симметричная матрица и почти всегда она будет получаться именно такой, в чём мы сейчас удостоверимся.

Итак, если у нашей функции все производные второго порядка являются непрерывными на некотором пространстве DD, то на этом пространстве по теореме Шварца будет выполнятся следующее свойство:

∂∂x(∂f∂y)=∂∂y(∂f∂x)∂∂x(∂f∂z)=∂∂z(∂f∂x)∂∂z(∂f∂y)=∂∂y(∂f∂z)\frac{\partial}{\partial x} \left( \frac{\partial f}{\partial y} \right) = \frac{\partial}{\partial y} \left( \frac{\partial f}{\partial x} \right)\\[0.8em]\frac{\partial}{\partial x} \left( \frac{\partial f}{\partial z} \right) = \frac{\partial}{\partial z} \left( \frac{\partial f}{\partial x} \right)\\[0.8em]\frac{\partial}{\partial z} \left( \frac{\partial f}{\partial y} \right) = \frac{\partial}{\partial y} \left( \frac{\partial f}{\partial z} \right)
А это в свою очередь значит, что мы можем транспонировать гессиан сколько угодно раз, при этом его не меняя.

Квадратичная форма

Ещё одно интересное свойство гессиана связанное с его симметрией заключается в том, что его можно представить в виде квадратичной формы

Пусть f ⁣:Rn→Rf \colon \RR^n \to \RR дважды непрерывно дифференцируема, x0∈Rnx_0 \in \RR^n. Рассмотрим приращение

Δx=x−x0\Delta x = x - x_0
Тогда разложение Тейлора второго порядка в окрестности точки x0x_0 имеет вид
f(x0+Δx)=f(x0)+∇f(x0)⋅Δx+12ΔxTH⁡(x0)Δx+o(∥Δx∥2)f(x_0 + \Delta x) = f(x_0) + \nabla f(x_0) \cdot \Delta x + \frac{1}{2} \Delta x^{\T} \hess(x_0) \Delta x + o \bigl( {\| \Delta x \|}^2 \bigr)
где H⁡(x0)=∇2f(x0)\hess(x_0) = \nabla^2 f(x_0) — гессиан в точке x0x_0. Выделим квадратичную форму
Q(Δx)=ΔxTH⁡(x0)ΔxQ(\Delta x) = \Delta x^{\T} \hess(x_0) \Delta x
В стационарной точке ∇f(x0)=0\nabla f(x_0) = 0 разложение упрощается до
f(x0+Δx)=f(x0)+12Q(Δx)+o(∥Δx∥2))f(x_0 + \Delta x) = f(x_0) + \frac{1}{2} Q(\Delta x) + o \bigl( {\| \Delta x \|}^2 \bigr))
и знак Q(Δx)Q(\Delta x) для малых Δx\Delta x определяет, растёт ли функция, убывает или ведёт себя по-разному в разных направлениях.

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

Экстремумы

Локальные безусловные экстремумы

Итак, что же из себя представляет экстремум многомерной функции? Из функций одной переменной мы помним что он фактически показывает точки "перегиба", однако в многомерном пространстве график может выгибаться во нескольких направлениях сразу, что значительно усложняет работу с экстремумами. Сейчас мы научимся анализировать такие точки, но для начала рассмотрим их определение

Локальный безусловный экстремум

Пусть f ⁣:D⊂Rn→Rf \colon D \subset \RR^n \to \RR — функция nn переменных, и пусть задана точка a∈dom⁡fa \in \dom f.

Точка aa называется точкой локального максимума функции ff, если

∃ δ>0∀ x∈U(a,δ)∩dom⁡ff(x)⩽f(a)\exists\, \delta > 0 \quad \forall\, x \in \U(a, \delta) \sect \dom f \? f(x) \le f(a)

Другими словами, точка aa называется точкой локального максимума функции ff, если в какой-то окрестности точки aa значение функции не больше значения функции в самой точке aa.

Точка aa называется точкой локального минимума функции ff, если

∃ δ>0∀ x∈U(a,δ)∩dom⁡ff(x)⩾f(a)\exists\, \delta > 0 \quad \forall\, x \in \U(a, \delta) \sect \dom f \? f(x) \ge f(a)

Другими словами, точка aa называется точкой локального минимума функции ff, если в какой-то окрестности точки aa значение функции не меньше значения функции в самой точке aa.

Точка aa называется точкой локального экстремума функции ff, если она является точкой локального максимума или локального минимума.

Как находить подобные точки у функции мы узнали ранее изучая градиент и теорему Ферма.

Теорема Ферма

Если функция ff дифференцируема в точке aa и эта точка aa является точкой локального экстремума функции ff, то

∇f(a)=0\nabla f (a) = \0

Предположим, что в точке aa, которая является точкой экстремума, градиент функции ff не нулевой: ∇f(a)≠0\nabla f (a) \neq \0.

Рассмотрим направление v=−∇f(a)/∥∇f(a)∥v = - \nabla f (a) / \| \nabla f (a) \|. Производная по этому направлению

∂f(a)∂v=∇f(a)⋅v=∇f(a)⋅(−∇f(a)∥∇f(a)∥)=−∥∇f(a)∥<0\frac{\partial f (a)}{\partial v} = \nabla f (a) \cdot v = \nabla f (a) \cdot \left( - \frac{\nabla f (a)}{\| \nabla f (a) \|} \right) = - \| \nabla f (a) \| < 0

Из этого равенства для производной по направлению vv получаем, что по направлению vv функция убывает, а по направлению −v-v функция возрастает. А значит, в любой окрестности точки aa есть точки, где функция принимает как большие, так и меньшие значения. Получаем противоречие.

Если функция ff дифференцируема в точке aa, и ∇f(a)=0\nabla f (a) = \0, то эта точка aa называется стационарной точкой функции ff. Не всякая стационарная точка является точкой экстремума, но всякая точка экстремума является стационарной точкой по теореме Ферма. Отсюда следует, что для того чтобы точка являлась точкой экстремума, необходимо, однако не достаточно того чтобы градиент в ней был равен нулю, это так называемое необходимое условие для экстремальных точек.

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

А теперь вспомним одно важное правило для симметричных матриц, а именно критерий Сильвестра, который показывает как знакоопределена матрица.

Критерий Сильвестра

Пусть у нас есть некоторая симметричная матрица Mn×nM^{n \times n}, а Δk=det⁡Mk\Delta_k = \det M_k — главные миноры порядка kk для этой матрицы. Тогда относительно неё будет выполнятся следующее:

M≻0  ⟺  ∀ Δk>0∀ k∈{1,2,…n}M \succ 0 \iff \forall\, \Delta_k > 0 \quad \forall\, k \in \{1, 2, \dotsc n \} — матрица определена положительно M≺0  ⟺  ∀ (−1)kΔk>0∀ k∈{1,2,…n}M \prec 0 \iff \forall\, (-1)^k \Delta_k > 0 \quad \forall\, k \in \{1, 2, \dotsc n \} — матрица определена отрицательно

Во всех иных случаях матрица считается не строго определённой, но стоит выделить случаи когда матрица может быть определена не строго положительно или не строго отрицательно. Тогда Δk≥0\Delta_k \geq 0 или (−1)kΔk≥0(-1)^k \Delta_k \geq 0 и при этом, хотя бы один из Δk\Delta_k равен нулю. Запись выглядит соответственно M⪰0M \succeq 0 и M⪯0M \preceq 0

Теперь, благодаря этому самому критерию, мы можем узнать знакоопределённость гессиана, и сделать из этого следующие выводы:

  1. H⁡f(x)≻0\hess_f(x) \succ 0 в точке экстремума, значит точка является локальным максимумом.
  2. H⁡f(x)⪰0\hess_f(x) \succeq 0 в точке экстремума, значит точка может являться локальным максимумом, однако по некоторым направлениям она плоская, из-за чего не возможно однозначно сказать что это точки максимума.
  3. H⁡f(x)≺0\hess_f(x) \prec 0 в точке экстремума, значит точка является локальным минимумом.
  4. H⁡f(x)⪯0\hess_f(x) \preceq 0 в точке экстремума, значит точка может являться локальным минимумом, однако по некоторым направлениям она плоская, из-за чего не возможно однозначно сказать что это точки минимума.
  5. H⁡f(x)=0\hess_f(x) = 0 в точке экстремума, значит экстремум является седловой точкой, то есть такой точкой в которой по одним направлениям функция возрастает, а по другим убывает из-за чего в окрестности такой точки график напоминает седло.

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

Теперь решим простой пример для закрепления изученного инструментария

Возьмём какую-нибудь f(x,y)=−x2−4yf(x, y) = -x^2 -4 y Сначала найдем градиент и определим точки в которых он равен нулю, ∇f(x,y)=(−2x,−8y)=0\nabla f(x, y) = (-2x, -8y) = 0 значит x,y=0,0x, y = 0, 0, единственная стационарная точка.

Гессиан:

H⁡f=(−200−8)\hess_f = \pmatrix{ -2 & 0 \\ 0 & -8 }
Главные миноры: Δ1=−2<0,Δ2=det⁡H⁡f=16>0\Delta_1 = -2 < 0, \quad \Delta_2 = \det \hess_f = 16 > 0. По критерию Сильвестра матрица H⁡f\hess_f отрицательно определена. Отрицательно определённый гессиан в стационарной точке означает, что (0,0)(0, 0) является точкой локального максимума функции ff.

Локальные условные экстремумы

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

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

Но прежде чем что-либо искать нам необходимо обзавестись соответствующим инструментарием для поиска. Чаще всего используется метод множителей Лагранжа.

Сначала представим метод на примере одной функции-ограничения, а после обобщим до mm функций связи.

Итак, первый шаг в решении задачи этим методом — составление функции Лагранжа (Лагранжиана). Назовём нашу функцию-ограничение g(x,y)g(x, y), тогда составим функцию Лагранжа относительно нашей основной функции f(x,y)f(x, y) и функции связи g(x,y)g(x, y)

L(x,y)=f(x,y)+λg(x,y)L(x, y) = f(x, y) + \lambda g(x, y)
Где параметр λ\lambda — множитель Лагранжа. Тогда стационарные точки можно получить из следующей системы уравнений:
{∂L∂x=0∂L∂y=0g(x,y)=0\left\{ \begin{aligned} \frac{\partial L} {\partial x} = 0 \\ \frac{\partial L} {\partial y} = 0 \\ g(x, y) = 0 \\ \end{aligned} \right.

Теперь попробуем решить простой пример при помощи полученных знаний. Наша задача найти условные экстремумы функции f(x,y)=xyf(x, y) = xy при ограничении g(x,y)=x2+y2−1=0g(x, y) = x^2 + y^2 - 1 = 0.

Составим функцию Лагранжа:

L(x,y,λ)=f(x,y)+λg(x,y)=xy+λ(x2+y2−1)L(x, y, \lambda) = f(x, y) + \lambda g(x, y) = xy + \lambda (x^2 + y^2 - 1)
Найдём частные производные:
∂L∂x=y+2λx∂L∂y=x+2λy∂L∂λ=x2+y2−1\frac{\partial L}{\partial x} = y + 2\lambda x\\[0.8em]\frac{\partial L}{\partial y} = x + 2\lambda y\\[0.8em]\frac{\partial L}{\partial \lambda} = x^2 + y^2 - 1
Стационарные точки Лагранжиана (и, значит, кандидаты на условный экстремум) удовлетворяют системе
{y+2λx=0,x+2λy=0,x2+y2−1=0\left\{ \begin{aligned} y + 2\lambda x &= 0,\\[0.8em]x + 2\lambda y &= 0,\\[0.8em]x^2 + y^2 - 1 &= 0 \end{aligned} \right.
Решив эту систему получим четыре возможных точки:
x={−12;y=−12}x={−12;y=12}x={12;y=−12}x={12;y=12}x = \{ - \frac{1}{\sqrt 2} ; \quad y = - \frac{1}{\sqrt 2} \}\\[0.8em]x = \{ - \frac{1}{\sqrt 2} ; \quad y = \frac{1}{\sqrt 2} \}\\[0.8em]x = \{ \frac{1}{\sqrt 2} ; \quad y = - \frac{1}{\sqrt 2} \}\\[0.8em]x = \{ \frac{1}{\sqrt 2} ; \quad y = \frac{1}{\sqrt 2} \}
Подставим эти точки в изначальную функцию f(x,y)=xyf(x, y) = x y и дважды получим точки — 0.50.5 и −0.5-0.5.

Следовательно при данных ограничениях максимум и минимум функции достигается в двух точках и равен 0.50.5 и −0.5-0.5 соответственно.

Теперь обобщим для функции многих переменных. Пусть у нас есть какая-то f ⁣:Rn→Rf \colon \RR^n \to \RR и mm уравнений связи (n>mn > m):

g1(x1,x2,…,xn)=0;  g2(x1,x2,…,xn)=0;  … ;  gm(x1,x2,…,xn)=0g_1(x_1, x_2, \dotsc, x_n) = 0; \; g_2(x_1, x_2, \dotsc, x_n) = 0; \; \dotsc; \; g_m(x_1, x_2, \dotsc, x_n) = 0
Обозначив множители Лагранжа как — λ1,λ2,…,λm\lambda_1, \lambda_2, \dotsc, \lambda_m, составим функцию Лагранжа:
L(x1,x2,…,xn,λ1,λ2,…,λm)=f+λ1g1+λ2g2+⋯+λmgmL(x_1, x_2, \dotsc, x_n, \lambda_1, \lambda_2, \dotsc, \lambda_m) = f + \lambda_1 g_1 + \lambda_2 g_2 + \dotsb + \lambda_m g_m
Необходимые условия наличия условного экстремума задаются системой уравнений, из которой находятся координаты стационарных точек и значения множителей Лагранжа:
{∂L∂xi=0,i=1,2,…,n,gj=0,j=1,2,…,m.\left\{ \begin{aligned} \frac{\partial L}{\partial x_i} &= 0, \quad i = 1, 2, \dotsc, n, \\ g_j &= 0, \quad j = 1, 2, \dotsc, m. \end{aligned} \right.

Выпуклые и вогнутые функции

Мы продолжаем увеличивать свой инструментарий анализа многомерных функций. Теперь нам известны способы найти локальные экстремумы и классифицировать их как точки максимума или минимума. Но очень часто, особенно в задачах оптимизации, нам необходимо найти не локальные а глобальные стационарные точки. От локальных они отличаются тем, что они единственны на всей области определения функции, а не на какой-то её части. В этой ситуации в первую очередь стоит проверить функцию на выпуклость или вогнутость.

Выпуклые и вогнутые функции

Функция f ⁣:Rn→Rf \colon \RR^n \to \RR называется выпуклой, если выполняется:

∀ x,y∈Rn∀ t∈[0,1]f(tx+(1−t)y)⩽tf(x)+(1−t)f(y)\forall\, x, y \in \RR^n \quad \forall\, t \in [0, 1] \quad f(t x + (1 - t) y) \le t f(x) + (1-t) f(y)
если выполняется обратное —
∀ x,y∈Rn∀ t∈[0,1]f(tx+(1−t)y)⩾tf(x)+(1−t)f(y)\forall\, x, y \in \RR^n \quad \forall\, t \in [0, 1] \quad f(t x + (1 - t) y) \ge t f(x) + (1-t) f(y)
то функция называется вогнутой.

При этом, если определение выше дополнить условием что t∈(0,1)t \in (0, 1) и x≠yx \neq y, то функция будет называться строго выпуклой и строго вогнутой соответственно.

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

При работе с выпуклыми функциями иногда опираются на Неравенство Йенсена. Давайте его рассмотрим

Неравенство Йенсена

Пусть f(x)f(x) выпукла вверх на [a;b][a; b]. Тогда для любых x1,x2,…,xn∈[a;b]x_1, x_2, \dotsc, x_n \in [a; b] и их выпуклой комбинации выполнено неравенство

∑k=1nαkf(xk)≤f(∑k=1nαkxk)\sum\limits_{k=1}^n \alpha_k f(x_k) \leq f \bigl( \sum\limits_{k=1}^n \alpha_k x_k \bigr)

Докажем по индукции. База: n=2n = 2. Неравенство превращается в определение выпуклой вверх функции, для которой это, очевидно, выполняется. Переход: пусть это верно для nn. Докажем, что это верно для n+1n + 1:

∑k=1n+1αk=1\sum\limits_{k=1}^{n+1} \alpha_k = 1
обозначим sn=∑k=1nαks_n = \sum\limits_{k=1}^n \alpha_k. Пусть βk=αksn\beta_k = \dfrac{\alpha_k}{s_n}. Тогда получаем: ∑k=1nβk=1\sum\limits_{k=1}^n \beta_k = 1.
∑k=1n+1αkf(xk)=sn∑k=1nβkf(xk)+αn+1f(xn+1)\sum\limits_{k=1}^{n+1} \alpha_k f(x_k) = s_n \sum\limits_{k=1}^n \beta_k f(x_k) + \alpha_{n+1} f(x_{n+1})
по предположению индукции
∑k=1n+1αkf(xk)≤snf(∑k=1nβkxk)+αn+1f(xn+1)\sum\limits_{k=1}^{n+1} \alpha_k f(x_k) \leq s_n f \bigl( \sum\limits_{k=1}^n \beta_k x_k \bigr) + \alpha_{n+1} f(x_{n+1})
так как sn+αn+1=1s_n + \alpha_{n+1} = 1
snf(∑k=1nβkxk)+αn+1f(xn+1)≤f(∑k=1n+1αkxk)s_n f \bigl( \sum\limits_{k=1}^n \beta_k x_k \bigr) + \alpha_{n+1} f(x_{n+1}) \leq f \bigl( \sum\limits_{k=1}^{n+1} \alpha_k x_k \bigr)
Значит, шаг индукции проделан, неравенство доказано для произвольного nn.

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

Рассмотрим сначала, то как ведёт себя одномерная выпуклая функция при дифференцировании.

Применим линейную интерполяцию (в случае 22 узлов), чтобы выяснить связь между выпуклостью и дифференцируемостью функции ff. Будем считать, что ff дифференцируема столько раз, сколько нам нужно. Имея 22 узла на (a;b)( a; b ) и y0=f(x0),  y1=f(x1)y_0 = f(x_0), \; y_1 = f(x_1), составим Ln(x)L_n(x):

Ln(x)=y0x−x1x0−x1+y1x−x0x1−x0L_n(x) = y_0 \frac{x - x_1}{x_0 - x_1} + y_1 \frac{x - x_0}{x_1 - x_0}
— прямая, проходящая через точки (x0,y0)(x_0, y_0) и (x1,y1)(x_1, y_1). Значит, между x0x_0 и x1x_1 получаем хорду, соединяющую две точки графика. В вопросе о выпуклости надо проверять знак такой разности:
f(x)−Ln(x)=f(2)(cx)2!(x−x0)(x−x1),x0≤x≤x1f(x) - L_n(x) = \frac{f^{(2)}(c_x)}{2!} (x - x_0)(x - x_1), \quad x_0 \leq x \leq x_1
Если f(2)≤0f^{(2)} \leq 0 на (a;b)(a; b), то правая часть будет неотрицательная, так как x∈[x0;x1]x \in [x_0; x_1], поэтому f(x)−Ln(x)≥0f(x) - L_n(x) \geq 0, и, т. к. x0x_0 и x1x_1 произвольны, то ff выпукла вверх. Итак, f(2)≤0  ⟹  ff^{(2)} \leq 0 \implies f выпукла вверх. Пусть ff выпукла вверх. Будем считать, что f(2)f^{(2)} непрерывна, x∈(a;b)x \in (a; b). Пусть x0=x−Δxx_0 = x - \Delta x, x1=x+Δxx_1 = x + \Delta x, где Δx\Delta x — малое положительное число. Рассмотрим полином Лагранжа LnL_n для системы узлов (x0,x1)(x_0, x_1):
f(t)−Ln(t)=f(2)(ct)2!(t−x0)(t−x1)≥0,(t−x0)(t−x1)<0  ⟹  f(2)(ct)≤0f(t) - L_n(t) = \frac{f^{(2)}(c_t)}{2!} (t - x_0)(t - x_1) \geq 0, \quad (t - x_0)(t - x_1) < 0 \implies f^{(2)}(c_t) \leq 0
ct∈(x−Δx;x+Δx)c_t \in ( x - \Delta x; x + \Delta x ).
Δx→0 ⁣:ct→x ⁣:f(2)(x)≤0\Delta x \to 0 \colon c_t \to x \colon f^{(2)}(x) \leq 0
Итак, если ff выпукла вверх, то f(2)≤0f^{(2)} \leq 0.

Теперь обобщим и докажем для многомерных функций

Пусть D⊂RnD \subset \RR^n — открытое выпуклое множество, f ⁣:D→Rf \colon D \to \RR дважды непрерывно дифференцируема, и для всех x∈Dx \in D гессиан H⁡(x)=∇2f(x)\hess(x) = \nabla^2 f(x) отрицательно полуопределён:

∀ x∈D  ∀ h∈Rn ⁣:  hTH⁡(x)h≤0\forall\, x \in D \; \forall\, h \in \RR^n \colon \; h^{\T} \hess(x) h \leq 0
Возьмём любые точки x0,x1∈Dx_0, x_1 \in D. Из выпуклости DD следует, что отрезок между ними лежит в DD. Введём параметризацию отрезка:
z(t)=x0+t(x1−x0),t∈[0,1]z(t) = x_0 + t (x_1 - x_0), \quad t \in [0, 1]
И рассмотрим функцию одной переменной
u(t)=f(z(t))=f(x0+t(x1−x0))u(t) = f(z(t)) = f\bigl( x_0 + t (x_1 - x_0) \bigr)
Тогда
u′(t)=∇f(z(t))⋅(x1−x0)u'(t) = \nabla f(z(t)) \cdot (x_1 - x_0)
u′′(t)=(x1−x0)TH⁡(z(t))(x1−x0)≤0u''(t) = (x_1 - x_0)^{\T} \hess(z(t)) (x_1 - x_0) \leq 0
по предположению об отрицательной полуопределённости гессиана. Значит, uu на [0,1][0, 1] выпукла вверх как функция одной переменной, и поэтому для всех t∈[0,1]t \in [0, 1]
u(t)≥(1−t)u(0)+tu(1)u(t) \geq (1 - t) u(0) + t u(1)
Подставляя обратно определения uu и zz, получаем
f((1−t)x0+tx1)≥(1−t)f(x0)+tf(x1),t∈[0,1]f\bigl( (1 - t) x_0 + t x_1 \bigr) \geq (1 - t) f(x_0) + t f(x_1), \quad t \in [0, 1]
Так как x0,x1x_0, x_1 выбирались произвольно, ff выпукла вверх на DD. Аналогично для вогнутых функций.

Теперь обобщим свойства таких функций

  1. Любой минимум у выпуклых функций и любой максимум у выгнутых функций является глобальным.

  2. Пусть функции f1 ⁣:Rn→R,…,fm ⁣:Rn→Rf_1 \colon \RR^n \to \RR, \dotsc , f_m \colon \RR^n \to \RR — выпуклы, w1∈R+,…,wm∈R+w_1 \in \RR_+, \dotsc , w_m \in \RR_+ Тогда функция f=f1w1+⋯+wmfmf = f_1 w_1 + \dotsb + w_m f_m — тоже выпуклая. Аналогично для вогнутых функций.

  3. Пусть f ⁣:Rn→Rf \colon \RR^n \to \RR — выпуклая, а A∈Rn×m,b∈RnA \in \RR^{n \times m}, b \in \RR^n, тогда функция g(x)=f(Ax+b)g(x) = f(A x + b) с областью определения dom⁡g={x ⁣:Ax+b∈dom⁡f}\dom g = \{x \colon A x + b \in \dom f \} — тоже является выпуклой. Аналогично для вогнутых функций.

  4. Пусть f ⁣:Rn→Rf \colon \RR^n \to \RR — выпуклая, а h ⁣:Rn→Rh \colon \RR^n \to \RR — выпуклая неубывающая, тогда композиция этих двух функций. g(f(x))g(f(x)) с областью определения dom⁡g={x∈dom⁡f ⁣:f(x)∈dom⁡h}\dom g = \{x \in \dom f \colon f(x) \in \dom h \} — является выпуклой. Аналогично для вогнутых функций.

  5. Если f1,…fmf_1, \dotsc f_m — выпуклые функции, то функция f(x)=max⁡{f1(x)…fm(x)}f (x) = \max\limits \{ f_1 (x) \dotsc f_m (x) \} с областью определения dom⁡f=dom⁡f1∩…∩dom⁡fm\dom f = \dom f_1 \sect \dotsc \sect \dom f_m — тоже выпукла.