ConvexOptimization

ConvexOptimization[f,cons,vars]

凸制約条件 cons に従って凸目的関数 f を最小にする変数 vars の値を求める.

ConvexOptimization[,"prop"]

解のどの特性"prop"を返すべきかを指定する.

詳細とオプション

  • 凸最適化は凸制約条件を持つ凸関数のための大域的非線形最適化である.凸問題については,大域的解が求まる.
  • 凸最適化には,線形計画法,線形分数最適化,二次計画法,二次錐計画問題,半正定値計画問題,円錐最適化を含む,最適化の多くの形が含まれる.
  • が凸なら,ConvexOptimization[-g,cons,vars]g を最大にする.
  • 凸最適化は次の問題を解く を求める.
  • 最小化
    制約条件
    ただし
  • cons には の形式の等式条件が含まれるかもしれない.
  • 混合整数凸最適化は,問題を解く および を求める.
  • 最小化
    制約条件
    ただし
  • 目的関数が実数値のとき,ConvexOptimizationx in TemplateBox[{}, Complexes]^nの問題をまず実変数 に変換することで解く.ただし,かつ である.
  • 変数指定 vars は,次の形のいずれかで変数を与える要素のリストでなければならない.
  • v という名前の変数と推測される次元
    vReals実数のスカラー変数
    vIntegers整数のスカラー変数
    vComplexes複素数のスカラー変数
    v幾何学領域 に制限されたベクトル変数
    vVectors[n,dom]またはTemplateBox[{}, Complexes]^nのベクトル変数
    vMatrices[{m,n},dom]TemplateBox[{}, Complexes]^(m x n)の行列変数
  • ConvexOptimizationは,最小化問題を解くための効率的なメソッドを見付けるために必要な変換を自動的に行う.
  • 解かれた主最小化問題には関連する最大化問題(ラグランジュ双対問題)がある.双対最大値は常に主最小値以下であるので,下限を与える.双対マキシマイザは,最小値の制約上限に対する感度を含む,主問題についての情報を与える.
  • 次は,可能な解の特性"prop" である.
  • "PrimalMinimizer" を最小化する変数値のリスト
    "PrimalMinimizerRules" を最小化する変数の値 vars={v1,}
    "PrimalMinimizerVector" を最小化するベクトル
    "PrimalMinimumValue"最小値
    "DualMaximizer"双対問題を最大にするベクトル
    "DualMaximumValue"双対最大値
    "DualityGap"双対最適値と主最適値の差
    "Slack"不等式制約を等式に変換するベクトル
    {"prop1","prop2",} いくつかの解の特性
  • 次のオプションが使用できる.
  • MaxIterationsAutomatic使用する最大反復回数
    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 についてドキュメントされている形式と一致するように,特定のソルバを使うように指定してもよい.使用可能なソルバは,LinearOptimizationLinearFractionalOptimizationQuadraticOptimizationSecondOrderConeOptimizationSemidefiniteOptimizationConicOptimizationGeometricOptimizationである.

例題

すべて開くすべて閉じる

  (2)

線形制約条件に従ってTemplateBox[{{x, +, {2, y}}}, Abs]を最小化する:

いくつかの要素についての制約条件に従って行列のノルムを最小化する:

スコープ  (28)

基本的な用法  (12)

制約条件 に従って を最小化する:

線形不等式条件の中にはVectorGreaterEqualで表せるものがある:

v>= または\[VectorGreaterEqual]を使ってベクトル不等式の符号を入力する:

スカラー不等式を使った同等の形:

ベクトル変数 を使う:

に縫い込まれている可能性があるので,不等式 と同じではないかもしれない:

への意図しない縫込みを避けるためにはInactive[Plus]を使うとよい:

パラメータが一定の等式を使って意図しない への縫込みを避ける:

VectorGreaterEqual"NonNegativeCone"についての円錐不等式を表す:

円錐の次元を明示的に指定するためには{"NonNegativeCone",n}を使う:

解を求める:

制約条件 に従って を最小化する:

"NormCone"の錐不等式を使うことで制約条件 を指定する:

解を求める:

半正定値行列制約条件(x 1; 1 y)_(TemplateBox[{2}, SemidefiniteConeList])0に従って を最小化する:

解を求める:

ベクトル変数 Indexed[x,i]を使って個々の成分を指定する:

ベクトル変数の次元が曖昧なときは,Vectors[n,Reals]を使って指定する:

NonNegativeReals ()を使って非負の制約条件を指定する:

ベクトル不等式 を使った同等の形:

周囲長が最大で1で縦が最大で横の半分である長方形の面積を最大にする:

が正なら,この問題はGeometricOptimization法で解くことができる:

正であると暗黙のうちに仮定してGeometricOptimization法を使う:

整数変数  (4)

Integersを使って整数変数を指定する:

Vectors[n,Integers]を使ってベクトル変数上に整数領域を指定する:

NonNegativeIntegers ()を使って非負の整数領域条件を指定する:

NonPositiveIntegers ()を使って非正の整数領域条件を指定する:

複素変数  (8)

Complexesを使って複素変数を指定する:

実数目的関数を複素変数と複素制約条件 で最小化する:

とする.制約条件を実数成分まで拡張すると以下が与えられる:

実数値目的関数と複素変数および制約条件で問題を解く:

同じ問題を実変数と制約条件で解く:

二次目的関数 をエルミート行列 および実数値変数と一緒に使う:

目的関数(1/2)Inactive[Dot][Conjugate[x],q,x]をエルミート行列 および複素変数と一緒に使う:

二次制約 をエルミート行列 および実数値変数と一緒に使う:

制約条件(1/2)Inactive[Dot][Conjugate[x],q,x]d をエルミート行列 および複素変数と一緒に使う:

行列 が半正定値になるような,最小で2ノルム(最大特異値)のエルミート行列を求める:

以下は,最大特異値についての最小値である:

線形行列不等式制約 a_(0)+a_(1) x_(1)+a_(2) x_(2)>=_(TemplateBox[{2}, SemidefiniteConeList])0をエルミート行列あるいは実数対称行列と一緒に使う:

線形行列不等式の変数は,総和がエルミートのままであるためには実数でなければならない:

主モデル特性  (1)

を三角形 と円板 の交点上で最小化する:

主ミニマイザをベクトルとして得る:

最小値を得る:

解をプロットする:

双対モデル特性  (3)

および に従って を最小化する:

双対問題は,に従ってを最大化することである:

強双対性のために主最小値と双対最大値は一致する:

これは,0の双対ギャップを持つことに等しい.一般に,最適点で である:

解の特性を使って双対最大値と双対マキシマイザを得る:

"DualMaximizer"は以下で得られる:

双対マキシマイザベクトル分割は双対円錐の数と次元をマッチする:

特定の問題タイプのソルバに対して双対形式を得るために,これをメソッドオプションとして指定する:

オプション  (13)

Method  (8)

"SCS"は分割円錐ソルバ法である:

"CSDP"は半定値問題についての内点法である:

"DSDP"は,半定値問題についてのまた別の内点法である:

"IPOPT"は,非線形問題についての内点法である:

メソッドによってデフォルトの許容範囲が異なるが,これは確度と精度に影響する:

厳密解と近似解を計算する:

"SCS"のデフォルトの許容範囲はである:

"CSDP""DSDP""IPOPT"のデフォルトの許容範囲はである:

"SCS"法は,指定されるとデフォルトの許容範囲が10-3のSCSライブラリとともに呼び出される:

デフォルトオプションでは,問題は"SCS"法で許容範囲は10-6で解かれる:

半正定制約条件に変換される制約条件に"CSDP"法または"DSDP"法を使う:

"CSDP"法を使って問題を解く:

"DSDP"法を使って問題を解く:

"CSDP"および"DSDP"が使えないときに,"IPOPT"法を使って正確な解を得る:

"IPOPT""SCS"より正確な結果を生成するが,はるかに遅いことが多い:

かかった時間を"SCS"法と比較する:

PerformanceGoal  (1)

オプションPerformanceGoalのデフォルト値は$PerformanceGoalである:

PerformanceGoal"Quality"を使ってより正確な結果を得る:

PerformanceGoal"Speed"を使ってより速く,しかし質を犠牲にして,結果を得る:

かかった時間を比較する:

"Speed"をゴールにすると,結果はあまり正確ではない:

Tolerance  (2)

Toleranceの設定を小さくするとより厳密な結果になる:

Minimizeで最小値の厳密値を計算する:

Toleranceの設定を変えて最小値における誤差を計算する:

許容範囲に対する最小値の誤差の変化を可視化する:

Toleranceの設定を小さくすると答はより厳密になるが,計算時間が長くなるかもしれない:

許容範囲を狭めるとより厳密な答が与えられる:

WorkingPrecision  (2)

デフォルトの作業精度はMachinePrecisionである:

WorkingPrecisionInfinityを使うと,可能な場合は厳密解が与えられる:

MachinePrecision 以外のWorkingPrecisionは拡張精度をサポートするメソッドを使おうとする:

WorkingPrecisionAutomaticを使うと入力問題の精度を使おうとする:

24桁の精度で二次目的関数の問題を解く:

現在のところ,厳密計算で二次目的関数の問題を解く方法はない.要求された精度がサポートされていない場合,計算は機械精度で行われる:

アプリケーション  (30)

基本的なモデリング変換  (11)

に従って を最大化する.目的関数を否定することで最大化問題を解く:

主最小値を否定することで対応する最大値を得る:

に従って を最小化する.制約条件 は凸ではないので,半定値制約条件を使って凸性を明示的にする:

左上のすべての部分行列が非負のときかつそのときに限り,行列は半正定値である:

解を求める:

のときは を仮定して,に従ってを最小化する.補助変数 を使うと,目的は となるように を最小化することになる:

を示唆することを確かめる:

シューア補行列の制約条件には,なら,のときかつそのときに限りブロック行列とある.したがって,のときかつそのときに限り である.縫込みを避けるための制約条件の構築にInactive[Plus]を使う:

を中心とするすべての楕円上でTemplateBox[{x}, Norm] を最小化する:

エピグラフ変換を使って,線形目的関数と追加変数および制約条件で問題が構築できる:

この形式なら,問題はConicOptimizationを使って直接解ける:

を最小化する.ただし, は非減少関数で,代りに を最小化する.主ミニマイザ はどちらの問題でも同じままである.に従って を最小化することを考える:

の最小値は の最小値に適用することで得られる:

ConvexOptimizationは,この変換を自動的に行う:

決定変数 に線形に依存する対称行列の最大固有値を最小化するを求める. と同じ(ただし,の第 固有値)なので,この問題は,線形行列不等式として定式化できる.線形行列関数 を定義する:

実対称行列 は直交行列 によってとなるように対角化できる.したがって,のときかつそのときに限り である.任意の について を取ると,になる.したがって,のときかつそのときに限り である.数値的にシミュレーションを行ってこれらの式が等しいことを示す:

結果の問題:

モンテカルロシミュレーションを実行して結果の妥当性を確認する:

決定変数に線形依存する対称行列 の最小固有値を最大にするを求める.線形行列関数 を定義する:

と等しいので(ただし, 番目の固有値),この問題は,線形行列不等式として定式化できる. を最大化するために を最小化する:

モンテカルロシミュレーションを実行して結果の妥当性を確認する:

決定変数に線形依存する対称行列 の最大固有値と最小固有値の差を最小にするを求める.線形行列関数 を定義する:

と等しいので(ただし,の第 固有値),この問題は,線形行列不等式として定式化できる.結果の問題を解く:

この場合は,最小固有値と最大固有値が一致するので差は0である:

決定変数に線形依存する対称行列 の(絶対値での)最大固有値を最小化する:

最大固有値は lambda I-A(x,y)>=_(TemplateBox[{2}, SemidefiniteConeList])0を満足する.の(絶対値が)最大の負の固有値はの最大固有値で,lambda I+A(x,y)>=_(TemplateBox[{2}, SemidefiniteConeList])0を満足する:

決定変数に線形依存する対称行列 の最大特異値 を最小化するを求める:

の最大特異値 の最大固有値の平方根であり,上記の例より,または(sigma I A(x,y); A(x,y)^T sigma I)_(TemplateBox[{5}, SemidefiniteConeList])0を満足する:

結果をプロットする:

楕円体,二次円錐,放物面を含む二次集合 を求め,かどうかを判定する.ただし,は対称行列,はベクトル,はスカラーである:

集合 が全次元であると仮定すると,S-procedureには となるような非負の数 が存在するときかつそのときに限り であるとある.非負の が存在することを視覚的に見る:

実現可能性が問題なので,目的関数として0を使う.λ0なので,である:

幾何学の問題  (8)

面積4の長方形の対角線の長さを最小にする.ただし,縦の3倍と横を足したものが7未満とする:

中心が で半径が1の2つの円板の最短距離を求める.を円板1の上の点,を円板2の上の点とする.目的は,制約条件に従ってを最小にすることである:

2つの点の位置を可視化する:

点の間の距離は以下である:

表面積が最大で1の楕円体の体積を最大にする主軸の長さの半分を求める:

表面積は以下で近似できる:

逆数を最小化することで体積領域を最大化にする:

以下は球面である.軸の長さについての追加的な制約条件を含めるとこれが変わる:

与えられた領域を包み込む最小の球体の半径 と中心 を求める:

制約条件 に従って半径 を最小化する:

包み込んでいる球体を可視化する:

包み込んでいる最小の球体はBoundingRegionを使って効率的に求めることができる:

凸多面体の解析的中心を求める.解析的中心は制約条件までの距離の積を最大にする点である:

凸多面体の各線分は半平面 の交線として表すことができる.線形不等式を抽出する:

目的はを最大にすることである.を取って目的関数を否定する.変換された目的関数は である:

補助変数 を使うと,変換された目的は,制約条件 に従う になる:

中心の位置を可視化する:

楕円体が の形の別の楕円体の部分集合かどうかを調べる:

S-procedureを使うと,であるときかつそのときに限り,楕円2が楕円1の部分集合であることがわかる:

条件が満足されるかどうかをチェックする:

楕円体を明示的な形に変換し,楕円2が楕円1の中にあることを確認する:

楕円体1と重なるように楕円体2を移動する:

テストは,楕円体2が楕円体1の部分集合ではなく,この問題は実行不可能であることを示している:

凸多面体内に収められるとしてパラメータ化される楕円の最大面積を求める:

凸多面体の各線分は,半平面 の交線として表すことができる.線形不等式を抽出する:

半平面にパラメータ化を適用するとが与えられる..したがって,制約条件は である:

面積を最小にするのはを最小にすることと同じであるが,それはを最小にすることと同じである:

パラメータ化された楕円をとして明示的な形に変換する:

体積を最小にすることで3Dの点集合を含む{x:TemplateBox[{{{a, ., x}, +, b}}, Norm]<=1}としてパラメータ化された最小の楕円体を求める:

制約条件TemplateBox[{{{a, ., {p, _, i}}, +, b,  }}, Norm]<=1, i=1,2,...,n が各点 について満足されなければならない:

体積を最小にすることはを最小にすることに等しいが,これはを最小にすることに等しい:

パラメータ化された楕円を明示的な形に変換する:

境界楕円体は,必ずしも体積が最小ではないが,BoundingRegionを使って求めることができる:

データフィット問題  (4)

指定された行列 a とベクトル b についての制約条件 に従ってを最小化する:

データの最初と最後の点が曲線上にあるようにして,三次元曲線を離散データにフィットする:

DesignMatrixを使って行列を構築する:

最初と最後の点が必ず曲線上にあるようになる制約条件を定義する:

を最小化することで係数 を求める:

フィットをデータと比較する:

を最小化することで,非線形離散データの外れ値にあまり敏感ではないフィットを求める:

基底 を使ってデータをフィットする.補間関数は になる:

解を求める:

フィットを可視化する:

補間関数を参照関数と比較する:

複素数 について||a.lambda-b||+sigma TemplateBox[{lambda, 1}, Norm2]を最小化することで,複素データへの正規化フィットを求める:

DesignMatrixを使って基底について行列 を構築する:

係数 を求める:

の実数成分と虚数成分の関数として定義されたフィットであるとする:

の実数成分についての結果を可視化する:

の虚数成分について結果を可視化する:

平方和表現  (1)

与えられた多項式 を平方和多項式 によって表す:

目的は, となるような を求めることである.ただし,は単項式のベクトルである:

対称行列 を構築する:

の多項式係数を求め,両者が等しいことを確認する:

の要素を求める:

二次の項 ,ただし, のコレスキー分解によって得られた下三角行列である:

平方和多項式を与えられた多項式と比較する:

分類問題  (3)

2つの点集合 を分割する直線 を求める:

分割するためには,集合1は を,集合2は を満足しなければならない:

目的はを最小にすることであるが,これは の間の厚みの2倍を与える:

分割線は以下で与えられる:

3Dの2つの点集合の を分割する二次多項式を求める:

DesignMatrixを使って2つの集合についての二次多項式データ行列を構築する:

分割するためには,集合は を,集合2は を満足しなければならない:

を最小にすることで分割多項式を求める:

2つの点集合を分割する多項式は以下で与えられる:

2つの点集合を分割する多項式をプロットする:

与えられた点集合 を別のグループに分割する.これは,を最小にして各グループの中心 を求めることで行える.ただし,は与えられたローカルカーネルで は与えられたペナルティパラメータである:

カーネル は,で他では k-最近傍()関数である.この問題のために の最近傍が選ばれている:

目的は以下である:

グループの中心を求める:

各データ点について対応する中心が存在する.同じグループに属すデータは同じ中心値を持つ:

グループ化された点を抽出してプロットする:

施設の位置についての問題  (1)

にいるクライアントにサービスを提供するために必要な,さまざまな携帯基地局の位置 とその範囲 を求める:

各携帯基地局はその範囲に比例して電力を消費するが,これは で与えられる.目的は電力消費量を最小にすることである:

クライアント が携帯基地局 でカバーされている場合に,を示す決定変数とする:

各携帯基地局はその範囲がクライアントのある部分をカバーするような場所になければならない:

各携帯基地局は複数のクライアントをカバーする:

各携帯基地局には最小および最大のカバレッジがある:

すべての変数を集める:

携帯基地局の位置とその範囲を求める:

携帯基地局の位置と範囲を抽出する:

クライアントの位置についての基地局の位置と範囲を可視化する:

ポートフォリオの最適化  (1)

リスクを最小に抑えながらリターンを最大化するために6つの株式に投資するための資本 の配分を求める:

リターンは で与えられる.ただし, は各株式の期待されるリターンの値のベクトルである:

リスクは で与えられる. はリスク回避パラメータで である:

目的は,指定されたリスク回避パラメータについてリスクを最小にしながらリターンを最大にすることである:

株式売買による株式の市場価格への影響は,でモデル化されるが,これは,エピグラフ変換を使ったPower Coneによってモデル化できる:

重み は0より大きくなければならず,重みと市場への影響のコストを1に加算する必要がある:

リスク回避パラメータの範囲についてリターンと対応するリスクを計算する:

の範囲における最適な は,リターンとリスクの間のトレードオフの上限を示す:

指定された数のリスク回避パラメータについて重みを計算する:

市場コストを考慮することで低リスク回避のための分散ポートフォリオを得ることができるが,リスク回避が高い場合は分散の少ない株式を購入するため,市場の影響コストが支配的になる:

画像処理  (1)

全変動ノルムの下で最も近い画像を探すことで,破損した画像を回復する:

40%のデータ点をランダムに削除することで破損した画像を作成する:

目的はsum_(i=1)^(n-1)sum_(j=1)^(m-1)sqrt(TemplateBox[{{TemplateBox[{u, {i, +, 1}, j}, IndexedDefault], -, TemplateBox[{u, i, j}, IndexedDefault]}}, Abs]^2+TemplateBox[{{TemplateBox[{u, i, {j, +, 1}}, IndexedDefault], -, TemplateBox[{u, i, j}, IndexedDefault]}}, Abs]^2)を最小化することである.ただし, は画像データである:

任意の非零のデータ点 TemplateBox[{u, i, j}, IndexedDefault]が破損していると仮定する.それらの点に対して TemplateBox[{u, i, j}, IndexedDefault]=u_(i j)^(orig)を設定する:

解を求め,回復された画像を表示する:

Wolfram Research (2020), ConvexOptimization, Wolfram言語関数, https://reference.wolfram.com/language/ref/ConvexOptimization.html.

テキスト

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

BibTeX

@misc{reference.wolfram_2024_convexoptimization, author="Wolfram Research", title="{ConvexOptimization}", year="2020", howpublished="\url{https://reference.wolfram.com/language/ref/ConvexOptimization.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_convexoptimization, organization={Wolfram Research}, title={ConvexOptimization}, year={2020}, url={https://reference.wolfram.com/language/ref/ConvexOptimization.html}, note=[Accessed: 22-November-2024 ]}