(57)【要約】  ドメイン制限部８１は、予測対象の予測に用いられる予測パラメータと、その予測の誤差分布とに基づいて、最適化の対象のドメインの範囲を制限する。不確実性領域形状決定部８２は、誤差分布に基づいて、ロバスト最適化における不確実性領域の形状を決定する。不確実性領域半径決定部８３は、不確実性領域の形状と制限されたドメインとから、指定された確率を保証する不確実性領域の半径を決定する。最適化部８４は、決定された半径の不確実性領域に基づいて、操作変数に関するロバスト最適化を行う。出力部８５は、ロバスト最適化による結果を出力する。
2018155319.tif 000002
【特許請求の範囲】
【請求項１】
予測対象の説明に用いられる説明変数が最適化の操作変数になり、当該予測対象の予測に基づいて前記最適化を行う最適化装置であって、
前記予測対象の予測に用いられる予測パラメータと、当該予測の誤差分布とに基づいて、前記最適化の対象のドメインを制限するドメイン制限部と、
前記誤差分布に基づいて、ロバスト最適化における不確実性領域の形状を決定する不確実性領域形状決定部と、
前記不確実性領域の形状と制限されたドメインとから、指定された確率を保証する前記不確実性領域の半径を決定する不確実性領域半径決定部と、
決定された半径の不確実性領域に基づいて、前記操作変数に関するロバスト最適化を行う最適化部と、
前記ロバスト最適化による結果を出力する出力部とを備えた
ことを特徴とする最適化装置。
【請求項２】
出力部は、最適化部が行うロバスト最適化を制限されたドメインの次元に適応した場合に得られる保証確率を出力する
請求項１記載の最適化装置。
【請求項３】
ドメイン制限部は、誤差分布の信頼領域を算出し、当該信頼領域に基づいて最適解となり得る解の集合にドメインを制限する
請求項１または請求項２記載の最適化装置。
【請求項４】
不確実性領域形状決定部は、不確実性領域の形状を、誤差分布を用いた順序集合で表す
請求項１から請求項３のうちのいずれか１項に記載の最適化装置。
【請求項５】
不確実性領域半径決定部は、誤差分布がＶの極錘と不確実性領域とのミンコフスキー和に属することが指定された確率以上になる最小の半径を算出する
請求項１から請求項４のうちのいずれか１項に記載の最適化装置。
【請求項６】
予測対象の説明に用いられる説明変数が最適化の操作変数になり、当該予測対象の予測に基づいて前記最適化を行う最適化方法であって、
前記予測対象の予測に用いられる予測パラメータと、当該予測の誤差分布とに基づいて、前記最適化の対象のドメインを制限し、
前記誤差分布に基づいて、ロバスト最適化における不確実性領域の形状を決定し、
前記不確実性領域の形状と制限されたドメインとから、指定された確率を保証する前記不確実性領域の半径を決定し、
決定された半径の不確実性領域に基づいて、前記操作変数に関するロバスト最適化を行い、
前記ロバスト最適化による結果を出力する
ことを特徴とする最適化方法。
【請求項７】
最適化部が行うロバスト最適化を制限されたドメインの次元に適応した場合に得られる保証確率を出力する
請求項６記載の最適化方法。
【請求項８】
予測対象の説明に用いられる説明変数が最適化の操作変数になり、当該予測対象の予測に基づいて前記最適化を行うコンピュータに適用される最適化プログラムであって、
前記コンピュータに、
前記予測対象の予測に用いられる予測パラメータと、当該予測の誤差分布とに基づいて、前記最適化の対象のドメインを制限するドメイン制限処理、
前記誤差分布に基づいて、ロバスト最適化における不確実性領域の形状を決定する不確実性領域形状決定処理、
前記不確実性領域の形状と制限されたドメインとから、指定された確率を保証する前記不確実性領域の半径を決定する不確実性領域半径決定処理、
決定された半径の不確実性領域に基づいて、前記操作変数に関するロバスト最適化を行う最適化処理、および、
前記ロバスト最適化による結果を出力する出力処理
を実行させるための最適化プログラム。
【請求項９】
コンピュータに、
出力処理で、最適化部が行うロバスト最適化を制限されたドメインの次元に適応した場合に得られる保証確率を出力させる
請求項８記載の最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予測に基づいて最適化を行う最適化装置、最適化方法および最適化プログラムに関する。
【背景技術】
【０００２】
近年、多くの情報を基に、所定の条件における最適な情報（例えば、プラントにおける材料の投入量、操作機器における操作量、又は、商品の設定価格）を利用者に提供する装置やシステムが用いられている。また、利用者が、最終的な選択を行うための情報（例えば、判断指標など）を提供する装置やシステムも用いられている。【０００３】
例えば、電力会社は、複数の発電所を含む発電システムの制御において、所定の条件（例えば、総需要電力を満足しながらコストを最小にする）を満足する各発電所の発電量を決定することが必要である。そこで、電力会社では、例えば、需要予測（総需要電力の予測）に基づく発電システムをモデル化した最適化モデルが作成される。そして、最適な発電量（最適解）を決定するために、所定の装置又はシステムを用いて、その最適化モデルにおける最適解（発電量）が算出される。【０００４】
他にも、企業の購入部門は、生産活動における資材の購入において、生産計画などを満足しながら利益を最大とする（購入コストを最小とする）資材の購入量（最適解）を決定することを必要とする。そこで、購入部門では、需要予測（例えば、必要となる資材の量の予測）に基づく購入量をモデル化した最適化モデルが作成される。そして、購入量を決定するため、所定の装置又はシステムを用いて、作成した最適化モデルにおける最適解（購入量）が算出される。【０００５】
このように、予測に基づいた判断又は計画をソフトウェア又は所定の装置が最適に行う技術について、以下、その具体例を説明する。【０００６】
まず、最適化の処理の対象となる最適化モデルが決定される。最適化モデルは、具体的な最適化の目的を示す「目的関数」と、最適解の算出における条件である「制約」とを含む。「目的関数」は、「操作変数」の関数として表される。「操作変数」は、最適化の対象である。最適化において、上記のソフトウェア又は装置は、制約を満たしつつ目的関数の値が最適（例えば、最大又は最小）となるように、「操作変数」の値を最適化する。最適化された目的変数の値を、以下、「最適解」と呼ぶ。なお、最適解は、将来的な値である。そのため、目的関数は、その中に、所定の変数及びパラメータを用いて表される予測モデルを含む。【０００７】
予測モデルは、予測対象である変数（以下、「被説明変数」と呼ぶ）と、予測対象に影響を及ぼし得る変数（以下、「説明変数」と呼ぶ）との関係性を示すモデルである。一般的に、被説明変数は、予測モデルにおいて、説明変数を用いた関数として表現される。【０００８】
上記のとおり、予測における予測対象である変数に対して、「被説明変数」という用語が用いられる。これに対し、最適化処理における最適化対象である変数に対して、「操作変数」という用語が用いられる。このように、以下の説明において、「被説明変数」という用語と、「操作変数」という用語とは、相互に区別して用いられる。【０００９】
なお、予測モデルは、例えば、過去の説明変数と被説明変数とを用いた機械学習等を基に作成される。予測モデルを生成する一般的な方法として、例えば、「回帰分析」がある。【００１０】
そして、情報処理装置は、最適化モデルの最適解として、目的関数を最適化（例えば、最大化）する目的変数の値（最適解）を算出する。ここで、予測モデルにおける説明変数の少なくとも一部が、最適化モデルにおける目的変数（最適化の対象である変数）となることがあり得る。この点については、後ほど価格最適化の具体例を用いて説明する。【００１１】
また、一般的に、目的変数は、取り得る値の範囲に制限がある。例えば、上記の発電所における発電量は、上限がある。例えば、このような制限が、「制約」の一例である。ただし、制約は、その他の条件を含んでもよい。そこで、情報処理装置は、例えば、所定の制約を満足する範囲で、目的関数の値が最大になるような最適解を算出する。このように、最適解を算出する情報処理装置が最適化の対象として用いる最適化モデルは、目的関数及び制約を含むモデルである。【００１２】
なお、最適化モデルは、情報処理装置において処理されるため、一般的には、上記の目的関数及び制約を、情報処理装置で取り扱い可能な形式（通常は、変数を用いて表現された数式）を用いて表される。そして、情報処理装置は、最適解として、最適化モデルに含まれる制約の下で、目的関数の値を最適値（最大値、又は、最小値）とする目的変数の値を算出する。【００１３】
最適化モデルに含まれる目的関数が、目的変数の一次関数を用いて表される場合、その最適化モデルは、「線形最適化モデル」と呼ばれる。また、最適化モデルに含まれる目的関数が、目的変数の二次関数を用いて表される場合、その最適化モデルは、「二次最適化モデル」と呼ばれる。【００１４】
ここで、具体例として、ある複数の商品又は役務（サービス）の総売上高を最適化するために、各商品又は各役務の価格をいくらに設定したらよいか、という価格最適化の最適化モデル説明する。ただし、以下では、一例として、商品を用いて説明する。【００１５】
総売上高は、各商品の価格と、商品の売上げ量（売上げ数）との積の総和である。つまり、総売上高は、「総売上高＝（各商品の価格×各商品の売上げ量）の合計」となる。【００１６】
ここで、商品の価格は、商品の販売者が、設定可能な値である。一方、売上げ量は、販売者が決定できない値であり、さらに、最適化処理を実行する時点から見て未来の値である。【００１７】
そこで、商品の売上げ量を予測するため、例えば、機械学習を用いて予測モデルが設定される。ここで、商品の売上げ量は、その商品の価格の影響を受けることは自明である。そのため、商品の売上げ量は、商品の売上げ量を予測する予測モデルにおいて、被説明変数である。また、商品の価格は、予測モデルにおいて、説明変数となる。つまり、被説明変数である商品の売上げ量は、予測モデルにおいて、商品の価格の関数として表される。つまり、総売上高（目的関数）は、「説明変数（商品の価格）」と「被説明変数（商品の価格に影響を受ける売上げ量）」との積となる。【００１８】
上記のとおり、被説明変数は、説明変数（商品の価格）の関数を用いて表される。このため、総売上高（目的関数）は、商品の価格（説明変数）の少なくとも二次の関数になる。【００１９】
ここで、商品の価格は、最適化モデルにおける目的変数である。つまり、総売上高（目的関数）は、目的変数（商品の価格）の少なくとも二次関数を用いて表される。そのため、上記のような商品の価格を操作して総売上高を最適化する場合、最適化モデルとして、二次最適化モデルが用いられている。なお、この場合、制約は、例えば、商品の在庫量である。【００２０】
上記の具体例から理解されるように、予測モデルにおける説明変数（商品の価格）が、最適化モデルにおける目的変数（商品の価格）、すなわち最適化対象である変数になり得ることに留意されたい。言い換えると、商品の価格という一つの変数が、学習処理及び予測処理においては説明変数として振る舞い、最適化処理においては目的変数として振る舞うことに留意されたい。【００２１】
最適化モデルは、最適化モデルを表す数式に、１つ又は複数のパラメータを含む。パラメータは、過去の観測データなどを基に決定される値である。しかし、観測データは、測定における誤差を含むデータである。また、最適化モデルの算出対象は、まだ確定していない将来における値（最適解）である。つまり、最適解は、過去のデータが生成された時とは異なる状況において算出される可能性がある。そのため、最適化モデルに含まれるパラメータは、不確実性を含む。【００２２】
一般的に広く用いられている最適化モデルにおける最適解を算出する手法は、パラメータにおける不確実性を考慮していない。そのため、一般的な最適化モデルを用いて算出された最適解は、実際に適用された場合において、最適とはならない可能性がある。以下、この理由を説明する。【００２３】
上記のとおり、最適化モデルは、パラメータを含む。そして、パラメータは、不確実性を含む。そのため、最適解の値が実際の適用される時におけるパラメータの値は、最適解の算出に用いたパラメータの値と異なっている場合がある。この場合、算出された最適解は、実際に適用されるときにおける最適解となっていない可能性がある。【００２４】
そこで、パラメータの不確実性を考慮した最適化モデルの一つとして、ロバスト最適化モデルが、提案されている（例えば、非特許文献１を参照）。ロバスト最適化モデルは、パラメータに対して所定の不確実性の範囲（例えば、パラメータ空間における楕円領域）を設定する。そして、ロバスト最適化モデルにおける最適解を算出する情報処理装置は、その不確実性の範囲における最適解を算出する。【００２５】
最適解が適用される時のパラメータの値が、想定されたパラメータの不確実性の範囲内の場合、ロバスト最適化モデルを用いて算出された最適解は、適応時における解の良さを保証できる。上記の線形最適化モデルにロバスト最適化モデルを適用した最適化モデルは、ロバスト線形最適化モデルと呼ばれている。また、二次最適化モデルにロバスト最適化モデルを適用した最適化モデルは、ロバスト二次最適化モデルと呼ばれている。
【先行技術文献】
【非特許文献】
【００２６】
【非特許文献１】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
【発明の概要】
【発明が解決しようとする課題】
【００２７】
上記パラメータの不確実性は、二種類想定される。一つは、最適化の入力に含まれるノイズである「予測誤差」である。もう一つは、最適化が終了した後に想定されるノイズである「システム誤差」である。「システム誤差」は、系自体が持つ不確実性を示す。「予測誤差」は、その系を過去データから推定（表現）しようとしたときに、過去データがシステム誤差から影響を受けていることに起因して推定自体に生じるブレを示す。【００２８】
以下、この二種類の誤差を電力需要予測の具体例を用いて説明する。“電力需要”と“電力需要に影響を与え得る各種要因”とについて、１００日分のデータが存在するとする。この１００日分のデータは、全て上述する電力需要と要因との間に成り立つ関係が同じであるとする。電力需要という系自体が「システム誤差」という不確実性を含んでいるため、「システム誤差」により各日における電力需要はばらついている。【００２９】
今、何らかの事情により、１００日分のデータのうち一度に観測（利用）可能なデータ数量が限られているとする。まず、１００日分のデータのうち、ランダムに選ばれたＮ日分のデータを観測できたとする。観測できたＮ日分のデータを訓練データとして電力需要を予測するためのモデル（以下、モデル１）を学習する。なお、Ｎ日分のデータは、モデルを学習するのに十分な数量のデータであるとする。【００３０】
また、１００日分のデータのうち、別のＮ日分のデータを観測できたとする。これを訓練データとして電力需要を予測するためのモデル（以下、モデル２）を学習する。モデル１とモデル２は、利用できるデータの量は同じであるため、潜在的な推定精度が同じとみなすことができる。しかし、モデル１とモデル２の学習には、別の日のデータが用いられているため、モデル１とモデル２の予測式の推定パラメータは異なる。この違いは、データの有限性に起因する。この違いが推定誤差である。より一般的には、このＮ日分のデータを選択するという動作とそれに伴う推定を繰り返したときに生じる推定パラメータのバラつきの分布が、予測誤差の分布である。【００３１】
また、上述する二種類の誤差の内容を、売上数予測に基づく販売価格の最適化問題を用いて説明する。売上数データは、価格の関数にシステム誤差を含む真のモデルにより生成されていると仮定できる。この真のモデルが得られた場合には、価格を最適化することで平均的な利得を最大化することができる。しかし、このように最適化された価格を戦略として用いたとしても、日々の売上数はシステム誤差によって変動するものである。このような真のモデルが得られているとの仮定のもと、変動によるリスクをロバスト最適化法により、好みに応じて小さくできることは知られている。【００３２】
ただし、一般には真のモデルを得ることができないため、真のモデルは、予測モデルを用いて置き換えられる。予測モデルは確率的に生成されたデータに基づき求められることから、予測モデル自体、確率的に生成されていると考えることができる。このとき、予測モデルに基づく最適戦略も、確率的に変動するものとなる。最適化手法として非ロバスト最適化を用いた場合、この変動する最適戦略で算出される真の利得の予測モデルにおける変動の平均は、変動する最適戦略において予測された利得より非常に大きくなり、一般的に差を抑えることができないことが知られている。【００３３】
最適化の入力に誤差が含まれる場合の最適化法としてロバスト最適化法が知られている。ロバスト最適化法は、パラメータの不確実性領域を入力として受け取り、これによって解の信頼性を決定する。不確実性領域を決定する手法には、大まかに以下の二通りの方法が考えられる。第一の方法は、最適化機の使用者が、専門知識に基づき天下り式に決定する方法である。第二の方法は、不確実なパラメータの信頼領域を決定する方法である。【００３４】
第一の方法を用いた場合、解は使用者の経験に大きく依存するため、客観的な観点、例えば９９％の保証、などを与えることができない。また、予測や最適化が高次元データに対して行われる場合に、人手でこれを定義するのは困難である。第二の方法を用いた場合、保証を与えること自体は可能である。しかし、信頼領域の大きさは不確実性パラメータの次元に応じて増加してしまうため、高次元の最適化問題を扱う場合には、過剰に保守的な解を算出してしまうという問題がある。【００３５】
このような状況を鑑みると、実用的な範囲において、予測誤差に基づく最適解に確率的な保証を与えられることが望ましい。【００３６】
そこで、本発明は、不確実性を有する最適化のパラメータが予測に基づいて与えられる場合に、指定された確率を保証する最適解を算出できる最適化装置、最適化方法および最適化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３７】
本発明による最適化装置は、予測対象の説明に用いられる説明変数が最適化の操作変数になり、その予測対象の予測に基づいて最適化を行う最適化装置であって、予測対象の予測に用いられる予測パラメータと、その予測の誤差分布とに基づいて、最適化の対象のドメインを制限するドメイン制限部と、誤差分布に基づいて、ロバスト最適化における不確実性領域の形状を決定する不確実性領域形状決定部と、不確実性領域の形状と制限されたドメインとから、指定された確率を保証する不確実性領域の半径を決定する不確実性領域半径決定部と、決定された半径の不確実性領域に基づいて、操作変数に関するロバスト最適化を行う最適化部と、ロバスト最適化による結果を出力する出力部とを備えたことを特徴とする。【００３８】
本発明による最適化方法は、予測対象の説明に用いられる説明変数が最適化の操作変数になり、その予測対象の予測に基づいて最適化を行う最適化方法であって、予測対象の予測に用いられる予測パラメータと、その予測の誤差分布とに基づいて、最適化の対象のドメインを制限し、誤差分布に基づいて、ロバスト最適化における不確実性領域の形状を決定し、不確実性領域の形状と制限されたドメインとから、指定された確率を保証する不確実性領域の半径を決定し、決定された半径の不確実性領域に基づいて、操作変数に関するロバスト最適化を行い、ロバスト最適化による結果を出力することを特徴とする。【００３９】
本発明による最適化プログラムは、予測対象の説明に用いられる説明変数が最適化の操作変数になり、その予測対象の予測に基づいて最適化を行うコンピュータに適用される最適化プログラムであって、コンピュータに、予測対象の予測に用いられる予測パラメータと、その予測の誤差分布とに基づいて、最適化の対象のドメインを制限するドメイン制限処理、誤差分布に基づいて、ロバスト最適化における不確実性領域の形状を決定する不確実性領域形状決定処理、不確実性領域の形状と制限されたドメインとから、指定された確率を保証する不確実性領域の半径を決定する不確実性領域半径決定処理、決定された半径の不確実性領域に基づいて、操作変数に関するロバスト最適化を行う最適化処理、および、ロバスト最適化による結果を出力する出力処理を実行させることを特徴とする。
【発明の効果】
【００４０】
本発明によれば、不確実性を有する最適化のパラメータが予測に基づいて与えられる場合に、指定された確率を保証する最適解を算出できる。
【図面の簡単な説明】
【００４１】
【図１】本発明による最適化装置の一実施形態を示すブロック図である。
【図２】最適化装置によるデータの流れの例を示す説明図である。
【図３】最適化装置の動作例を示すフローチャートである。
【図４】本発明による最適化装置の概要を示すブロック図である。
【図５】少なくとも１つの実施形態に係るコンピュータの構成を示す概略ブロック図である。
【発明を実施するための形態】
【００４２】
まず、本発明で想定する問題設定を具体例を用いて説明する。
Ｘは操作変数のドメインであり、ｍ次元ベクトル空間の部分集合であるとする。また、Ｘの要素をｘと表わす。また、ｖは、ｍ次元ベクトル空間からｎ次元ベクトル空間への写像である。このとき、真の最適化モデルは、真のパラメータθ＊を用いて、以下の式１のように定義される。
【００４３】
【数１】
2018155319.tif 000003
【００４４】
ここで、真のパラメータを得ることができず、その推定値θ’のみが得られるという状況を考える。ただし、θ’は真のパラメータθ＊にノイズを加えたものであり、以下に示す式２が成り立つものとする。式２においてεに従う誤差分布は得られるものとする。
【００４５】
【数２】
2018155319.tif 000004
【００４６】
このとき、ドメイン、パラメータθ’および誤差分布の情報を用いて、指定された確率αの保証つき解を最適化により得ることが目標である。
【００４７】
具体例として、ポートフォリオの最適化問題（具体的には、予算ｃをｎ個のオプションに配分し、利得を最大化する問題）を考える。このとき、最適化のドメインは、オプションｉへの投資額をｘｉとした場合、以下に示す式３のように表すことができる。
【００４８】
【数３】
2018155319.tif 000005
【００４９】
θ＊を真の平均利得であるとし、この真のパラメータが知られている場合、平均利得を最大化する最適化問題は以下に示す式４で表すことができる。このときの最適解は、平均利得の高い上位ｃ個のオプションに、予算１を配分するものになる。
【００５０】
【数４】
2018155319.tif 000006
【００５１】
一方、真の平均利得が分からない場合、平均利得を過去のデータから推定する必要がある。ここでは、ｄ日間にわたるデータθ１，…，θｄが以下の式５に基づいて独立に生成されているとする。式５において、Ｎ（０，Σ）は、平均０、分散共分散行列Σの正規分布を表す。
【００５２】
【数５】
2018155319.tif 000007
【００５３】
推定θ’を平均を用いて以下に示す式６のように定義する。このとき、θ’自体も、以下の式７に示す正規分布に従う。分散共分散行列Σが推定により得られれば、誤差分布を得ることができる。
【００５４】
【数６】
2018155319.tif 000008
【００５５】
次に、予測誤差を含む最適化問題において、予測誤差が与える影響を説明する。説明の簡易化のため、オプションはただ１つ存在する（上記例では、ｎ＝１）ものとし、予算ｃ＝１、真の期待利得θ＊＝１とする。これは、いかなる戦略も得をすることができない状況を想定したものである。
【００５６】
予測値をθ’＝θ＊＋εに基づいて得たとすると、半分の確率でθ’＞１となる。この場合、予測者は、投資をすることで利得θ’を得られると認識するため、半分の確率で利得の過剰見積もりが起こることになる。これは、半分の確率で予測した利得を得ることができない、つまり、最適化結果の信頼性がない、ということを意味する。なお、ここで設定した「予測されたように得をすることはできない（実際の利得がない）」という想定から、同様に「最適化をすると平均的に損をする」という例を想定することが可能である。
【００５７】
次に、不確実性領域を決定する一般的な方法の問題点を説明する。第一の方法は、専門知識に基づいて決定する方法であるため、確率的な保証を得ることができない。そこで、第二の方法（不確実なパラメータの信頼領域を決定する方法）について検討する。
【００５８】
式７におけるΣ／ｄを改めてΣに置き換え、予測誤差の分布をε〜Ｎ（θ＊，Σ）とする。予測誤差の分布が分かっている場合に、その信頼領域を考えてロバスト最適化を行う手法はよく知られている。信頼水準αの信頼領域Ｕは、以下に示す式８におけるＵｒαで与えられる。なお、ｒαは、以下の式９を満たす。
【００５９】
【数７】
2018155319.tif 000009
【００６０】
式８および式９におけるＵｒαは、体積の意味で、予測誤差がαの確率で含まれる最小の集合ととらえることができる。このとき、確率的に生成されるθ’に対して、集合｛θ’｝＋Ｕｒα（＋は集合のミンコフスキー和を示す）が確率αで真の値θ＊を含むことが分かる。
【００６１】
よって、集合｛θ’｝＋Ｕｒαにおける最悪ケースを考えるロバスト最適化問題は、以下に示す式１０で表すことができる。
【００６２】
【数８】
2018155319.tif 000010
【００６３】
また、式１０における最適解ｘ’は、少なくとも確率αで、以下に示す式１１を満たす。
【００６４】
【数９】
2018155319.tif 000011
【００６５】
上記式１１は、利得の過剰見積もりが起こらない確率が、少なくともαであることを意味する。
【００６６】
しかし、上記方法では、以下のような例において効果を発揮しない。
ｎ次元のポートフォリオ最適化問題において、予算をｃ＝１とし、真の利得ベクトルθ＊を以下の式１２のように想定する。式１２は、実質的に第一要素のオプションに投資する以外の選択肢がない状況を想定したものである。
【００６７】
【数１０】
2018155319.tif 000012
【００６８】
Σを単位行列とすると、以下の式１３が想定される。
【００６９】
【数１１】
2018155319.tif 000013
【００７０】
予測誤差が正規分布に従っているため、上記ｒαを以下に示す式１４で表すことができる。式１４におけるχｎは、自由度ｎのカイ分布の分布関数である。
ｒα＝χｎ−１（α）    （式１４）
【００７１】
この場合、αを固定したときにｒαは、次元ｎに対して、Ｏ（√ｎ）で増加する。よって、Ｏ（√ｎ）≧１０が成立する様な大きさの次元ｎに対して、信頼領域を用いたロバスト最適化の解は、「投資しない」ということが最適解になる。しかし、この解は、以下の点で不合理であるといえる。
【００７２】
本具体例では、第二要素以下のオプションはダミーであり、明らかに問題の本質に影響していないはずである。しかし、信頼領域の半径が次元の影響を受けるため、結果として、ダミーの次元によって異なる解が算出される。特に、次元が大きい場合、無駄に保守的な解が算出されるといえる。これにより、本来得られるはずであった利得も失ってしまうことになる。
【００７３】
以上の問題設定に対して、本発明では、概略以下のように処理を行う。本発明では、ロバスト最適化の不確実性領域Ｕｒの半径ｒを、パラメータの次元に基づいてではなく、最適化するドメインの本質的な次元に基づいて計算する。上記の例では、最適化するドメインは実質１次元であるため、本質的な次元は１になる。この次元に基づいて不確実性領域を計算するため、ダミー次元の影響を受けずに半径ｒを計算でき、かつ、得られた解について信頼領域を構成する場合と同等の確率的保証を得ることができる。
【００７４】
以下、本発明の実施形態を図面を参照して説明する。また、具体例として、前述するポートフォリオ最適化の例を適宜説明する。
【００７５】
図１は、本発明による最適化装置の一実施形態を示すブロック図である。また、図２は、最適化装置によるデータの流れの例を示す説明図である。本実施形態の最適化装置１００は、予測対象の説明に用いられる説明変数が最適化の操作変数になり、その予測対象の予測に基づいて前記最適化を行う。本実施形態の最適化装置１００は、学習部１０と、予測モデル入力部１１と、予測誤差入力部１２と、最適化入力部２０と、保証確率入力部２１と、ドメイン入力部２２と、予測最適化部３０と、ロバスト最適化部４０と、出力部５０とを備えている。
【００７６】
学習部１０は、予測パラメータθ’と予測誤差分布を出力する。学習部１０は、例えば、予測モデルの学習結果として、その予測モデルを表すパラメータを予測パラメータθ’として出力してもよい。また、誤差分布は、分散共分散行列Σで表すことができるため、学習部１０は、予測モデルに対応する分散共分散行列Σを予測誤差分布として出力してもよい。また、学習部１０は、学習結果を記憶部（図示せず）に記憶してもよい。
【００７７】
予測モデル入力部１１は、学習部１０が出力した予測パラメータθ’を予測最適化部３０に入力する。また、予測誤差入力部１２は、学習部１０が出力した予測誤差分布を予測最適化部３０に入力する。予測モデル入力部１１および予測誤差入力部１２は、学習部１０が出力した各情報を、そのまま予測最適化部３０に入力してもよいし、学習部１０が記憶部（図示せず）に記憶した学習結果を読み取り、その情報に基づいて各情報を予測最適化部３０に入力してもよい。
【００７８】
最適化入力部２０は、保証したい確率α（例えば、０．９９など）および最適化するドメインを保証確率入力部２１およびドメイン入力部２２にそれぞれ入力する。確率αおよびドメインは、例えば、ユーザにより指定される。最適化するドメインの例として、上記式３に示すドメインが挙げられる。
【００７９】
保証確率入力部２１は、最適化入力部２０に入力された確率αを予測最適化部３０に入力する。また、ドメイン入力部２２は、最適化入力部２０に入力された最適化するドメインを予測最適化部３０に入力する。
【００８０】
予測最適化部３０は、ドメイン制限部３１と、不確実性領域形状決定部３２と、不確実性領域半径決定部３３と、予測最適化出力部３４とを含む。
【００８１】
ドメイン制限部３１は、最適化するドメインを、予測パラメータおよび予測誤差分布に基づいて制限する。
【００８２】
例えば、上記具体例の場合、第二次元以下のオプションへ投資することはないと判断されるため、ドメインＸ’は、以下の式１５のように制限される。
【００８３】
【数１２】
2018155319.tif 000014
【００８４】
不確実性領域形状決定部３２は、不確実性領域の形状を、予測誤差分布に基づいて計算する。不確実性領域の形状は、正のパラメータｒを用いた順序集合｛Ｕｒ｝ｒ＞０で表される。上記具体例の場合、不確実性領域の形状は、以下に示す式１６で表される。
【００８５】
【数１３】
2018155319.tif 000015
【００８６】
不確実性領域半径決定部３３は、最適解が確率を保証するために必要な半径ｒ＊を、制限された最適化ドメインの次元を意味するパラメータを用いて決定する。上記具体例の場合、最適化するドメインは実質１次元であるため、半径ｒ＊は、以下に示す式１７で計算される。
【００８７】
【数１４】
2018155319.tif 000016
【００８８】
上記第二の方法（信頼領域法）を用いた場合の半径は、上記式１４に示すように次元ｎに依存する。一方、本実施形態では、上記式１７に示すように、次元ｎに依存せずに信頼領域を決定できる。
【００８９】
予測最適化出力部３４は、後述するロバスト最適化部４０による最適化結果を受け取り、出力部５０に入力する。
【００９０】
ロバスト最適化部４０は、予測パラメータθ’、制限されたドメインＸ’および不確実性領域Ｕｒ＊を用いてロバスト最適化問題を解く。上記具体例で示すような正規誤差に基づくポートフォリオ最適化問題では、ロバスト最適化部４０は、二次計画問題に変換してロバスト最適化問題を効率的に解くことができる。
【００９１】
なお、様々な目的関数と不確実性領域に対してロバスト最適化問題が効率的に解けることが知られているため、ここでは詳細な説明は省略する。
【００９２】
出力部５０は、ロバスト最適化問題の解を出力する。また、出力部５０は、最適化結果に加え、実質的次元に基づく最適化（すなわち、制限されたドメインの次元に基づく最適化）が、１次元の問題に適応されたときの保証確率を以下の式１８に基づいて出力してもよい。
【００９３】
【数１５】
2018155319.tif 000017
【００９４】
式１８におけるαバー（バーは上付き−）は、同じロバスト最適化法を実質１次元の問題に適応した場合に得られる保証確率である。したがって、αバー−αは、最適化するドメインの実質的次元によって失われた保証値、または、余分に保証が必要になった差分ととらえることができる。
【００９５】
以下、予測最適化部３０のより詳細な処理を説明する。まず、ドメイン制限部３１は、予測誤差の信頼領域を算出する。上述するように、予測誤差が分散Σの正規分布に従う場合、信頼領域Ｕｒは上記式８および式９で与えられる。
【００９６】
なお、一般的な誤差分布の場合、誤差εのｖ方向への射影ｖＴεが従う確率分布をΦｖとしたとき、信頼水準γの信頼領域Ｕγ，ｖは、以下の式１９で算出される。
【００９７】
【数１６】
2018155319.tif 000018
【００９８】
ドメイン制限部３１は、この信頼領域Ｕｒに基づいて最適解となり得る解の集合にドメインを制限する。制限されたドメインＸ’は、例えば、以下に示す式２０で表される。
【００９９】
【数１７】
2018155319.tif 000019
【０１００】
ドメイン制限部３１は、例えば、信頼領域Ｕｒの３倍の大きさの領域Ｕ＝３Ｕｒに対して、最適解となり得る解の集合にドメインを制限してもよい。なお、ここで例示する３倍とは、例えば、理論的な成果に基づいて決定されるものであり、信頼領域を決定する方法の一例である。ドメイン制限部３１は、信頼領域に基づいて任意の方法によりドメインＸを制限すればよい。
【０１０１】
ここで、ドメイン制限部３１の役割を説明する。ここで制限されたドメインＸ’は、非常に高い確率で真のパラメータθ＊における最適解ｘ＊を含む。ドメインＸ’に制限することは、解の質を損なうことなく、ドメインの次元を実質的に低くすることができることを意味する。
【０１０２】
なお、一般的には、制限されたドメインＸ’を厳密に求めることは難しい。ただし、ドメイン制限部３１は、不確実性領域半径決定部３３の処理に問題を生じさせなければ、厳密なドメインＸ’を求めなくてもよい。ドメイン制限部３１は、例えば、ｕ∈Ｕをサンプリングし、ドメインＸ’をそれらのｕに対する以下の式２１で示す最適解の凸包として近似してもよい。
【０１０３】
【数１８】
2018155319.tif 000020
【０１０４】
不確実性領域形状決定部３２は、誤差分布が正規分布の場合、上記式１６で示すように領域の形状を決定すればよい。また、一般的な誤差分布の場合、不確実性領域形状決定部３２は、上記で示すＵγを用いて、ｒに対するＵｒを、以下の式２２のように決定してもよい。
【０１０５】
【数１９】
2018155319.tif 000021
【０１０６】
ドメイン制限部３１の処理でも説明したように、一般にＵｒを求めることは困難である。ただし、誤差分布を正規分布で近似することや、Ｕ｛γ，ｖ｝を精度よく求めることは可能である。そこで、不確実性領域形状決定部３２は、有限個のＵ｛γ，ｖ｝の共通部分としてＵｒを近似してもよい。
【０１０７】
不確実性領域半径決定部３３は、まず、Ｖ＝｛ｖ（ｘ）｜ｘ∈Ｘ’｝を定義する。次に、不確実性領域半径決定部３３は、Ｖの極錘ＣＶを、以下に示す式２３で算出する。
【０１０８】
【数２０】
2018155319.tif 000022
【０１０９】
次に、不確実性領域半径決定部３３は、以下の式２４に示すように、確率がα以上になる最小のｒを算出する。
【０１１０】
【数２１】
2018155319.tif 000023
【０１１１】
誤差分布が分かっているため、εをサンプルすることが可能であり、式２４において、確率を算出することが可能である。不確実性領域半径決定部３３は、Ｕｒを所望の不確実性領域として出力する
【０１１２】
ここで、極錘Ｃｖによるミンコフスキー和Ｕｒ＋Ｃｖを考える理由を、具体例を用いて説明する。前述のポートフォリオ最適化の例において、Ｖ＝Ｘ’である。よって、以下に示す式２５が成り立つ。
【０１１３】
【数２２】
2018155319.tif 000024
【０１１４】
上記式２５は、ｎ次元空間における第一軸の半空間を示す。よって、Ｕｒ＋Ｃｖに誤差が含まれるか否かは、εの第一軸の値のみによって決定される。これにより、確率保証のために必要な不確実性領域の半径は、第二の方法（信頼領域法）を用いる場合の一次元の場合に対応する半径で十分になる。
【０１１５】
このように、にＵｒ＋Ｃｖに誤差が含まれる確率を考えることは、パラメータの次元ではなく、最適化するドメインの次元を考え、それに対応する信頼区間の半径を考えることに相当する。これにより、信頼領域を直接用いた場合と比較して、パラメータの次元に対する依存性が最適化するドメインの実質的な次元に対する依存性に置き換わり、パラメータのダミー次元によって最適解の質が下がるという事態を避けられる。
【０１１６】
なお、一般のＶに対しても、Ｃｖを求めることはできない。しかし、以下の式２６に示す最適化問題の最大値が少なくとも０の場合にのみ、θ∈Θについて、θ∈Ｕβ＋Ｃｖが成り立つ。
【０１１７】
【数２３】
2018155319.tif 000025
式２６において、ＵおよびＸ’ともに有限サンプルを用いて近似可能である。そのため、近似的にこの問題を解くことで、誤差が含まれるか否かを判定できる。
【０１１８】
このような処理が行われた後で、ロバスト最適化部４０は、不確実性領域Ｕに対するロバスト最適化問題を解く。なお、ロバスト最適化が効率的に解けるか否かは問題設定に依存する。例えば、目的関数が線形または２次であり、不確実性領域が楕円である場合に、ロバスト最適化問題を効率的に解くアルゴリズムが知られている。また、不確実性領域をサンプリングで近似することにより、ロバスト最適化問題を解くアルゴリズムなども知られている。
【０１１９】
予測最適化部３０（より具体的には、ドメイン制限部３１と、不確実性領域形状決定部３２と、不確実性領域半径決定部３３と、予測最適化出力部３４）と、ロバスト最適化部４０と、出力部５０とは、プログラム（最適化プログラム）に従って動作するコンピュータのＣＰＵによって実現される。例えば、プログラムは、最適化装置の記憶部（図示せず）に記憶され、ＣＰＵは、そのプログラムを読み込み、プログラムに従って、予測最適化部３０（より具体的には、ドメイン制限部３１と、不確実性領域形状決定部３２と、不確実性領域半径決定部３３と、予測最適化出力部３４）、ロバスト最適化部４０および出力部５０として動作してもよい。
【０１２０】
また、予測最適化部３０（より具体的には、ドメイン制限部３１と、不確実性領域形状決定部３２と、不確実性領域半径決定部３３と、予測最適化出力部３４）と、ロバスト最適化部４０と、出力部５０とは、それぞれが専用のハードウェアで実現されていてもよい。また、出力部５０は、ディスプレイ装置等の出力装置を含んでいてもよい。
【０１２１】
次に、本実施形態の最適化装置の動作を説明する。図３は、本実施形態の最適化装置の動作例を示すフローチャートである。
【０１２２】
ドメイン制限部３１は、入力された予測パラメータと誤差分布とに基づいて、最適化するドメインを制限する（ステップＳ１１）。また、不確実性領域形状決定部３２は、入力された誤差分布に基づいて、不確実性領域の形状を決定する（ステップＳ１２）。そして、不確実性領域半径決定部３３は、不確実性領域の形状と制限されたドメインとから、指定された確率を保証する不確実性領域の半径を決定する（ステップＳ１３）。ロバスト最適化部４０は、決定された半径の不確実性領域に基づいてロバスト最適化を行う（ステップＳ１４）。出力部５０は、ロバスト最適化による結果を出力する（ステップＳ１５）。
【０１２３】
以上のように、本実施形態では、ドメイン制限部３１が、予測対象の予測に用いられる予測パラメータθ’と、その予測の誤差分布とに基づいて、最適化の対象のドメインＸの範囲を制限し、不確実性領域形状決定部３２が、誤差分布に基づいて、ロバスト最適化における不確実性領域Ｕｒの形状を決定する。また、不確実性領域半径決定部３３が、不確実性領域Ｕｒの形状と制限されたドメインＸ’とから、指定された確率αを保証する不確実性領域Ｕｒの半径ｒを決定する。そして、ロバスト最適化部４０が、決定された半径の不確実性領域に基づいて、操作変数に関するロバスト最適化を行い、出力部５０が、ロバスト最適化による結果を出力する。そのような構成により、不確実性を有する最適化のパラメータが予測に基づいて与えられる場合に、指定された確率を保証する最適解を算出できる。
【０１２４】
また、本発明によれば、コンピュータが最適化処理を行った場合（特に高次元パラメータを有する最適化処理）の最適化結果の精度を格段に向上できる。
【０１２５】
なお、上記では、ポートフォリオの最適化問題について例示したが、本実施形態の最適化装置１００は、他にも価格最適化問題に適用され得る。この場合、例えば、操作変数が価格に対応し、予測対象が売上数に対応する。
【０１２６】
次に、本発明の概要を説明する。図４は、本発明による最適化装置の概要を示すブロック図である。本発明による最適化装置は、予測対象（例えば、利得）の説明に用いられる説明変数（例えば、戦略ｘ）が最適化の操作変数になり、その予測対象の予測に基づいて最適化を行う最適化装置８０（例えば、最適化装置１００）であって、予測対象の予測に用いられる予測パラメータ（例えばθ’）と、その予測の誤差分布（例えば、正規分布）とに基づいて、最適化の対象のドメイン（例えば、ドメインＸ）の範囲を制限するドメイン制限部８１（例えば、ドメイン制限部３１）と、誤差分布に基づいて、ロバスト最適化における不確実性領域の形状（例えば、式１６に示す形状）を決定する不確実性領域形状決定部８２（例えば、不確実性領域形状決定部３２）と、不確実性領域の形状と制限されたドメイン（例えば、ドメインＸ’）とから、指定された確率を保証する不確実性領域の半径（例えば、ｒ）を決定する不確実性領域半径決定部８３（例えば、不確実性領域半径決定部３３）と、決定された半径の不確実性領域に基づいて、操作変数に関するロバスト最適化を行う最適化部８４（例えば、ロバスト最適化部４０）と、ロバスト最適化による結果を出力する出力部８５（例えば、出力部５０）とを備えている。
【０１２７】
そのような構成により、不確実性を有する最適化のパラメータが予測に基づいて与えられる場合に、指定された確率を保証する最適解を算出できる。
【０１２８】
また、出力部８５は、最適化部が行うロバスト最適化を制限されたドメインの次元に適応した場合に得られる保証確率（例えば、式１８に示す保証確率）を出力してもよい。そのような構成により、最適化するドメインの実質的次元によって失われた保証値、または、余分に保証が必要になった差分を把握できる。
【０１２９】
また、ドメイン制限部８１は、（例えば、式１９を用いて）誤差分布の信頼領域を算出し、その信頼領域に基づいて最適解となり得る解の集合にドメインを制限してもよい。
【０１３０】
また、不確実性領域形状決定部８２は、不確実性領域の形状を、誤差分布を用いた順序集合で表してもよい。
【０１３１】
また、不確実性領域半径決定部８３は、誤差分布がＶの極錘と不確実性領域とのミンコフスキー和に属することが指定された確率以上になる最小の半径を算出してもよい。
【０１３２】
図５は、少なくとも１つの実施形態に係るコンピュータの構成を示す概略ブロック図である。コンピュータ１０００は、ＣＰＵ１００１、主記憶装置１００２、補助記憶装置１００３、インタフェース１００４を備える。
【０１３３】
上述の情報処理システムは、コンピュータ１０００に実装される。そして、上述した各処理部の動作は、プログラム（最適化プログラム）の形式で補助記憶装置１００３に記憶されている。ＣＰＵ１００１は、プログラムを補助記憶装置１００３から読み出して主記憶装置１００２に展開し、当該プログラムに従って上記処理を実行する。
【０１３４】
なお、少なくとも１つの実施形態において、補助記憶装置１００３は、一時的でない有形の媒体の一例である。一時的でない有形の媒体の他の例としては、インタフェース１００４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等が挙げられる。また、このプログラムが通信回線によってコンピュータ１０００に配信される場合、配信を受けたコンピュータ１０００が当該プログラムを主記憶装置１００２に展開し、上記処理を実行しても良い。
【０１３５】
また、当該プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、当該プログラムは、前述した機能を補助記憶装置１００３に既に記憶されている他のプログラムとの組み合わせで実現するもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１３６】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１３７】
この出願は、２０１７年２月２３日に出願された米国仮出願第６２／４６２，５７８号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１３８】
１０  学習部
１１  予測モデル入力部
１２  予測誤差入力部
２０  最適化入力部
２１  保証確率入力部
２２  ドメイン入力部
３０  予測最適化部
３１  ドメイン制限部
３２  不確実性領域形状決定部
３３  不確実性領域半径決定部
３４  予測最適化出力部
４０  ロバスト最適化部
５０  出力部
１００  最適化装置
【図１】
2018155319.tif 000026
【図２】
2018155319.tif 000027
【図３】
2018155319.tif 000028
【図４】
2018155319.tif 000029
【図５】
2018155319.tif 000030
【国際調査報告】
2018155319.tif 000031
2018155319.tif 000032