最適化ソルバメソッドフレームワーク
Optimization`MethodFramework`コンテキストは,最適化問題のクラスのソルバをWolfram言語の最適化関数に接続することを可能にするフレームワークを提供する.このノートブックでは,接続されるソルバの登録方法およびWolfram言語システムと連動する定義の作成方法を説明する.
以下の例題では,Optimization`MethodFramework`がコンテキストパス上に存在するものと仮定している.
Needs["Optimization`MethodFramework`"]ここで目的関数および制約は,問題を効率よく解くために使うことができる特殊な形式に適合する.
| {"NonNegativeCone", m} | |||
| {"NormCone", m} | |||
| {"SemidefiniteCone", m} | 対称半正定値行列 | ||
| "ExponentialCone" | |||
| "DualExponentialCone" | |||
| {"PowerCone",α} | |||
| {"DualPowerCone",α} |
ソルバは,それがサポートする目的関数および制約の種類を指定することによって,システムに登録される.あるソルバがすべての形式の目的関数,または制約をサポートすると思わないように注意すること.例えば,線形最適化ソルバは"EqualityConstraint"と"NonNegativeCone"だけサポートする.
ソルバを登録して接続する
ソルバはRegisterOptimizationMethodを使って登録すると,Wolfram言語の最適化システムに接続される.
| RegisterOptimizationMethod[method, assoc] | 名前 method と,ソルバの機能の詳細を含む Association assoc を持つソルバを登録する |
ソルバ名 method は文字列でなければならない.一旦ソルバが登録されると,Wolfram言語の最適化関数で Method->method を指定することで使うことができる.
Association assoc では以下のキーを使うことができる:
| "SolveFunction" | ソルバを使うために評価する関数 | |
| "Submethods" | 登録されたサブメソッドのリスト | |
| "ConstraintSupport" | 制約に対するサポートのリスト | |
| "ObjectiveSupport" | メソッドによってサポートされる目的関数のタイプ | |
| "MixedIntegerSupport" | ソルバが混合整数計画問題に使えるかどうか | |
| "ExtendedPrecisionSupport" | メソッドが拡張精度をサポートするかどうか | |
| "FreeMethodDataFunction" | ソルバのデータがそれ以上必要ではなくなったときに評価する関数 | |
| "MessageHandling" | ソルバによって生成されたメッセージを扱う方法 |
"ObjectiveSupport"
"ObjectiveSupport"に関連付けられる値は以下のうちのいずれか一つである:
"ObjectiveSupport"が指定されたいない場合は,サポートは線形とみなされる.
"ConstraintSupport"
"ConstraintSupport"に関連付けられる値は連想である.キーはサポートされる制約の形式,値は ctype->stype のリストのサポートタイプである.ここで ctype は制約のタイプ,stype はサポートタイプである.
| "EqualityConstraint" | 等式制約 | |
| "NonNegativeCone" | 線形不等式制約 | |
| "NormCone" | 二次錐制約 | |
| "SemidefiniteCone" | 半正定値制約 | |
| "ExponentialCone" | 指数錐制約 | |
| "DualExponentialCone" | 双対指数錐制約 | |
| "PowerCone" | power cone制約 | |
| "DualPowerCone" | 双対power cone制約 | |
| "QuadraticConstraint" | 二次制約 | |
| "NonlinearConstraint" | 非線形制約 |
| "Affine" | ||
| "Membership" | ||
| "LinearMatrixInequality" | a1 x1+…+ak xk+b⪰ | |
| "SplitAffine" | 線形行列不等式のブロック構造による,別の半正定値制約(半正定値錐のみ) |
メンバーシップのサポートタイプは「アフィン」サポートの特殊形である.ここで
はゼロベクトルであり,
ならば
でそれ以外の場合は0である.これが別のケースとして含まれる理由は,錐問題の標準形式を以下のように記述する場合があるからである.
ソルバがサポートされる錐の少なくとも1つについてのメンバーシップを要求する場合,Wolfram言語システムはその問題をソルバがサポートするものに自動的に変換する.
SemidefiniteOptimizationは問題の中のすべての制約を単独の半正定値制約にまとめることによって動作する.このデフォルトソルバは,問題が1つの線形行列不等式の形式で表されていることを想定している.ソルバがサポートされる錐の少なくとも1つについてのメンバーシップを要求する場合,Wolfram言語システムはその問題をソルバがサポートするものに自動的に変換する.
"SolveFunction"
"SolveFunction"キーに関連付けられた値 sfun = assoc["SolveFunction"]は,Wolfram言語の最適化関数の主なインターフェースである.最適化関数がMethod->method で使われると,sfun[problemData, opts]が評価される.
| sfun[problemData, opts] | Method->method がWolfram言語の最適化関数に与えられると式が評価される |
| problemData | 解く問題についてのデータを含むAssociation |
| opts | 使用するソルバのオプション(空の場合もある) |
sfun[problemData, opts]を評価すると,リスト{status, methodData}が返される.
| Success["Solved",assoc] | 問題が解かれた | |
| Success["Unbounded",assoc] | 問題が非有界であった | |
| Success["Infeasible",assoc] | 問題が実行不可能であった | |
| Failure[reason,assoc] | ある理由(reason)のためにソルバは問題が解けなかった |
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} | |||
| {"SemidefiniteCone", m} | 対称正定値行列 | ||
| "ExponentialCone" | |||
| "DualExponentialCone" | |||
| {"PowerCone",α} | |||
| {"DualPowerCone",α} | |||
| "QuadraticConstraint" | | ||
| "NonlinearConstraint" |
このリストは上の表で示したように並んでいる.線形制約は組み合せることができるため,"EqualityConstraint"および"NonNegativeCone"は多くても1回しか現れない.つまり,複数の等式制約がある場合,これらは第1要素として現れ,複数の線形不等式制約がある場合,これらは等式制約の有無によって第1または第2要素に現れる.
問題にソルバによってサポートされない制約が含まれる場合,Wolfram言語システムはこれを自動的に検出し,適切なメッセージを表示する.そのため,指定リストには,登録されたソルバがサポートを提供する対象と錐指定だけが含まれる.
"ConstraintCoefficientArrays"
"ConstraintCoefficientArrays"に関連付けられるリストの中の項目は,"ConstraintSpecifications"リストの中の指定に1対1で対応し,以下の形式のいずれか一つである:
| 二次制約の | ||
| Identity | 変数成分 |
正定値制約の場合,サポートが"LinearMatrixInequality"として与えられると,線数学的な正確性を維持しながら形行列不等式 a1 x1+…+ak xk+b⪰
0をできるだけ明示的にするために,
は特別な形式{bj,Inactive[Transpose][{aj,…,ajn},{3, 2, 1}]}で与えられる.
"ConeVariableColumns"
"ConstraintSpecifications"に関連付けられたリストで指定されている錐の中の少なくとも1つがソルバの"Membership"で登録されている場合のみ,キー"ConeVariableColumns"が存在する.
"ConeVariableColumns"に関連付けられたリストの中の項目は,"ConstraintSpecifications"リストの指定と1対1で対応しており,以下のいずれかの形式である:
| None | 錐制約がアフィン( |
"ExtraColumns"
メンバーシップ錐制約の必要条件を満たすように問題が変換されなかったら,"ExtraColumns"に関連付けられる値は,ゼロである.問題が変換された場合,この値は変換処理の間に加えられた追加列の数となる.
"IntegerVariableColumns"
"IntegerVariableColumns"に関連付けられたリストは,整数値を持たなければならない変数ベクトルの指標を与える.ソルバが混合整数サポートを持つように登録されていない場合は,これは常に空のリスト{}となる.
オプション
ソルバ関数 sfun[problemData, opts]に与えられるオプションは,Wolfram言語の最適化関数に与えられるオプションに加え,ソルバがメソッドオプションとして使う任意のオプションである.
Wolfram言語の最適化関数のオプションとして含まれるものは次の通りである:
| MaxIterations | Automatic | 使用する最大反復回数 | |
| PerformanceGoal | $PerformanceGoal | 最適化を試みるパフォーマンスの局面 | |
| Tolerance | Automatic | 内部比較に使う許容度 | |
| WorkingPrecision | MachinePrecision | 使用する精度 |
これらのオプションは,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で非線形の内点法を使って,非常に簡単な凸ソルバを設定するのに必要なステップを示す.このメソッドは専用の凸ソルバを使うほど速くも強力でもないが,ソルバの登録とインターフェースの説明の役割は果たす.
ソルバの登録と定義
Needs["Optimization`MethodFramework`"]RegisterOptimizationMethod["FindMinimum", Association["SolveFunction" -> FindMinimumSolve, "ConstraintSupport" -> <|"EqualityConstraint" -> "Affine", "NonNegativeCone" -> "Affine", "NormCone" -> "Affine"|>]]これは,"FindMinimum"という名前のソルバを登録する.このソルバには"FindMinimumSolve"という名前のSolve関数および錐制約が含まれる.錐制約は,アフィンが左辺にあるベクトルの等式( aj.x+bj==0),ベクトルの不等式(aj.x+bj0),ノルム錐制約(aj.x+bjm0)の可能性がある.ここで x∈n,aj∈mj×n,bj∈mj, j=1... k である.
ConeConditions[{"EqualityConstraint", _}, x_] := Thread[x == 0];
ConeConditions[{"NonNegativeCone", _}, x_] := Thread[x >= 0];
ConeConditions[{"NormCone", k_}, x_] := Block[{xt = Last[x], xx = Drop[x, -1]}, {xx.xx <= xt ^ 2, xt >= 0}];FindMinimumSolve[problemData_, opts___] :=
Module[{n, c = problemData["ObjectiveVector"], coneSpecifications = problemData["ConstraintSpecifications"], coefficients = problemData["ConstraintCoefficientArrays"], members, vars, x, conditions, constraints, minVal, rules, solution, status, data},
n = Length[c];
vars = Array[x, n];
members = Apply[Function[{b, a}, a.vars + b], coefficients, {1}];
conditions = MapThread[ConeConditions[##]&, {coneSpecifications, members}];
constraints = DeleteCases[Flatten[conditions], True];
solution = Apply[FindMinimum, {{c.vars, constraints}, vars, FilterRules[{opts}, Options[FindMinimum]], Method -> Except["Convex"]}];
If[MatchQ[solution, {_ ? NumberQ, {__Rule}}],
{minVal, rules} = solution;
status = Success["Solved", Association[]];
data = FindMinimumSolutionData[minVal, vars /. rules]
,
status = Failure["NoSolutionFound", Association[]];
data = $Failed
];
{status, data}
];FindMinimumSolutionData[minValue_, argMin_]["PrimalMinimumValue"] := minValue;
FindMinimumSolutionData[minValue_, argMin_]["PrimalMinimizerVector"] := argMin;
FindMinimumSolutionData[minValue_, argMin_][_String] := Missing["NotAvailable"];ソルバによって特性が与えられない場合,適切な設定はMissing["NotAvailable"]となる.これは"FindMinimum"ソルバのどの双対特性に対しても使われる.双対は通常の非線形内点法アルゴリズムで計算されることも考慮されることもないからである.
"FindMinimum"ソルバの使用例
ConicOptimization[x + y, {x ^ 2 + x y + y ^ 2 ≤ 1, x - y == 2}, {x, y}, Method -> "FindMinimum"]メインのソルバ関数は,FindMinimumに任意のオプションを渡す.凸ソルバからMethod->{"FindMinimum", fmopts}を与えると fmopts がFindMinimumに渡される.
ConicOptimization[x + y, {x ^ 2 + x y + y ^ 2 ≤ 1, x - y == 2}, {x, y}, Method -> {"FindMinimum", Method -> "IPOPT"}]ConicOptimization[x + y, {x ^ 2 + x y + y ^ 2 ≤ 1, x - y == 2}, {x, y}, Method -> {"FindMinimum", Method -> "InteriorPoint"}]問題が,ソルバが扱うように登録された問題の範疇にない場合,Wolfram言語は自動的にこれを検出してメッセージを発する.
ConicOptimization[x + y, {(| | |
| - | - |
| x | 1 |
| 1 | y |)Underscript[, "SemidefiniteCone"]0}, {x, y}, Method -> {"FindMinimum", Method -> "InteriorPoint"}]ConicOptimization[2x + 3 y, {(| | |
| - | - |
| x | 1 |
| 1 | y |)Underscript[, "SemidefiniteCone"]0}, {x, y}]上の例ではすべてConicOptimizationを使っているが,問題によっては他の凸最適化関数を使うこともできる.登録された凸ソルバでは,関数は自動的に錐形式に変換される.
SecondOrderConeOptimization[x + y, Norm[{x, y}] ≤ 1, {x, y}, Method -> "FindMinimum"]QuadraticOptimization[2x^2 + 20y^2 + 6x y + 5x, -x + y ≥ 2, {x, y}, Method -> "FindMinimum"]何らかの理由でFindMinimumが最小値を求められない場合,通常メッセージが発せられる.
ConicOptimization[x + y, {x ^ 2 + x y + y ^ 2 ≤ 1, x - y == 2}, {x, y}, Method -> {"FindMinimum", Method -> "Newton"}]このメソッドは"MessageHandling"特性を指定しないで登録されたので,デフォルトの"Collect"設定が使われる."Collect"では,あるメッセージが複数回出る場合でも一度しか表示されない.新しいソルバ関数をデバッグする場合は,メッセージが生成されるとすぐに表示された方が便利なことが多い.
RegisterOptimizationMethod["FindMinimum", Association["SolveFunction" -> FindMinimumSolve, "ConstraintSupport" -> <|"EqualityConstraint" -> "Affine", "NonNegativeCone" -> "Affine", "NormCone" -> "Affine"|>, "MessageHandling" -> "Immediate"]]ConicOptimization[x + y, {x ^ 2 + x y + y ^ 2 ≤ 1, x - y == 2}, {x, y}, Method -> {"FindMinimum", Method -> "Newton"}]FindMinimum::ucmtdというメッセージが何度も表示されるのは,FindMinimumで起こっているように,変数が局所的値を与えられたときのWolfram言語の動作のためである.
"CVX" ソルバ
これは,Wolfram言語に組み込まれているPython用の外部言語インターフェースを使って,凸最適化およびモデリングのためのCVXPYパッケージにアクセスする例である.
必要条件は,Pythonをインストールし,ExternalEvaluate用に設定すること,およびCVXPYをインストールすることである.デフォルトでCVXPYと一緒にインストールされるソルバに加え,CVXPYが呼び出すことのできる他のソルバをオプショナルでインストールしてもよい.
"CVX"凸ソルバの実装は,CVXLink`パッケージにある.
FindFile["CVXLink`"]Needs["CVXLink`"]Needs["Optimization`MethodFramework`"]ソルバの登録と定義
以下に示す登録と定義はCXVLinkパッケージに実装されている.これらはCXVLinkパッケージがロードされると評価されるので,ここでは説明のためだけに示すものである.
RegisterConvexMethod["CVX", Association["SolveFunction" -> CVXLink`CVXSolve, "FreeMethodDataFunction" -> CVXLink`DeleteCVXData, "ConicConstraintSupport" -> Thread[{"EqualityConstraint", "NonNegativeCone", "NormCone", "SemidefiniteCone", "ExponentialCone"} -> "Affine"]]];Options[CVXLink`CVXSolve] = {Method -> Automatic, Tolerance -> Automatic, MaxIterations -> Automatic, "Verbose" -> False};
CVXLink`CVXSolve[problemData_, OptionsPattern[]] := Module[{status, c = problemData["ObjectiveVector"], methodData, cones, affine, cvxMethod = OptionValue[Method], verbose = OptionValue["Verbose"], tolerance = OptionValue["Tolerance"], maxIterations = OptionValue["MaxIterations"]}, methodData = CVXLink`CreateCVXData[Length[c]];
methodData["SetObjective"[{c, 0}]];
cones = problemData["ConicConstraintConeSpecifications"];
affine = problemData["ConicConstraintAffineLists"];
MapThread[CVXLink`AddConstraint[methodData, ##]&, {cones, affine}];
status = methodData["Solve"[cvxMethod, verbose, tolerance, maxIterations]];
{status, CVXLink`CVXMethodData[methodData, affine]}];CVXLink`CVXMethodData[data : CVXData[__], ___]["PrimalMinimizerVector"] := Normal[CVXLink`CallMethodOnProblem[data, "primal_minimizer()"], NumericArray]
CVXLink`CVXMethodData[data : CVXData[__], ___]["PrimalMinimumValue"] := CVXLink`CallMethodOnProblem[data, "primal_value()"]
CVXLink`CVXMethodData[data : CVXData[__], ___]["DualMaximizer"] := Module[{types = CVXLink`CallMethodOnProblem[data, "constraint_types()"], maximizers = Normal[CVXLink`CallMethodOnProblem[data, "dual_maximizer()"], NumericArray]}, MapThread[CVXLink`ConvertPythonDualMaximizer, {types, maximizers}]]
CVXLink`CVXMethodData[data : CVXData[__], affine_]["DualMaximumValue"] := Module[{dmax, dval, types = CVXLink`CallMethodOnProblem[data, "constraint_types()"], maximizers = Normal[CVXLink`CallMethodOnProblem[data, "dual_maximizer()"], NumericArray]}, dmax = MapThread[CVXLink`ConvertPythonDualMaximizer, {types, maximizers}];
dval = -Flatten[dmax].Flatten[affine[[All, -1]]]]
CVXLink`CVXMethodData[data : CVXData[__], affine_]["Slack"] := Module[{x, slacks}, x = Normal[CVXLink`CallMethodOnProblem[data, "primal_minimizer()"], NumericArray];
slacks = Map[(#[[1]].x + #[[2]])&, affine]]"CVX"ソルバの使用例
ConicOptimization[Indexed[x, {1}] + Indexed[x, {2}], {Indexed[x, {1}] == Indexed[x, {2}], Indexed[x, {1}]^2 + Indexed[x, {2}]^2 ≤ 1}, {Indexed[x, {1}], Indexed[x, {2}]}, Method -> "CVX"]ConicOptimization[Indexed[x, {1}] + Indexed[x, {2}], {Indexed[x, {1}] == Indexed[x, {2}], Indexed[x, {1}]^2 + Indexed[x, {2}]^2 ≤ 1}, {Indexed[x, {1}], Indexed[x, {2}]}, Method -> {"CVX", Method -> "ECOS"}]ConicOptimization[Indexed[x, {1}] + Indexed[x, {2}], {Indexed[x, {1}] == Indexed[x, {2}], Indexed[x, {1}]^2 + Indexed[x, {2}]^2 ≤ 1}, {Indexed[x, {1}], Indexed[x, {2}]}, Method -> {CVX, Method -> "ECOS", Verbose -> True, Tolerance -> 10 ^ -10, MaxIterations -> 10}]