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

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

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

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

ОпределениеПравить

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

$f(\mathrm{\lambda <!--\; \lambda \; -->}x+(1-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->})y)\le <!--\; \le \; -->max(f(x),f(y)).$$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\ne <!--\; \ne \; -->y$$x\neq y$  и $\mathrm{\lambda <!--\; \lambda \; -->}\in <!--\; \in \; -->(0,1)$$\lambda \in (0,1)$  то функция называется строго квазивыпуклой.

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

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

$f(\mathrm{\lambda <!--\; \lambda \; -->}x+(1-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->})y)\ge <!--\; \ge \; -->min(f(x),f(y)).$$f(\lambda x+(1-\lambda )y)\geq \min {\big (}f(x),f(y){\big )}.$ 

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

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

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

ПримерыПравить

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

СвойстваПравить

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

$X_{\mathrm{\beta <!--\; \beta \; -->}}=\{x\in <!--\; \in \; -->X|f(x)⩽<!--\; ⩽\; -->\mathrm{\beta <!--\; \beta \; -->}\}$$X_{\beta }=\{x\in X|f(x)\leqslant \beta \}$  выпукло

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

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

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

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

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

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

$f(y)⩽<!--\; ⩽\; -->f(x)\Rightarrow <!--\; \Rightarrow \; -->⟨f^{{}^{\prime }}(x),y-<!--\; -\; -->x⟩⩽<!--\; ⩽\; -->0$$f(y)\leqslant f(x)\Rightarrow \left\langle f^{'}(x),y-x\right\rangle \leqslant 0$  для всех $x,y\in <!--\; \in \; -->X$$x,y\in X$ .

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

$⟨f^{{}^{\prime }}(x),y⟩=0\Rightarrow <!--\; \Rightarrow \; -->⟨f^{{}^{″}}(x)y,y⟩⩾<!--\; ⩾\; -->0,$$\left\langle f^{'}(x),y\right\rangle =0\Rightarrow \left\langle f^{''}(x)y,y\right\rangle \geqslant 0,$  для всех $x\in <!--\; \in \; -->X,y\in <!--\; \in \; -->{\mathbb{R}}^n$$x\in X,y\in \mathbb {R} ^{n}$ .

• Необходимые и достаточные условия квазивыпуклости и квазивогнутости можно также дать через так называемую окаймлённую матрицу Гессе. Для функции $f(x_1,\dots <!--\; \dots \; -->,x_m)$$f(x_{1},\ldots ,x_{m})$  определим для $1⩽<!--\; ⩽\; -->n⩽<!--\; ⩽\; -->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\{w_1{f}_1,\dots <!--\; \dots \; -->,w_n{f}_n\right\}$$f=\max \left\lbrace w_{1}f_{1},\ldots ,w_{n}f_{n}\right\rbrace$  где $w_i⩾<!--\; ⩾\; -->0$$w_{i}\geqslant 0$ 

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