準凸関数

準凸関数（じゅんとつかんすう、英: Quasiconvex function）とは、実ベクトル空間の凸集合上で定義される実数値関数であり、任意の集合 $(-\infty ,a)$ の逆像が凸集合になるものである。1変数の関数においては、曲線の任意の区間において最も高い点は区間の端点である。準凸関数の負の関数は準凹関数（quasiconcave function）と呼ばれる。

準凸性は凸性よりも一般的な性質であり、すべての凸関数は準凸関数でもあるが、準凸関数のすべてが凸関数であるわけではない。単峰性のある1変数関数は準凸または準凹であるが、複数の変数をもつ関数では必ずしもそうとは限らない。例えば、2次元のローゼンブロック関数（英語版）は単峰性を持つが準凸ではなく、星型集合の劣水準集合を持つ関数は、準凸でなくても単峰性を持ちうる。

定義と性質

凸部分集合 $S$ 上で定義された関数 $f:S\to \mathbb {R}$ が準凸であるとは、任意の $x,y\in S$ および $\lambda \in [0,1]$ に対して

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

が成立することである。言い換えれば、関数 $f$ が、2点 $x$ と $y$ の間の点の値が、常に $x$ と $y$ の値の最大値を超えないならば、 $f$ は準凸である。このとき、 $x$ 、 $y$ 、およびその中間点は直線上の点でもよいし、より一般に n 次元空間内の点でもよい。

準凸関数 $f(x)$ を定義する別の方法（序論参照）は、各劣水準集合 $S_{\alpha }(f)=\{x\mid f(x)\leq \alpha \}$ が凸集合であることを要請することである。

さらに、もし

f(\lambda x+(1-\lambda )y)<\max {\big \{}f(x),f(y){\big \}}

が任意の $x\neq y$ および $\lambda \in (0,1)$ に対して成立するならば、 $f$ は狭義準凸関数（strictly quasiconvex）である。すなわち、狭義準凸性とは、2点の中間点の関数値が必ず一方の関数値よりも小さいことを要請する。

準凹関数とは、その負の関数が準凸である関数のことであり、狭義準凹関数はその負が狭義準凸である関数である。すなわち関数 $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 \}}

（狭義）準凸関数は（狭義）凸な下等高線集合を持ち、（狭義）準凹関数は（狭義）凸な上等高線集合を持つ。

準凸かつ準凹である関数は準線形関数（quasilinear function）と呼ばれる。

特別な場合として、 $S\subset \mathbb {R}$ の場合には単峰性と一致し、局所的に最大値を持つ。

応用

準凸関数は解析学、数理最適化、さらにゲーム理論や経済学において応用される。

数理最適化

非線形最適化において、準凸計画法は準凸関数の最小値に収束する（もし存在すれば）反復法を研究する。準凸計画法は凸最適化の一般化である^[1]。準凸計画法は、原問題のラグランジュ双対問題が与える凸閉包よりも厳密な境界を与える「代替的」双対問題の解法に用いられる^[2]。理論的には、準凸計画法や凸計画法は、問題の次元や許容誤差の逆数に対して多項式時間で解けることが知られている^[3]。しかし、そのような理論的に「効率的な」手法は、古典的な劣勾配法に由来する「発散級数型」のステップ幅規則を利用しており、これは現代的な劣勾配法、非滑らかなフィルタ法などに比べると遅い。

経済学と偏微分方程式：ミニマックス定理

ミクロ経済学では、準凹な効用関数は消費者が凸選好を持つことを意味する。準凸関数はゲーム理論、産業組織論、一般均衡理論においても重要であり、特にシオンのミニマックス定理の応用において現れる。シオンの定理はジョン・フォン・ノイマンのミニマックス定理（英語版）を一般化したものであり、偏微分方程式の理論においても用いられる。

準凸性の保存

準凸性を保存する操作

準凸関数の最大値（すなわち $f=\max \left\lbrace f_{1},\ldots ,f_{n}\right\rbrace$ ）は準凸である。同様に、狭義準凸関数の最大値は狭義準凸である^[4]。同様に、準凹関数の最小値は準凹であり、狭義準凹関数の最小値は狭義準凹である。
単調非減少関数との合成： $g:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ が準凸であり、 $h:\mathbb {R} \rightarrow \mathbb {R}$ が単調非減少関数であるとき、 $f=h\circ g$ は準凸である。同様に、 $g:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ が準凹であり、 $h:\mathbb {R} \rightarrow \mathbb {R}$ が単調非減少関数であるとき、 $f=h\circ g$ は準凹である。
最小化：すなわち $f(x,y)$ が準凸であり、 $C$ が凸集合であるとき、 $h(x)=\inf _{y\in C}f(x,y)$ は準凸である。

準凸性を保存しない操作

同一の定義域上で定義された準凸関数の和は、必ずしも準凸であるとは限らない。言い換えると、 $f(x),g(x)$ が準凸であっても、 $(f+g)(x)=f(x)+g(x)$ は準凸とは限らない。
異なる定義域上で定義された準凸関数の和（すなわち $f(x),g(y)$ が準凸であり、 $h(x,y)=f(x)+g(y)$ の場合）も、必ずしも準凸ではない。このような関数は経済学では「加法分解型」（additively decomposed）、数理最適化では「分離可能」（separable）と呼ばれる。

出典

↑ Di Guglielmo (1977, pp. 287–288): Di Guglielmo, F. (1977). “Nonconvex duality in multiobjective optimization”. Mathematics of Operations Research 2 (3): 285–291. doi:10.1287/moor.2.3.285. JSTOR 3689518. MR 0484418.
↑ Di Guglielmo, F. (1981). “Estimates of the duality gap for discrete and quasiconvex optimization problems”. In Schaible, Siegfried; Ziemba, William T.. Generalized concavity in optimization and economics: Proceedings of the NATO Advanced Study Institute held at the University of British Columbia, Vancouver, B.C., August 4–15, 1980. New York: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. pp. 281–298. ISBN 0-12-621120-5. MR 0652702
↑ Kiwiel, Krzysztof C. (2001). “Convergence and efficiency of subgradient methods for quasiconvex minimization”. Mathematical Programming, Series A (Berlin, Heidelberg: Springer) 90 (1): 1–25. doi:10.1007/PL00011414. ISSN 0025-5610. MR 1819784. Kiwiel acknowledges that Yuri Nesterov first established that quasiconvex minimization problems can be solved efficiently.
↑ Johansson, Edvard; Petersson, David (2016). Parameter Optimization for Equilibrium Solutions of Mass Action Systems (MSc thesis). pp. 13–14. 2024年10月26日閲覧.

外部リンク

Sion, M., "On general minimax theorems", Pacific J. Math. 8 (1958), 171–176.
数理計画法用語集（Mathematical programming glossary）
準凹性と準凸性 - Martin J. Osborne（トロント大学経済学部）

[1] Di Guglielmo (1977, pp. 287–288): Di Guglielmo, F. (1977). “Nonconvex duality in multiobjective optimization”. Mathematics of Operations Research 2 (3): 285–291. doi:10.1287/moor.2.3.285. JSTOR 3689518. MR 0484418.

[2] Di Guglielmo, F. (1981). “Estimates of the duality gap for discrete and quasiconvex optimization problems”. In Schaible, Siegfried; Ziemba, William T.. Generalized concavity in optimization and economics: Proceedings of the NATO Advanced Study Institute held at the University of British Columbia, Vancouver, B.C., August 4–15, 1980. New York: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. pp. 281–298. ISBN 0-12-621120-5. MR 0652702

[3] Kiwiel, Krzysztof C. (2001). “Convergence and efficiency of subgradient methods for quasiconvex minimization”. Mathematical Programming, Series A (Berlin, Heidelberg: Springer) 90 (1): 1–25. doi:10.1007/PL00011414. ISSN 0025-5610. MR 1819784. Kiwiel acknowledges that Yuri Nesterov first established that quasiconvex minimization problems can be solved efficiently.

[4] Johansson, Edvard; Petersson, David (2016). Parameter Optimization for Equilibrium Solutions of Mass Action Systems (MSc thesis). pp. 13–14. 2024年10月26日閲覧.

[1]

[2]

[3]

[4]