GeometricOptimization

GeometricOptimization[f,cons,vars]

正の多項式制約 cons に従って正の多項目的関数を最小化する変数 vars の正の値を求める.

GeometricOptimization[{a0,b0},{{a1,b1},},{aeq,beq}]

不等式制約 と線形等式制約 に従って を最小化する正のベクトル x=yを求める.

GeometricOptimization[,"prop"]

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

詳細とオプション

  • 幾何学的最適化は幾何計画法(GP)および混合整数幾何計画法(MIGP)としても知られている.
  • 幾何学的最適化は,面積,体積,電力等の最小化にしばしば使われる.
  • 幾何学的最適化は主問題を解く を求める.
  • 最小化
    制約条件
    ただし
  • 単項式は,(ただし )のベキの積である.正多項式は単項式 (ただし )の正の和である.
  • 一般化された正多項式 は,正多項式または一般化された正多項式の組合せである.
  • 正多項式
    一般化された正多項式の和
    一般化された正多項式の積
    一般化された正多項式の最大値
    一般化された正多項式の正の実数ベキ
  • 正多項式 は,以下のように,変換 によって 行列 ()と -ベクトル ( )に対応する.
  • 同様の問題の定式化は を求めることである.ただし, が問題を解く.
  • 最小化
    制約条件
    ただし
  • GeometricOptimization[{a0,b0},{{a1,b1},},{aeq,beq}]ai 行列,biベクトル,aeq 行列,b_(eq)ベクトルである.等式制約がない場合は,{aeq,beq}{}で与えることも省略することもできる.
  • 主最小化問題には関連する最大化問題(ラグランジュ双対問題)がある.双対最大値は常に主最小値以下なので,下界を与える.双対マキシマイザは,制約条件の変化に対する最小値の感度を含む主問題の情報を与える.
  • 幾何学的最適化問題は双対問題を持つ.
  • 最大化
    制約条件
    ただし
  • 錐最適化については強双対性が常に存在するので,主最小化問題に解がある場合は双対最大化問題にも解があり,双対最大値は主最小値に等しい.
  • 次は,使用可能な解の特性"prop"である.
  • "PrimalMinimizer"f を最小化する vars={v1,}の値のリスト
    "PrimalMinimizerRules"vars={v1,}の値を最小化する規則
    "PrimalMinimizerVector"を最小化するベクトル
    "PrimalMinimumValue"最小値
    "DualMaximizer"を最大化するベクトル のリスト
    "DualMaximumValue"双対最大値
    "DualityGap"双対最適値と主最適値の差
    "Slack"正多項式項の各単項式の値を与えるベクトル
    "ConstraintSensitivity"
    の制約摂動に対する感度
    "ConstraintMatrices"についての行列
    "ObjectiveFunction"目的関数
    "GeometricConstraints" 幾何学的制約のリスト
    {"prop1","prop2",} いくつかの解の特性
  • 次は,使用可能なオプションである.
  • MaxIterationsAutomatic使用する反復の最大数
    MethodAutomatic使用するメソッド
    PerformanceGoal$PerformanceGoalパフォーマンスのどの面を最適化するか
    ToleranceAutomatic内部比較に使用する許容範囲
  • 計算はMachinePrecisionに限定される.

例題

すべて開くすべて閉じる

  (1)

外周が最大で1で縦の長さが横の長さの最大で半分になるようにして,長方形の面積を最大にする:

スコープ  (12)

基本的な用法  (4)

行列を使って幾何の問題を指定する:

問題について同等の目的関数と幾何学的制約を示す:

標準形式で与えられた等式制約がある幾何の問題を解く:

一般化された正多項式で与えられた幾何の問題を解く:

中間の正多項式形を得るために,アルゴリズムによって余分な変数が自動的に加えられる:

ベクトル変数によって与えられた幾何の問題を解く:

主モデル特性  (3)

標準的な正多項式の形で与えられた幾何の問題を解く:

最小値と最小化ベクトルを得る:

問題の行列表現を示す:

一般化された正多項式で与えられた幾何の問題を解く:

導入された中間変数を含む変換された制約を得る:

これらは行列表現に対応する:

行列形式で与えられた幾何の問題を解く:

形式変数を使って幾何の問題の記号形式を得る:

双対モデル特性  (2)

を求める.ただし,に従って を最小化する:

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

ConicOptimizationを使った定式化は,凸項 を中間変数 で置換し,以前使った双対指数錐制約に等しい制約条件 を加える.{-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault],TemplateBox[{{(, {t, _, 1}, )}, j}, IndexedDefault]-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault],1^.lambda_1}_(TemplateBox[{}, DualExponentialConeString])0xTemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault] ⅇ^((TemplateBox[{{TemplateBox[{{(, {t, _, 1}, )}, j}, IndexedDefault], -, {(, {lambda, _, 1}, )}}, j}, IndexedDefault])/(-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault])-1)<=1^.lambda_1 ∧-TemplateBox[{{(, {lambda, _, 1}, )}, j}, IndexedDefault]<=0を必要とする.

"DualMaximizer"特性からより簡単に得ることができる:

強双対性があるので,双対最大値は主最小値に等しい:

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

双対問題の解を得る:

GeometricOptimizationには強双対性があるので,双対最大値は主最小値に等しい.その差は双対性のギャップと言われる:

双対問題は問題の行列表現によって定義される:

すべての項が単項式なので,行列 のどれもが1行であり,双対ベクトル には1つの要素しかない.したがってである.を最大化することはを最小化することに等しい.また,指数関数が単調増加関数なので,これは を最小化することに等しい.したがって,双対問題は以下のように解くことができる:

主問題は,指数関数の単調性を使って線形最適化で解くこともできることに注意のこと:

感度特性  (3)

箱のコストを100ドル未満にするという制約条件に従って,縦 ,横 ,高さ の開放箱の体積を最大にする.底面のコストは単位面積あたり10ドルで,側面のコストは単位面積当たり1ドルである:

底面のコストを10%下げた場合に箱の体積が相対的にどのように変化するかを推測する:

底面のコストの内訳は,第2要素の最初の部分である(第1要素は目的関数に相当する).なので感度は打ち消される:

,横 ,高さ の箱の天面と底面あるいは側面についての制約条件を変えた場合に,この箱の最大体積が相対的にどのように変化するかを求める.体積を最大にすることは体積の逆数を最小にすることと同じである:

側面の総面積を 以下に,天面と底面の面積を 以下に制限する:

さらに,縦横比の限界を加える:

が与えられた場合に体積を計算する関数を定義する:

についての最大体積を求める:

のときの目的関数の制約条件に対する相対感度を得る:

面積の条件に関連するのは2番目と3番目である(最初のものは目的関数に関連している):

に対する体積の相対変化は である:

これは, が少し変化しても{α,β}={38,47}の体積は変化しないことを意味する:

が十分に小さければ,体積には影響しない:

感度は両対数プロット上の曲線の傾きである:

の2つの成分は相対する2組の側面から来ているので,体積の相対変化の合計は以下のようになる:

を.5増加させたことによる予測変化は以下の通りである:

実際の変化は以下の通りである:

感度は有限差分によっても確かめられる:

制約条件 に従った についての の最小値の相対変化を求める:

有限差分を使って であることを確かめる:

同様に であることを確かめる:

有限差分による推定は最適化の許容度内に収まっている:

アプリケーション  (16)

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

実行可能性を与える制約条件についての限界を決める:

この問題は実行可能である:

この問題は実行可能ではない:

幾何学的問題  (4)

面積4の長方形の対角線の長さを最小にする.ただし,横に縦の3倍を加えたものが7以下になるようにする:

体積 の球状のスクープを入れるアイスクリームコーンをデザインする.スクープとコーンの半径は同じであるとする.アイスクリームが溶けたときにコーンにスクープ全体が入るようにしてコーンの表面積を最小にする:

表面積が最大で1の楕円体の体積を最大にするを求める:

の違いがあまりない場合は,のときの表面積は以下で近似される:

体積をその逆数を最小にすることで最大にする:

予想通り,それは球である.軸の長さについての制限を加えると結果が変わる:

どの次元もその差が2倍以上にはならず,側面,天面,底面の総面積についての制約条件がある中で,縦 ,横 ,高さ の箱の体積を最大にする:

側面の総面積 と底面と天面の合計 が与えられると体積を返す関数を定義する:

体積の値の表を計算する:

体積を対数スケールによる側面および天面と底面の面積の関数として示す:

さまざまな側面積の値について,体積と許される天面/底面の面積のトレードオフ曲線を示す:

行列問題  (2)

非負の実数項を持つ 行列 が与えられた場合に,同様の行列 の平方和(フロベニウスのノルム平方)を最小にする正の項を持つ対角行列 を求める:

d={d1,,dn} の対角項だとする.diは正なので,の各項は{1/d1,,1/dn}となる.したがって,積の項はである:

もとの行列とスケールされた行列のノルムを比較する:

行列は相似なので,固有値は等しい:

x in TemplateBox[{}, Reals]^kのいくつかの変数に正の多項式要素を持つ TemplateBox[{}, Reals]^(n x n)行列であるとする. のスペクトル半径を最小にする を求める.スペクトル半径は の固有値の絶対値の最大値に等しい, max(TemplateBox[{lambda}, Abs], A.v=lambda

スペクトル半径は,で計算できるペロン・フロベニウス(PerronFrobenius)固有値 と同じである:

以下は,スペクトル半径が最小の行列である:

計算された がスペクトル半径であることを確認する:

ランダムに選んだ のスペクトル半径と比較する:

貯蔵タンクの設計  (1)

半径 ,高さ ,縦横比 の円筒形の貯蔵タンクの建設・運転費用を最小にする:

建設費用は底面と側面の費用である:

充填費用はタンク容量 と注入量 の比に比例するとみなされる:

総費用を最小にする:

フロアプラン  (1)

縦横比,長方形間の距離,相対的な配置の制約がある指定された面積の 個の長方形を囲む,全体の面積が最小の長方形フロアを計設計する.

大きい長方形を Rectangle[{0,0},{H,W}]で,個々の小さい長方形を ri=Rectangle[{xi,yi},{xi+wi,yi+hi}], i=1,,n で表す.

各長方形の縦横比 を, となるように から (ただし )に制限する.

相対配置は,水平配置 と垂直配置 の2つの有向グラフで表すことができる.ij という辺がある場合は rirjの左(または下)にならなければならない:

長方形間の最小スペースを とする.に辺 ij があるとき,長方形 となるように長方形 の左にならなければならない.に辺 ij があるとき,長方形 となるように長方形 の下にならなければならない.次の関数で,グラフを横断しフロアの端になる長方形を説明することができる:

配置グラフ,面積, および が与えられると,GeometricOptimizationを使う関数で規則を組み合せることができる:

次は,最初の長方形が他の2つの長方形の左側になり2番目の長方形が3番目の長方形の下になるような,3つの長方形の相対配置を表すグラフである:

次は,このプランを示す関数である:

次は,面積がランダムに割り当てられた10個の長方形についてのプランを示している:

構造最適化の問題  (3)

垂直荷重 または水平荷重 に従う最小重量のトラスを求める.トラスのバーは内半径 ,外半径 ,密度 の中空のパイプである:

バーの長さはトラスの高さ と幅 を使って定義される.断面積は である.目的は重みを最小にすることである:

垂直荷重 が適用された場合に各バーにかかる力は以下の通りである:

水平荷重 適用された場合に各バーにかかる力は以下の通りである:

バーにかかる力の合計は最大許容力 を超えてはならない.ただし, は最大許容応力である:

トラスの高さ と幅 には制限がある:

チューブは最低でも壁の厚さがなければならない.これは,(ただし )で達成できる.バーの面積と半径の関係は であるが,これは単項関数ではない.と制約条件 を使うと,結果の制約条件は単項式になる:

トラスのパラメータを指定する:

について解いて最適なトラスを得る:

を使ってバーの外半径 を得る:

垂直荷重 に従う最小重量のトラスを求める.トラスの高さ と幅 は既知である.接合部 の垂直位置は未知である:

を,それぞれバーおよびの断面積, をバーの密度とする.トラスの重みは以下で与えられる:

バーは伸長されている.を材料の引張応力とする.バーにかかる力は最大許容力を超えてはならない:

バーは圧縮されている.を材料の圧縮応力とする.にかかる力は最大許容力を超えてはならない:

パラメータを指定する:

幾何最適化問題の特定の例は,の与えられた値について解くことができる.接合部 の垂直位置が特定の範囲内にあると仮定して一連の問題を解く:

最小の重みをプロットする:

最小の重みを与える の特定の値を求める:

最適化された断面積とトラスの重みを求める:

自由端上の垂直重み に従う,重みが最小の片持ち梁を設計する.この梁は単位長の 個の部分からなっている.各部分の幅は で高さは である:

荷重によって梁はたわみ,梁の各部分にストレス がかかる.このストレスは最大許容応力 より小さくなければならない:

を部分 の右端のたわみとする.自由端のたわみ で再帰的に求められる. はヤング率で傾き である.部分 は固定されているので である:

梁の自由端のたわみは最大許容たわみ 未満でなければならない:

幅,高さ,縦横比は特定の範囲に制限されている:

パラメータを指定する:

重みを最小にして個々の部分の次元を求める:

片持ち梁を可視化する:

回路の問題  (3)

デジタル回路ゲートのサイジング.回路内の遅延が最小となるような力と面積の制約条件に従って,指定された回路内のゲートの最適サイズを求める.7ゲート回路について考えてみる:

を各ゲートを広げるスケール因子とする:

各ゲートが占める面積はこの倍率に比例すると考えられる.総回路面積は以下のようになる:

ゲート の遷移によるエネルギー損失は,スケール因子 ,ゲート の遷移周波数,ゲート遷移におけるエネルギー損失 に比例する:

ゲート の入力容量は,ゲート6およびゲート7を除いて である.ゲート6およびゲート7の入力容量は10である:

ゲート の打込み抵抗は である:

ゲート の容量は,その出力が接続されているゲート(ただしゲート6とゲート7を除く)の入力容量の合計である.出力ゲート6と7の容量はその入力容量と同じである:

ゲート の遅延は,その打込み抵抗とゲート容量の積である:

目的は,回路が横断するあらゆる経路の組合せにおける最悪の遅延を最小にすることである:

回路の面積は指定された最大許容面積未満でなければならない:

消費される電力は指定された最大許容電力未満でなければならない:

最大許容面積と最大許容電力のさまざまな組合せについて最小面積を求める:

最適なトレードオフ曲線をプロットする:

容量が既知である回路内の相互接続されたネットワークにおける 本のワイヤ断片の幅を求める.以下のネットワーク内には5本のワイヤ断片がある:

各ワイヤ断片について,抵抗 ,容量 である. はワイヤ特性に依存する正の定数, はワイヤの長さ,幅は である:

モデルを使うと,各ワイヤは抵抗とコンデンサを使ってモデル化できる.結果のネットワークは抵抗・コンデンサネットワークになる:

モデルの新たな容量は,個々のネットワークの容量とワイヤ容量 を合計することで得られる:

エルモア(Elmore)遅延は電圧変化と新しい値への収束の遅延を測定する.各コンデンサ のエルモア遅延は である.ただし,はコンデンサ の間の抵抗の集合である:

目的は最大のエルモア遅延を最小にすることである:

ワイヤは範囲内に収まるように制限されている:

総面積は最大許容面積を超えてはならない:

パラメータを指定する:

ワイヤの幅を求める:

ベースの通過時間が最小化されるようなトランジスタの最適ドーピングプロファイルを求める.ドーピングプロファイルを とする.ただし,はベース幅である. をベースの通過時間とする.の関数としての簡約モデルは で与えられる.ただし, は定数である.とすると, 個の等間隔に置かれた点を使って積分を離散化することができる:

ドーピング勾配制約は次のように近似できる:

ドーピングプロファイルには上限と下限があり,初期状態と最終状態が指定されている:

パラメータを指定する:

結果の幾何学的最適化問題を解いて最適ドーピングプロファイルを得る:

結果のプロファイルをプロットする:

電力制御  (1)

個の送電器が 個の受電器に送電する総電力レベル を最小化する:

受電器 が送電器 から受け取る電力は である.ただし,は,送電器 から受電器 までの経路利得である:

受信器 における信号電力は である:

受信器 における干渉電力は, を除くすべての送電器から受け取った総電力 である:

番目の受電器/送電器ペアの信号対干渉雑音比(SINR)はで与えられる.ただし,は受電器 における雑音電力である:

任意の受電器/送電器ペアのSINRには最小閾値がある,これを正多項式制約にするために,SINR制約の逆数を取る():

電力レベルには上限と下限がある:

パラメータを指定する:

電力レベルを求める:

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

テキスト

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

CMS

Wolfram Language. 2020. "GeometricOptimization." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/GeometricOptimization.html.

APA

Wolfram Language. (2020). GeometricOptimization. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/GeometricOptimization.html

BibTeX

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

BibLaTeX

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