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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Квазіопукла функція, що не є опуклою
Функція, що не є квазіопуклою: множина точок, значення функції в яких не перевищує червоної пунктирної лінії не є опуклою.

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

Визначення[ред.ред. код]

Нехай Xопукла підмножина \R^n. Функція f : X \to \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 \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_1x_2 є квазувігнутою на множині \R_+^2, (множина пар невід'ємних чисел) але не є ні опуклою, ні увігнутою.
  • Функція x\mapsto \lfloor x\rfloor є квазіопуклою і не є ні опуклою, ні неперервною.

Властивості[ред.ред. код]

  • Функція f : X \to \R, де X \subset \R^nопукла множина, квазіопукла тоді і тільки тоді, коли для всіх \beta \in \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 \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 \R, де X — опукла множина в \R, квазіопукла тоді і тільки тоді, коли виконується одна з таких умов:
  1. f — неспадна;
  2. f — незростаюча;
  3. існує така точка c \in X, що для всіх t \in X, t \leqslant c, функція f незростаюча, і для всіх t \in X, t \geqslant c, функція f неспадна.

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

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 \R^n.

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, тоді Dn(x) ≤ 0 для всіх n і всіх x з X.
  • Якщо функція f квазіувігнута на множині X, тоді D1(x) ≤ 0, D2(x) ≥ 0, ..., (-1)mDm(x) ≤ 0 для всіх x з X.
  • Якщо Dn(x) ≤ 0 для всіх n і всіх x з X, то функція f квазіопукла на множині X.
  • Якщо D1(x) ≤ 0, D2(x) ≥ 0, ..., (-1)mDm(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 : \R^{n} \rightarrow \R — квазіопукла, h : \R \rightarrow \R — неспадна, тоді f = h \circ g є квазіопуклою).
  • мінімізація (якщо f(x,y) є квазіопуклою, C — опукла множина, тоді h(x) = \inf_{y \in C} f(x,y) є квазіопуклою).

Посилання[ред.ред. код]

Література[ред.ред. код]

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