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

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

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

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

Визначення

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

Посилання

• М.П. Моклячук Основи опуклого аналізу. [ 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.