最適化ソルバメソッドフレームワーク

Optimization`MethodFramework`コンテキストは，最適化問題のクラスのソルバをWolfram言語の最適化関数に接続することを可能にするフレームワークを提供する．このノートブックでは，接続されるソルバの登録方法およびWolfram言語システムと連動する定義の作成方法を説明する．

以下の例題では，Optimization`MethodFramework`がコンテキストパス上に存在するものと仮定している．

候補となるメソッドは，最小化問題が解けるソルバである：

	最小化する
	次の制約に従う

ここで目的関数および制約は，問題を効率よく解くために使うことができる特殊な形式に適合する．

以下の形式の目的関数がサポートされる：

	"Linear"	線形目的関数
	"Quadratic"	二次目的関数
	"Nonlinear"	一般的な非線形目的関数

形式 の錐制約は，次の適切な凸錐 についてサポートされる：

	{"NonNegativeCone", m}		となるような
	{"NormCone", m}		≤ymとなるような
	{"SemidefiniteCone", m}		対称半正定値行列
	"ExponentialCone"		となるような
	"DualExponentialCone"		または となるような
	{"PowerCone",α}		となるような
	{"DualPowerCone",α}		となるような

さらに，以下の制約タイプがサポートされる：

	{"LinearEqualityConstraint", m}
	"QuadraticConstraint"
	"NonlinearConstraint"

ソルバは，それがサポートする目的関数および制約の種類を指定することによって，システムに登録される．あるソルバがすべての形式の目的関数，または制約をサポートすると思わないように注意すること．例えば，線形最適化ソルバは"EqualityConstraint"と"NonNegativeCone"だけサポートする．

ソルバを登録して接続する

ソルバはRegisterOptimizationMethodを使って登録すると，Wolfram言語の最適化システムに接続される．

ソルバのメソッドを登録する

ソルバ名 method は文字列でなければならない．一旦ソルバが登録されると，Wolfram言語の最適化関数で Method->method を指定することで使うことができる．

Association assoc では以下のキーを使うことができる：

"ObjectiveSupport"

"ObjectiveSupport"に関連付けられる値は以下のうちのいずれか一つである：

	"Linear"	線形目的関数
	"Quadratic"	二次目的関数
	"Nonlinear"	一般的な非線形目的関数

"ObjectiveSupport"が指定されたいない場合は，サポートは線形とみなされる．

"ConstraintSupport"

"ConstraintSupport"に関連付けられる値は連想である．キーはサポートされる制約の形式，値は ctype->stype のリストのサポートタイプである．ここで ctype は制約のタイプ，stype はサポートタイプである．

制約のタイプは以下のいずれかで与えることができる：

サポートタイプは以下のいずれか一つである：

	"Affine"
	"Membership"
	"LinearMatrixInequality"	a1 x1+…+ak xk+b⪰0（半正定値錐のみ）
	"SplitAffine"	線形行列不等式のブロック構造による，別の半正定値制約（半正定値錐のみ）

メンバーシップのサポートタイプは「アフィン」サポートの特殊形である．ここで はゼロベクトルであり， ならば でそれ以外の場合は0である．これが別のケースとして含まれる理由は，錐問題の標準形式を以下のように記述する場合があるからである．

	最小化する
	次の制約に従う

ここでΚは錐 のテンソル積である．これは次に等しい．

	最小化する
	次の制約に従う

ソルバがサポートされる錐の少なくとも1つについてのメンバーシップを要求する場合，Wolfram言語システムはその問題をソルバがサポートするものに自動的に変換する．

SemidefiniteOptimizationは問題の中のすべての制約を単独の半正定値制約にまとめることによって動作する．このデフォルトソルバは，問題が1つの線形行列不等式の形式で表されていることを想定している．ソルバがサポートされる錐の少なくとも1つについてのメンバーシップを要求する場合，Wolfram言語システムはその問題をソルバがサポートするものに自動的に変換する．

"SolveFunction"

"SolveFunction"キーに関連付けられた値 sfun = assoc["SolveFunction"]は，Wolfram言語の最適化関数の主なインターフェースである．最適化関数がMethod->method で使われると，sfun[problemData, opts]が評価される．

"SolveFunction"の評価

sfun[problemData, opts]を評価すると，リスト{status, methodData}が返される．

状態は以下のいずれか一つである：

Association assoc は解についての情報を含む場合もあるが，空()の場合もある．Wolfram言語システムはメッセージを自動的に処理する．

メソッドデータmethodDataは，これに関連付けられた，解の特性を取り出すための定義を持つ任意のWolfram言語式である．可能な買いの特性についての詳細は「メソッドデータ」セクションで説明する．

多数のオプションはどのようにメソッドが呼び出されるかによって異なるため，sfun は任意数の引数を取ることができる．したがって，ソルバ関数がDownValuesで定義されていれば，opts 引数のパターンはBlankNullSequence (opts___)を使って与えなければならない．例えば，定義は sfun[problemData_, opts___] := …となる場合もある．

問題データ

problemData Associationは次の問題に対応して，Wolfram言語の最適化関数によって構築される：

	最小化する
	次の制約に従う

問題は以下のキーを使って記述する：

	"ObjectiveVector"
	"ObjectiveMatrix"	"ObjectiveSupport"が"Quadratic"ならば二次行列
	"ObjectiveFunction"	非線形目的関数
	"ConstraintSpecifications"
	"ConstraintCoefficientArrays"
	"IntegerVariableColumns"	のすべての成分についての列番号のリストであり，整数と想定される
	"ConeVariableColumns"	変数のメンバーシップを要求する各錐制約に関連付けられた変数列のリスト
	"ExtraColumns"	変数メンバーシップを持つ錐制約に変換するために加えられた追加列の数
	"Caller"	ソルバを呼び出しているWolfram言語関数

"ObjectiveVector"

"ObjectiveSupport"が"Linear"または"Quadratic"の場合，または指定されておらず線形と想定される場合，"ObjectiveVector"に関連付けられる値はベクトル として定義される．この場合目的関数は である．

"ObjectiveMatrix"

"ObjectiveSupport"が"Quadratic"の場合にのみ，"ObjectiveMatrix"に関連付けられる値は正定値行列 として定義される．この場合目的関数は である．

"ObjectiveFunction"

"ObjectiveSupport"が"Nonlinear"の場合にのみ，"ObjectiveMatrix"に関連付けられる値はExperimental`NumericalFunctionの目的関数である として定義される．この場合目的関数は f[x]を使って計算される．一次および二次導関数も f["Gradient"[x]]および f["Hessian"[x]]を使って計算される．

"ConstraintSpecifications"

"ConstraintSpecifications"に関連付けられるリストには，以下の指定を含むことができる：

	{"EqualityConstraint", m}		となるような
	{"NonNegativeCone", m}		となるような
	{"NormCone", m}		≤ymとなるような
	{"SemidefiniteCone", m}		対称正定値行列
	"ExponentialCone"		となるような
	"DualExponentialCone"		または となるような
	{"PowerCone",α}		となるような
	{"DualPowerCone",α}		となるような
	"QuadraticConstraint"
	"NonlinearConstraint"

このリストは上の表で示したように並んでいる．線形制約は組み合せることができるため，"EqualityConstraint"および"NonNegativeCone"は多くても1回しか現れない．つまり，複数の等式制約がある場合，これらは第1要素として現れ，複数の線形不等式制約がある場合，これらは等式制約の有無によって第1または第2要素に現れる．

問題にソルバによってサポートされない制約が含まれる場合，Wolfram言語システムはこれを自動的に検出し，適切なメッセージを表示する．そのため，指定リストには，登録されたソルバがサポートを提供する対象と錐指定だけが含まれる．

"ConstraintCoefficientArrays"

"ConstraintCoefficientArrays"に関連付けられるリストの中の項目は，"ConstraintSpecifications"リストの中の指定に1対1で対応し，以下の形式のいずれか一つである：

		の{ベクトル, 行列}ペア
		二次制約の の{定数, ベクトル, 行列}からなる組
	Identity	変数成分の明示的なメンバーシップが要求される場合のみ

正定値制約の場合，サポートが"LinearMatrixInequality"として与えられると，線数学的な正確性を維持しながら形行列不等式 a₁ x₁+…+a_k x_k+b⪰0をできるだけ明示的にするために，は特別な形式{b_j,Inactive[Transpose][{a_j,…,a_jn},{3, 2, 1}]}で与えられる．

"ConeVariableColumns"

"ConstraintSpecifications"に関連付けられたリストで指定されている錐の中の少なくとも1つがソルバの"Membership"で登録されている場合のみ，キー"ConeVariableColumns"が存在する．

"ConeVariableColumns"に関連付けられたリストの中の項目は，"ConstraintSpecifications"リストの指定と1対1で対応しており，以下のいずれかの形式である：

	None	錐制約がアフィン()の場合

"ExtraColumns"

メンバーシップ錐制約の必要条件を満たすように問題が変換されなかったら，"ExtraColumns"に関連付けられる値は，ゼロである．問題が変換された場合，この値は変換処理の間に加えられた追加列の数となる．

"IntegerVariableColumns"

"IntegerVariableColumns"に関連付けられたリストは，整数値を持たなければならない変数ベクトルの指標を与える．ソルバが混合整数サポートを持つように登録されていない場合は，これは常に空のリスト{}となる．

オプション

ソルバ関数 sfun[problemData, opts]に与えられるオプションは，Wolfram言語の最適化関数に与えられるオプションに加え，ソルバがメソッドオプションとして使う任意のオプションである．

Wolfram言語の最適化関数のオプションとして含まれるものは次の通りである：

これらのオプションは，opts に上記のデフォルト値以外の値が与えられている場合にのみ含まれる．

WorkingPrecisionオプションは，ソルバが"ExtendedPrecisionSupport"->Trueで登録された場合にのみ含まれる．

メソッドは，メソッドオプションでMethod->{method, mopts}を使って指定することができる．ここで mopts はメソッドオプションである．

オプションが空の場合，ソルバ関数の評価は sfun[problemData]だけになる．

メソッドデータ

sfun[problemData, opts]を評価すると{status, methodData}になる場合，methodData は任意のWolfram言語式となり得る．

状態のHeadがSuccessの場合，以下の解の特性の定義がある：

	methodData["PrimalMinimizerVector"]
	methodData["PrimalMinimumValue"]
	methodData["DualMaximizer"]
	methodData["DualMaximumValue"]
	methodData["Slack"]	（定義されていない場合は自動的に計算される）

これらは以下で説明する表記による主問題および双対問題に基づいている．

主問題：

	最小化する
	次の制約に従う

これは以下と等しい：

	最小化する
	次の制約に従う

双対問題：

	最大化する
	次の制約に従う

"ExtendedPrecisionSupport"

通常，ソルバは計算を行うのに機械精度数を使うと想定される．しかし，メソッドが拡張精度数を扱えれば，ソルバ関数はWorkingPrecisionオプションを取り，"ExtendedPrecisionSupport"キーに関連付けられた値はTrueでなければならない．メソッドが追加で厳密値の計算も扱える場合は(WorkingPrecision->∞)，関連付けられた値はAllでなければならない．WorkingPrecisionオプションは，Method->{"methodName", WorkingPrecision->20}のようにメソッドオプションとして処理される．

"MessageHandling"

"MessageHandling"に関連付けられる値は以下のいずれか一つである：

デフォルト値の"Collect"では，メッセージはコードによって収集され，解法が終了したときに発せられる．ソルバを呼び出す関数のメッセージタグは，変更される．

例

"FindMinimum"ソルバ

この例では，関数FindMinimumで非線形の内点法を使って，非常に簡単な凸ソルバを設定するのに必要なステップを示す．このメソッドは専用の凸ソルバを使うほど速くも強力でもないが，ソルバの登録とインターフェースの説明の役割は果たす．

ソルバの登録と定義

これは，"FindMinimum"という名前のソルバを登録する．このソルバには"FindMinimumSolve"という名前のSolve関数および錐制約が含まれる．錐制約は，アフィンが左辺にあるベクトルの等式( a_j.x+b_j==0)，ベクトルの不等式(a_j.x+b_j0)，ノルム錐制約(a_j.x+b_j_^m0)の可能性がある．ここで x∈ⁿ,a_j∈^m_j×n,b_j∈^m_j, j=1... k である．

ソルバによって特性が与えられない場合，適切な設定はMissing["NotAvailable"]となる．これは"FindMinimum"ソルバのどの双対特性に対しても使われる．双対は通常の非線形内点法アルゴリズムで計算されることも考慮されることもないからである．

"FindMinimum"ソルバの使用例

メインのソルバ関数は，FindMinimumに任意のオプションを渡す．凸ソルバからMethod->{"FindMinimum", fmopts}を与えると fmopts がFindMinimumに渡される．

問題が，ソルバが扱うように登録された問題の範疇にない場合，Wolfram言語は自動的にこれを検出してメッセージを発する．

上の例ではすべてConicOptimizationを使っているが，問題によっては他の凸最適化関数を使うこともできる．登録された凸ソルバでは，関数は自動的に錐形式に変換される．

何らかの理由でFindMinimumが最小値を求められない場合，通常メッセージが発せられる．

このメソッドは"MessageHandling"特性を指定しないで登録されたので，デフォルトの"Collect"設定が使われる．"Collect"では，あるメッセージが複数回出る場合でも一度しか表示されない．新しいソルバ関数をデバッグする場合は，メッセージが生成されるとすぐに表示された方が便利なことが多い．

FindMinimum::ucmtdというメッセージが何度も表示されるのは，FindMinimumで起こっているように，変数が局所的値を与えられたときのWolfram言語の動作のためである．

"CVX" ソルバ

これは，Wolfram言語に組み込まれているPython用の外部言語インターフェースを使って，凸最適化およびモデリングのためのCVXPYパッケージにアクセスする例である．

必要条件は，Pythonをインストールし，ExternalEvaluate用に設定すること，およびCVXPYをインストールすることである．デフォルトでCVXPYと一緒にインストールされるソルバに加え，CVXPYが呼び出すことのできる他のソルバをオプショナルでインストールしてもよい．

"CVX"凸ソルバの実装は，CVXLink`パッケージにある．

ソルバの登録と定義

以下に示す登録と定義はCXVLinkパッケージに実装されている．これらはCXVLinkパッケージがロードされると評価されるので，ここでは説明のためだけに示すものである．

"CVX"ソルバの使用例