擬凸関数

凸解析と変分法という数学の分野において、擬凸関数とは、局所最小値を求めることに関して凸関数のように振る舞う関数であるが、実際には凸である必要はない関数である。非公式には、微分可能関数は、正の方向微分を持つ任意の方向において増加する場合、擬凸関数である。この性質は、近傍点だけでなく、関数の定義域全体で成立する必要がある。

正式な定義

有限次元ユークリッド空間の（空でない）凸開集合上に定義された微分可能関数を考える。この関数は、以下の性質が成り立つとき擬凸関数と呼ばれる： ^{[ 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 (y-x)\geq 0\Rightarrow f(y)\geq f(x).}$

同様に:

すべての人のために${\displaystyle x,y\in X:\quad f(y)<f(x)\Rightarrow \nabla f(x)\cdot (y-x)<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=y-x}$ ${\displaystyle f}$

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

プロパティ

他のタイプの「凸性」との関係

全ての凸関数は擬凸関数ですが、その逆は成り立ちません。例えば、 は擬凸関数ですが凸関数ではありません。同様に、全ての擬凸関数は準凸関数ですが、その逆は成り立ちません。なぜなら、 は準凸関数ですが擬凸関数ではないからです。これは、図式的に次のように要約できます。 ${\displaystyle f(x)=x+x^{3}}$ ${\displaystyle f(x)=x^{3}}$

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

関数 x^3（準凸関数だが擬凸関数ではない）と x^3 + x（擬凸関数であり、したがって準凸関数である）。どちらも凸関数ではない。

が擬凸でないことを確認するには、 におけるその微分を考えます。が擬凸で あれば、次の式が得られます。${\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 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 は任意の単位ベクトルである。上ディニ微分が正となる任意の方向において関数が増加する場合、その関数は擬凸関数と呼ばれる。より正確には、これは以下のように劣微分 によって特徴付けられる。 ${\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}$

参照

• 擬似凸性
• 凸関数
• 準凸関数
• Invex関数

注記

1. マンガサリアン 1965
2. マンガサリアン 1965
3. フロウダス＆パルダロス 2001
4. ラプサック 1991
5. 第5章：クレイヴン、BD（1988年）分数計画法、シグマ応用数学シリーズ第4巻、ベルリン：ヘルダーマン出版社、145ページ、ISBN 3-88538-404-3. MR  0949209 .
6. Kruk, Serge; Wolkowicz, Henry (1999). 「擬似線形計画法」. SIAM Review . 41 (4): 795– 805. Bibcode : 1999SIAMR..41..795K . doi : 10.1137/S0036144598335259 . JSTOR 2653207. MR 1723002 .  
7. Mathis, Frank H .; Mathis, Lenora Jane (1995). 「病院経営のための非線形計画アルゴリズム」. SIAM Review . 37 ( 2): 230– 234. doi : 10.1137/1037046 . JSTOR 2132826. MR 1343214. S2CID 120626738 .   
8. アンサリ、カムルル・ハサン、ラリタ、CS、メタ、モニカ (2013).一般化凸性、非滑らかな変分不等式、そして非滑らかな最適化. CRC Press. p. 107. ISBN 9781439868218. 2019年7月15日閲覧。
9. Mishra, Shashi K.; Giorgi, Giorgio (2008). Invexity and Optimization . Springer Science & Business Media. p. 39. ISBN 9783540785613. 2019年7月15日閲覧。

参考文献

• Floudas, Christodoulos A. ; Pardalos, Panos M. (2001)、「一般化単調多値マップ」、Encyclopedia of Optimization、Springer、p. 227、ISBN 978-0-7923-6932-5。
• Mangasarian, OL (1965年1月). 「擬似凸関数」. Journal of the Society for Industrial and Applied Mathematics, Series A: Control . 3 (2): 281– 290. doi : 10.1137/0303020 . ISSN  0363-0129 .。
• ラプサック, T. (1991-02-15). 「擬似線形関数について」.ヨーロッパオペレーションズリサーチジャーナル. 50 (3): 353– 360. doi : 10.1016/0377-2217(91)90267-Y . ISSN  0377-2217 .