Русская Википедия:Квазивыпуклая функция

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Quasiconvex function.png

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

Файл:Nonquasiconvex function.png

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

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

Определение

Пусть X — выпуклое подмножество <math>\R^n</math>. Функция <math>f : X \to \R</math> называется квазивыпуклой или унимодальной, если для произвольных элементов <math>x,y \in X</math> и <math>\lambda \in [0,1]</math> выполняется неравенство:

<math>f(\lambda x + (1 - \lambda)y)\leq\max\big(f(x),f(y)\big).</math>

Если также: <math>f(\lambda x + (1 - \lambda)y)<\max\big(f(x),f(y)\big)</math>

для <math>x \neq y</math> и <math>\lambda \in (0,1)</math> то функция называется строго квазивыпуклой.

Функция <math>f : X \to \R</math> называется квазивогнутой (строго квазивогнутой), если <math>-f</math> является квазивыпуклой (строго квазивыпуклой).

Аналогично, функция является квазивогнутой, если

<math>f(\lambda x + (1 - \lambda)y)\geq\min\big(f(x),f(y)\big).</math>

и строго квазивогнутой если

<math>f(\lambda x + (1 - \lambda)y)>\min\big(f(x),f(y)\big).</math>

Функция, которая одновременно является квазивыпуклой и квазивогнутой, называется квазилинейной.

Примеры

• Произвольная выпуклая функция является квазивыпуклой, произвольная вогнутая функция является квазивогнутой.
• Функция <math>f(x) = \ln x</math> является квазилинейной на множестве положительных действительных чисел.
• Функция <math>f(x_1, x_2) = x_1x_2</math> является квазивогнутой на множестве <math>\R_+^2,</math> (множество пар неотрицательных чисел) но не является ни выпуклой, ни вогнутой.
• Функция <math>x\mapsto \lfloor x\rfloor</math> является квазивыпуклой и не является ни выпуклой, ни непрерывной.

Свойства

• Функция <math>f : X \to \R</math>, где <math>X \subset \R^n</math> — выпуклое множество, квазивыпуклая тогда и только тогда, когда для всех <math>\beta \in \R,</math> множество

<math>X_\beta = \{x \in X | f(x) \leqslant \beta \}</math> выпукло

Доказательство. Пусть множество <math>X_\beta</math> выпуклое для любого β. Зафиксируем две произвольные точки <math>x_1, x_2 \in X</math> и рассмотрим точку <math>x = \lambda x_1 + (1 - \lambda) x_2, \quad \lambda \in (0,1).</math> Точки <math>x_1, x_2 \in X_\beta</math> при <math>\beta = \max \{f(x_1),f(x_2)\}</math>. Поскольку множество <math>X_\beta</math> выпуклое, то<math> \;x \in X_\beta</math>, а, значит, <math>f(x) \leqslant \beta = max\{f(x_1),f(x_2)\},</math> то есть выполняется неравенство, приведённое в определении, и функция является квазивыпуклой.

Пусть функция f квазивыпуклая. Для некоторого <math>\beta \in \R</math> зафиксируем произвольные точки <math>x_1, x_2 \in X_\beta.</math> Тогда <math>\max \{f(x_1),f(x_2)\} \leqslant \beta</math>. Поскольку X — выпуклое множество, то для любого <math>\lambda \in (0,1)</math> точка <math>x = \lambda x_1 + (1 - \lambda) x_2 \in X</math>. Из определения квазивыпуклости следует, что <math>f(x) \leqslant max\{f(x_1),f(x_2)\} \leqslant \beta</math>, то есть <math>x \in X_\beta</math>. Отже, <math>X_\beta</math> — выпуклое множество.

• Непрерывная функция <math>f : X \to \R</math>, где X — выпуклое множество в <math>\R</math>, квазивыпуклая тогда и только тогда, когда выполняется одно из следующих условий:

1. f — неубывающая;
2. f — невозрастающая;
3. существует такая точка <math>c \in X</math>, что для всех <math>t \in X, t \leqslant c,</math> функция f невозрастающая, и для всех <math>t \in X, t \geqslant c,</math> функция f неубывающая.

Дифференцируемые квазивыпуклые функции

• Пусть <math>f : X \to \R</math> — дифференцируемая функция на X, где <math>X \subset \R^n</math> — открытое выпуклое множество. Тогда f квазивыпукла на X тогда и только тогда, когда выполняется соотношение:

<math>f(y) \leqslant f(x) \Rightarrow \left \langle f^'(x), y - x \right \rangle \leqslant 0</math> для всех <math>x,y \in X</math>.

• Пусть f — дважды дифференцируемая функция. Если f квазивыпуклая на X, то выполняется условие:

<math>\left \langle f^'(x), y \right \rangle = 0 \Rightarrow \left \langle f^{}(x)y , y \right \rangle \geqslant 0,</math> для всех <math>x \in X, y \in \R^n</math>.

• Необходимые и достаточные условия квазивыпуклости и квазивогнутости можно также дать через так называемую окаймлённую матрицу Гессе. Для функции <math>f (x_1, \ldots, x_m)</math> определим для <math>1 \leqslant n \leqslant m</math> определители:

<math>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}</math>

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

• Если функция 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.

Операции, сохраняющие квазивыпуклость

• Максимум взвешенных квазивыпуклых функций с неотрицательными весами, то есть

<math>f = \max \left\lbrace w_1 f_1 , \ldots , w_n f_n \right\rbrace</math> где <math>w_i \geqslant 0</math>

• композиция с неубывающей функцией (если <math>g : \R^{n} \rightarrow \R</math> — квазивыпуклая, <math>h : \R \rightarrow \R</math> — неубывающая, тогда <math>f = h \circ g</math> является квазивыпуклой).
• минимизация (если f(x, y) является квазивыпуклой, C — выпуклое множество, тогда <math>h(x) = \inf_{y \in C} f(x,y)</math> является квазивыпуклой).

Ссылки

• Stephen Boyd, Lieven Vandenberghe Convex Optimization Шаблон:Wayback

Литература

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