ConvexOptimization
ConvexOptimization[f,cons,vars]
凸制約条件 cons に従って凸目的関数 f を最小にする変数 vars の値を求める.
ConvexOptimization[…,"prop"]
解のどの特性"prop"を返すべきかを指定する.
詳細とオプション
- 凸最適化は凸制約条件を持つ凸関数のための大域的非線形最適化である.凸問題については,大域的解が求まる.
- 凸最適化には,線形計画法,線形分数最適化,二次計画法,二次錐計画問題,半正定値計画問題,円錐最適化を含む,最適化の多くの形が含まれる.
- が凸なら,ConvexOptimization[-g,cons,vars]は g を最大にする.
- 凸最適化は次の問題を解く を求める.
-
最小化 制約条件 ただし - cons には の形式の等式条件が含まれるかもしれない.
- 混合整数凸最適化は,問題を解く および を求める.
-
最小化 制約条件 ただし - 目的関数が実数値のとき,ConvexOptimizationは の問題をまず実変数 に変換することで解く.ただし,かつ である.
- 変数指定 vars は,次の形のいずれかで変数を与える要素のリストでなければならない.
-
v という名前の変数と推測される次元 v∈Reals 実数のスカラー変数 v∈Integers 整数のスカラー変数 v∈Complexes 複素数のスカラー変数 v∈ℛ 幾何学領域 に制限されたベクトル変数 v∈Vectors[n,dom] ,またはのベクトル変数 v∈Matrices[{m,n},dom] ,,の行列変数 - ConvexOptimizationは,最小化問題を解くための効率的なメソッドを見付けるために必要な変換を自動的に行う.
- 解かれた主最小化問題には関連する最大化問題(ラグランジュ双対問題)がある.双対最大値は常に主最小値以下であるので,下限を与える.双対マキシマイザは,最小値の制約上限に対する感度を含む,主問題についての情報を与える.
- 次は,可能な解の特性"prop" である.
-
"PrimalMinimizer" を最小化する変数値のリスト "PrimalMinimizerRules" を最小化する変数の値 vars={v1,…} "PrimalMinimizerVector" を最小化するベクトル "PrimalMinimumValue" 最小値 "DualMaximizer" 双対問題を最大にするベクトル "DualMaximumValue" 双対最大値 "DualityGap" 双対最適値と主最適値の差 "Slack" 不等式制約を等式に変換するベクトル {"prop1","prop2",…} いくつかの解の特性 - 次のオプションが使用できる.
-
MaxIterations Automatic 使用する最大反復回数 Method Automatic 使用するメソッド PerformanceGoal $PerformanceGoal 最適化しようとするパフォーマンスの局面 Tolerance Automatic 内部の比較で使用する許容度 WorkingPrecision MachinePrecision 内部計算で使用する精度 - オプションMethodmethod を使って使用するメソッドが指定できる.以下は使用可能なメソッドである.
-
Automatic メソッドを自動選択する solver 可能な場合は,問題を解くために solver が使えるようにするために問題を変換する "SCS" SCS(分割円錐ソルバ)ライブラリ "CSDP" CSDP(COIN半定値計画)ライブラリ "DSDP" DSDP(半定値計画)ライブラリ "MOSEK" 商用MOSEK凸最適化ソルバ "Gurobi" 商用Gurobi線形・二次最適化ソルバ "Xpress" 商用Xpress形・二次最適化ソルバ - Methodsolver を使って,使われる双対形式が solver についてドキュメントされている形式と一致するように,特定のソルバを使うように指定してもよい.使用可能なソルバは,LinearOptimization,LinearFractionalOptimization,QuadraticOptimization,SecondOrderConeOptimization,SemidefiniteOptimization,ConicOptimization,GeometricOptimizationである.
例題
すべて開くすべて閉じるスコープ (28)
基本的な用法 (12)
線形不等式条件の中にはVectorGreaterEqualで表せるものがある:
v>= または\[VectorGreaterEqual]を使ってベクトル不等式の符号を入力する:
に縫い込まれている可能性があるので,不等式 は と同じではないかもしれない:
への意図しない縫込みを避けるためにはInactive[Plus]を使うとよい:
パラメータが一定の等式を使って意図しない への縫込みを避ける:
VectorGreaterEqualは"NonNegativeCone"についての円錐不等式を表す:
円錐の次元を明示的に指定するためには{"NonNegativeCone",n}を使う:
"NormCone"の錐不等式を使うことで制約条件 を指定する:
ベクトル変数 とIndexed[x,i]を使って個々の成分を指定する:
ベクトル変数の次元が曖昧なときは,Vectors[n,Reals]を使って指定する:
NonNegativeReals ()を使って非負の制約条件を指定する:
周囲長が最大で1で縦が最大で横の半分である長方形の面積を最大にする:
と が正なら,この問題はGeometricOptimization法で解くことができる:
正であると暗黙のうちに仮定してGeometricOptimization法を使う:
整数変数 (4)
Integersを使って整数変数を指定する:
Vectors[n,Integers]を使ってベクトル変数上に整数領域を指定する:
NonNegativeIntegers ()を使って非負の整数領域条件を指定する:
NonPositiveIntegers ()を使って非正の整数領域条件を指定する:
オプション (13)
Method (8)
PerformanceGoal (1)
オプションPerformanceGoalのデフォルト値は$PerformanceGoalである:
PerformanceGoal"Quality"を使ってより正確な結果を得る:
PerformanceGoal"Speed"を使ってより速く,しかし質を犠牲にして,結果を得る:
Tolerance (2)
WorkingPrecision (2)
デフォルトの作業精度はMachinePrecisionである:
WorkingPrecisionInfinityを使うと,可能な場合は厳密解が与えられる:
MachinePrecisionと ∞ 以外のWorkingPrecisionは拡張精度をサポートするメソッドを使おうとする:
WorkingPrecisionAutomaticを使うと入力問題の精度を使おうとする:
現在のところ,厳密計算で二次目的関数の問題を解く方法はない.要求された精度がサポートされていない場合,計算は機械精度で行われる:
アプリケーション (30)
基本的なモデリング変換 (11)
に従って を最大化する.目的関数を否定することで最大化問題を解く:
に従って を最小化する.制約条件 は凸ではないので,半定値制約条件を使って凸性を明示的にする:
左上のすべての部分行列が非負のときかつそのときに限り,行列は半正定値である:
のときは を仮定して,に従ってを最小化する.補助変数 を使うと,目的は となるように を最小化することになる:
シューア補行列の制約条件には,なら,のときかつそのときに限りブロック行列とある.したがって,のときかつそのときに限り である.縫込みを避けるための制約条件の構築にInactive[Plus]を使う:
エピグラフ変換を使って,線形目的関数と追加変数および制約条件で問題が構築できる:
この形式なら,問題はConicOptimizationを使って直接解ける:
を最小化する.ただし, は非減少関数で,代りに を最小化する.主ミニマイザ はどちらの問題でも同じままである.に従って を最小化することを考える:
ConvexOptimizationは,この変換を自動的に行う:
決定変数, に線形に依存する対称行列の最大固有値を最小化するを求める.は と同じ(ただし,はの第 固有値)なので,この問題は,線形行列不等式として定式化できる.線形行列関数 を定義する:
実対称行列 は直交行列 によってとなるように対角化できる.したがって,のときかつそのときに限り である.任意の について を取ると,になる.したがって,のときかつそのときに限り である.数値的にシミュレーションを行ってこれらの式が等しいことを示す:
モンテカルロシミュレーションを実行して結果の妥当性を確認する:
決定変数に線形依存する対称行列 の最小固有値を最大にするを求める.線形行列関数 を定義する:
は と等しいので(ただし, は の 番目の固有値),この問題は,線形行列不等式として定式化できる. を最大化するために を最小化する:
モンテカルロシミュレーションを実行して結果の妥当性を確認する:
決定変数に線形依存する対称行列 の最大固有値と最小固有値の差を最小にするを求める.線形行列関数 を定義する:
は と等しいので(ただし,は の第 固有値),この問題は,線形行列不等式として定式化できる.結果の問題を解く:
この場合は,最小固有値と最大固有値が一致するので差は0である:
決定変数に線形依存する対称行列 の(絶対値での)最大固有値を最小化する:
最大固有値は を満足する.の(絶対値が)最大の負の固有値はの最大固有値で,を満足する:
決定変数に線形依存する対称行列 の最大特異値 を最小化するを求める:
の最大特異値 は の最大固有値の平方根であり,上記の例より,またはを満足する:
楕円体,二次円錐,放物面を含む二次集合 を求め,かどうかを判定する.ただし,は対称行列,はベクトル,はスカラーである:
集合 が全次元であると仮定すると,S-procedureには となるような非負の数 が存在するときかつそのときに限り であるとある.非負の が存在することを視覚的に見る:
幾何学の問題 (8)
面積4の長方形の対角線の長さを最小にする.ただし,縦の3倍と横を足したものが7未満とする:
中心が と で半径が1の2つの円板の最短距離を求める.を円板1の上の点,を円板2の上の点とする.目的は,制約条件に従ってを最小にすることである:
表面積が最大で1の楕円体の体積を最大にする主軸の長さの半分を求める:
以下は球面である.軸の長さについての追加的な制約条件を含めるとこれが変わる:
与えられた領域を包み込む最小の球体の半径 と中心 を求める:
包み込んでいる最小の球体はBoundingRegionを使って効率的に求めることができる:
凸多面体の解析的中心を求める.解析的中心は制約条件までの距離の積を最大にする点である:
凸多面体の各線分は半平面 の交線として表すことができる.線形不等式を抽出する:
目的はを最大にすることである.を取って目的関数を否定する.変換された目的関数は である:
補助変数 を使うと,変換された目的は,制約条件 に従う になる:
S-procedureを使うと,であるときかつそのときに限り,楕円2が楕円1の部分集合であることがわかる:
楕円体を明示的な形に変換し,楕円2が楕円1の中にあることを確認する:
テストは,楕円体2が楕円体1の部分集合ではなく,この問題は実行不可能であることを示している:
凸多面体内に収められるとしてパラメータ化される楕円の最大面積を求める:
凸多面体の各線分は,半平面 の交線として表すことができる.線形不等式を抽出する:
半平面にパラメータ化を適用するとが与えられる..したがって,制約条件は である:
面積を最小にするのはを最小にすることと同じであるが,それはを最小にすることと同じである:
体積を最小にすることで3Dの点集合を含むとしてパラメータ化された最小の楕円体を求める:
体積を最小にすることはを最小にすることに等しいが,これはを最小にすることに等しい:
境界楕円体は,必ずしも体積が最小ではないが,BoundingRegionを使って求めることができる:
データフィット問題 (4)
指定された行列 a とベクトル b についての制約条件 に従ってを最小化する:
データの最初と最後の点が曲線上にあるようにして,三次元曲線を離散データにフィットする:
DesignMatrixを使って行列を構築する:
最初と最後の点が必ず曲線上にあるようになる制約条件を定義する:
を最小化することで,非線形離散データの外れ値にあまり敏感ではないフィットを求める:
複素数 についてを最小化することで,複素データへの正規化フィットを求める:
DesignMatrixを使って基底について行列 を構築する:
平方和表現 (1)
分類問題 (3)
分割するためには,集合1は を,集合2は を満足しなければならない:
目的はを最小にすることであるが,これは と の間の厚みの2倍を与える:
DesignMatrixを使って2つの集合についての二次多項式データ行列を構築する:
分割するためには,集合は を,集合2は を満足しなければならない:
与えられた点集合 を別のグループに分割する.これは,を最小にして各グループの中心 を求めることで行える.ただし,は与えられたローカルカーネルで は与えられたペナルティパラメータである:
カーネル は,で他では の -最近傍()関数である.この問題のために の最近傍が選ばれている:
施設の位置についての問題 (1)
ポートフォリオの最適化 (1)
リスクを最小に抑えながらリターンを最大化するために6つの株式に投資するための資本 の配分を求める:
リターンは で与えられる.ただし, は各株式の期待されるリターンの値のベクトルである:
リスクは で与えられる. はリスク回避パラメータで である:
目的は,指定されたリスク回避パラメータについてリスクを最小にしながらリターンを最大にすることである:
株式売買による株式の市場価格への影響は,でモデル化されるが,これは,エピグラフ変換を使ったPower Coneによってモデル化できる:
重み は0より大きくなければならず,重みと市場への影響のコストを1に加算する必要がある:
リスク回避パラメータの範囲についてリターンと対応するリスクを計算する:
の範囲における最適な は,リターンとリスクの間のトレードオフの上限を示す:
市場コストを考慮することで低リスク回避のための分散ポートフォリオを得ることができるが,リスク回避が高い場合は分散の少ない株式を購入するため,市場の影響コストが支配的になる:
テキスト
Wolfram Research (2020), ConvexOptimization, Wolfram言語関数, https://reference.wolfram.com/language/ref/ConvexOptimization.html.
CMS
Wolfram Language. 2020. "ConvexOptimization." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/ConvexOptimization.html.
APA
Wolfram Language. (2020). ConvexOptimization. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/ConvexOptimization.html