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

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

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

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

Визначення

Нехай 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}$, квазіопукла тоді і тільки тоді, коли виконується одна з таких умов:

1. f — неспадна;
2. f — незростаюча;
3. існує така точка $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)$ є квазіопуклою).

Посилання

• М.П. Моклячук Основи опуклого аналізу. [Архівовано 5 Липня 2016 у Wayback Machine.] К.:ТвіМС, 2004. – 240с.
• М.П. Моклячук, НЕГЛАДКИЙ АНАЛІЗ ТА ОПТИМІЗАЦІЯ [Архівовано 4 Березня 2016 у Wayback Machine.]
• 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.