凸解析

Mathematics of convex functions and sets

3次元凸多面体。凸解析には、ユークリッド空間の凸部分集合の研究だけでなく、抽象空間上の凸関数の研究も含まれます。

凸解析は、凸関数と凸集合の特性の研究に特化した数学の分野であり、多くの場合、最適化理論のサブドメインである凸最小化に応用されます。

凸集合

あるベクトル空間の部分集合が凸集合であるとは、次の同値な条件のいずれかを満たす場合です。 ${\displaystyle C\subseteq X}$ ${\displaystyle X}$

1. が実数であれば^[1] ${\displaystyle 0\leq r\leq 1}$ ${\displaystyle x,y\in C}$ ${\displaystyle rx+(1-r)y\in C.}$
2. が実数で、 ${\displaystyle 0<r<1}$ ${\displaystyle x,y\in C}$ ${\displaystyle x\neq y,}$ ${\displaystyle rx+(1-r)y\in C.}$

区間上の凸関数。

全体を通して、は、あるベクトル空間の凸部分集合を定義域とする、拡張実数で値をとる写像となる。この写像が凸関数であるのは、 ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle [-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \}}$ ${\displaystyle \operatorname {domain} f=X}$ ${\displaystyle f:X\to [-\infty ,\infty ]}$

${\displaystyle f(rx+(1-r)y)\leq rf(x)+(1-r)f(y)}$

凸度≤

は任意の実数と任意のに対して成り立ち、定義不等式（凸性≤）を厳密不等式に置き換えて もこれが成り立つならば、 ${\displaystyle 0<r<1}$ ${\displaystyle x,y\in X}$ ${\displaystyle x\neq y.}$ ${\displaystyle f}$

${\displaystyle f(rx+(1-r)y)<rf(x)+(1-r)f(y)}$

凸状性 <

は厳密に凸と呼ばれる。^[1] ${\displaystyle f}$

凸関数は凸集合と関連している。具体的には、関数が凸関数であるための必要十分条件は、そのエピグラフが ${\displaystyle f}$

関数 (黒) が凸関数となるのは、そのグラフ(緑)の上の領域であるエピグラフが凸集合である場合のみです。

二変数凸関数のグラフ ${\displaystyle x^{2}+xy+y^{2}.}$

${\displaystyle \operatorname {epi} f:=\left\{(x,r)\in X\times \mathbb {R} ~:~f(x)\leq r\right\}}$

エピグラフ定義。

は凸集合である。^{[2]拡張実数値関数のエピグラフは、}実解析における実数値関数のグラフの役割と同様の役割を凸解析において果たす。具体的には、拡張実数値関数のエピグラフは、定式化や仮説の証明に利用できる幾何学的直感を与える。

関数の定義域はで表され、その有効定義域は集合^{[2]で示される。} ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle \operatorname {domain} f}$

${\displaystyle \operatorname {dom} f:=\{x\in X~:~f(x)<\infty \}.}$

ドムfデフ。

関数は、すべての[2]に対して真^であると呼ばれる。あるいは、関数のドメインに、かつが決して等しくならないような関数が存在することを意味する。つまり、関数が真であるのは、そのドメインが空でなく、決して値をとらず、かつ全く等しくない場合である。関数が真であるのは、関数のドメインが空でなく、かつ、かつ、が真であるような 凸関数である場合、あるベクトルとあるベクトルが存在し、 ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle \operatorname {dom} f\neq \varnothing }$ ${\displaystyle f(x)>-\infty }$ ${\displaystyle x\in \operatorname {domain} f.}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle f(x)\in \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle -\infty .}$ ${\displaystyle -\infty ,}$ ${\displaystyle +\infty .}$ ${\displaystyle f:\mathbb {R} ^{n}\to [-\infty ,\infty ]}$ ${\displaystyle b\in \mathbb {R} ^{n}}$ ${\displaystyle r\in \mathbb {R} }$

${\displaystyle f(x)\geq x\cdot b-r}$     すべての ${\displaystyle x}$

ここで、 はこれらのベクトルのドット積を表します。 ${\displaystyle x\cdot b}$

凸共役

拡張実数値関数（必ずしも凸ではない）の凸共役は、 （連続）双対空間からの関数であり、^[3] ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle f^{*}:X^{*}\to [-\infty ,\infty ]}$ ${\displaystyle X^{*}}$ ${\displaystyle X,}$

${\displaystyle f^{*}\left(x^{*}\right)=\sup _{z\in X}\left\{\left\langle x^{*},z\right\rangle -f(z)\right\}}$

ここで、括弧は標準双対性を表します。が 上の - 値関数の集合を表す 場合、によって定義される写像は、ルジャンドル-フェンシェル変換と呼ばれます。 ${\displaystyle \left\langle \cdot ,\cdot \right\rangle }$ ${\displaystyle \left\langle x^{*},z\right\rangle :=x^{*}(z).}$ ${\displaystyle \operatorname {Func} (X;Y)}$ ${\displaystyle Y}$ ${\displaystyle X,}$ ${\displaystyle \operatorname {Func} (X;[-\infty ,\infty ])\to \operatorname {Func} \left(X^{*};[-\infty ,\infty ]\right)}$ ${\displaystyle f\mapsto f^{*}}$

劣微分集合とフェンチェル・ヤング不等式

とすると、部分微分集合は ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle x\in X}$

${\displaystyle {\begin{alignedat}{4}\partial f(x):&=\left\{x^{*}\in X^{*}~:~f(z)\geq f(x)+\left\langle x^{*},z-x\right\rangle {\text{ for all }}z\in X\right\}&&({\text{“}}z\in X{\text{''}}{\text{ can be replaced with: }}{\text{“}}z\in X{\text{ such that }}z\neq x{\text{''}})\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)\geq \left\langle x^{*},z\right\rangle -f(z){\text{ for all }}z\in X\right\}&&\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)\geq \sup _{z\in X}\left\langle x^{*},z\right\rangle -f(z)\right\}&&{\text{ The right hand side is }}f^{*}\left(x^{*}\right)\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)=f^{*}\left(x^{*}\right)\right\}&&{\text{ Taking }}z:=x{\text{ in the }}\sup {}{\text{ gives the inequality }}\leq .\\\end{alignedat}}}$

例えば、 がのノルムである重要な特殊なケースでは、 の 場合にはこの定義は次のように簡約されることが示されます^{[証明 1] 。} ${\displaystyle f=\|\cdot \|}$ ${\displaystyle X}$ ${\displaystyle 0\neq x\in X}$

${\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle =\|x\|{\text{ and }}\left\|x^{*}\right\|=1\right\}}$     そして     ${\displaystyle \partial f(0)=\left\{x^{*}\in X^{*}~:~\left\|x^{*}\right\|\leq 1\right\}.}$

任意の と に対して、はフェンチェル・ヤング不等式と呼ばれる。この不等式が等式（すなわち）となるのは、次の場合のみである。このようにして、劣微分集合は凸共役集合に直接関係している。 ${\displaystyle x\in X}$ ${\displaystyle x^{*}\in X^{*},}$ ${\displaystyle f(x)+f^{*}\left(x^{*}\right)\geq \left\langle x^{*},x\right\rangle ,}$ ${\displaystyle f(x)+f^{*}\left(x^{*}\right)=\left\langle x^{*},x\right\rangle }$ ${\displaystyle x^{*}\in \partial f(x).}$ ${\displaystyle \partial f(x)}$ ${\displaystyle f^{*}\left(x^{*}\right).}$

二重共役

関数 の共役は、通常 と表記され、共役 の共役です。任意の に対して成り立ちます。共役は、強い双対性または弱い双対性が成り立つ場合（摂動関数を介して）を示すのに役立ちます。 ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle f^{**}:X\to [-\infty ,\infty ]}$ ${\displaystyle f^{**}(x):=\sup _{z^{*}\in X^{*}}\left\{\left\langle x,z^{*}\right\rangle -f^{*}\left(z^{*}\right)\right\}}$ ${\displaystyle x\in X}$

任意の関数に対して、不等式 はフェンシェル・ヤング不等式から従う。固有関数に対して、が凸かつ下半連続であることは、フェンシェル・モロー定理により であるとき、かつその場合に限る。^{[3] [4]} ${\displaystyle x\in X,}$ ${\displaystyle f^{**}(x)\leq f(x)}$ ${\displaystyle f=f^{**}}$ ${\displaystyle f}$

凸最小化

凸最小化（プライマル）問題とは、次のような形式の一つである。

凸関数と凸部分集合が与えられたときに見つける ${\displaystyle \inf _{x\in M}f(x)}$ ${\displaystyle f:X\to [-\infty ,\infty ]}$ ${\displaystyle M\subseteq X.}$

二重問題

最適化理論における双対性原理は、最適化の問題は主問題と双対問題という 2 つの視点のいずれかから見ることができると述べています。

一般に、局所凸空間から分離された2つの双対の 対が与えられ、関数が与えられたとき、次のようなものを見つけることが主問題として定義できる。 ${\displaystyle \left(X,X^{*}\right)}$ ${\displaystyle \left(Y,Y^{*}\right).}$ ${\displaystyle f:X\to [-\infty ,\infty ],}$ ${\displaystyle x}$

${\displaystyle \inf _{x\in X}f(x).}$

制約条件がある場合、これらは関数に組み込むことができ、ここでは指示関数である。そして は摂動関数であり、 ^[5] ${\displaystyle f}$ ${\displaystyle f=f+I_{\mathrm {constraints} }}$ ${\displaystyle I}$ ${\displaystyle F:X\times Y\to [-\infty ,\infty ]}$ ${\displaystyle F(x,0)=f(x).}$

選択された摂動関数に関する双対問題は次のように与えられる。

${\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)}$

ここで、両変数の凸共役は ${\displaystyle F^{*}}$ ${\displaystyle F.}$

双対性ギャップとは不等式の右辺と左辺の差である^{[6] [5] [7]}

${\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)\leq \inf _{x\in X}F(x,0).}$

この原理は弱い双対性と同じです。両辺が等しい場合、問題は強い双対性を満たしていると言われます。

強い双対性が成立するための条件は多数あります。たとえば、

• ${\displaystyle F=F^{**}}$ここで、は主問題と双対問題に関連する摂動関数であり、はの共役関数である。^{[引用が必要]} ${\displaystyle F}$ ${\displaystyle F^{**}}$ ${\displaystyle F}$
• 主な問題は線形最適化問題です。
• 凸最適化問題に対するスレーターの条件。^{[8] [9]}

ラグランジュ双対性

不等式制約を伴う凸最小化問題の場合、

${\displaystyle \min {}_{x}f(x)}$対象となる ${\displaystyle g_{i}(x)\leq 0}$ ${\displaystyle i=1,\ldots ,m.}$

ラグランジアン双対問題は

${\displaystyle \sup {}_{u}\inf {}_{x}L(x,u)}$対象となる ${\displaystyle u_{i}(x)\geq 0}$ ${\displaystyle i=1,\ldots ,m.}$

ここで、目的関数は次のように定義されるラグランジュ双対関数です。 ${\displaystyle L(x,u)}$

${\displaystyle L(x,u)=f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)}$

参照

• 経済学における凸性 – 経済学の重要なトピック
  • 非凸性（経済学）  - 初等経済学の凸性仮定の違反
• 凸状性トピックのリスト
• ヴェルナー・フェンヒェル – ドイツの数学者 (1905–1988)

注記

1. Rockafellar, R. Tyrrell (1997) [1970].凸解析. プリンストン, ニュージャージー州: プリンストン大学出版局. ISBN 978-0-691-01586-6。
2. Rockafellar & Wets 2009、1–28ページ。
3. Zălinescu 2002、75–79 ページ。
4. ボルウェイン, ジョナサン; ルイス, エイドリアン (2006).凸解析と非線形最適化：理論と例（第2版）. シュプリンガー. pp. 76–77. ISBN 978-0-387-29570-1。
5. ボシュ、ラドゥ・ヨアン;ワンカ、ゲルト。卒業生、ソリンミハイ (2009)。ベクトル最適化の二重性。スプリンガー。ISBN 978-3-642-02885-4。
6. ザリネスク、2002、106–113 ページ。
7. Csetnek, Ernö Robert (2010).凸最適化における古典的な一般化内点正則性条件の破綻の克服．双対性理論の最大単調作用素の拡大への応用．Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3。
8. ボルウェイン、ジョナサン、ルイス、エイドリアン (2006).凸解析と非線形最適化：理論と例（第2版）. シュプリンガー. ISBN 978-0-387-29570-1。
9. Boyd, Stephen; Vandenberghe, Lieven (2004). 凸最適化(PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. 2011年10月3日閲覧。

1. 結論はすぐに出ます。そうであれば、そうでない場合は仮定します。修正ノルムを で置き換えるとが得られます。特に、 を取ると が得られ、 を取ると が得られるため、となります。さらに、 を加えると が得られるため、双対ノルムの定義から が導かれます。は と等しいため、 がすべてについて となるが導かれます。これらの事実から、結論に達することができます。∎ ${\displaystyle X=\{0\}}$ ${\displaystyle x\in X.}$ ${\displaystyle f}$ ${\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -\|x\|\geq \left\langle x^{*},z\right\rangle -\|z\|{\text{ for all }}z\in X\right\}.}$ ${\displaystyle x^{*}\in \partial f(x)}$ ${\displaystyle r\geq 0}$ ${\displaystyle z:=rx}$ ${\displaystyle \left\langle x^{*},x\right\rangle -\|x\|\geq \left\langle x^{*},rx\right\rangle -\|rx\|=r\left[\left\langle x^{*},x\right\rangle -\|x\|\right],}$ ${\displaystyle r:=2}$ ${\displaystyle x^{*}(x)\geq \|x\|}$ ${\displaystyle r:={\frac {1}{2}}}$ ${\displaystyle x^{*}(x)\leq \|x\|}$ ${\displaystyle x^{*}(x)=\|x\|}$ ${\displaystyle x\neq 0}$ ${\displaystyle x^{*}\left({\frac {x}{\|x\|}}\right)=1,}$ ${\displaystyle \left\|x^{*}\right\|\geq 1.}$ ${\displaystyle \partial f(x)\subseteq \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},}$ ${\displaystyle \partial f(x)=\partial f(x)\cap \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},}$ ${\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|{\text{ and }}\|z\|\geq \left\langle x^{*},z\right\rangle {\text{ for all }}z\in X\right\},}$ ${\displaystyle \left\|x^{*}\right\|\leq 1}$ ${\displaystyle x^{*}\in \partial f(x).}$

参考文献

• Bauschke, Heinz H.; Combettes, Patrick L. (2017年2月28日).ヒルベルト空間における凸解析と単調作用素理論. CMS Books in Mathematics. Springer Science & Business Media . ISBN 978-3-319-48311-5. OCLC  1037059594.
• Boyd, Stephen ; Vandenberghe, Lieven (2004年3月8日).凸最適化. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge, UK New York: Cambridge University Press . ISBN 978-0-521-83378-3. OCLC  53331084。
• Hiriart-Urruty、J.-B. Lemaréchal、C. (2001)。凸解析の基礎。ベルリン: Springer-Verlag。ISBN 978-3-540-42205-1。
• Kusraev, AG; Kutateladze, Semen Samsonovich (1995). Subdifferentials: Theory and Applications . Dordrecht: Kluwer Academic Publishers. ISBN 978-94-011-0265-0。
• R・ティレル・ロッカフェラー;ウェッツ、ロジャー J.-B. (2009 年 6 月 26 日)。変分分析。 Grundlehren der mathematischen Wissenschaften。 Vol. 317. ベルリン、ニューヨーク: Springer Science & Business Media。ISBN 9783642024313. OCLC  883392544。
• ロッカフェラー、R. ティレル (1970).凸解析. プリンストン数学シリーズ. プリンストン、ニュージャージー州: プリンストン大学出版局. ISBN 978-0-691-08069-7。
• ルディン、ウォルター(1991). 関数解析. 国際純粋・応用数学叢書. 第8巻（第2版）. ニューヨーク：McGraw-Hill Science/Engineering/Math . ISBN 978-0-07-054236-5. OCLC  21163277。
• シンガー、イヴァン (1997).抽象凸解析. カナダ数学会モノグラフおよび上級テキストシリーズ. ニューヨーク: John Wiley & Sons, Inc. pp. xxii+491. ISBN 0-471-16015-6. MR  1461544。
• Stoer, J.; Witzgall, C. (1970).有限次元における凸性と最適化. 第1巻. ベルリン: Springer. ISBN 978-0-387-04835-2。
• ザリネスク、コンスタンチン（2002年7月30日）『一般ベクトル空間における凸解析』リバーエッジ、ニュージャージー州ロンドン：ワールド・サイエンティフィック・パブリッシング、ISBN 978-981-4488-15-0. MR  1921556. OCLC  285163112 –インターネットアーカイブ経由。

外部リンク

• ウィキメディア・コモンズの凸解析関連メディア

Retrieved from "https://en.wikipedia.org/w/index.php?title=Convex_analysis&oldid=1294619167"