(57)【要約】【課題】複合構造下での最適化問題の解を、最小化すべき関数が悪条件な場合にも高速に得ることができる手法を提供することである。【解決手段】本発明の一態様は、３つの関数f, g, hの和で表される最適化関数f+g+hの最適解を計算する計算装置であって、２つの関数f, gの和で表される関数F=f+gと関数hとの和の関数F+hによって前記最適化関数f+g+hを表し、前記関数F+hの近接点を計算する第１計算部と、前記関数Fの近似近接点を計算する第２計算部と、前記第１計算部によって計算された近接点と前記第２計算部によって計算された近似近接点とに基づき所定の終了条件が充足されたか判定し、前記所定の終了条件が充足されるまで前記第１計算部と前記第２計算部とに前記近接点と前記近似近接点とを繰り返し計算させる収束判定部と、を有する計算装置に関する。【選択図】図１
2019192125.tif 000002
【特許請求の範囲】
【請求項１】
３つの関数f, g, hの和で表される最適化関数f+g+hの最適解を計算する計算装置であって、
２つの関数f, gの和で表される関数F=f+gと関数hとの和の関数F+hによって前記最適化関数f+g+hを表し、前記関数F+hの近接点を計算する第１計算部と、
前記関数Fの近似近接点を計算する第２計算部と、
前記第１計算部によって計算された近接点と前記第２計算部によって計算された近似近接点とに基づき所定の終了条件が充足されたか判定し、前記所定の終了条件が充足されるまで前記第１計算部と前記第２計算部とに前記近接点と前記近似近接点とを繰り返し計算させる収束判定部と、
を有する計算装置。
【請求項２】
前記第１計算部は、Douglas-Rachford法によって前記関数F+hの近接点を計算する、請求項１記載の計算装置。
【請求項３】
前記第２計算部は、主双対法によって前記関数Fの近似近接点を計算する、請求項１又は２記載の計算装置。
【請求項４】
前記第２計算部は、双対解を利用することによって前記近似近接点を計算する、請求項１乃至３何れか一項記載の計算装置。
【請求項５】
前記終了条件は、現在の近接点の精度を表す所定の評価関数が所定の閾値に達したこと、あるいは、繰り返し回数が所定の閾値に到達したことである、請求項１乃至４何れか一項記載の計算装置。
【請求項６】
前記関数fは最適化の対象となる関数であり、前記関数g, hは前記関数fに制約を課す関数である、請求項１乃至５何れか一項記載の計算装置。
【請求項７】
３つの関数f, g, hの和で表される最適化関数f+g+hの最適解を計算する計算装置によって実行される方法であって、
２つの関数f, gの和で表される関数F=f+gと関数hとの和の関数F+hによって前記最適化関数f+g+hを表し、前記関数F+hの近接点を計算するステップと、
前記関数Fの近似近接点を計算するステップと、
前記計算された近接点と前記計算された近似近接点とに基づき所定の終了条件が充足されたか判定し、前記所定の終了条件が充足されるまで前記近接点と前記近似近接点とを繰り返し計算するステップと、
を有する計算方法。
【請求項８】
請求項１乃至６何れか一項記載の計算装置の各部としてプロセッサを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化問題を解くための技術に関する。
【背景技術】
【０００２】
通常、最適化問題では、ある関数の値を最小化する解を計算する。解のうち、ある良い構造を持った解を求めたい場合には、最小化すべき関数に制約や正則化を課す項を付け加え、二つの項の和を最小化する解を計算する。例えば、統計学でしばしば用いられるリッジ回帰やスパースロジスティック回帰では、二つの項の和の最小化問題を解く。二つの項の和を最小化する解を計算する方法としては、Douglas-Rachford法が知られている（非特許文献１）。
【０００３】
さらに、解に要請する構造が二つある場合は、三つの項の和の最小化問題を解く。このような複合構造下での最適化問題は、サポートベクターマシンや圧縮センシング、スパース共分散行列推定などで現れる。複合構造下での最適化問題を解くために、いくつかの手法が提案されている（非特許文献２〜４）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Damek Davis and Wotao Yin. Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions. Mathematics of Operations Research, 2017.
【非特許文献２】Radu Ioan Bot and Erno Robert Csetnek. On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems. Optimization, 64(1):5-23, 2015.
【非特許文献３】Laurent Condat. A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. Journal of Optimization Theory and Applications, 158(2):460-479, 2013.
【非特許文献４】Damek Davis and Wotao Yin. A three-operator splitting scheme and its optimization applications. Set-Valued and Variational Analysis, pages 1-30, 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１の手法は２項の和で表現される最適化関数の解を求める手法であり、最適化関数が悪条件（ill-conditioned）である場合でも有用であるが、解に要請する構造が二つある複合構造下での最適化問題の解を求めることはできない。また、非特許文献２〜４の手法は複合構造下での最適化問題を扱うことができるが、最小化すべき関数が悪条件な場合、解を得るために長時間かかってしまうという問題がある。
【０００６】
上述した問題点を鑑み、本発明の課題は、複合構造下での最適化問題の解を、最小化すべき関数が悪条件な場合にも高速に得ることができる手法を提供することである。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、本発明の一態様は、３つの関数f, g, hの和で表される最適化関数f+g+hの最適解を計算する計算装置であって、２つの関数f, gの和で表される関数F=f+gと関数hとの和の関数F+hによって前記最適化関数f+g+hを表し、前記関数F+hの近接点を計算する第１計算部と、前記関数Fの近似近接点を計算する第２計算部と、前記第１計算部によって計算された近接点と前記第２計算部によって計算された近似近接点とに基づき所定の終了条件が充足されたか判定し、前記所定の終了条件が充足されるまで前記第１計算部と前記第２計算部とに前記近接点と前記近似近接点とを繰り返し計算させる収束判定部と、を有する計算装置に関する。
【発明の効果】
【０００８】
本発明によると、複合構造下での最適化問題の解を、最小化すべき関数が悪条件な場合にも高速に得ることができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の一実施例による計算装置の機能構成を示すブロック図である。
【図２】本発明の一実施例による最適解計算処理を示すフローチャートである。
【図３】本発明の一実施例による主双対法の処理を示すフローチャートである。
【図４】本発明の一実施例による最適解計算処理と従来技術との収束時間の比較を示す図である。
【発明を実施するための形態】
【００１０】
以下の実施例では、複合構造下での最適化問題の最適解を計算する計算装置が開示される。より詳細には、以下の実施例による計算装置は、３つの関数
【００１１】
【数１】
2019192125.tif 000003
と行列
【００１２】
【数２】
2019192125.tif 000004
により定まる最適化問題
【００１３】
【数３】
2019192125.tif 000005
の最適解を計算する。以下の実施例による計算装置によると、最小化すべき関数f(Ax)+g(x)+h(x)が悪条件な場合にも、最適解を高速に取得することができる。
【００１４】
まず、図１を参照して、本発明の一実施例による計算装置を説明する。図１は、本発明の一実施例による計算装置の機能構成を示すブロック図である。
【００１５】
図１に示されるように、計算装置１００は、記憶部１１０、初期化部１２０、第１計算部１３０、第２計算部１４０及び収束判定部１５０を有する。
【００１６】
記憶部１１０は、対象とする最適化問題を特定するパラメータを格納する。具体的には、記憶部１１０は、最適化関数を構成する３つの関数
【００１７】
【数４】
2019192125.tif 000006
と、行列
【００１８】
【数５】
2019192125.tif 000007
と、後述の計算過程で用いられるパラメータ
【００１９】
【数６】
2019192125.tif 000008
を格納する。ここで、γは正の実数であり、任意に設定することができる。例えば、γ=1であってもよい。これらの各関数、行列、パラメータ等は予め外部から入力され、記憶部１１０に記憶されるものとする。
【００２０】
上記の３つの関数f, g, hのうち、fは最小化すべき関数であり、g, hは最小化すべき関数fに制約や正則化を課す関数、すなわち、解に要請する構造を表す関数である。最適化の対象となる関数は以下のように表される。
【００２１】
【数７】
2019192125.tif 000009
初期化部１２０は、以降の処理で近接点の計算に用いる点列{zt}（tはインデックスであり、繰り返し回数を表す）の先頭の点z1の値を設定する。z1は実d次元ベクトルであり、初期化部１２０は、ベクトルz1の各要素の値を何れか適当な実数に設定する。また、初期化部１２０は、繰り返し回数tをt=1に設定する。
【００２２】
第１計算部１３０は、関数hに関するztの近接点proxγh(zt)を計算する。具体的には、第１計算部１３０は、
【００２３】
【数８】
2019192125.tif 000010
とし、最小化の対象となる関数である式（１）をF(x)とh(x)との２つの関数の和
【００２４】
【数９】
2019192125.tif 000011
とみなし、Douglas-Rachford法により近接点proxγh(zt)を求め、これをxtとする。
【００２５】
第２計算部１４０は、第１計算部１３０において求められた近接点xtを用いて点ut（ここで、ut=2xt-zt）を計算し、上記関数F(x)に関するutの近似近接点yt、すなわち、近接点proxγF(ut)に近い点ytを計算する。当該計算について、本実施例では、第２計算部１４０は、主双対法を用いる。主双対法の処理の詳細については後述する。
【００２６】
収束判定部１５０は、第１計算部１３０において求められたxt、第２計算部１４０において求められたyt及び現在のztを用いて次の点zt+1（ここで、zt+1=zt+yt-xt）を計算し、予め定めた終了条件を満たす場合、当該処理を終了し、解xtを出力する。予め定めた終了条件を満たさない場合、収束判定部１５０は、tに1を加算し、第１計算部１３０に近接点の計算を繰り返させる。例えば、終了条件としては、現在の解xtの精度を表す所定の評価関数が所定の閾値に達したこと、あるいは、繰り返し回数tが所定の閾値に到達したこと等を用いてもよい。評価関数が所定の閾値に到達するとは、例えば、訓練誤差の減少量 f(xt-1)-f(xt)が予め定めた閾値より小さいこと、バリデーション誤差の減少量が予め定めた閾値より小さいこと、解x1,...,xtから計算されるバリデーション誤差の最小値が予め定めた回数の反復の間更新されないこと、などであってもよい。
【００２７】
ここで、計算装置１００は、典型的には、サーバなどの計算装置により実現されてもよく、例えば、バスＢを介し相互接続されるドライブ装置、補助記憶装置、メモリ装置、プロセッサ、インタフェース装置及び通信装置から構成されてもよい。計算装置１００における各種機能及び処理を実現するプログラムを含む各種コンピュータプログラムは、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、フラッシュメモリなどの記録媒体によって提供されてもよい。プログラムを記憶した記録媒体がドライブ装置にセットされると、プログラムが記録媒体からドライブ装置を介して補助記憶装置にインストールされる。但し、プログラムのインストールは必ずしも記録媒体により行う必要はなく、ネットワークなどを介し何れかの外部装置からダウンロードするようにしてもよい。補助記憶装置は、インストールされたプログラムを格納すると共に、必要なファイルやデータなどを格納する。メモリ装置、プログラムの起動指示があった場合に、補助記憶装置からプログラムやデータを読み出して格納する。プロセッサは、メモリ装置に格納されたプログラムやプログラムを実行するのに必要なパラメータなどの各種データに従って、上述した計算装置１００の各種機能及び処理を実行する。インタフェース装置は、ネットワーク又は外部装置に接続するための通信インタフェースとして用いられる。通信装置は、インターネットなどのネットワークと通信するための各種通信処理を実行する。
【００２８】
しかしながら、計算装置１００は、上述したハードウェア構成に限定されるものでなく、他の何れか適切なハードウェア構成により実現されてもよい。
【００２９】
次に、図２を参照して、本発明の一実施例による最適解計算処理を説明する。図２は、本発明の一実施例による最適解計算処理を示すフローチャートである。
【００３０】
ステップＳ１０１において、記憶部１１０は、計算装置１００に入力された最適化関数を構成する３つの関数f, g, h、行列A及びパラメータγを格納する。
【００３１】
ステップＳ１０２において、初期化部１２０は、点列{zt}について、インデックスtをt=1に設定すると共に、z1を零ベクトルに初期化する。
【００３２】
ステップＳ１０３において、第１計算部１３０は、関数hに関するztの近接点proxγh(zt)をDouglas-Rachford法によって計算し、xtに代入する。
【００３３】
ステップＳ１０４において、第２計算部１４０は、関数f, gの和であるf+gに関するutの近似近接点を主双対法によって計算し、ytに代入する。
【００３４】
ステップＳ１０５において、収束判定部１５０は、zt+yt-xtを計算し、zt+1に代入する。
【００３５】
ステップＳ１０６において、収束判定部１５０は、所定の終了条件が充足されたか判定し、終了条件が充足されている場合（Ｓ１０６：Ｙｅｓ）、ステップＳ１０７に移行し、計算装置１００は、解xtを出力する。他方、終了条件が充足されていない場合（Ｓ１０６：Ｎｏ）、収束判定部１５０は、インデックスtを１だけインクリメントし、ステップＳ１０３に戻って、上述したステップＳ１０３〜Ｓ１０６が繰り返される。
【００３６】
次に、図３を参照して、本発明の一実施例によるステップＳ１０４における主双対法の処理の詳細を説明する。図３は、本発明の一実施例による主双対法の処理を示すフローチャートである。すなわち、図３では、第２計算部１４０において主双対法によって関数F（F=f+g）に関するut（ここで、ut=2xt-zt）の近似近接点ytを計算するステップＳ１０３の詳細が示される。本実施例による主双対法では、近似近接点ytの他に双対解βtも同時に計算される。
【００３７】
図３に示されるように、ステップＳ２０１において、第２計算部１４０は、yt及びβtを初期化する。具体的には、第２計算部１４０は、yt-1及びβt-1を用いて、
【００３８】
【数１０】
2019192125.tif 000012
によりβtを初期化し、さらに初期化されたβtを用いて、
【００３９】
【数１１】
2019192125.tif 000013
をytを初期化する。ここで、∇fはfの勾配を表し、θ∈(0, 1)はバックトラッキングにより定められるパラメータである。
【００４０】
ステップＳ２０２において、第２計算部１４０は、
【００４１】
【数１２】
2019192125.tif 000014
によってβtを更新する。
【００４２】
ステップＳ２０３において、第２計算部１４０は、
【００４３】
【数１３】
2019192125.tif 000015
によってytを更新する。
【００４４】
ステップＳ２０４において、第２計算部１４０は、
【００４５】
【数１４】
2019192125.tif 000016
によって主双対ギャップG(yt, βt)を計算する。ここで、f*は関数fの凸共役関数を表し、記号〈・，・〉はユークリッド空間上の標準内積を表す。
【００４６】
ステップＳ２０５において、第２計算部１４０は、現在の(yt, βt)が主双対ギャップに基づく終了条件
【００４７】
【数１５】
2019192125.tif 000017
を満たしていたら（Ｓ２０５：Ｙｅｓ）、当該処理を終了し、現在のytを収束判定部１５０にわたす。他方、満たしていなければ（Ｓ２０５：Ｎｏ）、第２計算部１４０は、インデックスtに1だけインクリメントし、ステップＳ２０２のβtの更新処理に戻る。このようにして、所定の終了条件を満たすまで、つまり、主双対ギャップが所定の誤差以下となるまで、第２計算部１４０は、yt及びβtを繰り返し更新する。
【００４８】
次に、図４を参照して、本発明と従来技術との数値実験結果を説明する。図４は、本発明の一実施例による最適解計算処理と従来技術との収束時間の比較を示す図である。
【００４９】
図４に示される６つの実データセットを用いて、カーネルサポートベクターマシンの最適化問題を各手法で解いた。従来技術としては、非特許文献４に示されるDavis-Yin法（DYS）と、非特許文献２，３に示されるprimal-dual proximal splitting（PDPS）を用いた。
【００５０】
図４では、各手法が収束するまでの時間が比較され、最適解との相対誤差が10-1以下である解が得られたとき、収束したとみなした。カーネル関数にはガウシアンカーネルを用い、計算を簡単にするためNystrom近似を用いた。この図から、多くの場合で本発明は従来技術より１００倍程度以上高速であることが分かる。
【００５１】
以上、本発明の実施例について詳述したが、本発明は上述した特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００５２】
１００  計算装置
１１０  記憶部
１２０  初期化部
１３０  第１計算部
１４０  第２計算部
１５０  収束判定部
【図１】
2019192125.tif 000018
【図２】
2019192125.tif 000019
【図３】
2019192125.tif 000020
【図４】
2019192125.tif 000021