(57)【要約】【課題】悪条件な問題に対しても、高速に質の良い非凸スパース最適化問題の解を求めることができるようにする。【解決手段】計算部１３０が、前回求められた非ゼロの要素の集合又は非ゼロの要素の集合の初期値に対して、非ゼロの要素の集合に含まれない要素を追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、目的関数の最適値を、非ゼロの要素の集合に含まれない要素の各々について計算し、主処理部１２０が、追加上限数の総和が所定数となるように繰り返し回数毎に予め定められた追加上限数だけ、目的関数の最適値が最適な順に、追加した要素を選択し、非ゼロの要素の集合に追加することを、判定部１４０が繰り返させ、出力部１５０が、非ゼロの要素の集合のみ非ゼロの要素となることを許容した際における、目的関数の値が最適となる前記変数ベクトルの値を出力する。【選択図】図１
2020102073.tif 000002
【特許請求の範囲】
【請求項１】
変数ベクトルが非ゼロの要素を高々所定数しか持たないという制約下において、目的関数の値が最適となる前記変数ベクトルの値を求める高速スパース最適化装置であって、
前回求められた非ゼロの要素の集合又は非ゼロの要素の集合の初期値に対して、前記非ゼロの要素の集合に含まれない要素を追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、前記目的関数の最適値を、前記非ゼロの要素の集合に含まれない要素の各々について計算する計算部と、
追加上限数の総和が前記所定数となるように繰り返し回数毎に予め定められた追加上限数だけ、前記目的関数の最適値が最適な順に、前記追加した要素を選択し、非ゼロの要素の集合に追加する主処理部と、
予め定められた繰り返し回数だけ、前記計算部による計算と、前記主処理部による選択及び追加とを繰り返させる判定部と、
前記非ゼロの要素の集合のみ非ゼロの要素となることを許容した際における、前記目的関数の値が最適となる前記変数ベクトルの値を出力する出力部と、
を含む高速スパース最適化装置。
【請求項２】
前記繰り返し回数毎に予め定められた追加上限数は１以上であり、かつ、少なくとも１つの前記追加上限数は２以上である
請求項１記載の高速スパース最適化装置。
【請求項３】
変数ベクトルが非ゼロの要素を高々所定数しか持たないという制約下において、目的関数の値が最適となる前記変数ベクトルの値を求める高速スパース最適化方法であって、
計算部が、前回求められた非ゼロの要素の集合又は非ゼロの要素の集合の初期値に対して、前記非ゼロの要素の集合に含まれない要素を追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、前記目的関数の最適値を、前記非ゼロの要素の集合に含まれない要素の各々について計算し、
主処理部が、追加上限数の総和が前記所定数となるように繰り返し回数毎に予め定められた追加上限数だけ、前記目的関数の最適値が最適な順に、前記追加した要素を選択し、非ゼロの要素の集合に追加し、
判定部が、予め定められた繰り返し回数だけ、前記計算部による計算と、前記主処理部による選択及び追加とを繰り返させ、
出力部が、前記非ゼロの要素の集合のみ非ゼロの要素となることを許容した際における、前記目的関数の値が最適となる前記変数ベクトルの値を出力する
高速スパース最適化方法。
【請求項４】
コンピュータを、請求項１又は２記載の高速スパース最適化装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速スパース最適化装置、高速スパース最適化方法、及びプログラムに係り、特に、高速に非凸スパース最適化問題の解を求めるための高速スパース最適化装置、高速スパース最適化方法、及びプログラムに関する。
【背景技術】
【０００２】
スパース推定等の分野で現れる非凸スパース最適化問題は、ｄ個の要素を持つ変数ベクトル
2020102073.tif 000003
がｋ個の非ゼロ（ゼロでない）要素しか持たないという制約の下で、変数ベクトル
2020102073.tif 000004
についての目的関数
2020102073.tif 000005
の値を最適化する問題である。
【０００３】
例えば、ノイズの乗ったｄ個の値を持つ信号からノイズを除去し、ｋ個の非ゼロ要素からなる真の信号の値を復元したいというような状況で、非凸スパース最適化問題は現れる。
【０００４】
非凸スパース最適化問題に対して、非特許文献１〜３のような高速化手法や、非特許文献４のような貪欲法に基づく手法を用いて解を求める研究がされてきた。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Jain, P., Tewari, A., and Kar, P. On iterative hard thresholding methods for high-dimensional M-estimation. In Advances in Neural Information Processing Systems 27. Curran Associates, Inc., 2014, pp. 685-693.
【非特許文献２】Yuan, X., Li, P., and Zhang, T. Exact recovery of hard thresholding pursuit. InAdvances in Neural Information Processing Systems 29. Curran Associates,Inc., 2016, pp. 3558-3566.
【非特許文献３】Marsousi, M., Abhari, K., Babyn, P., and Alirezaie, J. MULTI-STAGE OMP sparsecoding using local matching pursuit atoms selection. In 2013 IEEE International Conferenceon Acoustics, Speech and Signal Processing, 2013, pp.1783-1787.
【非特許文献４】Elenberg, E. R., Khanna, R., Dimakis, A. G., and Negahban, S. Restricted strongconvexity implies weak submodularity. Ann. Statist., 46(6B), 2018, pp.3539-3568.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、非特許文献１〜３の手法は、高速に解を出力できる一方で、問題によっては目的関数
2020102073.tif 000006
の値が最適でない、質の悪い解を出力してしまうことがある。
【０００７】
より具体的には、これらの既存の手法は、非凸スパース最適化問題を構成するデータに偏りがない良条件な問題に対しては質の良い解を出力できるが、データに偏りのある悪条件な問題に対しては出力解の質が悪くなる傾向がある。
【０００８】
一方、貪欲法に基づく手法（非特許文献４）は、上述の高速な手法に比べて悪条件な問題に対しても比較的良い解を出力できる。しかし、この手法は、実行時間が長くなる傾向にあり、大規模な問題への適用が難しい。
【０００９】
本発明は上記の点に鑑みてなされたものであり、悪条件な問題に対しても、高速に質の良い非凸スパース最適化問題の解を求めることができる高速スパース最適化装置、高速スパース最適化方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明に係る高速スパース最適化装置は、変数ベクトルが非ゼロの要素を高々所定数しか持たないという制約下において、目的関数の値が最適となる前記変数ベクトルの値を求める高速スパース最適化装置であって、前回求められた非ゼロの要素の集合又は非ゼロの要素の集合の初期値に対して、前記非ゼロの要素の集合に含まれない要素を追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、前記目的関数の最適値を、前記非ゼロの要素の集合に含まれない要素の各々について計算する計算部と、追加上限数の総和が前記所定数となるように繰り返し回数毎に予め定められた追加上限数だけ、前記目的関数の最適値が最適な順に、前記追加した要素を選択し、非ゼロの要素の集合に追加する主処理部と、予め定められた繰り返し回数だけ、前記計算部による計算と、前記主処理部による選択及び追加とを繰り返させる判定部と、前記非ゼロの要素の集合のみ非ゼロの要素となることを許容した際における、前記目的関数の値が最適となる前記変数ベクトルの値を出力する出力部と、を備えて構成される。
【００１１】
また、本発明に係る高速スパース最適化方法は、変数ベクトルが非ゼロの要素を高々所定数しか持たないという制約下において、目的関数の値が最適となる前記変数ベクトルの値を求める高速スパース最適化方法であって、計算部が、前回求められた非ゼロの要素の集合又は非ゼロの要素の集合の初期値に対して、前記非ゼロの要素の集合に含まれない要素を追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、前記目的関数の最適値を、前記非ゼロの要素の集合に含まれない要素の各々について計算し、主処理部が、追加上限数の総和が前記所定数となるように繰り返し回数毎に予め定められた追加上限数だけ、前記目的関数の最適値が最適な順に、前記追加した要素を選択し、非ゼロの要素の集合に追加し、判定部が、予め定められた繰り返し回数だけ、前記計算部による計算と、前記主処理部による選択及び追加とを繰り返させ、出力部が、前記非ゼロの要素の集合のみ非ゼロの要素となることを許容した際における、前記目的関数の値が最適となる前記変数ベクトルの値を出力する。
【００１２】
本発明に係る高速スパース最適化装置及び高速スパース最適化方法によれば、計算部が、前回求められた非ゼロの要素の集合又は非ゼロの要素の集合の初期値に対して、非ゼロの要素の集合に含まれない要素を追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、目的関数の最適値を、非ゼロの要素の集合に含まれない要素の各々について計算し、主処理部が、追加上限数の総和が所定数となるように繰り返し回数毎に予め定められた追加上限数だけ、目的関数の最適値が最適な順に、追加した要素を選択し、非ゼロの要素の集合に追加する。
【００１３】
そして、判定部が、予め定められた繰り返し回数だけ、計算部による計算と、主処理部による選択及び追加とを繰り返させ、出力部が、非ゼロの要素の集合のみ非ゼロの要素となることを許容した際における、目的関数の値が最適となる前記変数ベクトルの値を出力する。
【００１４】
このように、前回求められた非ゼロの要素の集合又は非ゼロの要素の集合の初期値に対して、非ゼロの要素の集合に含まれない要素を追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、目的関数の最適値を、非ゼロの要素の集合に含まれない要素の各々について計算し、追加上限数の総和が所定数となるように繰り返し回数毎に予め定められた追加上限数だけ、目的関数の最適値が最適な順に、追加した要素を選択し、非ゼロの要素の集合に追加することを繰り返し、非ゼロの要素の集合のみ非ゼロの要素となることを許容した際における、目的関数の値が最適となる前記変数ベクトルの値を出力することにより、悪条件な問題に対しても、高速に質の良い非凸スパース最適化問題の解を求めることができる。
【００１５】
また、本発明に係る高速スパース最適化装置の前記繰り返し回数毎に予め定められた追加上限数は１以上であり、かつ、少なくとも１つの前記追加上限数は２以上であるとすることができる。
【００１６】
本発明に係るプログラムは、コンピュータを、上記の高速スパース最適化装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１７】
本発明の高速スパース最適化装置、高速スパース最適化方法、及びプログラムによれば、悪条件な問題に対しても、高速に質の良い非凸スパース最適化問題の解を求めることができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施の形態に係る高速スパース最適化装置の構成を示す概略図である。
【図２】本発明の実施の形態に係る高速スパース最適化処理のアルゴリズムの一例を示す図である。
【図３】本発明の実施の形態に係る高速スパース最適化装置の実行時間を示すグラフである。
【図４】本発明の実施の形態に係る高速スパース最適化装置の訓練誤差を示すグラフである。
【図５】本発明の実施の形態に係る高速スパース最適化装置の高速スパース最適化処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態について図面を用いて説明する。
【００２０】
＜本発明の実施の形態に係る高速スパース最適化装置の原理＞
まず、本発明の実施形態の原理について説明する。
【００２１】
本実施形態では、貪欲法に基づく手法を高速化することで、悪条件な問題に対しても高速に質の良い解を出力できるようにする。
【００２２】
具体的な高速化の手段として、非凸スパース最適化問題とは異なる問題に対して考案された多段階貪欲法（参考文献１）を用いる。
［参考文献１］Wei, K., Iyer, R., and Bilmes, J. Fast multi-stage submodular maximization. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedingsof Machine Learning Research. PMLR, 22-24 Jun 2014, pp.1494-1502.
【００２３】
まず、［ｄ］＝｛１，２，...，ｄ｝を変数ベクトル
2020102073.tif 000007
の添字の集合とする。また、
2020102073.tif 000008
を変数ベクトル
2020102073.tif 000009
の非ゼロ要素の個数とし、
2020102073.tif 000010
を変数ベクトル
2020102073.tif 000011
の非ゼロ要素の添字の集合とする。さらに、
2020102073.tif 000012
を変数ベクトル
2020102073.tif 000013
を引数に持つ目的関数とする。
【００２４】
目的関数
2020102073.tif 000014
は、例えばノイズの乗ったｄ個の値を持つ信号からノイズを除去し、所定数ｋ個の非ゼロ要素からなる真の信号の値を復元したいというような状況で、真の信号らしさを評価するための関数であり、例えば値が小さいほど真の信号らしさ、すなわち最適であることを表すものである。
【００２５】
本実施形態では、変数ベクトル
2020102073.tif 000015
の非ゼロ要素の個数が所定数ｋ（上限数）以下になるような解で、目的関数
2020102073.tif 000016
の値ができるだけ最適となる解を見つける非凸スパース最適化問題を考える。以下、本実施形態では、目的関数
2020102073.tif 000017
の値が小さいほど最適であり、当該値ができるだけ小さくなるような解を見つける非凸スパース最適化問題を考える場合を例に説明する。
【００２６】
この問題は、下記式（１）のように定式化できる。
【００２７】
【数１】
2020102073.tif 000018
【００２８】
この問題に対する多段階貪欲法の詳細を図２に示す。図２は、本発明の実施の形態に係る高速スパース最適化処理のアルゴリズムの一例を示す図である。
【００２９】
図２に示すアルゴリズムは、許容される非ゼロ要素の数である所定数ｋ、目的関数ｌ（・）、及び事前に定められたｍ個の正整数である追加上限数ｂ１，...，ｂｍであり、
2020102073.tif 000019
を満たすものを入力とし、解であるベクトル
2020102073.tif 000020
を出力する。
【００３０】
通常の貪欲法では、非ゼロとなることを許容することで、最も目的関数
2020102073.tif 000021
の値が小さくなる添字を繰り返し追加する。すなわち、現在の解Ｓに対し、下記式（２）で示す添字Ｆｊが最小となる
2020102073.tif 000022
を各反復で選んで解Ｓに追加するという手続きを取る。
【００３１】
【数２】
2020102073.tif 000023
【００３２】
一方、多段階貪欲法では、ｉ反復目には添字Ｆｊの値が小さい順にｂｉの添字を集合Ｕから選択し、その添字の集合
2020102073.tif 000024
をＳに追加する。ここで、繰り返し回数毎に予め定められた追加上限数ｂｉは１以上であり、かつ、追加上限数ｂ１，...，ｂｍのうち少なくとも１つの追加上限数ｂｉは２以上とする。
【００３３】
このように、各反復で非ゼロ要素の添字をまとめて追加することにより、Ｆｊの値を計算する手間を削減し、通常の貪欲法よりも高速な動作を実現する。
【００３４】
＜本発明の実施の形態に係る高速スパース最適化装置の構成＞
図１を参照して、本発明の実施の形態に係る高速スパース最適化装置１０の構成について説明する。図１は、本発明の実施の形態に係る高速スパース最適化装置１０の構成を示すブロック図である。
【００３５】
高速スパース最適化装置１０は、ＣＰＵと、ＲＡＭと、後述する高速スパース最適化処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。
【００３６】
図１に示すように、本実施形態に係る高速スパース最適化装置１０は、入力部１１０と、主処理部１２０と、計算部１３０と、判定部１４０と、出力部１５０とを備えて構成される。
【００３７】
入力部１１０は、目的関数
2020102073.tif 000025
、非ゼロ要素の所定数ｋ、繰り返し回数毎の追加上限数ｂ１〜ｂｍ、及び変数ベクトル
2020102073.tif 000026
の添字の集合［ｄ］の入力を受け付ける。
【００３８】
ここで、繰り返し回数毎に予め定められた追加上限数ｂｉは１以上であり、かつ、追加上限数ｂ１，...，ｂｍのうち少なくとも１つの追加上限数ｂｉは２以上であり、
2020102073.tif 000027
を満たす。
【００３９】
そして、入力部１１０は、受け付けた目的関数
2020102073.tif 000028
、非ゼロ要素の所定数ｋ、繰り返し回数毎の追加上限数ｂ１〜ｂｍ、及び添字の集合［ｄ］を、主処理部１２０に渡す。また、入力部１１０は、目的関数
2020102073.tif 000029
を計算部１３０に渡し、繰り返し回数毎の追加上限数ｂ１〜ｂｍの個数ｍを、判定部１４０に渡す。
【００４０】
主処理部１２０は、追加上限数ｂｉの総和が所定数ｋとなるように繰り返し回数ｉ毎に予め定められた追加上限数ｂｉだけ、非ゼロの要素の集合Ｓに要素を追加したときの目的関数
2020102073.tif 000030
の最適値が最適な順に、当該追加した要素ｊを選択し、非ゼロの要素の集合Ｓに追加する。
【００４１】
具体的には、主処理部１２０は、まず、非ゼロの要素の集合Ｓを
2020102073.tif 000031
とし、集合Ｓに含まれない要素の添字からなる添字集合Ｕを添字の集合［ｄ］に初期化する。
【００４２】
次に、主処理部１２０は、初期化した非ゼロの要素の集合Ｓ及び添字集合Ｕを、計算部１３０に渡す。
【００４３】
主処理部１２０は、計算部１３０により得られた、非ゼロの要素の集合Ｓに含まれない要素ｊ毎の最適値Ｆｊを受け取ると、最適値Ｆｊが小さい順に、追加した要素ｊを追加上限数ｂｉ番目まで選択し、選択した要素ｊの集合Ｂｉを、前回求められた非ゼロの要素の集合Ｓに追加する。また、主処理部１２０は、非ゼロの要素の集合Ｓに追加した集合Ｂｉに含まれる要素ｊを、添字集合Ｕから削除する。
【００４４】
そして、主処理部１２０は、目的関数
2020102073.tif 000032
、繰り返し回数毎の追加上限数ｂ１〜ｂｍ、非ゼロの要素の集合Ｓ、及び添字集合Ｕを判定部１４０に渡す。
【００４５】
計算部１３０は、前回求められた非ゼロの要素の集合Ｓ又は非ゼロの要素の集合Ｓの初期値に対して、非ゼロの要素の集合Ｓに含まれない要素ｊを追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、目的関数
2020102073.tif 000033
の最適値を、非ゼロの要素の集合Ｓに含まれない要素ｊの各々について計算する。
【００４６】
具体的には、計算部１３０は、入力部１１０から取得した目的関数
2020102073.tif 000034
と、主処理部１２０又は判定部１４０から取得した非ゼロの要素の集合Ｓ、及び添字集合Ｕとに基づいて、当該添字集合Ｕに含まれる要素ｊの各々について、上記式（２）を計算し、目的関数
2020102073.tif 000035
の最適値Ｆｊを求める。
【００４７】
そして、計算部１３０は、添字集合Ｕに含まれる要素ｊの各々について、目的関数
2020102073.tif 000036
の最適値Ｆｊを、主処理部１２０に渡す。
【００４８】
判定部１４０は、予め定められた繰り返し回数ｍだけ、計算部１３０による計算と、主処理部１２０による選択及び追加とを繰り返させる。
【００４９】
具体的には、判定部１４０は、繰り返し回数がｍ以上であるか否かを判定する。
【００５０】
繰り返し回数がｍ以上でない場合、判定部１４０は、非ゼロの要素の集合Ｓ、及び添字集合Ｕを計算部１３０に渡し、計算部１３０による計算と、主処理部１２０による選択及び追加とを繰り返させる。
【００５１】
一方、繰り返し回数がｍ以上である場合、判定部１４０は、目的関数
2020102073.tif 000037
、繰り返し回数毎の追加上限数ｂ１〜ｂｍ、非ゼロの要素の集合Ｓ、及び添字集合Ｕを出力部１５０に渡す。
【００５２】
出力部１５０は、非ゼロの要素の集合Ｓのみ非ゼロの要素となることを許容した際における、目的関数
2020102073.tif 000038
の値が最適となる変数ベクトル
2020102073.tif 000039
の値を出力する。
【００５３】
具体的には、出力部１５０は、まず、目的関数
2020102073.tif 000040
、及び非ゼロの要素の集合Ｓに基づいて、下記式（３）を用いて、非ゼロの要素の集合Ｓのみ非ゼロの要素となることを許容した際における、目的関数
2020102073.tif 000041
の値が最小となる変数ベクトル
2020102073.tif 000042
の値を算出する。
【００５４】
【数３】
2020102073.tif 000043
【００５５】
そして、出力部１５０は、算出した目的関数
2020102073.tif 000044
の値が最小となる変数ベクトル
2020102073.tif 000045
の値を出力する。
【００５６】
図３、４に本実施形態に係る高速スパース最適化装置１０（多段階貪欲法）を用いた実行結果と、非特許文献１〜４の各手法を、悪条件な問題に適用した場合の実行結果を示す。図３は、許容する非ゼロ成分の上限である所定数ｋを変化させた場合の所定数ｋと実行時間（Ｒｕｎｎｉｎｇ  ｔｉｍｅ）との関係を示し、図４は、所定数ｋを変化させた場合の所定数ｋと訓練誤差（Ｔｒａｉｎｉｎｇ  ｅｒｒｏｒ）との関係を示す。図４では、訓練誤差が小さい程、解の質が良いことを表す。
【００５７】
図３、４において、四角、菱形、三角を含む線が高速な手法（非特許文献１〜３）における実験結果であり、丸を含む実線は通常の貪欲法（非特許文献４）における実験結果である。
【００５８】
また、図３、４において、丸を含む点線２種が、多段階貪欲法を用いた実験結果であり、繰り返し回数ｍの決め方に応じて２つの結果が得られている。
【００５９】
図３によれば、本実施形態に係る手法である多段階貪欲法は、いずれも貪欲法より高速であり、高速な手法のうちの１つ（非特許文献１）と同等あるいはそれ以上に高速に動作していることが分かる。
【００６０】
一方で、図４によれば、解の質は丸を含む実線の貪欲法に若干劣るものの、他の高速な手法に比べて質の良い解を出力していることがわかる。
【００６１】
以上のように、本実施形態に係る高速スパース最適化装置１０によって、悪条件な問題に対し良質な解を効率的に計算することができることが分かった。
【００６２】
＜本発明の実施の形態に係る高速スパース最適化装置の作用＞
図５は、本発明の実施の形態に係る高速スパース最適化処理ルーチンを示すフローチャートである。
【００６３】
入力部１１０に目的関数
2020102073.tif 000046
、非ゼロ要素の所定数ｋ、繰り返し回数毎の追加上限数ｂ１〜ｂｍ、及び変数ベクトル
2020102073.tif 000047
の添字の集合［ｄ］が入力されると、高速スパース最適化装置１０において、図５に示す高速スパース最適化処理ルーチンが実行される。
【００６４】
まず、ステップＳ１００において、入力部１１０は、目的関数
2020102073.tif 000048
、非ゼロ要素の所定数ｋ、繰り返し回数毎の追加上限数ｂ１〜ｂｍ、及び変数ベクトル
2020102073.tif 000049
の添字の集合［ｄ］の入力を受け付ける。
【００６５】
ステップＳ１１０において、主処理部１２０は、まず、非ゼロの要素の集合Ｓを
2020102073.tif 000050
とし、添字集合Ｕを添字の集合［ｄ］に初期化する。
【００６６】
ステップＳ１２０において、判定部１４０は、ｉ＝１とする。ここで、ｉは繰り返し回数を数えるカウンタである。
【００６７】
ステップＳ１３０において、計算部１３０は、前回求められた非ゼロの要素の集合Ｓ又は非ゼロの要素の集合Ｓの初期値に対して、非ゼロの要素の集合Ｓに含まれない要素ｊを追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、目的関数
2020102073.tif 000051
の最適値を、非ゼロの要素の集合Ｓに含まれない要素ｊの各々について計算する。
【００６８】
ステップＳ１４０において、主処理部１２０は、最適値Ｆｊが小さい順に、追加した要素ｊを追加上限数ｂｉ番目まで選択し、選択した要素ｊの集合Ｂｉを、前回求められた非ゼロの要素の集合Ｓに追加する。
【００６９】
ステップＳ１５０において、主処理部１２０は、上記ステップＳ１４０により非ゼロの要素の集合Ｓに追加した集合Ｂｉに含まれる要素ｊを、添字集合Ｕから削除する。
【００７０】
ステップＳ１６０において、判定部１４０は、ｉがｍ以上であるか否かを判定する。
【００７１】
ｉがｍ以上でない場合（上記ステップＳ１６０のＮＯ）、ステップＳ１７０において、判定部１４０は、ｉに１を加算し、ステップＳ１３０に戻る。
【００７２】
一方、ｉがｍ以上である場合（上記ステップＳ１６０のＹＥＳ）、ステップＳ１８０において、出力部１５０は、目的関数
2020102073.tif 000052
、及び非ゼロの要素の集合Ｓに基づいて、上記式（３）を用いて、非ゼロの要素の集合Ｓのみ非ゼロの要素となることを許容した際における、目的関数
2020102073.tif 000053
の値が最小となる変数ベクトル
2020102073.tif 000054
の値を算出する。
【００７３】
ステップＳ１９０において、出力部１５０は、上記ステップＳ１８０により算出した目的関数
2020102073.tif 000055
の値が最小となる変数ベクトル
2020102073.tif 000056
の値を出力する。
【００７４】
以上説明したように、本発明の実施形態に係る高速スパース最適化装置によれば、前回求められた非ゼロの要素の集合又は非ゼロの要素の集合の初期値に対して、非ゼロの要素の集合に含まれない要素を追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、目的関数の最適値を、非ゼロの要素の集合に含まれない要素の各々について計算し、追加上限数の総和が所定数となるように繰り返し回数毎に予め定められた追加上限数だけ、目的関数の最適値が最適な順に、追加した要素を選択し、非ゼロの要素の集合に追加することを繰り返し、非ゼロの要素の集合のみ非ゼロの要素となることを許容した際における、目的関数の値が最適となる前記変数ベクトルの値を出力することにより、悪条件な問題に対しても、高速に質の良い非凸スパース最適化問題の解を求めることができる。
【００７５】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７６】
上述した実施形態では、目的関数
2020102073.tif 000057
が最小である場合に最適となる場合を例に説明したが、これに限定されるものではなく、目的関数
2020102073.tif 000058
が最大である場合に最適となる場合にも適用することができる。
【００７７】
この場合、計算部１３０は、下記式（４）を用いて、前回求められた非ゼロの要素の集合Ｓ又は非ゼロの要素の集合の初期値に対して、非ゼロの要素の集合Ｓに含まれない要素ｊを追加した集合に含まれる要素のみ非ゼロの要素となることを許容した際における、目的関数
2020102073.tif 000059
の最適値を、非ゼロの要素の集合に含まれない要素ｊの各々について計算する。
【００７８】
【数４】
2020102073.tif 000060
【００７９】
また、この場合、主処理部１２０は、追加上限数ｂｉだけ、目的関数
2020102073.tif 000061
の最適値が大きい順に、追加した要素ｊを選択し、非ゼロの要素の集合Ｓに追加する。
【００８０】
そして、出力部１５０は、目的関数
2020102073.tif 000062
、及び非ゼロの要素の集合Ｓに基づいて、下記式（５）を用いて、非ゼロの要素の集合Ｓのみ非ゼロの要素となることを許容した際における、目的関数
2020102073.tif 000063
の値が最大となる変数ベクトル
2020102073.tif 000064
の値を算出する。
【００８１】
【数５】
2020102073.tif 000065
【００８２】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００８３】
１０   高速スパース最適化装置
１１０ 入力部
１２０ 主処理部
１３０ 計算部
１４０ 判定部
１５０ 出力部
【図１】
2020102073.tif 000066
【図２】
2020102073.tif 000067
【図３】
2020102073.tif 000068
【図４】
2020102073.tif 000069
【図５】
2020102073.tif 000070