QuadraticOptimization

QuadraticOptimization[f,cons,vars]

線形制約条件 cons に従って二次目的関数 f を最小化する変数 vars の値を求める．

QuadraticOptimization[{q,c},{a,b}]

線形不等式制約に従って二次目的関数を最小化するベクトルを求める．

QuadraticOptimization[{q,c},{a,b},{a_eq,b_eq}]

線形等式制約を含む．

QuadraticOptimization[{q,c},…,{dom₁,dom₂,…}]

が領域 dom_iにあるとする．dom_iはIntegersまたはRealsである．

QuadraticOptimization[…,"prop"]

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

詳細とオプション

二次最適化は，二次計画法(QP)，混合整数二次計画法(MIQP)，あるいは線形制約二次最適化としても知られている．
二次最適化は，パラメータのフィット，ポートフォリオの最適化，幾何学的距離問題等によく使われる．
二次最適化は，実変数，整数変数あるいは複素変数で大域的に効率よく解くことができる凸最適化問題である．
二次最適化は主問題を解くを求める． »
最小化

制約条件

ただし
空間は対称正定値行列からなる．
混合整数の二次最適化は，問題を解くおよびを求める．
最小化

制約条件

ただし $(q_(rr) q_(ri); TemplateBox[{{q, _, {(, {r, , i}, )}}}, Transpose] q_(ii)) in S_+^n,c_r in R^(n_r),c_i in R^(n_i),a_r in R^(mxn_r),a_i in R^(mxn_i),b in R^m,a_(eq_r) in R^(kxn_r),a_(eq_i) in R^(kxn_i)b_(eq) in R^k$
QuadraticOptimizationは，目的関数が実数値のときは，内部的に実変数に変換して $x in TemplateBox[{}, Complexes]^n$ の問題を解く．ただし，でである．

変数指定 vars は，次のいずれかの形式で変数を与える要素のリストでなければならない．

	v	名前がで次元が推測される変数
	v∈Reals	実数のスカラー変数
	v∈Integers	整数のスカラー変数
	v∈Complexes	複素数のスカラー変数
	v∈ℛ	幾何学領域に制限されたベクトル変数
	v∈Vectors[n,dom]	またはのベクトル変数
	v∈Matrices[{m,n},dom]	またはの行列変数

制約条件 cons は以下で指定できる．

	LessEqual		スカラー不等式
	GreaterEqual		スカラー不等式
	VectorLessEqual		ベクトル不等式
	VectorGreaterEqual		ベクトル不等式
	Equal		スカラー等式またはベクトル等式
	Element		凸領域または領域要素

QuadraticOptimization[f,cons,vars]のとき，f または cons に使われるパラメータを定義するために，parval の形式のパラメータ方程式が制約条件に含まれることがある．ただし，par は vars に含まれず，val は数値または数値配列である．
目的関数は次の方法で指定できる．
q

{q,c}

${{q_(f)},c}$ $1/2(q_f.x).(q_f.x)+c.x=1/2(x.TemplateBox[{{q, _, f}}, Transpose]).(q_f.x)+c.x$

${{q_(f),c_(f)},c}$ $1/2(c_f+q_f.x).(c_f+q_f.x)+c.x=1/2(x.TemplateBox[{{q, _, f}}, Transpose]+c_f).(q_f.x+c_f)+c.x$
因数分解した形式では，とである．
主最小化問題には関連したラグランジュ双対問題である最大化問題がある．双対最大値は常に主最小値以下である．したがって，これは下界を与える．双対マキシマイザは主問題についての，最小値の感度や制約条件の変更等を含む情報を与える．
目的関数がの二次最適化についてのラグランジュ双対問題は以下で与えられる． »
最大化

制約条件

ただし
因数分解された二次目的関数が $1/2(x.TemplateBox[{{q, _, f}}, Transpose]+c_f).(q_f.x+c_f)+c.x$ のとき，双対問題は次のように表すことができる．
最大化

制約条件

ただし
因数分解された双対ベクトルと因数分解されていない双対ベクトルの関係はである．
二次最適化では，が半正定値の場合は強双対性が成り立つ．したがって，主最小化問題に解があれば双対最大化問題にも解があり，双対最大値と主最小値は等しい．
使用可能な解の特性"prop"には以下がある．

	"PrimalMinimizer"		目的関数を最小化する変数値のリスト
	"PrimalMinimizerRules"		を最小化する変数の値 vars={v₁,…}
	"PrimalMinimizerVector"		を最小化するベクトル
	"PrimalMinimumValue"		最小値
	"DualMaximizer"		を最大化するベクトル
	"DualMaximumValue"		双対最大値
	"DualityGap"		双対最適値と主最適値の差（強双対性のため0）
	"Slack"		制約条件の摂動に対する感度
	"ConstraintSensitivity"		最小値の制約条件に対する感度
	"ObjectiveMatrix"		二次目的行列
	"ObjectiveVector"		線形目的ベクトル
	"FactoredObjectiveMatrix"		因数分解された目的形式の行列
	"FactoredObjectiveVector"		因数分解された目的形式のベクトル
	"LinearInequalityConstraints"		線形不等式制約行列と線形不等式制約ベクトル
	"LinearEqualityConstraints"		線形等式制約行列と線形等式制約ベクトル
	{"prop₁","prop₂",…}		いくつかの解の特性

双対マキシマイザの成分は，で与えられるとの関数である．
次は，使用可能なオプションである．

MaxIterations	Automatic	使用する最大反復回数
Method	Automatic	使用するメソッド
PerformanceGoal	$PerformanceGoal	パフォーマンスのどの局面について最適化するか
Tolerance	Automatic	内部比較の許容度
WorkingPrecision	MachinePrecision	内部計算精度

オプション Method->method を使って使用するメソッドを指定することができる．次は，使用可能なメソッドである．

	Automatic	自動的にメソッドを選択する
	"COIN"	COIN ライブラリ二次計画法
	"SCS"	SCS（分割円錐ソルバ）ライブラリ
	"OSQP"	二次問題のためにソルバを分割するOSQP演算子
	"CSDP"	CSDP（COIN半定値計画法）ライブラリ
	"DSDP"	DSDP（半定値計画法）ライブラリ
	"PolyhedralApproximation"	客観的なエピグラフは多面体を使って近似される
	"MOSEK"	商用MOSEK凸最適化ソルバ
	"Gurobi"	商用Gurobi線形・二次最適化ソルバ
	"Xpress"	商用Xpress線形・二次最適化ソルバ

例題

すべて開くすべて閉じる

例 (3)

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

最適点は制約条件で定義され，が最小となる領域にある：

等式制約と不等式制約に従ってを最小化する：

目的関数をとして，制約条件をおよびとして定義する：

行列ベクトル入力を使って解く：

最適点はの等高線が等式制約に接するところにある：

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

同等の行列ベクトル表現を使用する：

スコープ (26)

基本的な用法 (8)

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

解の特性"PrimalMinimumValue"を使って最小にする値を得る：

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

解の特性を使って最小化する値と最小化するベクトルを得る：

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

目的関数をとして，制約条件をとして定義する：

行列ベクトル入力を使って解く：

等式制約と不等式制約件に従ってを最小化する：

目的関数をとして，制約条件をおよびとして定義する：

行列ベクトル入力を使って解く：

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

目的関数をとして，制約条件をとして定義する：

行列ベクトル入力を使って解く：

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

VectorGreaterEqual ()とVectorLessEqual ()を使って制約条件を指定する：

に従ってを最小化する．ベクトル変数と定数パラメータ方程式を使う：

に従ってを最小化する．NonNegativeRealsを使って制約条件を指定する：

整数変数 (4)

Integersを使って整数領域制約を指定する：

Vectors[n,Integers]を使ってベクトル変数についての整数領域制約を指定する：

NonNegativeIntegers ()を使って非負の整数領域制約を指定する：

NonPositiveIntegers ()を使って非正の整数制約を指定する：

複素変数 (3)

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

目的関数でエルミート行列と実数値の変数を使う：

目的関数でエルミート行列と複素変数を使う：

主モデルの特性 (4)

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

"PrimalMinimizer"を使ってベクトル出力を得る：

"PrimalMinimizerRules"を使ってルールベースの結果を得る：

"PrimalMinimumValue"を使って最適化の最小にする値を得る：

記号入力を使って主最小値を得る：

最適化問題の行列ベクトル入力を抽出する：

行列ベクトル形式を使って解く：

目的定数を加えることで記号による主値を回復する：

最小化問題に関連する等式と不等式についてスラックを求める：

最小値と制約行列を得る：

不等式制約についてのスラックは，となるようなベクトルである：

等式制約のスラックは，となるようなベクトルである：

等式スラックはゼロベクトルであることが多い：

双対モデルの特性 (3)

とに従ってを最小化する：

双対問題は，に従ってを最大化する：

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

したがって，双対性ギャップはゼロである．一般に，最適点でである：

主問題から抽出した制約行列を使って双対問題を構築する：

目的関数と制約行列および制約ベクトルを抽出する：

双対問題は，に従ってを最大化する：

解の特性を使って双対最大値を直接得る：

感度特性 (4)

"ConstraintSensitivity"を使って，制約緩和による最適値の変化を求める：

第1ベクトルは不等式感度で第2ベクトルは等式感度である：

制約条件について考える．ただし，は緩和である：

近似した新たな最適値は以下で与えられる：

緩和問題を直接解く場合と比較する：

不等式制約または等式制約に関連した各感度：

制約条件を抽出する：

不等式制約と関連する感度：

等式制約と関連する感度：

制約条件の緩和による最適値の変化は感度値に比例する：

最小値と制約感度を計算する：

制約条件が緩和している場合は，ゼロ感度が最適値を変える：

負の感度は最適値を減少させる：

正の感度は最適値を増大させる：

"ConstraintSensitivity"は，問題の双対マキシマイザに関連している：

不等式感度はを満足する．ただし，は双対不等式マキシマイザである：

等式感度はを満足する．ただし，は双対等式マキシマイザである：

オプション (12)

Method (5)

メソッド "COIN"はCOINライブラリを使う：

"CSDP"と"DSDP"は半正定値最適化に還元される：

"SCS"は円錐最適化に還元される：

"PolyhedralApproximation"は線形制約を使ってオブジェクトを近似する：

最小二乗型の二次問題については，"CSDP"と"DSDP"は"COIN"または"SCS"よりも低速である：

"COIN"メソッドを使って最小二乗問題を解く：

"CSDP"メソッドを使って問題を解く：

最小二乗型の二次問題については，"CSDP"，"DSDP"，"PolyhedralApproximation"は"COIN"あるいは"SCS"よりも遅い：

"COIN"法を使って最小二乗問題を解く：

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

"PolyhedralApproximation"法を使って問題を解く：

複数の最適解がある問題については，メソッドによって結果が異なることがある：

凹関数の最小化はMethod"COIN"を使ってのみ行うことができる：

その他のメソッドは目的行列の因数分解が必要なので使えない：

PerformanceGoal (1)

"Quality"設定で計算時間を犠牲にし，より正確な結果を得る：

"Speed"を使って品質を犠牲にし，結果をより速く得る：

Tolerance (2)

Toleranceの設定値を小さくすると，より正確な結果が得られる：

Toleranceの設定値を変えて，計算上の最小値と厳密な最小値の誤差を求める：

許容度に対する最小値の誤差の変化を可視化する：

Toleranceの設定を小さくするとより正確な答が得られるが，計算時間は長くなることが多い：

許容範囲を狭くすると時間がかかる：

許容範囲が狭いとより正確な答が得られる：

WorkingPrecision (4)

MachinePrecisionは，QuadraticOptimizationにおけるWorkingPrecisionオプションのデフォルトである：

WorkingPrecisionAutomaticのとき，QuadraticOptimizationは使用する精度を入力から推測する：

QuadraticOptimizationは任意性度数を使って結果が計算できる：

指定された精度が入力引数の精度よりも低い場合は，メッセージが出される：

高精度の結果が計算できないときは，メッセージが出されてMachinePrecisionの結果が返される：

アプリケーション (29)

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

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

主最小値を否定して対応する最大値を得る：

目的関数をに変換することでを最小化する：

を拡張することで目的関数を構築する：

QuadraticOptimizationはを最小化するので，行列は2倍される：

もとの関数の最小値はとして回復される：

QuadraticOptimizationはこの変換を直接実行する．Inactiveを使って目的関数を構築することで縫込みを回避する：

制約条件に従ってを最小化する．目的関数をに変換して問題を解く：

変換を使ってもとの最小値を回復する：

制約条件に従ってを最小化する．制約条件はに変換することができる：

制約条件に従ってを最小化する．制約条件はと解釈することができる．各制約条件でこの問題を解く：

最適解は2つの解の小さい方である：

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

真の最小値は関数を主最小値に適用することで得られる：

に従ってを最小化する：

なので，主最小値が0より大きいときにのみ解は真の解である．主最小値は関数を主最小値に適用することで得られる：

データフィッティング問題 (7)

を最小化することで離散データの線形フィットを求める：

DesignMatrixを使って因数分解した二次行列を構築する：

線の係数を求める：

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

を最小化することで離散データへの二次フィットを求める：

DesignMatrixを使って因数分解した二次行列を構築する：

二次曲線の係数を求める：

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

データの最初と最後の点が曲線上にあるようにして，二次曲線データをフィットする：

DesignMatrixを使って因数分解した二次行列を構築する：

次は，2つの等式制約である：

線の係数を求める：

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

基底を使ってノイズのあるデータの補間関数を求める：

補間関数はである：

補間関数の係数を求める：

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

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

の制約条件がない最小値と比較する：

濃度で制約された最小二乗問題．が最大で個の非零要素を持つようにを最小化する：

が，もしならばは非零となるような決定ベクトルであるとする．決定制約は次のようになる：

のときの制約をモデル化するために，となるような大きい定数を選ぶ：

濃度で制約された最小二乗問題を解く：

部分集合の選択は，Fitで正規化を使うとより効率よくできる．まず，最高で個の基底関数を使う正規化パラメータの範囲を求める：

で正規化されたフィットにおける非零項を求める：

これらの基底項だけのフィットを求める：

関数集合候補から与えられたデータを近似する関数の最良の部分集合を求める：

近似関数はとなる：

最終の近似には最大5個の基底関数が使われる：

選択されなかった関数に関連付けられた係数は0でなければならない：

関数の最良の部分集合を求める：

結果の近似を与えられたデータと比較する：

分類問題 (2)

三次元の点の2つの集合とを分割する平面を求める：

分割するためには，集合1はを，集合2はを満足しなければならない．を最小化することで超平面を求める：

平面と平面の距離はである：

点の2つの集合を分割する平面は以下の通りである：

2つのデータ集合を分割する平面をプロットする：

三次元の2つの点の集合とを分割する二次多項式を求める：

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

分割するためには，集合1はを，集合2はを満足しなければならない．を最小化することで分割曲面を求める：

点の2つの集合を分割する多項式は以下の通りである：

2つのデータ集合を分割する多項式をプロットする：

幾何問題 (3)

平面との上の点に最も近い点を求める：

を最小化することでに最も近い点を求める．目的関数の構築にはInactive Plusを使う：

2つの凸多面体間の距離を求める：

両者を繋ぐ線に最も近い点を示す：

指定された領域を包含する最小の球の半径と重心を求める：

もとの最小化問題は，に従ってを最小化するものである．この問題の双対は，に従ってを最大化するものである：

双対最大化問題を解く：

包含している最小の球の重心はである：

包含している最小の球の半径は最大値のSqrtである：

包含している球を可視化する：

包含している最小の球はBoundingRegionを使って効率よく求めることができる：

投資問題 (3)

最低でも1000ドルの配当が得られリスクが最小となるように，資本金10000ドルを4つの株に割り当てる方法を求める．期待する戻り値と株式に関連付けられた共分散行列は次の通りである：

4つの株の単価は1ドルである．各株には最大で2500ドルを割り当てることができる：

この投資は最小で1000ドルを生み出さなければならない：

負の株式を買ってはならない：

各株式に費やす金額の総量は，で与えられるリスクを最小化することで求められる：

最低でも1000ドルが得られる総投資額は以下の通りである：

空売りオプションも含めて最低でも配当が1000ドルになるようにし，リスクが最小となるようにして，4つの株式から買う株の数を求める：

資本金についての制約と投資に対する配当の制約は次の通りである：

空売りオプションを使用すると株が売却できる．目的関数によって与えられるリスクを最小化することで，買う／空売りする株式の最適数がもとまる：

2番目の株式は空売りすることができる．空売りで最低1000ドル得るための総投資額は以下の通りである：

空売りをしなければ，初期投資ははるかに大きくなければならない：

リスクを最小限に抑えながら収益を最大化するために，可能性のある20の候補株の中から投資する6つの株の最適な組合せを求める：

を株式で行われた総投資の割合とする．利益はで与えられる．ここで，は各株式の期待利益値のベクトルである：

を決定ベクトルとし，の場合はその株を購入する．6つの銘柄を選択する必要がある：

投資の割合は0より大きく，1に加算する必要がある：

で与えられるリスクを最小化して利益を最大化する最適な株式の組合せを求める：

最適な株式の組合せは以下のようになる：

各株式に投じる投資額の割合は以下のようになる：

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

リスクが最小で利益か最大になるような，資本の6つの株式への投資配分を求める：

株式への投資の全投資に占める割合をとしよう．利益はで与えられる．ただし，は個別の株式の予想収益の値のベクトルである：

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

目標は，指定されたリスク回避パラメータについてリスクを最小にしつつ利益を最大にすることである：

投資の割合はすべて0より大きく1に加えられなければならない：

リスク回避パラメータの範囲内で利益と対応するリスクを計算する：

範囲における最適値は，リスクと利益のトレードオフにおける上包を与える：

指定された数のリスク回避パラメータについて投資の占める割合を計算する：

リスク回避パラメータを大きくすると株式が多様化しリスクが軽減される：

リスク回避パラメータを大きくすると投資に対する予想収益が減少する：

軌道最適化問題 (2)

に従ってを最小化する．最小化関数積分は台形規則を使って近似することができる．離散化された目的関数はである：

制約条件は有限差分を使って離散化することができる：

制約条件はIndexed関数を使って表すことができる：

制約条件は有限差分を使って離散化することができる．最初と最後の行だけが使われる：

離散化された軌道問題を解く：

離散化された結果をInterpolatingFunctionに変換する：

結果を解析解と比較する：

2点間の最短経路を障害物を避けながら求める．障害物を指定する：

凸型の障害を形成する半空間を抽出する：

経路の始点と終点を指定する：

この経路は点を使って離散化できる．が位置ベクトルを表すとする：

目的はを最小化することである．とする．目的はに変換された：

終点の制約を指定する：

連続する任意の2点間の距離は長過ぎてはならない：

の要素の少なくとも1つが0未満のとき，点は目的の外になる．この制約条件を強制するために，が決定ベクトルでがとなるようなの番目の要素であるとする．こうするととなりはとなるための十分大きくなる：

障害物の周囲の経路の最短距離を求める：

経路を抽出して表示する：

障害物との潜在的な交差を避けるために，領域を膨張させて問題をもう一度解く：

障害物を避けるための新たな制約条件を得る：

新たな問題を解く：

新たな経路を抽出して表示する：

最適制御問題 (2)

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

積分は台形法を使って離散化できる：

．目的関数は以下の通りである：

の時間導関数は有限差分を使って離散化できる：

端末条件の制約はIndexedを使って指定できる：

離散化された問題を解く：

離散化された結果をInterpolatingFunctionに変換する：

制御変数をプロットする：

状態変数をプロットする：

制御変数についての，，に従ってを最小化する：

この積分は台形法を使って離散化できる：

．目的関数は以下の通りである：

における時間導関数は有限差分を使って離散化できる：

端末条件の制約はIndexedを使って指定できる：

制御変数についての制約条件：

離散化された問題を解く：

離散化された結果をInterpolatingFunctionに変換する：

制御変数はから5までに制限されるようになった：

状態変数をプロットする：

逐次二次最適化 (2)

非線形制約条件に従って非線形関数を最小化する．最小化は，をとして，また制約条件をとして近似することで行える．こうすると，反復的に解ける二次最小化問題になる．でである場合について考える：

最小化関数の勾配とヘッシアンは以下の通りである：

制約条件の勾配：

下位問題は，に従ってを最小化することでを求めることである：

最初の推測から始めて反復する．次の反復はである．ただし，は制約条件が常に満足されるためのステップ長である：

結果の収束を可視化する．最終結果は緑の点である：

に従ってを最小化する：

最小化関数の勾配とヘッシアン：

制約条件の勾配：

下位問題をとに従ってを最小化することである：

最初の推測から始めて反復する：

結果の収束を可視化する．最終結果は緑の点である：

特性と関係 (9)

QuadraticOptimizationは目的関数の大域的最小値を与える：

目的関数を可視化する：

ミニマイザは可能領域の内部または境界上にあってよい：

Minimizeは二次最適化問題の大域的厳密結果を与える：

NMinimizeを使って，大域法を使った近似結果を得ることができる：

FindMinimumを使って局所法を使った近似結果を得ることができる：

LinearOptimizationはQuadraticOptimizationの特殊ケースである：

行列ベクトル形式では，二次の項は0に設定されている：

SecondOrderConeOptimizationはQuadraticOptimizationの一般化である：

補助変数を使い，追加的な制約条件でを最小化する：

SemidefiniteOptimizationはQuadraticOptimizationの一般化である：

補助変数を使い，追加的な制約条件でを最小化する：

ConicOptimizationはQuadraticOptimizationの一般化である：

補助変数を使い，追加的な制約条件でを最小化する：

考えられる問題 (6)

狭義の不等式を使って指定された制約条件は，メソッドによっては満足されないかもしれない：

理由は，QuadraticOptimizationを解くとになるからである：

空集合あるいは実行不可能な問題の最小値はと定義されている：

ミニマイザは Indeterminateである：

非有界集合あるいは非有界問題の最小値はである：

ミニマイザはIndeterminateである：

解の特性の中には記号入力には使えないものがある：

混合整数問題に対する双対に関連した解の特性は得られないかもしれない：

複素数値を含む制約条件はベクトル不等式で指定しなければならない：

GreaterEqualを使うだけではうまくいかない：

トップへ

	最小化
	制約条件
	ただし	$(q_(rr) q_(ri); TemplateBox[{{q, _, {(, {r, , i}, )}}}, Transpose] q_(ii)) in S_+^n,c_r in R^(n_r),c_i in R^(n_i),a_r in R^(mxn_r),a_i in R^(mxn_i),b in R^m,a_(eq_r) in R^(kxn_r),a_(eq_i) in R^(kxn_i)b_(eq) in R^k$

	q
	{q,c}
	${{q_(f)},c}$	$1/2(q_f.x).(q_f.x)+c.x=1/2(x.TemplateBox[{{q, _, f}}, Transpose]).(q_f.x)+c.x$
	${{q_(f),c_(f)},c}$	$1/2(c_f+q_f.x).(c_f+q_f.x)+c.x=1/2(x.TemplateBox[{{q, _, f}}, Transpose]+c_f).(q_f.x+c_f)+c.x$

QuadraticOptimization

詳細とオプション

例題

例 (3)

スコープ (26)

基本的な用法 (8)

整数変数 (4)

複素変数 (3)

主モデルの特性 (4)

双対モデルの特性 (3)

感度特性 (4)

オプション (12)

Method (5)

PerformanceGoal (1)

Tolerance (2)

WorkingPrecision (4)

アプリケーション (29)

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

データフィッティング問題 (7)

分類問題 (2)

幾何問題 (3)

投資問題 (3)

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

軌道最適化問題 (2)

最適制御問題 (2)

逐次二次最適化 (2)

特性と関係 (9)

考えられる問題 (6)

関連項目

テクニカルノート

関連するガイド

履歴

テキスト

CMS

APA

BibTeX

BibLaTeX