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

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

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


Определение[править | править вики-текст]

Пусть 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.