Квазіопукла функція

Квазіопукла функція — узагальнення поняття опуклої функції, що знайшло широке використання в нелінійній оптимізації, зокрема при застосуванні оптимізації до питань економіки.

Квазіопукла функція, що не є опуклою

Функція, що не є квазіопуклою: множина точок, значення функції в яких не перевищує червоної пунктирної лінії не є опуклою.

Визначення

Нехай 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)$ є квазіопуклою).

Посилання

М.П. Моклячук Основи опуклого аналізу. К.:ТвіМС, 2004. – 240с.
М.П. Моклячук, НЕГЛАДКИЙ АНАЛІЗ ТА ОПТИМІЗАЦІЯ
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.