意味
凸最適化問題は、次のように記述できる場合に標準形である。
最小限に抑える x f （ x ） s u b j e c t t o g 私 （ x ） ≤ 0 、 私 = 1 、 … 、 m h 私 （ x ） = 0 、 私 = 1 、 … 、 p 、 {\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}} 場所：[ 7 ] ：
x ∈ R n {\displaystyle \mathbf {x} \in \mathbb {R} ^{n}} 目的関数f : D ⊆ R n → R {\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} } 凸関数 である。 不等式制約関数g 私 : R n → R {\displaystyle g_{i}:\mathbb {R} ^{n}\to \mathbb {R} } 私 = 1 、 … 、 m {\displaystyle i=1,\ldots ,m} 等式制約関数h 私 : R n → R {\displaystyle h_{i}:\mathbb {R} ^{n}\to \mathbb {R} } 私 = 1 、 … 、 p {\displaystyle i=1,\ldots ,p} これらはアフィン変換 であり、すなわち次の形式である。h 私 （ x ） = 1 私 ⋅ x − b 私 {\displaystyle h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}} 1 私 {\displaystyle \mathbf {a_{i}} } b 私 {\displaystyle b_{i}} 実行可能集合C {\displaystyle C} x ∈ D {\displaystyle \mathbf {x} \in {\mathcal {D}}} D {\displaystyle {\mathcal {D}}} サブレベル集合は 凸集合であり、アフィン集合は凸集合であり、凸集合の交差は凸集合である。[ 7 ] ：
多くの最適化問題は、この標準形式で等価的に定式化できる。例えば、凹関数を最大化する問題などである。 f {\displaystyle f} − f {\displaystyle -f} [ 8 ]
標準形式では、一般性を失うことなく、目的関数fが 線形関数 であると仮定することができる。これは、一般的な目的関数を持つ任意のプログラムは、単一の変数 t と単一の制約 を追加することによって、次のように線形目的関数を持つプログラムに変換できるためである。[ 9 ] ：
最小限に抑える x 、 t t s u b j e c t t o f （ x ） − t ≤ 0 g 私 （ x ） ≤ 0 、 私 = 1 、 … 、 m h 私 （ x ） = 0 、 私 = 1 、 … 、 p 、 {\displaystyle {\begin{aligned}&{\underset {\mathbf {x} ,t}{\operatorname {minimize} }}&&t\\&\operatorname {subject\ to} &&f(\mathbf {x} )-t\leq 0\\&&&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}
すべての凸プログラムは円錐形式 で表現でき、これはアフィン平面と凸円錐の交点における線形目的関数を最小化することを意味します。[ 9 ] :
最小限に抑える x c T x s u b j e c t t o x ∈ （ b + L ） ∩ K {\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&c^{T}x\\&\operatorname {subject\ to} &&x\in (b+L)\cap K\end{aligned}}} ここで、K は閉じた頂点を持つ凸錐 、L はR n の線形部分空間、b は R n n
線形等式制約の排除 標準形式の凸計画問題を、等式制約のない凸計画問題に変換することが可能です。[ 7 ] ： h i ( x )=0 をAx = b と表します。ここで、Aは n 列の行列です。Ax = b が 実行不可能であれば、当然元の問題も実行不可能です。そうでなければ、何らかの解x 0 が存在し、すべての解の集合は次のように表すことができます。Fz + x 0 、 ここでzは R k の k = n -rank( A ) であり、Fは n × k 行列です。x = Fz + x 0 を 元の問題に代入すると、次のようになります。
最小限に抑える x f （ F z + x 0 ） s u b j e c t t o g 私 （ F z + x 0 ） ≤ 0 、 私 = 1 、 … 、 m {\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\leq 0,\quad i=1,\dots ,m\\\end{aligned}}}
ここで、変数はz です。変数の数が rank( A ) 少ないことに注意してください。これは、原理的には、等式制約のない凸最適化問題にのみ注目できることを意味します。しかし実際には、等式制約があると一部のアルゴリズムの効率が向上し、問題の理解と分析が容易になるため、等式制約を保持する方が好ましい場合が多いです。
アルゴリズム
制約なし問題と等式制約付き問題 最も解きやすい凸最適化問題は、制約のない問題、つまり等式制約のみを持つ問題です。等式制約はすべて線形であるため、 線形代数 を用いて消去し、目的関数に組み込むことで、等式制約のある問題を制約のない問題に変換できます。
制約なし（または等式制約あり）問題のクラスにおいて、最も単純なのは目的関数が二次関数 である問題である。これらの問題では、最適性に必要なKKT条件は すべて線形であるため、解析的に解くことができる。[ 7 ] ：
2 度微分可能な一般的な凸目的関数を持つ制約なし (または等式制約あり) の問題に対しては、ニュートン法を 使用できます。これは、一般的な制約なし凸問題を、一連の 2 次問題に還元するものと見なすことができます。[ 7 ] : ニュートン法は、適切なステップ サイズで線探索 と組み合わせることができ、数学的に高速に収束することが証明されています。
制約のない最小化のための他の効率的なアルゴリズムとしては、勾配降下法（ 最急降下法 の特殊なケース）がある。
一般的な問題 より困難な問題は、不等式制約のある問題です。これらの問題を解決する一般的な方法は、目的関数に不等式制約を強制するバリア関数 を追加することで、制約のない問題に還元することです。このような方法は、内点法 と呼ばれます。[ 7 ] ： フェーズI 法を用いて実行可能な内点を見つけることで初期化する必要があります。フェーズI法は、実行可能な点を見つけるか、存在しないことを示します。フェーズI法は一般的に、問題の探索をより単純な凸最適化問題に還元することから成ります。[ 7 ] ：
凸最適化問題は、以下の現代的な方法でも解くことができます。[ 12 ]
劣勾配法は簡単に実装できるため、広く使用されています。[ 15 ] 双対問題 に適用される劣勾配法です。ドリフトプラスペナルティ 法は双対劣勾配法に似ていますが、主変数の時間平均を取ります。
ラグランジュ乗数 コスト関数によって標準形式で与えられる凸最小化問題を考えるf （ x ） {\displaystyle f(x)} g 私 （ x ） ≤ 0 {\displaystyle g_{i}(x)\leq 0} 1 ≤ 私 ≤ m {\displaystyle 1\leq i\leq m} X {\displaystyle {\mathcal {X}}}
X = { x ∈ X | g 1 （ x ） 、 … 、 g m （ x ） ≤ 0 } 。 {\displaystyle {\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leq 0\right\}.} この問題のラグランジュ関数は[ 16 ]である。
L （ x 、 λ 0 、 λ 1 、 … 、 λ m ） = λ 0 f （ x ） + λ 1 g 1 （ x ） + ⋯ + λ m g m （ x ） 。 {\displaystyle L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).} 各ポイントについてx {\displaystyle x} X {\displaystyle X} f {\displaystyle f} X {\displaystyle X} λ 0 、 λ 1 、 … 、 λ m 、 {\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m},} ラグランジュ乗数 と呼ばれるもので、以下の条件を同時に満たすもの。
x {\displaystyle x} L （ y 、 λ 0 、 λ 1 、 … 、 λ m ） {\displaystyle L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})} y ∈ X 、 {\displaystyle y\in X,} λ 0 、 λ 1 、 … 、 λ m ≥ 0 、 {\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,} λ k > 0 、 {\displaystyle \lambda _{k}>0,} λ 1 g 1 （ x ） = ⋯ = λ m g m （ x ） = 0 {\displaystyle \lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0} 「厳密に実行可能な点」、つまり点が存在する場合z {\displaystyle z}
g 1 （ z ） 、 … 、 g m （ z ） < 0 、 {\displaystyle g_{1}(z),\ldots ,g_{m}(z)<0,} すると、上記の記述は次のように強化できる。λ 0 = 1 {\displaystyle \lambda _{0}=1}
逆に、もしx {\displaystyle x} X {\displaystyle X} スカラー に対して(1)～(3)を満たすλ 0 、 … 、 λ m {\displaystyle \lambda _{0},\ldots ,\lambda _{m}} λ 0 = 1 {\displaystyle \lambda _{0}=1} x {\displaystyle x} f {\displaystyle f} X {\displaystyle X}
ソフトウェア 凸最適化のためのソフトウェアエコシステムは大規模である。このエコシステムは、ソルバー とモデリングツール （またはインターフェース ）という2つの主要なカテゴリに分けられる。
ソルバーはアルゴリズム自体を実装し、通常はC言語で記述されます。ソルバーでは、ユーザーは最適化問題を非常に特殊な形式で指定する必要があり、これはモデリングの観点からは必ずしも自然な形式ではありません。モデリングツールは、ユーザーがより高レベルの構文で最適化を指定できるようにする別のソフトウェアです。モデリングツールは、ユーザーの高レベルモデルとソルバーの入出力形式との間のすべての変換を管理します。
以下に2つの表を示します。1つ目の表はモデリングツール（CVXPYやJuMP.jlなど）を示し、2つ目の表はソルバー（SCSやMOSEKなど）を示しています。これらは網羅的なものではありません。
注記 1 2 ネステロフと ネミロフスキー 1994 ↑ Murty, Katta; Kabadi, Santosh (1987). "Some NP-complete problems in quadratic and nonlinear programming". Mathematical Programming . 39 (2): 117–129 . Bibcode : 1987MatPr..39..117M . doi : 10.1007/BF02592948 . hdl : 2027.42/6740 . S2CID 30500771 . ↑ Sahni, S.「計算に関連する問題」SIAM Journal on Computing、3、262-279、1974年。 ↑ Pardalos, Panos M.; Vavasis, Stephen A. (1991). "1つの負の固有値を持つ二次計画法はNP困難である" . Journal of Global Optimization . 1 : 15– 22. doi : 10.1007/BF00120662 . ↑ ヒリアルト・ウルティ、ジャン・バティスト。ルマレシャル、クロード (1996)。 凸解析および最小化アルゴリズム: 基礎 。スプリンガー。 p. 291.ISBN 9783540568506 。↑ Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications . pp. 335–336 . ISBN 9780898714913 。1 2 3 4 5 6 7 8 9 10 11 12 Boyd , Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF) . Cambridge University Press . ISBN 978-0-521-83378-3 2021年4月12日 に取得 。↑ 「最適化問題の種類 - 凸最適化」 。2011年1月9日。 1 2 Arkadi Nemirovsky (2004). 凸計画法における内点多項式時間法 。 ↑ Agrawal, Akshay; Verschueren, Robin; Diamond, Steven; Boyd, Stephen (2018). "凸最適化問題のための書き換えシステム" (PDF) . Control and Decision . 5 (1): 42– 60. arXiv : 1709.04494 . doi : 10.1080/23307706.2017.1397554 . S2CID 67856259 . ↑ Rockafellar, R. Tyrrell (1993). "Lagrange multipliers and optimality" (PDF) . SIAM Review . 35 (2): 183– 238. Bibcode : 1993SIAMR..35..183R . CiteSeerX 10.1.1.161.7209 . doi : 10.1137/1035044 . ↑ 凸最小化の方法については、Hiriart-UrrutyとLemaréchalの著作（バンドル）およびRuszczyński 、 Bertsekas 、BoydとVandenbergheの教科書（内点法）を参照してください。 ↑ ネステロフ、ユーリ；アルカディ、ネミロフスキー (1995)。 凸計画における内点多項式アルゴリズム 。応用数理学会 。ISBN 978-0898715156 。↑ Peng, Jiming; Roos, Cornelis; Terlaky, Tamás (2002). "線形および半正定値最適化のための自己正則関数と新しい探索方向". Mathematical Programming . 93 (1): 129– 171. doi : 10.1007/s101070200296 . ISSN 0025-5610 . S2CID 28882966 . ↑ 「 数値最適化」 。Springer Series in Operations Research and Financial Engineering 。 2006年 。doi : 10.1007/978-0-387-40065-5。ISBN 978-0-387-30303-1 。↑ ビービス、ブライアン；ドブス、イアン M. (1990). 「静的最適化」 . 経済分析のための最適化と安定性理論 . ニューヨーク：ケンブリッジ大学出版局. p. 40. ISBN 0-521-33605-8 。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Borchers, Brian. "凸最適化のためのソフトウェア の 概要" (PDF) 。2017-09-18 の オリジナル (PDF)からアーカイブ済み。2021 年 4 月 12 日 に取得 。 ↑ 「CVXPY 1.1へようこそ — CVXPY 1.1.11ドキュメント」 。www.cvxpy.org 。 2021年4月12日 取得 。 ↑ Udell, Madeleine; Mohan, Karanveer; Zeng, David; Hong, Jenny; Diamond, Steven; Boyd, Stephen (2014-10-17). "Convex Optimization in Julia". arXiv : 1410.4821 [ math.OC ]. ↑ 「規律ある凸最適化 - CVXR」 。www.cvxgrp.org 。 2021年6月17日 取得 。 ↑ Lubin, Miles; Dowson, Oscar; Dias Garcia, Joaquim; Huchette, Joey; Legat, Benoît; Vielma, Juan Pablo (2023). "JuMP 1.0: 数理最適化のためのモデリング言語の最近の改善点". Mathematical Programming Computation . 15 (3): 581–589 . arXiv : 2206.03866 . doi : 10.1007/s12532-023-00239-3 . ↑ クリステンセン/クラーブリング、章。 4. ↑ Schmit, LA; Fleury, C. 1980:近似概念と双対法を組み合わせた構造合成 . J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260 1 2 3 4 5 Boyd, Stephen; Diamond, Stephen; Zhang, Junzi; Agrawal, Akshay. "Convex Optimization Applications" (PDF) . 2015-10-01 のオリジナルから アーカイブ (PDF) . 2021 年 4 月 12 日 に取得 . 1 2 3 Malick, Jérôme (2011-09-28). "凸最適化: アプリケーション、定式化、緩和" (PDF) . 2021-04-12 のオリジナルから アーカイブ (PDF) . 2021 年 4 月 12 日 に取得 . ↑ Ben Haim Y. および Elishakoff I.、『応用力学における不確実性の凸型モデル』、Elsevier Science Publishers、アムステルダム、1990年 ↑ Ahmad Bazzi 、Dirk TM Slock、Lisa Meilhac。「相互結合が存在する場合のオンライン到来角推定」。2016 IEEE Statistical Signal Processing Workshop (SSP)。IEEE、2016年。
参考文献 Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003).凸解析と最適化 . Belmont, MA.: Athena Scientific. ISBN 978-1-886529-45-8 。 Bertsekas, Dimitri P. (2009).凸最適化理論 . ベルモント、マサチューセッツ州: Athena Scientific. ISBN 978-1-886529-31-1 。Bertsekas, Dimitri P. (2015).凸最適化アルゴリズム . Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1 。Borwein, Jonathan; Lewis, Adrian (2000). Convex Analysis and Nonlinear Optimization: Theory and Examples, Second Edition (PDF) . Springer . 2021年 4月12日 取得 . Christensen, Peter W.; Anders Klarbring (2008).構造最適化入門 . 第 153巻. Springer Science & Business Media. ISBN 9781402086663 。 Hiriart-Uruty、Jean-Baptiste、およびLemaréchal、Claude 。 (2004)。凸分析の基礎 。ベルリン：シュプリンガー。 ヒリアルト・ウルティ、ジャン・バティスト。ルマレシャル、クロード (1993)。凸解析および最小化アルゴリズム、第 1 巻: 基礎 。 Grundlehren der Mathematischen Wissenschaften [数学科学の基本原理]。 Vol. 305. ベルリン: Springer-Verlag。ページ xviii+417。ISBN 978-3-540-56850-6 MR 1261420 . ヒリアルト・ウルティ、ジャン・バティスト。ルマレシャル、クロード (1993)。凸解析および最小化アルゴリズム、第 II 巻: 高度な理論とバンドル法 。 Grundlehren der Mathematischen Wissenschaften [数学科学の基本原理]。 Vol. 306. ベルリン: Springer-Verlag。ページ xviii+346。ISBN 978-3-540-56852-0 MR 1295240 . Kiwiel, Krzysztof C. (1985).微分不可能な最適化のための降下法 ISBN 978-3-540-15642-0 。 ルマレシャル、クロード (2001)。 「ラグランジュ緩和」。 Michael Jünger と Denis Naddef (編)。計算による組み合わせ最適化: 2000 年5 月 15 ～ 19 日に ダグシュトゥール城で開催されたスプリング スクールの論文 。コンピューターサイエンスの講義ノート。 Vol. 2241. ベルリン: Springer-Verlag。 pp. 112–156 . doi : 10.1007/3-540-45586-8_4。ISBN 978-3-540-42877-0 . MR 1900016 . S2CID 9048698 . ネステロフ、ユリ。ネミロフスキー、アルカディ (1994)。凸計画法における内点多項式法 。サイアム。 ネステロフ、ユーリー。（2004）。凸最適化入門講義 、クルーワー・アカデミック・パブリッシャーズ Rockafellar, RT (1970).凸解析 . プリンストン: プリンストン大学出版局.ルシュチンスキ、アンジェイ (2006)。非線形最適化 。プリンストン大学出版局。Schmit, LA; Fleury, C. 1980:近似概念と双対法を組み合わせた構造合成 . J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260
外部リンク EE364a：凸最適化IおよびEE364b：凸最適化II、スタンフォード大学コースホームページ 6.253: 凸解析と最適化、MIT OCWコースのホームページ ブライアン・ボーチャーズ著「凸最適化のためのソフトウェアの概要」 リーベン・ヴァンデンベルゲとスティーブン・P・ボイド著『凸最適化』
