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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

Примеры

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

Свойства

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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.

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

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

${\displaystyle f=\max \left\lbrace w_{1}f_{1},\ldots ,w_{n}f_{n}\right\rbrace }$ где ${\displaystyle w_{i}\geqslant 0}$

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