Квазивыпуклая функция

Квазивыпуклая функция, не являющаяся выпуклой

Функция, не являющаяся квазивыпуклой: множество точек, значение функции в которых не превышает красной пунктирной линии не является выпуклой.

Квазивыпуклая функция — обобщение понятия выпуклой функции, нашедшее широкое применение в нелинейной оптимизации, в частности, при применении оптимизации к вопросам экономики.

Определение

Пусть 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 : X \to \R$ — дифференцируемая функция на X, где $X \subset \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 \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 : \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)$ является квазивыпуклой).

Ссылки

• Stephen Boyd, Lieven Vandenberghe Convex Optimization

Литература

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