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

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

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

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

Визначення

Нехай X — опукла підмножина ${ℝ}^n$. Функція $f:X\to ℝ$ називається квазіопуклою або унімодальною, якщо для довільних елементів $x,y\in X$ і $\lambda \in [0,1]$ виконується нерівність:

$f(\lambda x+(1-\lambda )y)\le \max (f(x),f(y)).$

Якщо також: $f(\lambda x+(1-\lambda )y)<\max (f(x),f(y))$

для $x\ne y$ і $\lambda \in (0,1)$ то функція називається строго квазіопуклою.

Функція $f:X\to ℝ$ називається квазіувігнутою (строго квазіувігнутою), якщо $-f$ є квазіопуклою (строго квазіопуклою).

Еквівалентно, функція є квазіувігнутою, якщо

$f(\lambda x+(1-\lambda )y)\ge \min (f(x),f(y)).$

і строго квазіувігнутою якщо

$f(\lambda x+(1-\lambda )y)>\min (f(x),f(y)).$

Функція, яка одночасно є квазіопуклою та квазіувігнутою називається квазілінійною.

Приклади

• Довільна опукла функція є квазіопуклою, довільна увігнута функція є квазіувігнутою.
• Функція $f(x)=\ln x$ є квазілінійною на множині додатних дійсних чисел.
• Функція $f(x_1,x_2)=x_1{x}_2$ є квазувігнутою на множині ${ℝ}_{+}^2,$ (множина пар невід'ємних чисел) але не є ні опуклою, ні увігнутою.
• Функція $x\mapsto \lfloor x\rfloor$ є квазіопуклою і не є ні опуклою, ні неперервною.

Властивості

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

$X_{\beta }=\{x\in X|f(x)⩽\beta \}$

Доведення. Нехай множина $X_{\beta }$ опукла для будь-якого β. Зафіксуємо дві довільні точки $x_1,x_2\in X$ та розглянемо точку $x=\lambda x_1+(1-\lambda )x_2,\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)⩽\beta =max\{f(x_1),f(x_2)\},$ тобто виконується нерівність у визначенні і функція є квазіопуклою.

Нехай функція f квазіопукла. Для деякого $\beta \in ℝ$ зафіксуємо довільні точки $x_1,x_2\in X_{\beta }.$ Тоді $\max \{f(x_1),f(x_2)\}⩽\beta$. Оскільки X — опукла множина, то для будь-якого $\lambda \in (0,1)$ точка $x=\lambda x_1+(1-\lambda )x_2\in X$. З означення квазіопуклості випливає, що $f(x)⩽max\{f(x_1),f(x_2)\}⩽\beta$, тобто $x\in X_{\beta }$. Отже, $X_{\beta }$ — опукла множина.

• Неперервна функція $f:X\to ℝ$, де X — опукла множина в $ℝ$, квазіопукла тоді і тільки тоді, коли виконується одна з таких умов:

1. f — неспадна;
2. f — незростаюча;
3. існує така точка $c\in X$, що для всіх $t\in X,t⩽c,$ функція f незростаюча, і для всіх $t\in X,t⩾c,$ функція f неспадна.

Диференційовні квазіопуклі функції

• Нехай $f:X\to ℝ$ — диференційована функція на X, де $X\subset {ℝ}^n$ — відкрита опукла множина. Тоді f квазіопукла на X тоді і тільки тоді, коли справджується співвідношення:

$f(y)⩽f(x)\Rightarrow ⟨f^{\text{'}}(x),y-x⟩⩽0$ для всіх $x,y\in X$.

• Нехай f — двічі диференційовна функція. Якщо f квазіопукла на X, то виконується умова:

$⟨f^{\text{'}}(x),y⟩=0\Rightarrow ⟨f^{{\text{'}}^{\prime }}(x)y,y⟩⩾0,$ для всіх $x\in X,y\in {ℝ}^n$.

• Необхідні і достатні умови квазіопуклості і квазіувігнутості можна також дати через так звану обрамлену матрицю Гессе. Для функції $f(x_1,\dots ,x_m)$ визначимо для $1⩽n⩽m$ визначники:

$D_n=\left|\begin{array}{ccccc}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}\\ \\ ⋮& ⋮& ⋮& \ddots & ⋮\\ \\ \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{array}\right|$

Тоді справедливі твердження:

• Якщо функція 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 \{w_1{f}_1,\dots ,w_n{f}_n\}$ де $w_i⩾0$

• композиція з неспадною функцією (якщо $g:{ℝ}^n\to ℝ$ — квазіопукла, $h:ℝ\to ℝ$ — неспадна, тоді $f=h\circ g$ є квазіопуклою).
• мінімізація (якщо f(x,y) є квазіопуклою, C — опукла множина, тоді $h(x)=\underset{y\in C}{\inf }f(x,y)$ є квазіопуклою).

Посилання

• М.П. Моклячук Основи опуклого аналізу. Шаблон:Webarchive К.:ТвіМС, 2004. – 240с.
• М.П. Моклячук, НЕГЛАДКИЙ АНАЛІЗ ТА ОПТИМІЗАЦІЯ Шаблон:Webarchive
• Stephen Boyd, Lieven Vandenberghe Convex Optimization Шаблон:Webarchive

Література

• Alpha C Chiang, "Fundamental Methods of Mathematical Economics, Third Edition", McGraw Hill Book Company, 1984.