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

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

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

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

Определение

Пусть 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}$ , квазивыпуклая тогда и только тогда, когда выполняется одно из следующих условий:

f — неубывающая;
f — невозрастающая;
существует такая точка $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

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.