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

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

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

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

Определение

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

$f(\lambda x+(1-\lambda )y)\leq \max {\big (}f(x),f(y){\big )}.$

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

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

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

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

$f(\lambda x+(1-\lambda )y)\geq \min {\big (}f(x),f(y){\big )}.$

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

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

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

Примеры

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

Свойства

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

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

Доказательство. Пусть множество $X_{\beta }$ выпуклое для любого β. Зафиксируем две произвольные точки $x_{1},x_{2}\in X$ и рассмотрим точку $x=\lambda x_{1}+(1-\lambda )x_{2},\quad \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)\leqslant \beta =max\{f(x_{1}),f(x_{2})\},$ то есть выполняется неравенство, приведённое в определении, и функция является квазивыпуклой.

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

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

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

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

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

$f(y)\leqslant f(x)\Rightarrow \left\langle f^{'}(x),y-x\right\rangle \leqslant 0$ для всех $x,y\in X$.

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

$\left\langle f^{'}(x),y\right\rangle =0\Rightarrow \left\langle f^{''}(x)y,y\right\rangle \geqslant 0,$ для всех $x\in X,y\in \mathbb {R} ^{n}$.

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

$D_{n}={\begin{vmatrix}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}}}\\\\\vdots &\vdots &\vdots &\ddots &\vdots \\\\{\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{vmatrix}}$

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

• Если функция 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 \left\lbrace w_{1}f_{1},\ldots ,w_{n}f_{n}\right\rbrace$ где $w_{i}\geqslant 0$

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

Ссылки

• Stephen Boyd, Lieven Vandenberghe Convex Optimization Архивная копия от 13 июля 2017 на Wayback Machine

Литература

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