擬似凸関数

数学の分野である凸解析と変分法において、擬凸関数とは、局所的最小値を見つけることに関しては凸関数のように動作するが、実際には凸である必要はない関数のことである。非公式には、微分可能関数は、正の方向導関数を持つ任意の方向に増加する場合、擬凸である。この特性は、近傍点だけでなく、関数ドメイン全体で保持される必要がある。

有限次元ユークリッド空間の（空でない）凸開集合上に定義された微分可能関数を考える。この関数は、次の性質が成り立つとき擬凸関数と呼ばれる： ^[1]${\displaystyle f:X\subseteq \mathbb {R} ^{n}\rightarrow \mathbb {R} }$ ${\displaystyle X}$ ${\displaystyle \mathbb {R} ^{n}}$

すべてに対して。${\displaystyle x,y\in X:\quad \nabla f(x)\cdot (yx)\geq 0\Rightarrow f(y)\geq f(x)}$

同様に:

すべてに対して。${\displaystyle x,y\in X:\quad f(y)<f(x)\Rightarrow \nabla f(x)\cdot (yx)<0}$

ここで、の勾配は次のように定義されます。${\displaystyle \nabla f}$${\displaystyle f}$${\displaystyle \nabla f=\left({\frac {\partial f}{\partial x_{1}}},\dots ,{\frac {\partial f}{\partial x_{n}}}\right).}$

定義は、ベクトル によって与えられた方向におけるの方向微分によっても表されることに注意してください。これは、が微分可能であるため、この方向微分は次のように与えられるためです。 ${\displaystyle f}$${\displaystyle v=yx}$${\displaystyle f}$

${\displaystyle {\frac {\partial f}{\partial v}}(x)=\nabla f(x)\cdot v=\nabla f(x)\cdot (yx).}$

すべての凸関数は擬凸ですが、その逆は真ではありません。たとえば、関数は擬凸ですが凸ではありません。同様に、すべての擬凸関数は準凸ですが、その逆は真ではありません。関数は準凸ですが擬凸ではないからです。これは次のように概略的にまとめることができます。 ${\displaystyle f(x)=x+x^{3}}$${\displaystyle f(x)=x^{3}}$

凸 擬凸準凸${\displaystyle \Rightarrow}$${\displaystyle \Rightarrow}$

が擬凸でないことを確認するには、 におけるその導関数を考えます。が擬凸であれば、次の式が得られます。 ${\displaystyle f(x)=x^{3}}$${\displaystyle x=0}$${\displaystyle f^{\prime }(0)=0}$${\displaystyle f(x)=x^{3}}$

${\displaystyle f^{\prime }(0)(y-0)=0\geq 0\Rightarrow f(y)\geq f(0),\quad \forall \,y\in \mathbb {R} .}$

特に、 については真であるはずです。しかし、次の通りではありません: 。 ${\displaystyle y=-1}$${\displaystyle f(-1)=(-1)^{3}=-1<f(0)=0}$

任意の微分可能関数に対して、フェルマーの定理の最適性の必要条件が成り立ちます。これは、 が開領域で で極小値を持つ場合、は の定常点である必要があります(つまり、)。 ${\displaystyle f}$${\displaystyle x^{*}}$${\displaystyle x^{*}}$${\displaystyle f}$${\displaystyle \nabla f(x^{*})=0}$

擬凸性は最適化の分野で大きな関心を集めています。なぜなら、任意の擬凸関数に対して逆も成り立つからです。つまり、^[2]が擬凸関数の停留点である場合、 は で大域的最小値を持ちます。また、結果は（局所的だけでなく）大域的最小値を保証することにも注意してください。 ${\displaystyle x^{*}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle x^{*}}$

この最後の結果は凸関数にも当てはまりますが、準凸関数には当てはまりません。たとえば、準凸関数を考えてみましょう。

${\displaystyle f(x)={\frac {e^{x}}{x^{2}+1}}+{\frac {1}{e^{x}}}}$。

この関数は擬凸関数ではありませんが、準凸関数です。また、 のとき、点は の臨界点です。ただし、は で大域的最小値を持ちません(局所的最小値さえも持ちません)。 ${\displaystyle x=0}$${\displaystyle f}$${\displaystyle f^{\prime }(0)=0}$${\displaystyle f}$${\displaystyle x=0}$

最後に、擬凸関数には臨界点がない場合があることに注意してください。たとえば、擬凸関数 を考えます。この関数の導関数は常に正です。 ${\displaystyle f(x)=x^{3}+x}$${\displaystyle f^{\prime }(x)=3x^{2}+1>0,\,\forall \,x\in \mathbb {R} }$

擬似凸関数だが凸関数ではない関数の例は次の通りです。図は、 の場合のこの関数を示しています。この例は、次のように 2 つの変数に一般化できます。 ${\displaystyle f(x)={\frac {x^{2}}{x^{2}+k}},\,k>0.}$${\displaystyle k=0.2}$

${\displaystyle f(x)={\frac {x^{2}+y^{2}}{x^{2}+y^{2}+k}},\,k>0.}$

前の例を修正すると、凸関数でも擬似凸関数でもないが、準凸関数が得られます。

${\displaystyle f(x)={\frac {|x|^{p}}{|x|^{p}+k}},\,k>0,\,p\in (0,1).}$

図は、 の場合のこの関数を示しています。 見てわかるように、この関数は凹面であるため凸ではなく、 で微分不可能であるため擬凸でもありません。 ${\displaystyle k=0.5,p=0.6}$${\displaystyle x=0}$

擬凸性の概念は、次のように微分不可能な関数に一般化できる。^[3]任意の関数が与えられたとき、上ディニ導関数を次のように定義できる。 ${\displaystyle f:X\rightarrow \mathbb {R} }$${\displaystyle f}$

${\displaystyle f^{+}(x,u)=\limsup _{h\to 0^{+}}{\frac {f(x+hu)-f(x)}{h}};}$

ここで、u は任意の単位ベクトルです。上側の Dini 導関数が正である任意の方向に増加する場合、関数は擬凸関数と呼ばれます。より正確には、これは次のように部分微分 の観点から特徴付けられます。 ${\displaystyle \partial f}$

すべて に対して:が となる場合、すべて に対して となる。${\displaystyle x,y\in X}$${\displaystyle x^{*}\in \partial f(x)}$${\displaystyle \langle x^{*},y-x\rangle \geq 0}$${\displaystyle f(x)\leq f(z)}$${\displaystyle z\in [x,y]}$

ここで、 はxとyに隣接する線分を表します。 ${\displaystyle [x,y]}$

あ擬似凹関数は、その負の部分が擬似凸となる関数である。擬似線型関数は擬似凸関数かつ擬似凹関数である。^[4]例えば、線形分数計画法は擬似線型目的関数と線形不等式制約をジョージ・B・ダンツィグの単体法の変種によって解くことができる。^[5][6][7]

ベクトル値関数 が与えられた場合、より一般的な概念である-擬似凸性^{[8] [9]}と-擬似線形性があります。ここで、古典的な擬似凸性と擬似線形性は の場合に関係します。 ${\displaystyle \eta }$${\displaystyle \eta }$${\displaystyle \eta }$${\displaystyle \eta (x,y)=y-x}$

• 擬似凸性
• 凸関数
• 準凸関数
• インベックス関数

• Floudas, Christodoulos A. ; Pardalos, Panos M. (2001)、「一般化単調多値マップ」、Encyclopedia of Optimization、Springer、p. 227、ISBN 978-0-7923-6932-5。
• マンガサリアン、OL（1965年1月）。 「擬似凸関数」。工業および応用数学協会のジャーナル、シリーズ A。3 (2): 281-290。土井：10.1137/0303020。ISSN  0363-0129。。
• Rapcsak, T. (1991-02-15). 「擬似線形関数について」.ヨーロッパオペレーションズリサーチジャーナル. 50 (3): 353–360. doi :10.1016/0377-2217(91)90267-Y. ISSN  0377-2217.