Kvasikonvex funktion

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 mars 2017; kontroller kräver 3 redigeringar .

En kvasi-konvex funktion är en generalisering av begreppet en konvex funktion , som har funnit bred tillämpning inom olinjär optimering , i synnerhet när optimering tillämpas på ekonomi .

Definition

Låt X vara en konvex delmängd av . En funktion kallas kvasi-konvex eller unimodal om följande olikhet gäller för godtyckliga element och : $\mathbb {R} ^{n}$ $f:X\to \mathbb {R}$ $x,y\in X$ $\lambda \in [0,1]$

$f(\lambda x+(1-\lambda )y)\leq \max {\big (}f(x),f(y){\big )}.$

Om också: ${\displaystyle f(\lambda x+(1-\lambda )y)<\max {\big (}f(x),f(y){\big )))$

för och då sägs funktionen vara strikt kvasi-konvex . $x\neq y$ $\lambda \in(0,1)$

En funktion kallas kvasikonkav (strikt kvasikonkav) om den är kvasikonvex (strängt kvasikonvex). $f:X\to \mathbb {R}$ $-f$

På samma sätt är en funktion kvasikonkav if

f(\lambda x+(1-\lambda )y)\geq \min {\big (}f(x),f(y){\big )}.

och strikt kvasi-konkav om

f(\lambda x+(1-\lambda )y)>\min {\big (}f(x),f(y){\big )}.

En funktion som är både kvasi-konvex och kvasi-konkav kallas kvasi -linjär .

Exempel

En godtycklig konvex funktion är kvasikonvex, en godtycklig konkav funktion är kvasikonkav.
Funktionen är kvasilinjär på uppsättningen av positiva reella tal . $f(x)=\ln x$
Funktionen är kvasikonkav på mängden (mängden av par av icke-negativa tal) men är varken konvex eller konkav. ${\displaystyle f(x_{1},x_{2})=x_{1}x_{2))$ $\mathbb {R} _{+}^{2},$
Funktionen är kvasi-konvex och är varken konvex eller kontinuerlig . $x\mapsto \lfloor x\rfloor$

Egenskaper

Funktionen , där är en konvex mängd , är kvasikonvex om och endast om för hela mängden $f:X\to \mathbb {R}$ $X\subset \mathbb {R} ^{n}$ $\beta \in \mathbb {R} ,$

${\displaystyle X_{\beta }=\{x\in X|f(x)\leqslant \beta \))$ konvex

Bevis. Låt mängden vara konvex för vilken β som helst. Vi fixar två godtyckliga punkter och betraktar punkten Points at . Eftersom mängden är konvex, är , och därför, det vill säga, den olikhet som ges i definitionen uppfylld, och funktionen är kvasikonvex.

{\displaystyle X_{\beta ))

x_1, x_2\in X

x=\lambda x_{1}+(1-\lambda )x_{2},\quad \lambda \in (0,1).

{\displaystyle x_{1},x_{2}\in X_{\beta ))

{\displaystyle \beta =\max\{f(x_{1}),f(x_{2})\))

{\displaystyle X_{\beta ))

{\displaystyle \;x\in X_{\beta ))

f(x)\leqslant \beta =max\{f(x_{1}),f(x_{2})\},

Låt funktionen f vara kvasikonvex. För vissa fixar vi godtyckliga punkter Sedan . Eftersom X är en konvex mängd, då för vilken punkt som helst . Av definitionen av kvasi-konvexitet följer att , det vill säga . Otzhe, är en konvex uppsättning.

\beta \in \mathbb {R}

x_{1},x_{2}\in X_{\beta }.

\max\{f(x_{1}),f(x_{2})\}\leqslant \beta

\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

{\displaystyle x\in X_{\beta ))

{\displaystyle X_{\beta ))

En kontinuerlig funktion , där X är en konvex inställning i , är kvasikonvex om och endast om ett av följande villkor är uppfyllt: $f:X\to \mathbb {R}$ $\mathbb {R}$

f är icke-minskande;
f - icke-ökande;
det finns en punkt så att funktionen f för alla är icke-ökande, och för alla är funktionen f icke-minskande. $c\in X$ $t\in X,t\leqslant c,$ $t\in X,t\geqslant c,$

Differentiera kvasi-konvexa funktioner

Låta vara en differentierbar funktion på X , där är en öppen konvex uppsättning. Då är f kvasi-konvex på X om och endast om relationen gäller: $f:X\to \mathbb {R}$ $X\subset \mathbb {R} ^{n}$

f(y)\leqslant f(x)\Rightarrow \left\langle f^{'}(x),yx\right\rangle \leqslant 0

för alla .

x,y\in X

Låt f vara en två gånger differentierbar funktion. Om f är kvasi-konvex på X, är följande villkor uppfyllt:

\left\langle f^{'}(x),y\right\rangle =0\Rightarrow \left\langle f^{''}(x)y,y\right\rangle \geqslant 0,

för alla .

x\in X,y\in \mathbb {R} ^{n}

Nödvändiga och tillräckliga villkor för kvasi-konvexitet och kvasi-konkavitet kan också ges i termer av den så kallade kantade hessiska matrisen . För funktionen definierar vi determinanterna för : $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}}$

Då är påståendena sanna:

Om funktionen f är kvasikonvex på en mängd X , då är D n (x) ≤ 0 för alla n och alla x från X .
Om funktionen f är kvasikonkav på mängden X , då är D 1 (x) ≤ 0, D 2 (x) ≥ 0, …, (-1) m D m (x) ≤ 0 för alla x med X .
Om D n (x) ≤ 0 för alla n och alla x med X , då är funktionen f kvasikonvex på mängden X .
Om D 1 (x) ≤ 0, D 2 (x) ≥ 0, …, (-1) m D m (x) ≤ 0 för alla x med X , är funktionen f kvasikonkav på mängden X .

Operationer som bevarar kvasi-konvexitet

Maximum av viktade kvasikonvexa funktioner med icke-negativa vikter, dvs.

f=\max \left\lbrace w_{1}f_{1},\ldots ,w_{n}f_{n}\right\rbrace

var

w_{i}\geqslant 0

en komposition med en icke-minskande funktion (om är kvasi-konvex, är icke-minskande, så är den kvasi-konvex). $g:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ $h:\mathbb {R} \rightarrow \mathbb {R}$ $f=h\circ g$
minimering (om f(x, y) är kvasikonvex, C är en konvex mängd, då är den kvasikonvex). $h(x)=\inf _{y\in C}f(x,y)$

Länkar

Stephen Boyd, Lieven Vandenberghe Convex Optimization Arkiverad 13 juli 2017 på Wayback Machine

Litteratur

Alpha C Chiang, Fundamental Methods of Mathematical Economics, tredje upplagan, McGraw Hill Book Company, 1984.