離散構造の凸近似に関する研究

離散最適化問題は,生産計画,ロジスティクス,システム設計,ファイナンスなどの様々な応用分野で現れるが,最適解を効率的に求めることは多くの場合に困難である.本研究では,研究代表者によって提唱された離散凸解析という理論体系を踏まえて,非線形離散関数の離散凸関数による近似の理論構築を目的とした.さらに,この離散凸近似理論を基にして,非線形目的関数に関する離散最適化問題という扱いにくい問題を,離散凸関数最小化という扱いやすい問題で繰り返し近似して解くという新たなアプローチを提案する.しかし離散凸関数最小化は,連続凸関数の場合と異なり,より詳細な細分化を行わないと,扱いやすい問題が得られない.離散凸近似による効率的な最適化アプローチの実現には,離散凸関数の細分化の緻密さと,与えられた非線形目的関数に対してどの離散凸性による近似を採用するかが,重要な鍵となる.このため,本年度行った具体的な研究内容は以下の通りである.・これまで離散凸解析で扱ってきたM凸性という概念を,ジャンプシステム上で定義された関数にまで拡張した.ジャンプシステム上のM凸関数最小化問題に対する最適性規準を導出した.・離散関数に対するヘッセ行列および局所2次展開の概念を導入し,これらを用いたL凸関数およびM凸関数の特徴づけを与えた.この特徴づけは,連続凸関数に対する特徴づけとよく対応している.さらに,離散凸解析とは独立して研究されてきたmultimodularityという概念が,実質的にL凸性と等価な概念であることを,L凸関数の特徴づけを用いて簡単に示した.・上記の結果に基づき,2次のL凸,M凸関数を用いた凸近似手法を構築した.さらに,一般のL凸,M凸関数による最良凸近似について検討を行った.

離散最適化問題は,生産計画,ロジスティクス,システム設計,ファイナンスなどの様々な応用分野で現れるが,最適解を効率的に求めることは多くの場合に困難である.本研究では,研究代表者によって提唱された離散凸解析という理論体系を踏まえて,非線形離散関数の離散凸関数による近似の理論構築を目的とした.さらに,この離散凸近似理論を基にして,非線形目的関数に関する離散最適化問題という扱いにくい問題を,離散凸関数最小化という扱いやすい問題で繰り返し近似して解くという新たなアプローチを提案する.しかし離散凸関数最小化は,連続凸関数の場合と異なり,より詳細な細分化を行わないと,扱いやすい問題が得られない.離散凸近似による効率的な最適化アプローチの実現には,離散凸関数の細分化の緻密さと,与えられた非線形目的関数に対してどの離散凸性による近似を採用するかが,重要な鍵となる.このため,本年度行った具体的な研究内容は以下の通りである.・これまで離散凸解析で扱ってきたM凸性という概念を,ジャンプシステム上で定義された関数にまで拡張した.ジャンプシステム上のM凸関数最小化問題に対する最適性規準を導出した.・離散関数に対するヘッセ行列および局所2次展開の概念を導入し,これらを用いたL凸関数およびM凸関数の特徴づけを与えた.この特徴づけは,連続凸関数に対する特徴づけとよく対応している.さらに,離散凸解析とは独立して研究されてきたmultimodularityという概念が,実質的にL凸性と等価な概念であることを,L凸関数の特徴づけを用いて簡単に示した.・上記の結果に基づき,2次のL凸,M凸関数を用いた凸近似手法を構築した.さらに,一般のL凸,M凸関数による最良凸近似について検討を行った.