Квазивыпуклая функция

Квазивыпуклая функция, не являющаяся выпуклой

Функция, не являющаяся квазивыпуклой: множество точек абсциссы, значение функции в которых не превышает красной пунктирной линии, не является связным.

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

Определение

Пусть X — выпуклое подмножество ${ℝ}^n$. Функция $f:X\to ℝ$ называется квазивыпуклой или унимодальной, если для произвольных элементов $x,y\in X$ и $\lambda \in [0,1]$ выполняется неравенство:

$f(\lambda x+(1-\lambda )y)\le \max (f(x),f(y)).$

Если также: $f(\lambda x+(1-\lambda )y)<\max (f(x),f(y))$

для $x\ne y$ и $\lambda \in (0,1)$ то функция называется строго квазивыпуклой.

Функция $f:X\to ℝ$ называется квазивогнутой (строго квазивогнутой), если $-f$ является квазивыпуклой (строго квазивыпуклой).

Аналогично, функция является квазивогнутой, если

$f(\lambda x+(1-\lambda )y)\ge \min (f(x),f(y)).$

и строго квазивогнутой если

$f(\lambda x+(1-\lambda )y)>\min (f(x),f(y)).$

Функция, которая одновременно является квазивыпуклой и квазивогнутой, называется квазилинейной.

Примеры

• Произвольная выпуклая функция является квазивыпуклой, произвольная вогнутая функция является квазивогнутой.
• Функция $f(x)=\ln x$ является квазилинейной на множестве положительных действительных чисел.
• Функция $f(x_1,x_2)=x_1{x}_2$ является квазивогнутой на множестве ${ℝ}_{+}^2,$ (множество пар неотрицательных чисел) но не является ни выпуклой, ни вогнутой.
• Функция $x\mapsto \lfloor x\rfloor$ является квазивыпуклой и не является ни выпуклой, ни непрерывной.

Свойства

• Функция $f:X\to ℝ$, где $X\subset {ℝ}^n$ — выпуклое множество, квазивыпуклая тогда и только тогда, когда для всех $\beta \in ℝ,$ множество

$X_{\beta }=\{x\in X|f(x)⩽\beta \}$ выпукло

Доказательство. Пусть множество $X_{\beta }$ выпуклое для любого β. Зафиксируем две произвольные точки $x_1,x_2\in X$ и рассмотрим точку $x=\lambda x_1+(1-\lambda )x_2,\lambda \in (0,1).$ Точки $x_1,x_2\in X_{\beta }$ при $\beta =\max \{f(x_1),f(x_2)\}$. Поскольку множество $X_{\beta }$ выпуклое, то$x\in X_{\beta }$, а, значит, $f(x)⩽\beta =max\{f(x_1),f(x_2)\},$ то есть выполняется неравенство, приведённое в определении, и функция является квазивыпуклой.

Пусть функция f квазивыпуклая. Для некоторого $\beta \in ℝ$ зафиксируем произвольные точки $x_1,x_2\in X_{\beta }.$ Тогда $\max \{f(x_1),f(x_2)\}⩽\beta$. Поскольку X — выпуклое множество, то для любого $\lambda \in (0,1)$ точка $x=\lambda x_1+(1-\lambda )x_2\in X$. Из определения квазивыпуклости следует, что $f(x)⩽max\{f(x_1),f(x_2)\}⩽\beta$, то есть $x\in X_{\beta }$. Отже, $X_{\beta }$ — выпуклое множество.

• Непрерывная функция $f:X\to ℝ$, где X — выпуклое множество в $ℝ$, квазивыпуклая тогда и только тогда, когда выполняется одно из следующих условий:

1. f — неубывающая;
2. f — невозрастающая;
3. существует такая точка $c\in X$, что для всех $t\in X,t⩽c,$ функция f невозрастающая, и для всех $t\in X,t⩾c,$ функция f неубывающая.

Дифференцируемые квазивыпуклые функции

• Пусть $f:X\to ℝ$ — дифференцируемая функция на X, где $X\subset {ℝ}^n$ — открытое выпуклое множество. Тогда f квазивыпукла на X тогда и только тогда, когда выполняется соотношение:

$f(y)⩽f(x)\Rightarrow ⟨f^{\text{'}}(x),y-x⟩⩽0$ для всех $x,y\in X$.

• Пусть f — дважды дифференцируемая функция. Если f квазивыпуклая на X, то выполняется условие:

$⟨f^{\text{'}}(x),y⟩=0\Rightarrow ⟨f^{{\text{'}}^{\prime }}(x)y,y⟩⩾0,$ для всех $x\in X,y\in {ℝ}^n$.

• Необходимые и достаточные условия квазивыпуклости и квазивогнутости можно также дать через так называемую окаймлённую матрицу Гессе. Для функции $f(x_1,\dots ,x_m)$ определим для $1⩽n⩽m$ определители:

$D_n=\left|\begin{array}{ccccc}0& \frac{\partial f}{\partial x_1}& \frac{\partial f}{\partial x_2}& \cdots & \frac{\partial f}{\partial x_n}\\ \\ \frac{\partial f}{\partial x_1}& \frac{{\partial }^{2}f}{\partial x_1^2}& \frac{{\partial }^{2}f}{\partial x_1\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_1\partial x_n}\\ \\ \frac{\partial f}{\partial x_2}& \frac{{\partial }^{2}f}{\partial x_2\partial x_1}& \frac{{\partial }^{2}f}{\partial x_2^2}& \cdots & \frac{{\partial }^{2}f}{\partial x_2\partial x_n}\\ \\ ⋮& ⋮& ⋮& \ddots & ⋮\\ \\ \frac{\partial f}{\partial x_n}& \frac{{\partial }^{2}f}{\partial x_n\partial x_1}& \frac{{\partial }^{2}f}{\partial x_n\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right|$

Тогда справедливы утверждения:

• Если функция f квазивыпукла на множестве X, тогда D_n(x) ≤ 0 для всех n и всех x из X.
• Если функция f квазивогнута на множестве X, тогда D₁(x) ≤ 0, D₂(x) ≥ 0, …, (-1)^mD_m(x) ≤ 0 для всех x с X.
• Если D_n(x) ≤ 0 для всех n и всех x с X, то функция f квазивыпуклая на множестве X.
• Если D₁(x) ≤ 0, D₂(x) ≥ 0, …, (-1)^mD_m(x) ≤ 0 для всех x с X, функция f квазивогнута на множестве X.

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

• Максимум взвешенных квазивыпуклых функций с неотрицательными весами, то есть

$f=\max \{w_1{f}_1,\dots ,w_n{f}_n\}$ где $w_i⩾0$

• композиция с неубывающей функцией (если $g:{ℝ}^n\to ℝ$ — квазивыпуклая, $h:ℝ\to ℝ$ — неубывающая, тогда $f=h\circ g$ является квазивыпуклой).
• минимизация (если f(x, y) является квазивыпуклой, C — выпуклое множество, тогда $h(x)=\underset{y\in C}{\inf }f(x,y)$ является квазивыпуклой).

Ссылки

• Stephen Boyd, Lieven Vandenberghe Convex Optimization Шаблон:Wayback

Литература

• Alpha C Chiang, «Fundamental Methods of Mathematical Economics, Third Edition», McGraw Hill Book Company, 1984.