凸とつ最適さいてき化か

凸とつ最適さいてき化か（とつさいてきか）とは最適さいてき化か問題もんだいの分野ぶんやのひとつで、凸とつ集合しゅうごう上うえの凸とつ関数かんすうの最小さいしょう化か問題もんだいである。凸とつ最小さいしょう化か問題もんだいは一般いっぱん的てきな最適さいてき化か問題もんだいよりも簡単かんたんに最適さいてき化かが可能かのうであり、局所きょくしょ的てきな最小さいしょう値ちが大域たいいき的てきな最小さいしょう値ちと一致いっちする性質せいしつをもつ。

実みベクトル空間くうかん $X$ 上うえの実じつ数値すうち凸とつ関数かんすう

f:{\mathcal {X}}\to \mathbb {R}

が $X$ の凸とつ部分ぶぶん集合しゅうごう ${\mathcal {X}}$ 上うえで定義ていぎされる。

凸とつ最適さいてき化か問題もんだいとは $f(x)$ の最小さいしょう値ちとなる ${\mathcal {X}}$ 上うえの点てん $x^{\ast }$ を見みつけることである。

すなわち $x^{\ast }$ は

f(x^{\ast })\leq f(x)

for all

x\in {\mathcal {X}}

.

である。

凸とつ最適さいてき化か問題もんだい[編集へんしゅう]

${\mathcal {X}}$ 上うえの $x^{\ast }$ を見みつける最適さいてき化か問題もんだいである。

f(x^{\ast })=\min\{f(x):x\in {\mathcal {X}}\},

ここで ${\mathcal {X}}\subset \mathbb {R} ^{n}$ は実現じつげん可能かのう集合しゅうごうで、 $f(x):\mathbb {R} ^{n}\rightarrow \mathbb {R}$ は目的もくてき関数かんすうである。 ${\mathcal {X}}$ が閉凸集合しゅうごうで、 $\mathbb {R} ^{n}$ 上うえで $f(x)$ が凸とつ関数かんすうであれば、これを凸とつ最適さいてき化か問題もんだいという。

以上いじょうは数学すうがく的てきに一般いっぱん化かされた定義ていぎであるが、この問題もんだいが実際じっさいに提示ていじされる場面ばめんにおいて ${\mathcal {X}}\subseteq \mathbb {R^{2}}$ は具体ぐたい的てきな形かたちで表現ひょうげんされることが多おおい。よくある例れいとして、与あたえられた凸とつ関数かんすう $g_{i}(x):i=1,\dots ,m$ を用もちいて以下いかのように連立れんりつ不等式ふとうしきをみたす集合しゅうごうとして定義ていぎされる：

${\mathcal {X}}:=\{x\in \mathbb {R^{n}} :g_{i}(x)\leq 0,i=1,\dots ,m\}$

こういった事情じじょうを踏ふまえて以下いかのような定義ていぎが与あたえられることもある：

{\begin{aligned}&\operatorname {minimize} &&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}

ここで、関数かんすう $f,g_{1}\ldots g_{m}:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ は凸とつである。

理論りろん[編集へんしゅう]

凸とつ最適さいてき化か問題もんだいにおいて以下いかの命題めいだいは真しんである。

極小きょくしょう値ちが存在そんざいすれば大域たいいき的てき最小さいしょう値ちである
すべての（大域たいいき的てき）最小さいしょう値ちの集合しゅうごうは凸とつである
強つよ凸とつ関数かんすうであり関数かんすうが最小さいしょう値ちを持もてば、一意いちいに決きまる

ヒルベルト射影しゃえい理論りろん、分離ぶんり超ちょう平面へいめん理論りろん、Farkasの補題ほだいなどの関数かんすう解析かいせき（ヒルベルト空間くうかん上うえの）とも関係かんけいしている。

標準ひょうじゅん形がた[編集へんしゅう]

標準ひょうじゅん形がたは凸とつ最小さいしょう化か問題もんだいをよく使用しようされる直感ちょっかん的てきな形式けいしきで表現ひょうげんする。

3つの部分ぶぶんで成なり立たつ。

凸とつ関数かんすう $f(x):\mathbb {R} ^{n}\to \mathbb {R}$ 　 $x$ に関かんして最小さいしょう化かされる。
不等式ふとうしき制約せいやく $g_{i}(x)\leq 0$ 。ここで関数かんすう $g_{i}$ は凸とつである。
等式とうしき制約せいやく $h_{j}(x)=0$ 　関数かんすう $h_{j}$ はアフィン変換へんかん、すなわち線形せんけい関数かんすう。

実際じっさいには線形せんけい制約せいやくとアフィンな制約せいやくはよく使用しようされる。これらの形式けいしきは $h_{j}(x)=a_{j}^{T}x+b_{j}$ と表あらわせられる。ここで、 $a_{j}$ は列れつベクトル、 $b_{j}$ は実数じっすうである。

凸とつ最小さいしょう化か問題もんだいは以下いかのように表あらわされる

{\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p.\end{aligned}}

等式とうしき制約せいやく $h(x)=0$ は2つの不等式ふとうしき制約せいやく $h(x)\leq 0$ と $-h(x)\leq 0$ を用もちいて置おき換かえることができる。そのため等式とうしき制約せいやくは理論りろん的てきには冗長じょうちょうであるが実際じっさい上じょうの利点りてんのため使用しようされる。これらのことから、なぜ $h_{j}(x)=0$ が単たんに凸とつであるのではなくアフィンであるのかが容易よういに理解りかいできる。 $h_{j}(x)$ を凸とつとすると $h_{j}(x)\leq 0$ は凸とつであるが $-h_{j}(x)\leq 0$ は凹となる。そのため $h_{j}(x)=0$ が凸とつとなるための条件じょうけんが $h_{j}(x)$ がアフィンであることである。

例れい[編集へんしゅう]

以下いかで示しめす例れいはすべて凸とつ最小さいしょう化か問題もんだいであるか、変数へんすう変換へんかんにより凸とつ最小さいしょう化か問題もんだいにできる問題もんだいである。

ラグランジュの未定みてい乗数じょうすう法ほう[編集へんしゅう]

標準ひょうじゅん形がたに表あらわされた凸とつ最小さいしょう化か問題もんだいを考かんがえる。コスト関数かんすうを $f(x)$ 、不等式ふとうしき制約せいやくを $g_{i}(x)\leq 0(i=1\ldots m)$ とすると、定義ていぎ域いき ${\mathcal {X}}$ は

{\mathcal {X}}=\left\lbrace {x\in X\vert g_{1}(x)\leq 0,\ldots ,g_{m}(x)\leq 0}\right\rbrace .

この問題もんだいに対たいするラグランジュ関数かんすうは

L(x,λらむだ₀,...,λらむだ_m) = λらむだ₀f(x) + λらむだ₁g₁(x) + ... + λらむだ_mg_m(x).

X上うえの関数かんすうfを最小さいしょう化かするX上うえの点てんxに関かんして実じつ数値すうちのラグランジュ係数けいすうλらむだ₀, ..., λらむだ_mが存在そんざいし、以下いかを満みたす。

X上うえのすべての変数へんすうに関かんしてxはL(y, λらむだ₀, λらむだ₁, ..., λらむだ_m) を最小さいしょう化かする
λらむだ₀ ≥ 0, λらむだ₁ ≥ 0, ..., λらむだ_m ≥ 0, 少すくなくともひとつは λらむだ_k>0,
λらむだ₁g₁(x) = 0, ..., λらむだ_mg_m(x) = 0 (相補そうほスラック性せい).

方法ほうほう[編集へんしゅう]

凸とつ最小さいしょう化か問題もんだいは以下いかの方法ほうほうを用もちいて解とくことが可能かのうである。

その他たの手法しゅほう

劣れつ勾配こうばい法ほうは簡単かんたんに実装じっそうでき多おおくの適応てきおう例れいがある。双対そうつい劣れつ勾配こうばい法ほうは劣れつ勾配こうばい法ほうを双対そうつい問題もんだいに適応てきおうした方法ほうほうである。ドリフトプラスペナルティー法ほうは双対そうつい劣れつ勾配こうばい法ほうと類似るいじしているが、主しゅ変数へんすうに関かんして時間じかん平均へいきんをとっている点てんが異ことなる。

凸とつ最小さいしょう化かが難むずかしい場合ばあい: 自己じこ調和ちょうわ障壁しょうへき[編集へんしゅう]

凸とつ最適さいてき化か問題もんだいにクラスによっては更新こうしん法ほうの効率こうりつは悪わるいものがある。それはクラスには多おおくの関数かんすうと劣れつ勾配こうばいを評価ひょうかしなければ精確せいかくに最小さいしょう値ちを得えられない問題もんだいを含ふくんでいるからである。この問題もんだいはArkadi Nemirovskiiによって議論ぎろんされている。

そのため実用じつよう上じょうの効率こうりつを求もとめるには問題もんだいのクラスにさらに制約せいやくを加くわえる必要ひつようがある。 2つの障壁しょうへき関数かんすう法ほうの方法ほうほうがある。 1つはNesterovとNemirovskiiによる自己じこ調和ちょうわ(self-concordant)障壁しょうへき関数かんすう、もう1つはTerlakyらによる自己じこ正規せいき障壁しょうへき関数かんすうである。

準じゅん凸とつ最小さいしょう化か[編集へんしゅう]

凸とつのレベル集合しゅうごうをもつ問題もんだいは理論りろん上じょうは効率こうりつ的てきに最小さいしょう化かできる。 Yuri Nesterovは準じゅん凸とつ最小さいしょう化か問題もんだいを効率こうりつ的てきに解とけることを証明しょうめいした。これの結果けっかはKiwielによって拡張かくちょうされた。

計算けいさん複雑ふくざつ性せいの理論りろんの中なかでは、準じゅん凸計画とつけいかく問題もんだいと凸計画とつけいかく問題もんだいは問題もんだいの次元じげんに対たいして多項式たこうしき時間じかんで解とくことが可能かのうである。 Yuri Nesterovが最初さいしょに準じゅん凸とつ最小さいしょう化か問題もんだいを効率こうりつ的てきに解とくことが可能かのうであることを示しめした。しかし、この理論りろん的てきに効率こうりつ的てきな方法ほうほうは発散はっさんする数列すうれつをステップサイズに用もちいていた。これは古典こてん的てきな劣れつ勾配こうばい法ほうの開発かいはつに使つかわれていた。発散はっさん数列すうれつを用もちいる古典こてん的てきな劣れつ勾配こうばい法ほうは、劣れつ勾配こうばい射影しゃえい法ほう、勾配こうばいバンドル法ほう、非ひ平滑へいかつフィルタ法ほうなどの現代げんだい的てきな凸とつ最小さいしょう化か法ほうよりかなり遅おそいことが知しられている。

凸とつに近ちかいが非ひ凸とつの関数かんすうの問題もんだいは計算けいさん困難こんなんである。 Ivanovの結果けっかによれば関数かんすうが滑なめらかさあっても単たん峰みねの関数かんすうを最小さいしょう化かすることは難むずかしい。

拡張かくちょう[編集へんしゅう]

正せい無限むげんを含ふくむように凸とつ関数かんすうを拡張かくちょうできる。たとえば、指標しひょう関数かんすうは $x\in {\mathcal {X}}$ を満みたす領域りょういきでは $0$ をもち、その他たは正せい無限むげんである。

凸とつ関数かんすうの拡張かくちょうには擬似ぎじ凸とつ関数かんすうと準じゅん凸とつ関数かんすうを含ふくむ。凸とつ解析かいせきと更新こうしん法ほうの部分ぶぶん的てきな拡張かくちょうは非ひ凸とつ最小さいしょう化か問題もんだいに対たいする近似きんじ解法かいほうとして一般いっぱん化かされた凸とつ性せいの中なかで考かんがえられている。

脚注きゃくちゅう[編集へんしゅう]

Bertsekas, Dimitri (2003). Convex Analysis and Optimization. Athena Scientific
Boyd, Stephen P.; Vandenberghe, Lieven (2004) (pdf). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3 2011年ねん10月がつ15日にち閲覧えつらん。
Borwein, Jonathan, and Lewis, Adrian. (2000). Convex Analysis and Nonlinear Optimization. Springer.
Hiriart-Urruty, Jean-Baptiste, and Lemaréchal, Claude. (2004). Fundamentals of Convex analysis. Berlin: Springer.
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 3-540-56850-6
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. MR1295240
Kiwiel, Krzysztof C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. New York: Springer-Verlag. ISBN 978-3540156420
Lemaréchal, Claude (2001). “Lagrangian relaxation”. In Michael Jünger and Denis Naddef. Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR1900016
Nesterov, Y. and Nemirovsky, A. (1994). Interior Point Polynomial Methods in Convex Programming. SIAM
Nesterov, Yurii. (2004). Introductory Lectures on Convex Optimization, Kluwer Academic Publishers
Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press
Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton University Press

外部がいぶリンク[編集へんしゅう]

Stephen Boyd and Lieven Vandenberghe, Convex optimization (book in pdf)
EE364a: Convex Optimization I and EE364b: Convex Optimization II, Stanford course homepages
6.253: Convex Analysis and Optimization, an MIT OCW course homepage
Brian Borchers, An overview of software for convex optimization