(57)【特許請求の範囲】
【請求項１】
予測対象の説明に用いられる説明変数が最適化の操作変数になり、当該予測対象の予測に基づいて最適化を行う最適化装置であって、
予測される操作変数の候補の集合を決定する候補集合決定部と、
前記集合に含まれる操作変数に対して、指定された確率で前記予測による誤差である推定誤差が含まれるマージンを決定するマージン決定部と、
決定されたマージンを用いて、操作変数に関するロバスト最適化を行うロバスト最適化部とを備え、
前記マージン決定部は、決定された前記集合に含まれるすべての操作変数の候補に対して、前記推定誤差を含むマージン付き制約式が真の制約式の上界になるマージンを決定する
ことを特徴とする最適化装置。
【請求項２】
候補集合決定部は、予測値からの誤差の範囲に含まれるサンプルで候補の集合を近似する
請求項１記載の最適化装置。
【請求項３】
マージン決定部は、マージンの候補集合の中から、決定された集合に含まれるすべての説明変数の候補に対して、指定された確率で推定誤差が含まれたマージン付制約式が、真の制約式よりも厳しくなる、最小のマージンを決定する
請求項１または請求項２記載の最適化装置。
【請求項４】
マージンの候補集合は、１次元のパラメータで表されるマージンの候補を含む
請求項３記載の最適化装置。
【請求項５】
候補集合決定部は、最適化による誤差を示すシステム誤差および推定誤差の範囲に含まれるサンプルで候補の集合を近似し、
マージン決定部は、指定された確率で前記システム誤差および推定誤差が含まれるマージンを決定する
請求項１から請求項４のうちのいずれか１項に記載の最適化装置。
【請求項６】
予測対象の説明に用いられる説明変数が最適化の操作変数になり、当該予測対象の予測に基づいて最適化を行う最適化方法であって、
コンピュータが、予測される操作変数の候補の集合を決定し、
前記コンピュータが、前記集合に含まれる操作変数に対して、指定された確率で前記予測による誤差である推定誤差が含まれるマージンを決定し、
前記コンピュータが、決定されたマージンを用いて、操作変数に関するロバスト最適化を行い、
前記マージンを決定する際、前記コンピュータが、決定された前記集合に含まれるすべての操作変数の候補に対して、前記推定誤差を含むマージン付き制約式が真の制約式の上界になるマージンを決定する
ことを特徴とする最適化方法。
【請求項７】
コンピュータが、予測値からの誤差の範囲に含まれるサンプルで候補の集合を近似する
請求項６記載の最適化方法。
【請求項８】
予測対象の説明に用いられる説明変数が最適化の操作変数になり、当該予測対象の予測に基づいて最適化を行うコンピュータに適用される最適化プログラムであって、
前記コンピュータに、
予測される操作変数の候補の集合を決定する候補集合決定処理、
前記集合に含まれる操作変数に対して、指定された確率で前記予測による誤差である推定誤差が含まれるマージンを決定するマージン決定処理、および、
決定されたマージンを用いて、操作変数に関するロバスト最適化を行うロバスト最適化処理を実行させ、
前記マージン決定処理で、決定された前記集合に含まれるすべての操作変数の候補に対して、前記推定誤差を含むマージン付き制約式が真の制約式の上界になるマージンを決定させる
ための最適化プログラム。
【請求項９】
コンピュータに、
候補集合決定処理で、予測値からの誤差の範囲に含まれるサンプルで候補の集合を近似させる
請求項８記載の最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予測に基づいて最適化を行う最適化装置、最適化方法および最適化プログラムに関する。
【背景技術】
【０００２】
近年、多くの情報を基に、所定の条件における最適な情報（例えば、プラントにおける材料の投入量、操作機器における操作量、又は、商品の設定価格）を利用者に提供する装置やシステムが用いられている。また、利用者が、最終的な選択を行うための情報（例えば、判断指標など）を提供する装置やシステムも用いられている。【０００３】
例えば、電力会社は、複数の発電所を含む発電システムの制御において、所定の条件（例えば、総需要電力を満足しながらコストを最小にする）を満足する各発電所の発電量を決定することが必要である。そこで、電力会社では、例えば、需要予測（総需要電力の予測）に基づく発電システムをモデル化した最適化モデルが作成される。そして、最適な発電量（最適解）を決定するために、所定の装置又はシステムを用いて、その最適化モデルにおける最適解（発電量）が算出される。【０００４】
他にも、企業の購入部門は、生産活動における資材の購入において、生産計画などを満足しながら利益を最大とする（購入コストを最小とする）資材の購入量（最適解）を決定することを必要とする。そこで、購入部門では、需要予測（例えば、必要となる資材の量の予測）に基づく購入量をモデル化した最適化モデルが作成される。そして、購入量を決定するため、所定の装置又はシステムを用いて、作成した最適化モデルにおける最適解（購入量）が算出される。【０００５】
このように、予測に基づいた判断又は計画をソフトウェア又は所定の装置が最適に行う技術について、以下、その具体例を説明する。【０００６】
まず、最適化の処理の対象となる最適化モデルが決定される。最適化モデルは、具体的な最適化の目的を示す「目的関数」と、最適解の算出における条件である「制約」とを含む。「目的関数」は、「操作変数」の関数として表される。「操作変数」は、最適化の対象である。最適化において、上記のソフトウェア又は装置は、制約を満たしつつ目的関数の値が最適（例えば、最大又は最小）となるように、「操作変数」の値を最適化する。最適化された目的変数の値を、以下、「最適解」と呼ぶ。なお、最適解は、将来的な値である。そのため、目的関数は、その中に、所定の変数及びパラメータを用いて表される予測モデルを含む。【０００７】
予測モデルは、予測対象である変数（以下、「被説明変数」と呼ぶ）と、予測対象に影響を及ぼし得る変数（以下、「説明変数」と呼ぶ）との関係性を示すモデルである。一般的に、被説明変数は、予測モデルにおいて、説明変数を用いた関数として表現される。【０００８】
上記のとおり、予測における予測対象である変数に対して、「被説明変数」という用語が用いられる。これに対し、最適化処理における最適化対象である変数に対して、「操作変数」という用語が用いられる。このように、以下の説明において、「被説明変数」という用語と、「操作変数」という用語とは、相互に区別して用いられる。【０００９】
なお、予測モデルは、例えば、過去の説明変数と被説明変数とを用いた機械学習等を基に作成される。予測モデルを生成する一般的な方法として、例えば、「回帰分析」がある。【００１０】
そして、情報処理装置は、最適化モデルの最適解として、目的関数を最適化（例えば、最大化）する目的変数の値（最適解）を算出する。ここで、予測モデルにおける説明変数の少なくとも一部が、最適化モデルにおける目的変数（最適化の対象である変数）となることがあり得る。この点については、後ほど価格最適化の具体例を用いて説明する。【００１１】
また、一般的に、目的変数は、取り得る値の範囲に制限がある。例えば、上記の発電所における発電量は、上限がある。例えば、このような制限が、「制約」の一例である。ただし、制約は、その他の条件を含んでもよい。そこで、情報処理装置は、例えば、所定の制約を満足する範囲で、目的関数の値が最大になるような最適解を算出する。このように、最適解を算出する情報処理装置が最適化の対象として用いる最適化モデルは、目的関数及び制約を含むモデルである。【００１２】
なお、最適化モデルは、情報処理装置において処理されるため、一般的には、上記の目的関数及び制約を、情報処理装置で取り扱い可能な形式（通常は、変数を用いて表現された数式）を用いて表される。そして、情報処理装置は、最適解として、最適化モデルに含まれる制約の下で、目的関数の値を最適値（最大値、又は、最小値）とする目的変数の値を算出する。【００１３】
最適化モデルに含まれる目的関数が、目的変数の一次関数を用いて表される場合、その最適化モデルは、「線形最適化モデル」と呼ばれる。また、最適化モデルに含まれる目的関数が、目的変数の二次関数を用いて表される場合、その最適化モデルは、「二次最適化モデル」と呼ばれる。【００１４】
ここで、具体例として、ある複数の商品又は役務（サービス）の総売上高を最適化するために、各商品又は各役務の価格をいくらに設定したらよいか、という価格最適化の最適化モデル説明する。ただし、以下では、一例として、商品を用いて説明する。【００１５】
総売上高は、各商品の価格と、商品の売上げ量（売上げ数）との積の総和である。つまり、総売上高は、「総売上高＝（各商品の価格×各商品の売上げ量）の合計」となる。【００１６】
ここで、商品の価格は、商品の販売者が、設定可能な値である。一方、売上げ量は、販売者が決定できない値であり、さらに、最適化処理を実行する時点から見て未来の値である。【００１７】
そこで、商品の売上げ量を予測するため、例えば、機械学習を用いて予測モデルが設定される。ここで、商品の売上げ量は、その商品の価格の影響を受けることは自明である。そのため、商品の売上げ量は、商品の売上げ量を予測する予測モデルにおいて、被説明変数である。また、商品の価格は、予測モデルにおいて、説明変数となる。つまり、被説明変数である商品の売上げ量は、予測モデルにおいて、商品の価格の関数として表される。つまり、総売上高（目的関数）は、「説明変数（商品の価格）」と「被説明変数（商品の価格に影響を受ける売上げ量）」との積となる。【００１８】
上記のとおり、被説明変数は、説明変数（商品の価格）の関数を用いて表される。このため、総売上高（目的関数）は、商品の価格（説明変数）の少なくとも二次の関数になる。【００１９】
ここで、商品の価格は、最適化モデルにおける目的変数である。つまり、総売上高（目的関数）は、目的変数（商品の価格）の少なくとも二次関数を用いて表される。そのため、上記のような商品の価格を操作して総売上高を最適化する場合、最適化モデルとして、二次最適化モデルが用いられている。なお、この場合、制約は、例えば、商品の在庫量である。【００２０】
上記の具体例から理解されるように、予測モデルにおける説明変数（商品の価格）が、最適化モデルにおける目的変数（商品の価格）、すなわち最適化対象である変数になり得ることに留意されたい。言い換えると、商品の価格という一つの変数が、学習処理及び予測処理においては説明変数として振る舞い、最適化処理においては目的変数として振る舞うことに留意されたい。【００２１】
最適化モデルは、最適化モデルを表す数式に、１つ又は複数のパラメータを含む。パラメータは、過去の観測データなどを基に決定される値である。しかし、観測データは、測定における誤差を含むデータである。また、最適化モデルの算出対象は、まだ確定していない将来における値（最適解）である。つまり、最適解は、過去のデータが生成された時とは異なる状況において算出される可能性がある。そのため、最適化モデルに含まれるパラメータは、不確実性を含む。【００２２】
一般的に広く用いられている最適化モデルにおける最適解を算出する手法は、パラメータにおける不確実性を考慮していない。そのため、一般的な最適化モデルを用いて算出された最適解は、実際に適用された場合において、最適とはならない可能性がある。以下、この理由を説明する。【００２３】
上記のとおり、最適化モデルは、パラメータを含む。そして、パラメータは、不確実性を含む。そのため、最適解の値が実際の適用される時におけるパラメータの値は、最適解の算出に用いたパラメータの値と異なっている場合がある。この場合、算出された最適解は、実際に適用されるときにおける最適解となっていない可能性がある。【００２４】
そこで、パラメータの不確実性を考慮した最適化モデルの一つとして、ロバスト最適化モデルが提案されている（例えば、非特許文献１を参照）。ロバスト最適化モデルは、パラメータに対して所定の不確実性の範囲（例えば、パラメータ空間における楕円領域）を設定する。そして、ロバスト最適化モデルにおける最適解を算出する情報処理装置は、その不確実性の範囲における最適解を算出する。【００２５】
最適解が適用される時のパラメータの値が想定されたパラメータの不確実性の範囲内の場合、ロバスト最適化モデルを用いて算出された最適解は、適応時における解の良さを保証できる。上記の線形最適化モデルにロバスト最適化モデルを適用した最適化モデルは、ロバスト線形最適化モデルと呼ばれている。また、二次最適化モデルにロバスト最適化モデルを適用した最適化モデルは、ロバスト二次最適化モデルと呼ばれている。
【先行技術文献】
【非特許文献】
【００２６】
【非特許文献１】Dimitris Bertsimas, David B. Brown, and Constantine Caramanis, "Theory and Application of Robust Optimization", SIAM (Society for Industrial and Applied Mathematics) Review, Vol. 53, No. 3, pp. 464-501, August 05, 2011
【発明の概要】
【発明が解決しようとする課題】
【００２７】
上記パラメータの不確実性は、二種類想定される。一つは、最適化の入力に含まれるノイズである「予測誤差」である。もう一つは、最適化が終了した後に想定されるノイズである「システム誤差」である。「システム誤差」は、系自体が持つ不確実性を示す。「予測誤差」は、その系を過去データから推定（表現）しようとしたときに、過去データがシステム誤差から影響を受けていることに起因して推定自体に生じるブレを示す。【００２８】
ロバスト最適化では、どの程度の不確実性を想定するか決定する必要がある。以下、この不確実性の程度をマージンと記す。マージンは、要求する保証水準（例えば、欠品確率１０％など）に対して、過不足がない程度に設定される必要がある。想定する不確実性が小さすぎると保証を満たすことが出来なくなり、一方で、水準より大きすぎる不確実性を想定すると、コストが莫大になってしまうからである。つまり、過剰に保守的な戦略は、保証を満たさない戦略と同等に非現実的である。また、この水準は、データから自動で決定できることが望ましい。【００２９】
一般的には、パラメータの「推定の不確実性」に基づいて、この水準（マージン）が自動で決定される。具体的には、不確実性領域Ｕに対して保証水準αで含まれるパラメータを想定し、その不確実性領域Ｕにおける最悪ケースを想定してロバスト最適化を行う方法が知られている。【００３０】
しかし、このように決定された不確実性領域Ｕのサイズ（円における半径に相当する量）は、パラメータの次元が上がるにつれて増加する。これは、より多くのパラメータの不確実性を保証するために、各パラメータに対して想定する不確実性（≒半径）を増加させる必要があるからである。しかし、このような不確実性領域Ｕを用いたロバスト最適化は、過剰に保守的になることが経験的に知られている。【００３１】
このような過剰に保守的になる典型例を説明する。推定パラメータにダミーのパラメータ（すなわち、最適化には全く関係のないパラメータ）が含まれていたとする。このとき、上述する保証を想定すると、ダミーのパラメータを含めた次元に基づいて不確実性領域Ｕのサイズが決定される。ダミーのパラメータは本来不要なものであるにも関わらず、これによるサイズの増加分だけ過剰な保証が要求されてしまうという問題がある。【００３２】
そこで、本発明は、不確実性を有する最適化のパラメータが予測に基づいて与えられる場合に、過剰な保証を抑制して最適解を算出できる最適化装置、最適化方法および最適化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３３】
本発明による最適化装置は、予測対象の説明に用いられる説明変数が最適化の操作変数になり、その予測対象の予測に基づいて最適化を行う最適化装置であって、予測される操作変数の候補の集合を決定する候補集合決定部と、集合に含まれる操作変数に対して、指定された確率で予測による誤差である推定誤差が含まれるマージンを決定するマージン決定部と、決定されたマージンを用いて、操作変数に関するロバスト最適化を行うロバスト最適化部とを備え、マージン決定部が、決定された集合に含まれるすべての操作変数の候補に対して、推定誤差を含むマージン付き制約式が真の制約式の上界になるマージンを決定することを特徴とする。
【００３４】
本発明による最適化方法は、予測対象の説明に用いられる説明変数が最適化の操作変数になり、その予測対象の予測に基づいて最適化を行う最適化方法であって、コンピュータが、予測される操作変数の候補の集合を決定し、コンピュータが、集合に含まれる操作変数に対して、指定された確率で予測による誤差である推定誤差が含まれるマージンを決定し、コンピュータが、決定されたマージンを用いて、操作変数に関するロバスト最適化を行い、マージンを決定する際、コンピュータが、決定された集合に含まれるすべての操作変数の候補に対して、推定誤差を含むマージン付き制約式が真の制約式の上界になるマージンを決定することを特徴とする。
【００３５】
本発明による最適化プログラムは、予測対象の説明に用いられる説明変数が最適化の操作変数になり、その予測対象の予測に基づいて最適化を行うコンピュータに適用される最適化プログラムであって、コンピュータに、予測される操作変数の候補の集合を決定する候補集合決定処理、集合に含まれる操作変数に対して、指定された確率で予測による誤差である推定誤差が含まれるマージンを決定するマージン決定処理、および、決定されたマージンを用いて、操作変数に関するロバスト最適化を行うロバスト最適化処理を実行させ、マージン決定処理で、決定された集合に含まれるすべての操作変数の候補に対して、推定誤差を含むマージン付き制約式が真の制約式の上界になるマージンを決定させることを特徴とする。
【発明の効果】
【００３６】
本発明によれば、不確実性を有する最適化のパラメータが予測に基づいて与えられる場合に、過剰な保証を抑制して最適解を算出できる。
【図面の簡単な説明】
【００３７】
【図１】本発明による最適化装置の一実施形態を示すブロック図である。
【図２】最適化装置の動作例を示すフローチャートである。
【図３】本発明による最適化装置の概要を示すブロック図である。
【図４】少なくとも１つの実施形態に係るコンピュータの構成を示す概略ブロック図である。
【発明を実施するための形態】
【００３８】
まず、本発明で想定する問題設定を具体例を用いて説明する。
Ｘは操作変数のドメインであり、ｍ次元ベクトル空間の部分集合であるとする。また、Ｘの要素をｘと表わす。このとき、パラメータの実現値θに対する最適化モデルは、以下に例示する式１のように定義される。
【００３９】
ｍｉｎ ｆ０（ｘ）
s.t.  ｆｋ（ｘ，θ）≦０    （式１）
【００４０】
式１において、θは、未来の実現パラメータである。また、ｆｋは、θに関して線形であるとする。例えば、ポートフォリオの最適化問題では、期待利得ｒを最大化することが求められる。そこで、ポートフォリオ最適化問題は、以下に例示する式２のように定義できる。
【００４１】
ｍａｘ  ｒ
s.t.  ｒ≦θＴｘ  ０≦Σｘ≦Ｃ    （式２）
【００４２】
式２において、θはベクトルであり、θのｉ番目の要素は、資産ｉに投資した結果得られる利得である。ｘｉは、資産ｉに投資する金額を表す。また、Ｃは、総資産額である。言い換えると、上記式２で示す問題は、限られた資産を配分し、投資効果を最大化する問題と言える。
【００４３】
また、例えば、在庫コストの最適化問題では、在庫コストを最小化することが求められる。そこで、在庫コスト最小化問題は、以下に例示する式３のように定義できる。
【００４４】
ｍｉｎ Σｃｉｘｉ
s.t.   ｘｉ≧θｉ    （式３）
【００４５】
式３において、ｃｉは商品ｉ１つあたりの在庫コスト、ｘｉは商品ｉの在庫量、θｉは、商品ｉの需要量である。
【００４６】
他にも、電力需要パラメータに基づく発電最適化、商品需要パラメータに基づくプラントの設計最適化など、多くの問題が、上述する式１〜３のように定式化される。
【００４７】
実際には、上述するθを戦略ｘの決定に用いることはできない。これは、θは、ｘを決定した未来に判明する値のためである。よって、θの平均的な値θ＊を予測し、その予測値としてθハット（θの上付き＾。以下θ＾と記す。）を取得する。このθ＾をもとに最適化を行う必要がある。以下、この処理について説明する。
【００４８】
まず、未来の値θは、θ〜θ＊−θｓにより決定されると仮定する。ここで、θｓはシステム誤差を示す確率変数であり、その平均を０とする。上述するように、システム誤差は予測不可能な値である。
【００４９】
次に、過去のデータを用いて予測エンジンに基づきθ＊を推定する。推定値θ＾は、不変推定量の場合、θ＾〜θ＊−θｅと記述できる。ここで、θｅは、推定誤差を示す確率変数であり、その平均は０である。これは、過去のデータの統計的不確実性から、推定値θ＾も、推定誤差θｅが含まれた不確実な値になることを示している。
【００５０】
予測最適化のプロセスは、以下の３ステップで行われる。
ステップ１：θ＾の実現値θチルダ（θの上付き〜。以下θ〜と記す。）を取得する。θ〜は、推定値ということが出来る。
ステップ２：θ〜をもとに最適化を行う。
ステップ３：θの実現値をもとに利得を算出する。
【００５１】
なお、ステップ１におけるθ＾は推定値を表す確率変数であり、現実ではその実現値の１つのみが取得される。
【００５２】
ここで、ステップ２において、真の値θ＊も未来のθの実現値も知り得ない。しかし、「θ〜がどれだけθ＊から離れているか」を得ることは出来なくても、「θ〜がどれだけθ＊から離れやすいか」を得ることは可能である。例えば、θ＾の分散共分散行列を推定したり、ブートストラップサンプルによってθｓおよびθｅのサンプルを近似的に得ることによって、「θ〜がどれだけθ＊から離れやすいか」を得ることが可能である。
【００５３】
一方、ステップ２において、以下に例示する式４のように、θを単に推定値で置き換えて最適化を行うと、高確率で制約を満たさなくなってしまう。なお、Ｋは、制約条件式のインデックスである。
【００５４】
ｍｉｎ ｆ０（ｘ）
s.t.  ｆｋ（ｘ，θ〜）≦０，  ｋ＝１，２，…，Ｋ    （式４）
【００５５】
そのため、適切なマージンｇｋ（ｘ）≧０を設定し、以下に例示する式５のような最適化を行う必要がある。
【００５６】
ｍｉｎ ｆ０（ｘ）
s.t.  ｆｋ（ｘ，θ〜）＋ｇｋ（ｘ）≦０，  ｋ＝１，２，…，Ｋ    （式５）
【００５７】
このような最適化方法がロバスト最適化と呼ばれる。マージンｇｋ（ｘ）を設定する方法として、保証水準αが与えられたとき、領域Ｕを、以下に例示する式６を満たすように設定する。
【００５８】
Ｐｒｏｂ（θｓ＋θｅ∈Ｕ）≧α  （式６）
【００５９】
このとき、ｇｋを以下に例示する式７のように定義すると、このマージンｇｋ（ｘ）に対して得られる解は、確率α以上で未来の実現値θに対する制約を満たす。
【００６０】
ｇｋ（ｘ）＝ｍａｘ｛ｕ∈Ｕ｝ｆ（ｘ，ｕ）  （式７）
【００６１】
しかし、このように設定された領域Ｕは、例えばダミーの推定パラメータが増加すると、その大きさも増大するため、ｇｋの値も増加する。その結果、過剰保証された戦略が選択されてしまう。このように定めたｇｋは、確率αでいかなる戦略ｘに対しても、マージン込みの制約値が真の実現値以上になるからである。すなわち、以下に例示する式８を満たすようにするためである。
【００６２】
∀ｘ∈Ｘ，  ｆ（ｘ，θ）≦ｆｋ（ｘ，θ〜）＋ｇｋ（ｘ）  （式８）
【００６３】
しかし、実際には全てのｘに対して、上述する式８における不等式が成立する必要はなく、解の候補になるようなｘに対して成立すれば十分であることを本願発明者は発見した。具体的には、発明者は、上述するダミーのパラメータの例から、パラメータの「本質的な次元」を測り、それに応じた不確実性を想定する必要があることを発見した。
【００６４】
そこで、本発明では、この本質的な次元を、最適化ドメインの大きさ、つまり「最適化の不確実性」を測ることにより測定する。すなわち、「推定の不確実性」に加えて「最適化の不確実性」を測ることで、過不足のない不確実性水準に基づく最適化を行うことが可能になる。
【００６５】
以下、本発明の実施形態を図面を参照して説明する。
【００６６】
図１は、本発明による最適化装置の一実施形態を示すブロック図である。本実施形態の最適化装置１００は、予測対象の説明に用いられる説明変数が最適化の操作変数になり、その予測対象の予測に基づいて最適化を行う。
【００６７】
本実施形態の最適化装置１００は、入力部１０と、候補集合決定部２０と、マージン決定部３０と、ロバスト最適化部４０と、出力部５０と、記憶部６０とを備えている。
【００６８】
記憶部６０は、例えば、磁気ディスク等により実現され、入力された情報や処理途中の情報、処理結果の情報などを記憶する。また、記憶部６０は、後述するマージン決定部３０がマージンを決定する際に利用するマージンの候補とする集合を記憶する。
【００６９】
入力部１０は、候補集合決定部２０、マージン決定部３０およびロバスト最適化部４０が後述処理で用いる情報を入力する。具体的には、入力部１０は、予測に用いる予測式（予測モデル）および推定誤差を入力する。入力部１０は、例えば、予測モデルを表すパラメータを予測パラメータとして入力してもよい。また、入力部１０は、推定誤差として、例えば、分散共分散行列Σで表される予測誤差部分布を入力してもよい。また、入力部１０は、保証確率αを入力する。保証確率αは、例えば、ユーザにより指定されて入力される。
【００７０】
候補集合決定部２０は、操作変数の候補の集合（以下、ドメインと記すこともある。）を決定する。候補集合決定部２０がドメインを決定する方法は任意である。候補集合決定部２０は、例えば、推定誤差θｅの不確実性により、解に相当する操作変数ｘの集合Ｘを決定してもよい。また、候補集合決定部２０は、例えば、不確実性を含まない制約のみを抽出することにより集合Ｘを決定してもよい。不確実性を含まない制約は、不確実なパラメータを含まないため、不確実性を含む制約と区別可能である。
【００７１】
例えば、価格の最適化問題の場合、「価格は定価から５割引までの間であること」という制約は、不確実性を含まない制約である。また、例えば、在庫の最適化問題の場合、「在庫量は非負であること」および「在庫投資額は予算以内であること」という制約は、不確実性を含まない制約である。一方、「在庫量は需要を高確率で上回ること」という制約は、需要が不確実性を含むことから、不確実性を含む制約である。
【００７２】
候補集合決定部２０が集合Ｘを決定する具体例を説明する。例えば、θｓ＋θｅをサンプリングし、θ〜＋θｓ＋θｅを未来の実現値の候補とする。このとき、候補集合決定部２０は、以下に例示する式９を繰り返し解くことにより、集合Ｘを有限サンプルで近似してもよい。
【００７３】
ｍｉｎ ｆ０（ｘ）
s.t.  ｆｋ（ｘ，θ〜＋θｓ＋θｅ）≦０，  ｋ＝１，２，…，Ｋ    （式９）
【００７４】
他にも、例えば、Ｐｒｏｂ（θｓ＋θｅ∈Ｔ）≧１−δを満たす領域Ｔを定義する。なお、１−δは確率基準であり、集合Ｘの範囲を制限した場合に真の最適解を含む確率である。δは、例えば、ユーザにより指定される。このとき、候補集合決定部２０は、領域Ｔを複数サンプルで近似し、そのサンプルｔに対して、以下に例示する式１０を解くことにより、集合Ｘを近似してもよい。
【００７５】
ｍｉｎ ｆ０（ｘ）
s.t.  ｆｋ（ｘ，θ〜＋ｔ）≦０，  ｋ＝１，２，…，Ｋ    （式１０）
【００７６】
マージン決定部３０は、候補集合決定部２０によって決定された集合に含まれる操作変数に対して、指定された確率αで推定誤差が含まれるマージンを決定する。具体的には、マージン決定部３０は、決定された集合に含まれるすべての操作変数の候補（解の候補）ｘに対して、推定誤差を含むマージン付き制約式が真の制約式の上界になるマージンを計算する。ここで、真の制約式をｆｋ（ｘ，θ〜）とし、マージンをｇｋ（ｘ）とすると、マージン付き制約式は、ｆｋ（ｘ，θ〜＋θｅ）＋ｇｋ（ｘ）と表わすことができる。これは、ｆの線形性から、ｆｋ（ｘ，−θｅ）＋ｇｋ（ｘ）≧０と等価である。よって、システム誤差を想定しない場合、マージン決定部３０は、以下に例示する式１１を満たす最小のマージンｇを求めればよい。
【００７７】
【数１】
0006947229.tif 000002
【００７８】
なお、本実施形態では、マージンの候補集合Ｇｒ＝（ｇ｛１，ｒ｝，…，ｇ｛Ｋ，ｒ｝）を定義しておく。マージンの候補集合Ｇｒは、例えば、１次元のパラメータｒ≧０でパラメータ化されたマージンの候補を含む。例えば、不確実な制約が一つの場合、Ｇｒは、一つの関数を含むことになる。このとき、ある非負の関数ｇ（ｘ）に基づいて、Ｇｒ＝（ｒｇ（ｘ））と定義した場合、これは、マージンになる。一般に、不確実な制約がＫ個存在するとき、各制約に関する「単位マージン」ｇ１，ｇ２，…，ｇＫに基づいて、マージンを、Ｇｒ＝（ｒｇ１，ｒｇ２，…，ｒｇＫ）と定義すればよい。マージン決定部３０は、決定された集合に含まれるすべての説明変数の候補ｘに対して、確率αで推定誤差が含まれたマージン付制約式が、真の制約式よりも厳しくなるような、最小のマージンＧ｛ｒ＊｝を決定すればよい。
【００７９】
また、マージン決定部３０は、マージンを決定する際、上記確率基準（集合の範囲を制限した場合に真の最適解を含む確率）を考慮してもよい。すなわち、候補集合決定部２０が１−δの確率基準により解の候補の集合Ｘを制限した場合、マージン決定部３０は、確率αをα＋δに置き換えてマージンを決定してもよい。
【００８０】
具体的には、θｅはサンプル出来るため、マージン決定部３０は、θ｛ｅ，ｉ｝，ｉ＝１，…，Ｉに対し、そのうちαＳサンプルが、以下に例示する式１２を満たすような最小のｒを求めればよい。より具体的には、Ｓが整数であり、αが０から１の実数であるため、マージン決定部３０は、αＳを切り上げた数のサンプルが、以下に例示する式１２を満たすような最小のｒを求めればよい。
【００８１】
ｍｉｎ｛ｘ∈Ｘ｝  ｆｋ（ｘ，−θ｛ｅ，ｉ｝）＋ｇ｛ｋ，ｒ｝（ｘ）≧０  ｋ＝１，２，…，Ｋ
（式１２）
【００８２】
各ｒに対して、Ｘが有限個の点により近似されているため、上記式１２は、関数ｆおよび関数ｇの計算のみで判定が可能である。
【００８３】
さらに、システム誤差θＳを考慮する場合、上記式１１は、以下に例示する式１３に置き換えることが可能である。
【００８４】
【数２】
0006947229.tif 000003
【００８５】
式１３において、−θｓに関する確率Ｐｒｏｂ｛θｓ｝は、θｓの有限サンプルをとることにより近似でき、確率積分∫ｄθｅも同様にサンプルにより近似できる。そのため、各ｒに関して上記式１３が成立するか否か判定することが可能である。マージン決定部３０は、例えば、２分探索により条件を満たす最小のｒ（最小のマージン）を決定してもよい。
【００８６】
ロバスト最適化部４０は、決定されたマージンを用いて、操作変数に関するロバスト最適化を行う。すなわち、ロバスト最適化部４０は、決定されたマージンｇを用いて、上記マージン付最適化問題を解くことにより、ロバスト最適化を行う。
【００８７】
ロバスト最適化部４０がロバスト最適化を行う方法は任意である。ロバスト最適化部４０は、一般的に知られた方法を用いてロバスト最適化を行ってもよい。ロバスト最適化を行う方法は広く知られているため、ここでは詳細な説明は省略する。
【００８８】
なお、想定した候補である集合Ｘが最適解を含むことを想定しているが、本実施形態の場合、得られた解が集合Ｘに含まれない場合もある。このとき、ロバスト最適化部４０は、集合Ｘの中で、得られた解に最も近い値に最適解を近似してもよい。また、ロバスト最適化部４０は、追加のマージンを再度設定して最適化を行うことにより最適解を補正してもよい。なお、ロバスト最適化部４０は、修正を行うことなく得られた解を最適解として採用してもよい。
【００８９】
候補集合決定部２０と、マージン決定部３０と、ロバスト最適化部４０とは、プログラム（最適化プログラム）に従って動作するコンピュータのプロセッサ（例えば、ＣＰＵ（Central Processing Unit ）、ＧＰＵ（Graphics Processing Unit）、ＦＰＧＡ（field-programmable gate array ））によって実現される。
【００９０】
例えば、プログラムは、記憶部（図示せず）に記憶され、プロセッサは、そのプログラムを読み込み、プログラムに従って、候補集合決定部２０、マージン決定部３０およびロバスト最適化部４０として動作してもよい。また、最適化装置の機能がＳａａＳ（Software as a Service ）形式で提供されてもよい。
【００９１】
候補集合決定部２０と、マージン決定部３０と、ロバスト最適化部４０とは、それぞれが専用のハードウェアで実現されていてもよい。また、各装置の各構成要素の一部又は全部は、汎用または専用の回路（circuitry ）、プロセッサ等やこれらの組合せによって実現されもよい。これらは、単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。各装置の各構成要素の一部又は全部は、上述した回路等とプログラムとの組合せによって実現されてもよい。
【００９２】
また、最適化装置の各構成要素の一部又は全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は、集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【００９３】
次に、本実施形態の最適化装置の動作を説明する。図２は、本実施形態の最適化装置の動作例を示すフローチャートである。
【００９４】
候補集合決定部２０は、操作変数の候補の集合Ｘを決定する（ステップＳ１１）。マージン決定部３０は、集合Ｘに含まれる操作変数に対して、指定された確率αで推定誤差が含まれるマージンを決定する（ステップＳ１２）。そして、ロバスト最適化部４０は、決定されたマージンを用いて、操作変数に関するロバスト最適化を行う（ステップＳ１３）。
【００９５】
以上のように、本実施形態では、候補集合決定部２０が、操作変数の候補集合を決定し、マージン決定部３０が、集合に含まれる操作変数に対して、指定された確率で推定誤差が含まれるマージンを決定する。そして、ロバスト最適化部４０が、決定されたマージンを用いて、操作変数に関するロバスト最適化を行う。そのため、不確実性を有する最適化のパラメータが予測に基づいて与えられる場合に、過剰な保証を抑制して最適解を算出できる。
【００９６】
このように、本実施形態の最適化装置は、要求する保証水準を満たすようなロバスト最適化をする際の計算コストを低減させることができる。言い換えると、本実施形態の最適化装置により、コンピュータによるロバスト最適化の計算コストを大きく抑制することが可能になる。
【００９７】
次に、本実施形態の最適化問題を、在庫の最適化問題を例に説明する。ここでは、以下の式１４に例示する１００商品の在庫最適化問題を想定する。需要量は、正規分布により生成されていると想定し、θ＊＝１０、θｓ，ｉ〜Ｎ（０，２）とする。
【００９８】
ｍｉｎ Σｃｉｘｉ
s.t.   ｘｉ≧θｉ  ｉ＝１，２，…，１００  （式１４）
【００９９】
説明を簡素化するため、非整数の需要および負の需要を許容するとする。ただし、本例において、θｉが負になる確率は十分に低い。また、ここでは、過去４日間のデータをもとに需要を予測する。このとき、正規性の仮定のもと、推定値は、θｅ，ｉ〜Ｎ（１０，１）に従う。
【０１００】
まず、あらゆる商品で欠品が起こらない確率が９０％になるようなマージンを考える。例えば、一般的な方法によりマージンを決定する場合、θｅ，ｉ＋θｓ，ｉ〜Ｎ（０，３）であるため、ｇｉ（ｘ）＝√３、χ−１１００（０．９）≒１８．９になる。つまり、在庫を推定値より１８．９多く備える必要があると算出される。なお、χ１００は、自由度１００のカイ２乗分布の分布関数である。
【０１０１】
２〜１００番目の商品を、固定的に１００個生産するとする。このとき、２〜１００番目の商品は、制約がほぼ確実に守られるため、実質的には１番目の在庫を保証するマージンを考慮すればよい。つまり、推定パラメータは１００個存在するが、この想定では実質的に１次元の問題である。
【０１０２】
上述するステップ１に対応する集合Ｘが、Ｘ＝｛ｘ１≧０，ｘ２＝ｘ３＝…＝ｘ１００＝１００｝で与えられる状況に対応する。このとき、上述するステップ２において、以下に例示する式１５が満たされる。
【０１０３】
【数３】
0006947229.tif 000004
【０１０４】
したがって、ｇ１（ｘ）＝√３  Φ−１（０．９）≒２．２になる。すなわち、本実施形態の算出方法によれば、マージンは２．２と算出される。なお、一般的な方法では、最適化の不確実性を考慮しないため、固定値が与えられたとしても同じマージン（１８．９）と算出されてしまう。
【０１０５】
ロバスト最適化部４０は、推定値θ＾およびマージン２．２を加えて上述するステップ３の処理（ロバスト最適化）を行えばよい。
【０１０６】
上述する例では、説明を簡略化するため、実質的なドメインＸを決定する根拠を明示せずに説明した。次に、推定値に基づいてドメインＸを決定する具体例を説明する。具体例として、ポートフォリオ最適化を挙げ、次元は１００であるとする。
【０１０７】
ここで、推定される期待利得において、１〜３番目の商品の利得がその他の商品の利得に比べて非常に大きいとする。このとき、実質的なドメインＸは、Ｘ＝｛ｘ≧０｜ｘ４＝ｘ５＝…＝ｘ１００＝０｝であると考えられる。誤差θｓおよび誤差θｅをサンプルして得られた推定値に含めて最適化を繰り返すことで、Ｘを近似するサンプルが得られる。このような方法でも、ドメインＸを自動的に決定することが可能である。
【０１０８】
次に、本発明の概要を説明する。図３は、本発明による最適化装置の概要を示すブロック図である。本発明による最適化装置は、予測対象（例えば、利得）の説明に用いられる説明変数（例えば、戦略ｘ）が最適化の操作変数になり、その予測対象の予測に基づいて最適化を行う最適化装置８０（例えば、最適化装置１００）であって、予測される操作変数の候補の集合（例えば、ドメイン）を決定する候補集合決定部８１（例えば、候補集合決定部２０）と、集合に含まれる操作変数に対して、指定された確率（例えば、保証確率α）で予測による誤差である推定誤差（例えば、θｅ）が含まれるマージン（例えば、ｇ）を決定するマージン決定部８２（例えば、マージン決定部３０）と、決定されたマージンを用いて、操作変数に関するロバスト最適化を行うロバスト最適化部８３（例えば、ロバスト最適化部４０）とを備えている。
【０１０９】
そのような構成により、不確実性を有する最適化のパラメータが予測に基づいて与えられる場合に、過剰な保証を抑制して最適解を算出できる。
【０１１０】
また、候補集合決定部８１は、予測値からの誤差（例えば、システム誤差、推定誤差）の範囲に含まれるサンプルで候補の集合を近似してもよい。
【０１１１】
また、マージン決定部８２は、決定された集合に含まれるすべての操作変数の候補に対して、推定誤差を含むマージン付き制約式が真の制約式の上界になるマージンを決定してもよい。
【０１１２】
また、マージン決定部８２は、マージンの候補集合の中から、決定された集合に含まれるすべての説明変数の候補に対して、指定された確率で推定誤差が含まれたマージン付制約式が、真の制約式よりも厳しくなる、最小のマージンを決定してもよい。
【０１１３】
具体的には、マージンの候補集合は、１次元のパラメータで表されるマージンの候補を含んでいてもよい。
【０１１４】
また、候補集合決定部８１は、最適化による誤差を示すシステム誤差および推定誤差の範囲に含まれるサンプルで候補の集合を近似し、マージン決定部８２は、指定された確率でシステム誤差および推定誤差が含まれるマージンを決定してもよい。
【０１１５】
図４は、少なくとも１つの実施形態に係るコンピュータの構成を示す概略ブロック図である。コンピュータ１０００は、ＣＰＵ１００１、主記憶装置１００２、補助記憶装置１００３、インタフェース１００４を備える。
【０１１６】
上述の最適化装置は、コンピュータ１０００に実装される。そして、上述した各処理部の動作は、プログラム（最適化プログラム）の形式で補助記憶装置１００３に記憶されている。ＣＰＵ１００１は、プログラムを補助記憶装置１００３から読み出して主記憶装置１００２に展開し、当該プログラムに従って上記処理を実行する。
【０１１７】
なお、少なくとも１つの実施形態において、補助記憶装置１００３は、一時的でない有形の媒体の一例である。一時的でない有形の媒体の他の例としては、インタフェース１００４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等が挙げられる。また、このプログラムが通信回線によってコンピュータ１０００に配信される場合、配信を受けたコンピュータ１０００が当該プログラムを主記憶装置１００２に展開し、上記処理を実行しても良い。
【０１１８】
また、当該プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、当該プログラムは、前述した機能を補助記憶装置１００３に既に記憶されている他のプログラムとの組み合わせで実現するもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【符号の説明】
【０１１９】
１０  入力部
２０  候補集合決定部
３０  マージン決定部
４０  ロバスト最適化部
５０  出力部
１００  最適化装置
【図１】
0006947229.tif 000005
【図２】
0006947229.tif 000006
【図３】
0006947229.tif 000007
【図４】
0006947229.tif 000008