凸最適化

凸最適化は、凸集合上の凸関数を最小化する問題（あるいは、凸集合上の凹関数を最大化する問題）を研究する数学的最適化の分野である。凸最適化問題の多くのクラスは多項式時間アルゴリズムを許容するが^[1] 、数学的最適化は一般にNP困難である^[2]^[3]^[4]。

意味

抽象的な形式

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

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

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

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

。

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

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

標準フォーム

凸最適化問題は次のように書かれるとき標準形である。

{\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]^{: 第4章}

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

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

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

エピグラフ形式（線形目的の標準形式）

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

{\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}

{\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 ₀があり、すべての解の集合はFz + x ₀と表すことができます。ここで、zはR ^k、k = nランク ( A )、Fはn行k列の行列です。元の問題にx = Fz + x _{0を代入すると、次のようになります。}

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

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

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

プロパティ

凸最適化問題の有用な性質は以下の通りである: ^[11]^[7]^{: chpt.4}

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

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

アルゴリズム

制約なし問題と等式制約あり問題

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

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

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

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

一般的な問題

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

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

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

劣勾配法は実装が簡単なため、広く利用されている。^[15]双対劣勾配法は、双対問題に適用される劣勾配法である。ドリフト・プラス・ペナルティ法は双対劣勾配法に似ているが、主変数の時間平均をとる。^[要出典]

ラグランジュ乗数

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

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

この問題のラグランジアン関数は^{[16]である。}

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$ $X$ $f$ $X$ $\lambda _{0},\lambda _{1},\ldots ,\lambda _{m},$

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

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

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

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

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

ソフトウェア

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

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

以下に2つの表を示します。最初の表はモデリングツール（CVXPYやJuMP.jlなど）を示し、2番目の表はソルバー（SCSやMOSEKなど）を示しています。ただし、これらがすべてを網羅しているわけではありません。


プログラム	言語	説明	フォス？	参照
CVX	MATLAB	SeDuMi および SDPT3 ソルバーとのインターフェース。凸最適化問題のみを表現するように設計されています。	はい	^[17]
CVXPY	パイソン		はい	^[18]
凸状.jl	ジュリア	規律凸計画法、多くのソルバーをサポートします。	はい	^[19]
CVXR	R		はい	^[20]
GAMS		線形、非線形、混合整数線形/非線形、および 2 次円錐計画問題のモデリングシステム。	いいえ	^[17]
グロプティポリ	MATLAB、オクターブ	多項式最適化のためのモデリングシステム。	はい	^[17]
ジャンプ	ジュリア	多数のソルバーをサポートします。整数最適化、非線形最適化、および一部の非凸最適化もサポートします。	はい	^[21]
ローマ		ロバスト最適化のためのモデリングシステム。分布的にロバストな最適化と不確実性セットをサポートします。	はい	^[17]
ソスツール		多項式最適化のためのモデリングシステム。SDPT3とSeDuMiを使用します。Symbolic Computation Toolboxが必要です。	はい	^[17]
スパースポップ		多項式最適化のためのモデリングシステム。SDPAまたはSeDuMiソルバーを使用します。	はい	^[17]
ヤルミップ	MATLAB、オクターブ	CPLEX、GUROBI、MOSEK、SDPT3、SEDUMI、CSDP、SDPA、PENNONソルバーとのインターフェースを備え、整数最適化、非線形最適化、および一部の非凸最適化もサポートしています。LP /SOCP/SDP制約における不確実性を考慮したロバスト最適化を実行できます。	はい	^[17]


プログラム	言語	説明	フォス？	参照
エイムズ		線形計画法（MOSEKを用いて2次円錐計画法を解く）と混合整数線形計画法において、ロバストな最適化を実行できます。LP + SDPおよびロバストバージョン用のモデリングパッケージ。	いいえ	^[17]
CPLEX		LP + SOCPの主双対法をサポートします。LP、QP、SOCP、混合整数線形計画問題を解くことができます。	いいえ	^[17]
CSDP	C	LP + SDPの主双対法をサポートします。MATLAB、R、Python用のインターフェースが用意されています。並列版も利用可能です。SDPソルバーです。	はい	^[17]
CVXOPT	パイソン	LP + SOCP + SDPのプライマル・デュアル法をサポートします。Nesterov-Toddスケーリングを使用します。MOSEKおよびDSDPとのインターフェースを備えています。	はい	^[17]
モセク		LP + SOCP のプライマルデュアル法をサポートします。	いいえ	^[17]
セドゥミ	MATLAB、Octave、MEX	LP + SOCP + SDP を解きます。LP + SOCP + SDP の主双対法をサポートします。	はい	^[17]
SDPA	C++	LP + SDPを解きます。LP + SDPの主双対法をサポートします。並列化バージョンと拡張精度バージョンも利用可能です。	はい	^[17]
SDPT3	MATLAB、Octave、MEX	LP + SOCP + SDP を解きます。LP + SOCP + SDP の主双対法をサポートします。	はい	^[17]
コニックバンドル		LP + SOCP + SDPの汎用コードをサポートします。バンドル法を使用します。SDPおよびSOCP制約を特別にサポートします。	はい	^[17]
DSDP		LP + SDPの汎用コードをサポートします。双対内点法を使用します。	はい	^[17]
ロコ		非線形計画問題として扱う SOCP の汎用コードをサポートします。	いいえ	^[17]
槍旗		汎用コードをサポートします。特にSDP制約のある問題には、拡張ラグランジュ法を使用します。	いいえ	^[17]
SDPLR		汎用コードをサポートします。拡張ラグランジュ法を用いた低ランク因数分解を使用します。	はい	^[17]

アプリケーション

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

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

拡張機能

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

参照

注記

^ ab ネステロフとネミロフスキー 1994
^ Murty, Katta; Kabadi, Santosh (1987). 「二次計画法と非線形計画法におけるNP完全問題」.数学プログラミング. 39 (2): 117– 129. 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.
^ Hiriart-Uruty、ジャン-バティスト;ルマレシャル、クロード (1996)。凸解析と最小化アルゴリズム: 基礎。スプリンガー。 p. 291.ISBN 9783540568506。
^ Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich (2001). 現代凸最適化に関する講義：解析、アルゴリズム、そして工学的応用. pp. 335– 336. ISBN 9780898714913。
^ abcdefghijkl ボイド、スティーブン;ヴァンデンバーグ、リーヴェン (2004)。凸型最適化(PDF)。ケンブリッジ大学出版局。ISBN 978-0-521-83378-3. 2021年4月12日閲覧。
^ 「最適化問題の種類 - 凸最適化」。2011年1月9日。
^ ab 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). 「ラグランジュ乗数と最適性」(PDF) . SIAM Review . 35 (2): 183– 238. 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). 「線形および半正定値最適化のための自己正則関数と新しい探索方向」.数理計画. 93 (1): 129– 171. doi :10.1007/s101070200296. ISSN 0025-5610. S2CID 28882966.
^ 「数値最適化」 . Springerシリーズオペレーションズ・リサーチ・アンド・ファイナンシャル・エンジニアリング. 2006. doi :10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1。
^ ブライアン・ビービス、イアン・M・ドブス（1990年）「静的最適化」『経済分析のための最適化と安定性理論』ニューヨーク：ケンブリッジ大学出版局、p. 40. ISBN 0-521-33605-8。
^ abcdefghijklmnopqrst Borchers, Brian. 「凸最適化ソフトウェアの概要」(PDF) 。 2017年9月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). 「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.
^ クリステンセン/クラーブリング、chpt. 4.
^ Schmit, LA; Fleury, C. 1980:近似概念とデュアルメソッドを組み合わせた構造合成. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260
^ abcde Boyd, Stephen; Diamond, Stephen; Zhang, Junzi; Agrawal, Akshay. 「凸最適化アプリケーション」(PDF) 。 2015年10月1日時点のオリジナルよりアーカイブ(PDF) 。 2021年4月12日閲覧。
^ abc Malick, Jérôme (2011年9月28日). 「凸最適化：応用、定式化、緩和法」(PDF) . 2021年4月12日時点のオリジナルよりアーカイブ(PDF) . 2021年4月12日閲覧。
^ Ben Haim Y.とElishakoff I.、「応用力学における不確実性の凸モデル」、Elsevier Science Publishers、アムステルダム、1990年
^ Ahmad Bazzi、Dirk TM Slock、Lisa Meilhac。「相互結合がある場合のオンライン到来角推定」2016 IEEE統計信号処理ワークショップ（SSP）。IEEE、2016年。

参考文献

Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003).凸解析と最適化. ベルモント, MA.: Athena Scientific. ISBN 978-1-886529-45-8。
ベルツェカス、ディミトリ・P. (2009).凸最適化理論. ベルモント、マサチューセッツ州: アテナ・サイエンティフィック. ISBN 978-1-886529-31-1。
Bertsekas, Dimitri P. (2015).凸最適化アルゴリズム. ベルモント, MA.: Athena Scientific. ISBN 978-1-886529-28-1。
ボルウェイン、ジョナサン、ルイス、エイドリアン (2000). 凸解析と非線形最適化：理論と例第2版(PDF) . シュプリンガー. 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。
キヴィエル、クリストフ・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。土井:10.1007/3-540-45586-8_4。ISBN 978-3-540-42877-0. MR 1900016. S2CID 9048698.
ネステロフ、ユリ;ネミロフスキー、アルカディ (1994)。凸計画法における内点多項式法。サイアム。
ネステロフ、ユーリイ (2004). 『凸最適化入門講義』クルーワー・アカデミック・パブリッシャーズ
ロッカフェラー, 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 による凸最適化の本

[Nesterov_1994-1] ネステロフとネミロフスキー 1994

[2] Murty, Katta; Kabadi, Santosh (1987). 「二次計画法と非線形計画法におけるNP完全問題」.数学プログラミング. 39 (2): 117– 129. doi :10.1007/BF02592948. hdl : 2027.42/6740 . S2CID 30500771.

[3] Sahni, S. 「計算関連の問題」、SIAM Journal on Computing、3、262--279、1974 年。

[4] Pardalos, Panos M.; Vavasis, Stephen A. (1991). 「負の固有値を1つ持つ二次計画法はNP困難である」 . Journal of Global Optimization . 1 : 15–22 . doi :10.1007/BF00120662.

[5] Hiriart-Uruty、ジャン-バティスト;ルマレシャル、クロード (1996)。凸解析と最小化アルゴリズム: 基礎。スプリンガー。 p. 291.ISBN 9783540568506。

[6] Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich (2001). 現代凸最適化に関する講義：解析、アルゴリズム、そして工学的応用. pp. 335– 336. ISBN 9780898714913。

[:2-7] ボイド、スティーブン;ヴァンデンバーグ、リーヴェン (2004)。凸型最適化(PDF)。ケンブリッジ大学出版局。ISBN 978-0-521-83378-3. 2021年4月12日閲覧。

[8] 「最適化問題の種類 - 凸最適化」。2011年1月9日。

[:02-9] Arkadi Nemirovsky (2004). 凸計画法における内点多項式時間法.

[rewriting-10] 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.

[rockafellar93-11] Rockafellar, R. Tyrrell (1993). 「ラグランジュ乗数と最適性」(PDF) . SIAM Review . 35 (2): 183– 238. CiteSeerX 10.1.1.161.7209 . doi :10.1137/1035044.

[12] 凸最小化の方法については、Hiriart-UrrutyとLemaréchalの著書（バンドル）およびRuszczyński、 Bertsekas、BoydとVandenbergheの教科書（内点）を参照してください。

[13] ネステロフ、ユーリイ、アルカディ、ネミロフスキー (1995).凸計画法における内点多項式アルゴリズム. 応用数学協会. ISBN 978-0898715156。

[PengRoos2002-14] Peng, Jiming; Roos, Cornelis; Terlaky, Tamás (2002). 「線形および半正定値最適化のための自己正則関数と新しい探索方向」.数理計画. 93 (1): 129– 171. doi :10.1007/s101070200296. ISSN 0025-5610. S2CID 28882966.

[15] 「数値最適化」 . Springerシリーズオペレーションズ・リサーチ・アンド・ファイナンシャル・エンジニアリング. 2006. doi :10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1。

[16] ブライアン・ビービス、イアン・M・ドブス（1990年）「静的最適化」『経済分析のための最適化と安定性理論』ニューヨーク：ケンブリッジ大学出版局、p. 40. ISBN 0-521-33605-8。

[:3-17] qrst Borchers, Brian. 「凸最適化ソフトウェアの概要」(PDF) 。 2017年9月18日時点のオリジナル(PDF)からアーカイブ。 2021年4月12日閲覧。

[18] 「CVXPY 1.1へようこそ — CVXPY 1.1.11ドキュメント」www.cvxpy.org . 2021年4月12日閲覧。

[19] Udell, Madeleine; Mohan, Karanveer; Zeng, David; Hong, Jenny; Diamond, Steven; Boyd, Stephen (2014-10-17). 「Juliaにおける凸最適化」. arXiv : 1410.4821 [math.OC].

[20] 「規律凸最適化 - CVXR」www.cvxgrp.org . 2021年6月17日閲覧。

[21] 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.

[22] クリステンセン/クラーブリング、chpt. 4.

[23] Schmit, LA; Fleury, C. 1980:近似概念とデュアルメソッドを組み合わせた構造合成. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260

[:0-24] Boyd, Stephen; Diamond, Stephen; Zhang, Junzi; Agrawal, Akshay. 「凸最適化アプリケーション」(PDF) 。 2015年10月1日時点のオリジナルよりアーカイブ(PDF) 。 2021年4月12日閲覧。

[:1-25] Malick, Jérôme (2011年9月28日). 「凸最適化：応用、定式化、緩和法」(PDF) . 2021年4月12日時点のオリジナルよりアーカイブ(PDF) . 2021年4月12日閲覧。

[26] Ben Haim Y.とElishakoff I.、「応用力学における不確実性の凸モデル」、Elsevier Science Publishers、アムステルダム、1990年

[27] Ahmad Bazzi、Dirk TM Slock、Lisa Meilhac。「相互結合がある場合のオンライン到来角推定」2016 IEEE統計信号処理ワークショップ（SSP）。IEEE、2016年。

v t e 凸解析と変分解析
基本概念	凸結合凸関数凸集合
トピック（リスト）	ショケ理論凸幾何学凸距離空間凸最適化二重性ラグランジュ乗数ルジャンドル変換局所凸位相ベクトル空間シンプレックス
地図	凸共役凹面（閉店 K- 対数的にちゃんとした擬似- 準凸関数 Invex関数ルジャンドル変換半連続性部分微分
主な結果（リスト）	カラテオドリーの定理エケランドの変分原理フェンシェル・モローの定理フェンチェル・ヤング不等式ジェンセンの不等式エルミート・アダマール不等式クライン・ミルマン定理マズールの補題シャプレー・フォークマンの補題ロビンソン・ウルシェスクシモンズウルシェスク
セット	凸包（直交、擬似）凸集合有効ドメイン碑文ヒポグラフジョン楕円体レンズ放射状集合/代数的内部ゾノトープ
シリーズ	関連する凸級数（（cs、lcs）閉、（cs、bcs）完全、（下）理想的凸、（H x）、および（Hw x））
二重性	デュアルシステム双対性ギャップ強い二重性弱い双対性
アプリケーションおよび関連	経済における凸性