Выпуклая функция

Выпуклая функция на интервале .

Действительная функция с секущей линией между точками над самим графиком

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

График двумерной выпуклой функции x ² + xy + y ² .

Выпуклый против невыпуклого

В математике действительная функция называется выпуклой , если отрезок прямой между любыми двумя различными точками на графике функции лежит выше или на графике между двумя точками. Эквивалентно, функция является выпуклой, если ее надграфик (множество точек на или над графиком функции) является выпуклым множеством . Проще говоря, график выпуклой функции имеет форму чашки (или прямой линии, как у линейной функции), в то время как график вогнутой функции имеет форму колпачка . ${\displaystyle \cup }$ ${\displaystyle \cap }$

Дважды дифференцируемая функция одной переменной является выпуклой тогда и только тогда, когда ее вторая производная неотрицательна на всей своей области определения . ^[1] Хорошо известными примерами выпуклых функций одной переменной являются линейная функция (где — действительное число ), квадратичная функция ( как неотрицательное действительное число) и показательная функция ( как неотрицательное действительное число). ${\displaystyle f(x)=cx}$ ${\displaystyle c}$ ${\displaystyle cx^{2}}$ ${\displaystyle c}$ ${\displaystyle ce^{x}}$ ${\displaystyle c}$

Выпуклые функции играют важную роль во многих областях математики. Они особенно важны при изучении задач оптимизации , где они отличаются рядом удобных свойств. Например, строго выпуклая функция на открытом множестве имеет не более одного минимума . Даже в бесконечномерных пространствах при подходящих дополнительных гипотезах выпуклые функции продолжают удовлетворять таким свойствам и, как следствие, они являются наиболее хорошо изученными функционалами в вариационном исчислении . В теории вероятностей выпуклая функция, примененная к ожидаемому значению случайной величины, всегда ограничена сверху ожидаемым значением выпуклой функции случайной величины. Этот результат, известный как неравенство Йенсена , может быть использован для вывода неравенств, таких как неравенство среднего арифметического и геометрического и неравенство Гёльдера .

Определение

Визуализация выпуклой функции и неравенства Йенсена

Пусть — выпуклое подмножество действительного векторного пространства и пусть — функция. ${\displaystyle X}$ ${\displaystyle f:X\to \mathbb {R} }$

Тогда называется выпуклым тогда и только тогда, когда выполняется любое из следующих эквивалентных условий: ${\displaystyle f}$

1. Для всех и всех : Правая сторона представляет прямую линию между и на графике как функция увеличения от до или уменьшения от до заметает эту линию. Аналогично, аргумент функции в левой стороне представляет прямую линию между и на или -оси графика Таким образом, это условие требует, чтобы прямая линия между любой парой точек на кривой была выше или просто пересекала график. ^[2] ${\displaystyle 0\leq t\leq 1}$ ${\displaystyle x_{1},x_{2}\in X}$ $${\displaystyle f\left(tx_{1}+(1-t)x_{2}\right)\leq tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$$ ${\displaystyle \left(x_{1},f\left(x_{1}\right)\right)}$ ${\displaystyle \left(x_{2},f\left(x_{2}\right)\right)}$ ${\displaystyle f}$ ${\displaystyle t;}$ ${\displaystyle t}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle t}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle f}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle f.}$ ${\displaystyle f}$
2. Для всех и всех таких, что : Отличие этого второго условия от первого условия выше заключается в том, что это условие не включает точки пересечения (например, и ) между прямой линией, проходящей через пару точек на кривой (прямая линия представлена ​​правой частью этого условия), и кривой первого условия включает точки пересечения, поскольку она становится или при или или На самом деле, точки пересечения не нужно рассматривать в условии выпуклости, используя, поскольку и всегда истинны (поэтому бесполезно быть частью условия). ${\displaystyle 0<t<1}$ ${\displaystyle x_{1},x_{2}\in X}$ ${\displaystyle x_{1}\neq x_{2}}$ $${\displaystyle f\left(tx_{1}+(1-t)x_{2}\right)\leq tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$$ ${\displaystyle \left(x_{1},f\left(x_{1}\right)\right)}$ ${\displaystyle \left(x_{2},f\left(x_{2}\right)\right)}$ ${\displaystyle f}$ ${\displaystyle f;}$ ${\displaystyle f\left(x_{1}\right)\leq f\left(x_{1}\right)}$ ${\displaystyle f\left(x_{2}\right)\leq f\left(x_{2}\right)}$ ${\displaystyle t=0}$ ${\displaystyle 1,}$ ${\displaystyle x_{1}=x_{2}.}$ $${\displaystyle f\left(tx_{1}+(1-t)x_{2}\right)\leq tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$$ ${\displaystyle f\left(x_{1}\right)\leq f\left(x_{1}\right)}$ ${\displaystyle f\left(x_{2}\right)\leq f\left(x_{2}\right)}$

Второе утверждение, характеризующее выпуклые функции, которые оцениваются в вещественной прямой , также является утверждением, используемым для определения выпуклых функций , которые оцениваются в расширенной вещественной прямой, где такая функция может принимать значение. Первое утверждение не используется, поскольку оно позволяет принимать или в качестве значения, и в этом случае, если или соответственно, то будет неопределенным (поскольку умножения и не определены). Сумма также не определена, поэтому выпуклая расширенная вещественная функция обычно может принимать только одно из и в качестве значения. ${\displaystyle \mathbb {R} }$ ${\displaystyle [-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \},}$ ${\displaystyle f}$ ${\displaystyle \pm \infty }$ ${\displaystyle t}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle f\left(x_{1}\right)=\pm \infty }$ ${\displaystyle f\left(x_{2}\right)=\pm \infty ,}$ ${\displaystyle tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$ ${\displaystyle 0\cdot \infty }$ ${\displaystyle 0\cdot (-\infty )}$ ${\displaystyle -\infty +\infty }$ ${\displaystyle -\infty }$ ${\displaystyle +\infty }$

Второе утверждение также можно модифицировать, чтобы получить определение строгой выпуклости , где последнее получается заменой на строгое неравенство Явно, отображение называется строго выпуклым тогда и только тогда, когда для всех действительных и всех таких, что : ${\displaystyle \,\leq \,}$ ${\displaystyle \,<.}$ ${\displaystyle f}$ ${\displaystyle 0<t<1}$ ${\displaystyle x_{1},x_{2}\in X}$ ${\displaystyle x_{1}\neq x_{2}}$ $${\displaystyle f\left(tx_{1}+(1-t)x_{2}\right)<tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$$

Строго выпуклая функция — это функция, прямая линия между любой парой точек на кривой находится выше кривой, за исключением точек пересечения прямой и кривой. Примером функции, которая является выпуклой, но не строго выпуклой, является . Эта функция не является строго выпуклой, поскольку любые две точки, разделяющие координату x, будут иметь прямую линию между ними, в то время как любые две точки, НЕ разделяющие координату x, будут иметь большее значение функции, чем точки между ними. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f(x,y)=x^{2}+y}$

Функция называется вогнутой (соответственно строго вогнутой ), если ( умноженная на −1) является выпуклой (соответственно строго выпуклой). ${\displaystyle f}$ ${\displaystyle -f}$ ${\displaystyle f}$

Альтернативное наименование

Термин выпуклый часто называют выпуклым вниз или вогнутым вверх , а термин вогнутый часто называют вогнутым вниз или выпуклым вверх . ^{[3] [4] [5]} Если термин «выпуклый» используется без ключевых слов «вверх» или «вниз», то он относится строго к чашеобразному графику . Например, неравенство Йенсена относится к неравенству, включающему выпуклую или выпуклую (вниз) функцию. ^[6] ${\displaystyle \cup }$

Характеристики

Многие свойства выпуклых функций имеют ту же простую формулировку для функций многих переменных, что и для функций одной переменной. Ниже приведены свойства для случая многих переменных, так как некоторые из них не перечислены для функций одной переменной.

Функции одной переменной

• Предположим, что является функцией одной действительной переменной, определенной на интервале, и пусть (обратите внимание, что является наклоном фиолетовой линии на первом рисунке; ​​функция симметрична относительно означает , что не меняется при замене и ). является выпуклой тогда и только тогда, когда является монотонно неубывающей по для каждого фиксированного (или наоборот). Эта характеристика выпуклости весьма полезна для доказательства следующих результатов. ${\displaystyle f}$ $${\displaystyle R(x_{1},x_{2})={\frac {f(x_{2})-f(x_{1})}{x_{2}-x_{1}}}}$$ ${\displaystyle R(x_{1},x_{2})}$ ${\displaystyle R}$ ${\displaystyle (x_{1},x_{2}),}$ ${\displaystyle R}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle f}$ ${\displaystyle R(x_{1},x_{2})}$ ${\displaystyle x_{1},}$ ${\displaystyle x_{2}}$
• Выпуклая функция одной действительной переменной, определенная на некотором открытом интервале , непрерывна на допускает левые и правые производные , и они монотонно не убывающие . Кроме того, левая производная непрерывна слева, а правая производная непрерывна справа. Как следствие, дифференцируема во всех, кроме счетного числа точек, множество, в котором она не дифференцируема, может, однако, быть плотным. Если замкнуто, то может не быть непрерывным в конечных точках (пример показан в разделе примеров). ${\displaystyle f}$ ${\displaystyle C}$ ${\displaystyle C.}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle C}$ ${\displaystyle f}$ ${\displaystyle C}$
• Дифференцируемая функция одной переменной выпукла на интервале тогда и только тогда, когда ее производная монотонно не убывает на этом интервале. Если функция дифференцируема и выпукла, то она также непрерывно дифференцируема .
• Дифференцируемая функция одной переменной выпукла на интервале тогда и только тогда, когда ее график лежит выше всех своих касательных : ^{[7] : 69} для всех и на интервале. $${\displaystyle f(x)\geq f(y)+f'(y)(x-y)}$$ ${\displaystyle x}$ ${\displaystyle y}$
• Дважды дифференцируемая функция одной переменной выпукла на интервале тогда и только тогда, когда ее вторая производная неотрицательна там; это дает практический тест на выпуклость. Визуально дважды дифференцируемая выпуклая функция «изгибается вверх», без каких-либо изгибов в другую сторону ( точки перегиба ). Если ее вторая производная положительна во всех точках, то функция строго выпукла, но обратное не верно. Например, вторая производная от равна , которая равна нулю при , но является строго выпуклой. ${\displaystyle f(x)=x^{4}}$ ${\displaystyle f''(x)=12x^{2}}$ ${\displaystyle x=0,}$ ${\displaystyle x^{4}}$
  • Это свойство и указанное выше свойство в терминах «...ее производная монотонно не убывает...» не равны, поскольку если неотрицательна на интервале , то монотонно не убывает на , в то время как обратное утверждение неверно, например, монотонно не убывает на , в то время как ее производная не определена в некоторых точках на . ${\displaystyle f''}$ ${\displaystyle X}$ ${\displaystyle f'}$ ${\displaystyle X}$ ${\displaystyle f'}$ ${\displaystyle X}$ ${\displaystyle f''}$ ${\displaystyle X}$
• Если — выпуклая функция одной действительной переменной, и , то она супераддитивна на положительных действительных числах , то есть для положительных действительных чисел и . ${\displaystyle f}$ ${\displaystyle f(0)\leq 0}$ ${\displaystyle f}$ ${\displaystyle f(a+b)\geq f(a)+f(b)}$ ${\displaystyle a}$ ${\displaystyle b}$

Доказательство

Так как является выпуклым, то, используя одно из определений выпуклой функции выше и допуская , что для всех действительных Из следует, что А именно, . ${\displaystyle f}$ ${\displaystyle x_{2}=0,}$ ${\displaystyle 0\leq t\leq 1,}$ $${\displaystyle {\begin{aligned}f(tx_{1})&=f(tx_{1}+(1-t)\cdot 0)\\&\leq tf(x_{1})+(1-t)f(0)\\&\leq tf(x_{1}).\\\end{aligned}}}$$ ${\displaystyle f(tx_{1})\leq tf(x_{1})}$ $${\displaystyle {\begin{aligned}f(a)+f(b)&=f\left((a+b){\frac {a}{a+b}}\right)+f\left((a+b){\frac {b}{a+b}}\right)\\&\leq {\frac {a}{a+b}}f(a+b)+{\frac {b}{a+b}}f(a+b)\\&=f(a+b).\\\end{aligned}}}$$ ${\displaystyle f(a)+f(b)\leq f(a+b)}$

• Функция является средневыпуклой на интервале , если для всех Это условие лишь немного слабее, чем выпуклость. Например, вещественная измеримая по Лебегу функция , которая является средневыпуклой, является выпуклой: это теорема Серпинского . ^[8] В частности, непрерывная функция, которая является средневыпуклой, будет выпуклой. ${\displaystyle f}$ ${\displaystyle C}$ ${\displaystyle x_{1},x_{2}\in C}$ $${\displaystyle f\!\left({\frac {x_{1}+x_{2}}{2}}\right)\leq {\frac {f(x_{1})+f(x_{2})}{2}}.}$$

Функции многих переменных

• Функция, которая является предельно выпуклой по каждой отдельной переменной, не обязательно является (совместно) выпуклой. Например, функция является предельно линейной , и, таким образом, предельно выпуклой, по каждой переменной, но не (совместно) выпуклой. ${\displaystyle f(x,y)=xy}$
• Функция, принимающая значения в расширенных действительных числах, является выпуклой тогда и только тогда, когда ее надграфик является выпуклым множеством. ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle [-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \}}$ $${\displaystyle \{(x,r)\in X\times \mathbb {R} ~:~r\geq f(x)\}}$$
• Дифференцируемая функция, определенная на выпуклой области, является выпуклой тогда и только тогда, когда выполняется для всех функций в области. ${\displaystyle f}$ ${\displaystyle f(x)\geq f(y)+\nabla f(y)^{T}\cdot (x-y)}$ ${\displaystyle x,y}$
• Дважды дифференцируемая функция многих переменных является выпуклой на выпуклом множестве тогда и только тогда, когда ее матрица Гессе вторых частных производных положительно полуопределена на внутренней части выпуклого множества.
• Для выпуклой функции множества подуровней и с являются выпуклыми множествами. Функция, удовлетворяющая этому свойству, называется квазивыпуклой функцией и может не быть выпуклой функцией. ${\displaystyle f,}$ ${\displaystyle \{x:f(x)<a\}}$ ${\displaystyle \{x:f(x)\leq a\}}$ ${\displaystyle a\in \mathbb {R} }$
• Следовательно, множество глобальных минимизаторов выпуклой функции является выпуклым множеством: - выпукло. ${\displaystyle f}$ ${\displaystyle {\operatorname {argmin} }\,f}$
• Любой локальный минимум выпуклой функции также является глобальным минимумом . Строго выпуклая функция будет иметь не более одного глобального минимума. ^[9]
• Неравенство Йенсена применимо к любой выпуклой функции . Если — случайная величина, принимающая значения в области , то где обозначает математическое ожидание . Действительно, выпуклые функции — это в точности те, которые удовлетворяют гипотезе неравенства Йенсена . ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle f,}$ ${\displaystyle \operatorname {E} (f(X))\geq f(\operatorname {E} (X)),}$ ${\displaystyle \operatorname {E} }$
• Однородная функция первого порядка двух положительных переменных и (то есть функция, удовлетворяющая для всех положительных действительных ), которая является выпуклой по одной переменной, должна быть выпуклой и по другой переменной. ^[10] ${\displaystyle x}$ ${\displaystyle y,}$ ${\displaystyle f(ax,ay)=af(x,y)}$ ${\displaystyle a,x,y>0}$

Операции, сохраняющие выпуклость

• ${\displaystyle -f}$является вогнутым тогда и только тогда, когда является выпуклым. ${\displaystyle f}$
• Если — любое действительное число, то оно выпукло тогда и только тогда, когда оно выпукло. ${\displaystyle r}$ ${\displaystyle r+f}$ ${\displaystyle f}$
• Неотрицательные взвешенные суммы:
  • если и все выпуклые, то также выпукла и В частности, сумма двух выпуклых функций является выпуклой. ${\displaystyle w_{1},\ldots ,w_{n}\geq 0}$ ${\displaystyle f_{1},\ldots ,f_{n}}$ ${\displaystyle w_{1}f_{1}+\cdots +w_{n}f_{n}.}$
  • это свойство распространяется также на бесконечные суммы, интегралы и ожидаемые значения (при условии, что они существуют).
• Поэлементный максимум: пусть будет набором выпуклых функций. Тогда является выпуклым. Область определения — это набор точек, где выражение конечно. Важные особые случаи: ${\displaystyle \{f_{i}\}_{i\in I}}$ ${\displaystyle g(x)=\sup \nolimits _{i\in I}f_{i}(x)}$ ${\displaystyle g(x)}$
  • Если являются выпуклыми функциями, то также ${\displaystyle f_{1},\ldots ,f_{n}}$ ${\displaystyle g(x)=\max \left\{f_{1}(x),\ldots ,f_{n}(x)\right\}.}$
  • Теорема Данскина : Если является выпуклым по , то является выпуклым по , даже если не является выпуклым множеством. ${\displaystyle f(x,y)}$ ${\displaystyle x}$ ${\displaystyle g(x)=\sup \nolimits _{y\in C}f(x,y)}$ ${\displaystyle x}$ ${\displaystyle C}$
• Состав:
  • Если и являются выпуклыми функциями и не убывает в одномерной области, то является выпуклой. Например, если является выпуклой, то также является, поскольку является выпуклой и монотонно возрастает. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle h(x)=g(f(x))}$ ${\displaystyle f}$ ${\displaystyle e^{f(x)}}$ ${\displaystyle e^{x}}$
  • Если вогнутая, выпуклая и невозрастающая в одномерной области, то выпуклая. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle h(x)=g(f(x))}$
  • Выпуклость инвариантна относительно аффинных отображений: то есть, если выпукло с областью , то также выпукло , где с областью ${\displaystyle f}$ ${\displaystyle D_{f}\subseteq \mathbf {R} ^{m}}$ ${\displaystyle g(x)=f(Ax+b)}$ ${\displaystyle A\in \mathbf {R} ^{m\times n},b\in \mathbf {R} ^{m}}$ ${\displaystyle D_{g}\subseteq \mathbf {R} ^{n}.}$
• Минимизация: Если является выпуклым по , то является выпуклым по при условии, что является выпуклым множеством и что ${\displaystyle f(x,y)}$ ${\displaystyle (x,y)}$ ${\displaystyle g(x)=\inf \nolimits _{y\in C}f(x,y)}$ ${\displaystyle x,}$ ${\displaystyle C}$ ${\displaystyle g(x)\neq -\infty .}$
• Если выпукло, то его перспектива с областью определения выпукла. ${\displaystyle f}$ ${\displaystyle g(x,t)=tf\left({\tfrac {x}{t}}\right)}$ ${\displaystyle \left\{(x,t):{\tfrac {x}{t}}\in \operatorname {Dom} (f),t>0\right\}}$
• Пусть будет векторным пространством. является выпуклым и удовлетворяет тогда и только тогда, когда для любого и любых неотрицательных действительных чисел , удовлетворяющих ${\displaystyle X}$ ${\displaystyle f:X\to \mathbf {R} }$ ${\displaystyle f(0)\leq 0}$ ${\displaystyle f(ax+by)\leq af(x)+bf(y)}$ ${\displaystyle x,y\in X}$ ${\displaystyle a,b}$ ${\displaystyle a+b\leq 1.}$

Сильно выпуклые функции

Концепция сильной выпуклости расширяет и параметризует понятие строгой выпуклости. Интуитивно, сильно выпуклая функция — это функция, которая растет так же быстро, как квадратичная функция. ^[11] Сильно выпуклая функция также строго выпукла, но не наоборот. Если одномерная функция дважды непрерывно дифференцируема, а область определения — вещественная прямая, то мы можем охарактеризовать ее следующим образом: ${\displaystyle f}$

• ${\displaystyle f}$выпуклый тогда и только тогда, когда для всех ${\displaystyle f''(x)\geq 0}$ ${\displaystyle x.}$
• ${\displaystyle f}$строго выпукло, если для всех (примечание: этого достаточно, но не необходимо). ${\displaystyle f''(x)>0}$ ${\displaystyle x}$
• ${\displaystyle f}$сильно выпуклый тогда и только тогда, когда для всех ${\displaystyle f''(x)\geq m>0}$ ${\displaystyle x.}$

Например, пусть будет строго выпуклой, и предположим, что существует последовательность точек такая, что . Даже если , функция не является сильно выпуклой, поскольку станет произвольно малой. ${\displaystyle f}$ ${\displaystyle (x_{n})}$ ${\displaystyle f''(x_{n})={\tfrac {1}{n}}}$ ${\displaystyle f''(x_{n})>0}$ ${\displaystyle f''(x)}$

В более общем случае дифференцируемая функция называется сильно выпуклой с параметром , если для всех точек ее области определения выполняется следующее неравенство : ^[12] или, в более общем случае, где — любое скалярное произведение , а — соответствующая норма . Некоторые авторы, например ^[13], называют функции, удовлетворяющие этому неравенству, эллиптическими функциями. ${\displaystyle f}$ ${\displaystyle m>0}$ ${\displaystyle x,y}$ $${\displaystyle (\nabla f(x)-\nabla f(y))^{T}(x-y)\geq m\|x-y\|_{2}^{2}}$$ $${\displaystyle \langle \nabla f(x)-\nabla f(y),x-y\rangle \geq m\|x-y\|^{2}}$$ ${\displaystyle \langle \cdot ,\cdot \rangle }$ ${\displaystyle \|\cdot \|}$

Эквивалентным условием является следующее: ^[14] $${\displaystyle f(y)\geq f(x)+\nabla f(x)^{T}(y-x)+{\frac {m}{2}}\|y-x\|_{2}^{2}}$$

Для того чтобы функция была сильно выпуклой, не обязательно быть дифференцируемой. Третье определение ^[14] для сильно выпуклой функции с параметром заключается в том, что для всех в области определения и ${\displaystyle m,}$ ${\displaystyle x,y}$ ${\displaystyle t\in [0,1],}$ $${\displaystyle f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)-{\frac {1}{2}}mt(1-t)\|x-y\|_{2}^{2}}$$

Обратите внимание, что это определение приближается к определению строгой выпуклости при и идентично определению выпуклой функции при Несмотря на это, существуют функции, которые являются строго выпуклыми, но не являются сильно выпуклыми ни для какого (см. пример ниже). ${\displaystyle m\to 0,}$ ${\displaystyle m=0.}$ ${\displaystyle m>0}$

Если функция дважды непрерывно дифференцируема, то она сильно выпукла с параметром тогда и только тогда, когда для всех в области определения, где — единица, а — матрица Гессе , и неравенство означает, что является положительно полуопределенной . Это эквивалентно требованию, чтобы минимальное собственное значение было не менее для всех Если область определения — это просто вещественная прямая, то — это просто вторая производная , поэтому условие становится . Если то это означает, что гессиан положительно полуопределен (или если область определения — это вещественная прямая, то это означает, что ), что подразумевает, что функция выпукла и, возможно, строго выпукла, но не сильно выпукла. ${\displaystyle f}$ ${\displaystyle m}$ ${\displaystyle \nabla ^{2}f(x)\succeq mI}$ ${\displaystyle x}$ ${\displaystyle I}$ ${\displaystyle \nabla ^{2}f}$ ${\displaystyle \succeq }$ ${\displaystyle \nabla ^{2}f(x)-mI}$ ${\displaystyle \nabla ^{2}f(x)}$ ${\displaystyle m}$ ${\displaystyle x.}$ ${\displaystyle \nabla ^{2}f(x)}$ ${\displaystyle f''(x),}$ ${\displaystyle f''(x)\geq m}$ ${\displaystyle m=0}$ ${\displaystyle f''(x)\geq 0}$

Предполагая по-прежнему, что функция дважды непрерывно дифференцируема, можно показать, что нижняя граница влечет ее сильную выпуклость. Используя теорему Тейлора, существует такое, что Тогда по предположению о собственных значениях, и, следовательно, мы восстанавливаем второе уравнение сильной выпуклости выше. ${\displaystyle \nabla ^{2}f(x)}$ $${\displaystyle z\in \{tx+(1-t)y:t\in [0,1]\}}$$ $${\displaystyle f(y)=f(x)+\nabla f(x)^{T}(y-x)+{\frac {1}{2}}(y-x)^{T}\nabla ^{2}f(z)(y-x)}$$ $${\displaystyle (y-x)^{T}\nabla ^{2}f(z)(y-x)\geq m(y-x)^{T}(y-x)}$$

Функция является сильно выпуклой с параметром m тогда и только тогда, когда функция выпукла. ${\displaystyle f}$ $${\displaystyle x\mapsto f(x)-{\frac {m}{2}}\|x\|^{2}}$$

Дважды непрерывно дифференцируемая функция на компактной области , удовлетворяющая для всех , является сильно выпуклой. Доказательство этого утверждения следует из теоремы об экстремальном значении , которая утверждает, что непрерывная функция на компактном множестве имеет максимум и минимум. ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle f''(x)>0}$ ${\displaystyle x\in X}$

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

Свойства сильно выпуклых функций

Если f — сильно выпуклая функция с параметром m , то: ^{[15] : Предложение 6.1.4}

• Для каждого действительного числа r множество уровня { x | f ( x ) ≤ r } является компактным .
• Функция f имеет единственный глобальный минимум на R ⁿ .

Равномерно выпуклые функции

Равномерно выпуклая функция ^{[16] [17]} с модулем , является функцией , которая для всех в области и удовлетворяет условию , где — функция, которая неотрицательна и обращается в нуль только в точке 0. Это обобщение концепции сильно выпуклой функции; взяв , мы восстанавливаем определение сильной выпуклости. ${\displaystyle \phi }$ ${\displaystyle f}$ ${\displaystyle x,y}$ ${\displaystyle t\in [0,1],}$ $${\displaystyle f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)-t(1-t)\phi (\|x-y\|)}$$ ${\displaystyle \phi }$ ${\displaystyle \phi (\alpha )={\tfrac {m}{2}}\alpha ^{2}}$

Стоит отметить, что некоторые авторы требуют, чтобы модуль был возрастающей функцией, ^[17] но это условие требуется не всеми авторами. ^[16] ${\displaystyle \phi }$

Примеры

Функции одной переменной

• Функция имеет , поэтому f — выпуклая функция. Она также сильно выпукла (и, следовательно, строго выпукла тоже), с константой сильной выпуклости 2. ${\displaystyle f(x)=x^{2}}$ ${\displaystyle f''(x)=2>0}$
• Функция имеет , поэтому f — выпуклая функция. Она строго выпукла, хотя вторая производная не строго положительна во всех точках. Она не сильно выпукла. ${\displaystyle f(x)=x^{4}}$ ${\displaystyle f''(x)=12x^{2}\geq 0}$
• Функция абсолютного значения является выпуклой (что отражено в неравенстве треугольника ), хотя она и не имеет производной в точке Она не является строго выпуклой. ${\displaystyle f(x)=|x|}$ ${\displaystyle x=0.}$
• Функция для является выпуклой. ${\displaystyle f(x)=|x|^{p}}$ ${\displaystyle p\geq 1}$
• Экспоненциальная функция является выпуклой. Она также строго выпукла, так как , но она не является сильно выпуклой, так как вторая производная может быть сколь угодно близка к нулю. В более общем случае функция является логарифмически выпуклой, если является выпуклой функцией. Иногда вместо этого используется термин «супервыпуклая». ^[18] ${\displaystyle f(x)=e^{x}}$ ${\displaystyle f''(x)=e^{x}>0}$ ${\displaystyle g(x)=e^{f(x)}}$ ${\displaystyle f}$
• Функция с областью определения [0,1], определенная с помощью for, является выпуклой; она непрерывна на открытом интервале , но не непрерывна в точках 0 и 1. ${\displaystyle f}$ ${\displaystyle f(0)=f(1)=1,f(x)=0}$ ${\displaystyle 0<x<1}$ ${\displaystyle (0,1),}$
• Функция имеет вторую производную ; таким образом, она выпукла на множестве , где и вогнута на множестве , где ${\displaystyle x^{3}}$ ${\displaystyle 6x}$ ${\displaystyle x\geq 0}$ ${\displaystyle x\leq 0.}$
• Примерами функций, которые монотонно возрастают , но не являются выпуклыми, являются и . ${\displaystyle f(x)={\sqrt {x}}}$ ${\displaystyle g(x)=\log x}$
• Примерами выпуклых, но не монотонно возрастающих функций являются и . ${\displaystyle h(x)=x^{2}}$ ${\displaystyle k(x)=-x}$
• Функция имеет значение , которое больше 0, если так, является выпуклой на интервале . Она является вогнутой на интервале . ${\displaystyle f(x)={\tfrac {1}{x}}}$ ${\displaystyle f''(x)={\tfrac {2}{x^{3}}}}$ ${\displaystyle x>0}$ ${\displaystyle f(x)}$ ${\displaystyle (0,\infty )}$ ${\displaystyle (-\infty ,0)}$
• Функция при , выпукла на интервале и выпукла на интервале , но не выпукла на интервале , из-за сингулярности в точке ${\displaystyle f(x)={\tfrac {1}{x^{2}}}}$ ${\displaystyle f(0)=\infty }$ ${\displaystyle (0,\infty )}$ ${\displaystyle (-\infty ,0)}$ ${\displaystyle (-\infty ,\infty )}$ ${\displaystyle x=0.}$

Функциинпеременные

• Функция LogSumExp , также называемая функцией softmax, является выпуклой функцией.
• Функция на области положительно определенных матриц является выпуклой. ^{[7] : 74} ${\displaystyle -\log \det(X)}$
• Каждое действительное линейное преобразование является выпуклым, но не строго выпуклым, поскольку если является линейным, то . Это утверждение также справедливо, если мы заменим «выпуклый» на «вогнутый». ${\displaystyle f}$ ${\displaystyle f(a+b)=f(a)+f(b)}$
• Каждая действительнозначная аффинная функция , то есть каждая функция вида, является одновременно выпуклой и вогнутой. ${\displaystyle f(x)=a^{T}x+b,}$
• Каждая норма является выпуклой функцией в силу неравенства треугольника и положительной однородности .
• Спектральный радиус неотрицательной матрицы является выпуклой функцией ее диагональных элементов. ^[19]

Смотрите также

• Вогнутая функция
• Выпуклый анализ
• Выпуклый сопряженный
• Выпуклая кривая
• Выпуклая оптимизация
• Геодезическая выпуклость
• Теорема Хана–Банаха
• Неравенство Эрмита-Адамара
• Функция Invex
• Неравенство Йенсена
• K-выпуклая функция
• Теорема Качуровского , связывающая выпуклость с монотонностью производной
• Неравенство Караматы
• Логарифмически выпуклая функция
• Псевдовыпуклая функция
• Квазивыпуклая функция
• Субпроизводная выпуклой функции

Примечания

1. "Lecture Notes 2" (PDF) . www.stat.cmu.edu . Получено 3 марта 2017 г. .
2. "Вогнутый вверх и вниз". Архивировано из оригинала 2013-12-18.
3. Стюарт, Джеймс (2015). Calculus (8-е изд.). Cengage Learning. стр. 223–224. ISBN 978-1305266643.
4. W. Hamming, Richard (2012). Методы математики, применяемые к исчислению, вероятности и статистике (иллюстрированное издание). Courier Corporation. стр. 227. ISBN 978-0-486-13887-9.Выдержка из страницы 227
5. Уваров, Василий Борисович (1988). Математический анализ. Издательство «Мир». С. 126-127. ISBN 978-5-03-000500-3.
6. Прюгель-Беннетт, Адам (2020). Вероятностный компаньон для инженерии и компьютерных наук (иллюстрированное издание). Cambridge University Press. стр. 160. ISBN 978-1-108-48053-6.Выдержка из страницы 160
7. Boyd, Stephen P.; Vandenberghe, Lieven (2004). Выпуклая оптимизация (pdf) . Cambridge University Press. ISBN 978-0-521-83378-3. Получено 15 октября 2011 г. .
8. Донохью, Уильям Ф. (1969). Распределения и преобразования Фурье. Academic Press. стр. 12. ISBN 9780122206504. Получено 29 августа 2012 г. .
9. "Если f строго выпукло в выпуклом множестве, покажите, что оно имеет не более 1 минимума". Math StackExchange. 21 марта 2013 г. Получено 14 мая 2016 г.
10. Альтенберг, Л., 2012. Резольвентные положительные линейные операторы демонстрируют явление редукции. Труды Национальной академии наук, 109(10), стр.3705-3710.
11. "Сильная выпуклость · Блог Синю Чжоу". xingyuzhou.org . Получено 2023-09-27 .
12. Димитрий Берцекас (2003). Выпуклый анализ и оптимизация . Авторы: Анджелия Недич и Асуман Э. Оздаглар. Athena Scientific. стр. 72. ISBN 9781886529458.
13. Филипп Г. Сиарле (1989). Введение в численную линейную алгебру и оптимизацию . Cambridge University Press. ISBN 9780521339841.
14. Юрий Нестеров (2004). Вводные лекции по выпуклой оптимизации: базовый курс . Kluwer Academic Publishers. стр. 63–64. ISBN 9781402075537.
15. Немировски и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .
16. C. Zalinescu (2002). Выпуклый анализ в общих векторных пространствах . World Scientific. ISBN 9812380671.
17. H. Bauschke и PL Combettes (2011). Выпуклый анализ и теория монотонных операторов в гильбертовых пространствах . Springer. стр. 144. ISBN 978-1-4419-9467-7.
18. Кингман, Дж. Ф. К. (1961). «Свойство выпуклости положительных матриц». The Quarterly Journal of Mathematics . 12 : 283–284. doi :10.1093/qmath/12.1.283.
19. Коэн, Дж. Э., 1981. Выпуклость доминирующего собственного значения существенно неотрицательной матрицы. Труды Американского математического общества, 81(4), стр. 657-658.

Ссылки

• Берцекас, Димитрий (2003). Выпуклый анализ и оптимизация . Athena Scientific.
• Борвейн, Джонатан и Льюис, Адриан. (2000). Выпуклый анализ и нелинейная оптимизация. Springer.
• Донохью, Уильям Ф. (1969). Распределения и преобразования Фурье . Academic Press.
• Хириар-Уррути, Жан-Батист, и Лемарешаль, Клод . (2004). Основы выпуклого анализа. Берлин: Шпрингер.
• Красносельский М.А. , Рутицкий Я.Б. (1961). Выпуклые функции и пространства Орлича . Гронинген: P.Noordhoff Ltd.
• Лауритцен, Нильс (2013). Выпуклость бакалавриата . World Scientific Publishing.
• Люенбергер, Дэвид (1984). Линейное и нелинейное программирование . Эддисон-Уэсли.
• Люенбергер, Дэвид (1969). Оптимизация методами векторного пространства . Wiley & Sons.
• Рокафеллар, Р. Т. (1970). Выпуклый анализ . Принстон: Princeton University Press.
• Томсон, Брайан (1994). Симметричные свойства действительных функций . CRC Press.
• Zălinescu, C. (2002). Выпуклый анализ в общих векторных пространствах . River Edge, NJ: World Scientific Publishing Co., Inc. стр. xx+367. ISBN 981-238-067-1. МР  1921556.

Внешние ссылки

• «Выпуклая функция (действительной переменной)», Энциклопедия математики , EMS Press , 2001 [1994]
• «Выпуклая функция (комплексной переменной)», Энциклопедия математики , EMS Press , 2001 [1994]