凸最適化

凸最適化は数学的最適化のサブフィールドであり、凸集合上の凸関数を最小化する問題（または、同等に、凸集合上の凹関数を最大化する問題）を研究する。凸最適化問題の多くのクラスは多項式時間アルゴリズムを許容するが、^[1]数学的最適化は一般にNP困難である。^{[2] [3] [4]}

凸最適化問題は2つの要素によって定義される: ^{[5] [6]}

• 目的関数 はn変数 の実数値凸関数であり、${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$
• 実行可能集合、これは凸部分集合 です。${\displaystyle C\subseteq \mathbb {R} ^{n}}$

問題の目的は、達成できる ものを見つけることです${\displaystyle \mathbf {x^{\ast }} \in C}$

${\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\}}$。

一般的に、解決策の存在に関しては3つの選択肢がある：^{[7] ：第4章}

• そのような点x * が存在する場合、それは最適点または最適解と呼ばれます。すべての最適点の集合は最適集合と呼ばれ、問題は解決可能と呼ばれます。
• が 未満で を超える場合、または下限に達しない場合、最適化問題は無制限であると言われます。${\displaystyle f}$${\displaystyle C}$
• そうでない場合、 が空集合である場合、問題は実行不可能であると言われます。${\displaystyle C}$

凸最適化問題は次のように書かれる場合、 標準形式である。

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {最小化} }}&&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] : chpt.4}

• ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$最適化変数のベクトルです。
• 目的関数は凸関数である。${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$
• 不等式制約関数、は凸関数です。${\displaystyle g_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle i=1,\ldots ,m}$
• 等式制約関数、は、次の形式のアフィン変換です。 、ここではベクトル、はスカラーです。${\displaystyle h_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle i=1,\ldots ,p}$${\displaystyle h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}}$${\displaystyle \mathbf {a_{i}} }$${\displaystyle b_{i}}$

最適化問題の実行可能集合は、不等式と等式制約を満たすすべての点から構成される。この集合は凸集合である。なぜなら、凸集合は凸であり、凸関数のサブレベル集合は凸であり、アフィン集合は凸であり、凸集合の交差は凸であるからである。^{[7] : chpt.2}${\displaystyle C}$${\displaystyle \mathbf {x} \in {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$

多くの最適化問題は、この標準形式で同等に定式化できます。たとえば、凹関数 を最大化する問題は、凸関数を最小化する問題として同等に再定式化できます。凸集合上で凹関数を最大化する問題は、一般に凸最適化問題と呼ばれます。^[8]${\displaystyle f}$${\displaystyle -f}$

標準形式では、一般性を失うことなく、目的関数fが線形関数であると仮定することができます。これは、一般的な目的を持つ任意のプログラムは、次のように単一の変数tと単一の制約を追加することで線形目的のプログラムに変換できるためです。^{[9] ：1.4}

${\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] : 5.1}

${\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 ⁿの線型部分空間、 b は R ⁿのベクトルです。 K が R ⁿの非負直交座標である特殊なケースにおける標準形式の線型計画。

標準形式の凸計画法を、等式制約のない凸計画法に変換することは可能である。^{[7] : 132}等式制約h _i ( x )=0 をAx = bと表記する。ここでA はn列である。 Ax = bが実行不可能であれば、もちろん元の問題は実行不可能である。それ以外の場合は何らかの解x _{0があり、すべての解の集合は}Fz + x ₀と表すことができる。ここでz はR ^kにあり、k = nランク ( A )、Fはn行k列の行列である。元の問題にx = Fz + x _{0を代入すると、次のようになる。}

${\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 ) 少ない変数があることに注意してください。これは、原理的には、等式制約のない凸最適化問題に注意を限定できることを意味します。ただし、実際には、等式制約を保持することが好まれることがよくあります。等式制約によって、一部のアルゴリズムがより効率的になり、問題を理解して分析しやすくなるためです。

以下の問題クラスはすべて凸最適化問題であり、または単純な変換によって凸最適化問題に還元できる: ^{[7] : chpt.4  [10]}

• 線形計画問題は最も単純な凸計画です。 LP では、目的関数と制約関数はすべて線形です。
• 二次計画法は次に簡単です。QP では、制約はすべて線形ですが、目的は凸二次関数である場合があります。
• 2 次コーンプログラミングの方が一般的です。
• 半正定値計画法はより一般的です。
• 円錐最適化はさらに一般的です - 右の図を参照してください。

その他の特殊なケースとしては、

• 最小二乗法
• 凸二次制約による二次最小化
• 幾何プログラミング
• 適切な制約によるエントロピー最大化。

凸最適化問題の有用な性質としては次のようなものがある: ^{[11] [7] : chpt.4}

• あらゆる局所最小値は大域最小値である。
• 最適集合は凸集合である。
• 目的関数が厳密に凸である場合、問題には最大で 1 つの最適点が存在します。

これらの結果は、ヒルベルト射影定理、分離超平面定理、ファルカスの補題など、ヒルベルト空間における関数解析の幾何学的概念とともに、凸最小化の理論で利用される。^[要出典]

最も簡単に解ける凸プログラムは、制約のない問題、つまり等式制約のみを持つ問題です。等式制約はすべて線形なので、線形代数で除去して目的関数に統合することができ、等式制約の問題を制約のない問題に変換できます。

制約のない（または等式制約のある）問題の中で、最も単純なのは目的関数が2次関数である問題である。これらの問題では、KKT条件（最適性に必要な条件）はすべて線形であるため、解析的に解くことができる。^{[7] : chpt.11}

2回微分可能な一般的な凸目的関数を持つ制約のない（または等式制約のある）問題には、ニュートン法を使用することができます。これは、一般的な制約のない凸問題を一連の二次問題に縮小したものと見ることができます。^{[7] ：chpt.11}ニュートン法は、適切なステップサイズを見つけるための直線探索と組み合わせることができ、急速に収束することが数学的に証明されています。

制約のない最小化のための他の効率的なアルゴリズムとしては、勾配降下法（最急降下法の特殊なケース）があります。

より難しい問題は、不等式制約のある問題です。これらの問題を解く一般的な方法は、不等式制約を強制するバリア関数を目的関数に追加して、制約のない問題に簡約することです。このような方法は、内点法と呼ばれます。^{[7] : chpt.11}内点法は、実行可能な内点を見つけることによって初期化される必要があります。これは、実行可能な点を見つけるか、実行可能な点が存在しないことを示します。フェーズ I 法は、通常、問題の検索をより単純な凸最適化問題に簡約することから成ります。^{[7] : chpt.11}

凸最適化問題は、次のような現代的な方法でも解くことができる。^[12]

• バンドル法（Wolfe、Lemaréchal、Kiwiel）および
• サブグラディエント投影法（Polyak）、
• 内点法[ ^1]は自己一致バリア関数^[13]と自己正則バリア関数^[14]を利用する。
• 切断面法
• 楕円体法
• 劣勾配法
• デュアルサブグラディエントとドリフトプラスペナルティ法

サブグラディエント法は簡単に実装できるため、広く使用されています。^[15]デュアルサブグラディエント法は、デュアル問題に適用されるサブグラディエント法です。ドリフトプラスペナルティ法はデュアルサブグラディエント法に似ていますが、主変数の時間平均を取ります。^[要出典]

コスト関数と不等式制約によって標準形式で与えられた凸最小化問題を考えます。この場合、領域は次のようになります。 ${\displaystyle f(x)}$${\displaystyle g_{i}(x)\leq 0}$${\displaystyle 1\leq i\leq m}$${\displaystyle {\mathcal {X}}}$

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

この問題のラグランジアン関数は^[16]

${\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).}$

においてを最小化するの各点に対して、ラグランジュ乗数と呼ばれる実数が存在し、これらの条件を同時に満たします。 ${\displaystyle x}$${\displaystyle X}$${\displaystyle f}$${\displaystyle X}$${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m},}$

1. ${\displaystyle x}$全体的に最小限に抑える${\displaystyle L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})}$${\displaystyle y\in X,}$
2. ${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,}$少なくとも1つ${\displaystyle \lambda _{k}>0,}$
3. ${\displaystyle \lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0}$（補完的な緩み）。

「厳密に実行可能な 点」、つまり${\displaystyle z}$

${\displaystyle g_{1}(z),\ldots ,g_{m}(z)<0,}$

上記の記述は、次のように強化することができます。 ${\displaystyle \lambda _{0}=1}$

逆に、 のスカラーに対してが(1)–(3) を満たす場合、 は に対して必ず最小化されます。 ${\displaystyle x}$${\displaystyle X}$ ${\displaystyle \lambda _{0},\ldots ,\lambda _{m}}$${\displaystyle \lambda _{0}=1}$${\displaystyle x}$${\displaystyle f}$${\displaystyle X}$

凸最適化のための大規模なソフトウェア エコシステムが存在します。このエコシステムには、ソルバーとモデリング ツール(またはインターフェイス) という 2 つの主なカテゴリがあります。

ソルバーはアルゴリズムを独自に実装し、通常は C で記述されます。ソルバーでは、モデリングの観点からは自然ではない非常に特殊な形式で最適化問題を指定する必要があります。モデリング ツールは、ユーザーがより高レベルの構文で最適化を指定できるようにする独立したソフトウェアです。モデリング ツールは、ユーザーの高レベル モデルとソルバーの入力/出力形式との間のすべての変換を管理します。

以下の表には、モデリング ツール (CVXPY や Convex.jl など) とソルバー (CVXOPT や MOSEK など) の組み合わせが示されています。この表は、決して網羅的なものではありません。

凸最適化は、自動制御システム、推定と信号処理、通信とネットワーク、電子回路設計、^{[7] ：17}データ分析とモデリング、金融、統計（最適実験計画）、^[21]構造最適化など、幅広い分野の問題をモデル化するために使用できます。これらの分野では、近似概念が効率的であることが証明されています。^{[7] [22]}凸最適化は、次の分野の問題をモデル化するために使用できます。

• ポートフォリオ最適化[ ^23]
• 最悪のリスク分析^[23]
• 最適な広告。^[23]
• 統計的回帰のバリエーション（正則化と分位回帰を含む）。^[23]
• モデルフィッティング^[23]（特に多クラス分類^[24]）。
• 発電の最適化^[24]
• 組み合わせ最適化[ ^24]
• 不確実性の非確率的モデリング^[25 ]
• 無線信号を用いた位置特定^[26]

凸最適化の拡張には、双凸関数、擬似凸関数、準凸関数の最適化が含まれます。凸解析の理論の拡張と非凸最小化問題を近似的に解く反復法は、抽象凸解析としても知られる一般化凸性の分野で行われます。 ^[要出典]

• 二重性
• カルーシュ・クーン・タッカー条件
• 最適化問題
• 近位勾配法
• 凸集合上のアルゴリズム問題

• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003).凸解析と最適化。ベルモント、マサチューセッツ州: Athena Scientific。ISBN 978-1-886529-45-8。
• Bertsekas, Dimitri P. (2009).凸最適化理論. ベルモント、マサチューセッツ州: Athena Scientific. ISBN 978-1-886529-31-1。
• Bertsekas, Dimitri P. (2015).凸最適化アルゴリズム. ベルモント、マサチューセッツ州: Athena Scientific. ISBN 978-1-886529-28-1。
• Borwein, Jonathan; Lewis, Adrian (2000). 凸解析と非線形最適化: 理論と例、第2版(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-6MR  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)。微分不可能な最適化のための降下法。数学の講義ノート。ニューヨーク：Springer- Verlag。ISBN 978-3-540-15642-0。
• ルマレシャル、クロード(2001)。 「ラグランジュ緩和」。 Michael Jünger と Denis Naddef (編)。計算による組み合わせ最適化: 2000 年 5 月 15 ～ 19 日にダグシュトゥール城で開催されたスプリング スクールの論文。コンピューターサイエンスの講義ノート。 Vol. 2241. ベルリン: Springer-Verlag。 112–156ページ。土井：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 コースのホームページ
• ブライアン・ボルチャーズ、凸最適化ソフトウェアの概要
• Lieven Vandenberghe と Stephen P. Boyd による凸最適化の本