WikiSort.ru - Не сортированное

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

Определение

Пусть 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.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии