权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

离散结构凸逼近研究

基本信息

批准号：
16654019
负责人：
室田一雄
金额：
$ 2.24万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Exploratory Research
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2005
项目状态：
已结题

项目摘要

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

Discrete optimization problems, production planning, system design, optimization problems, etc. This study aims at the theoretical construction of discrete convex relations approximation for nonlinear discrete relations. In this paper, the discrete convex approximation theory is based on the discrete optimization problem of nonlinear objective function minimization. The problem of minimizing the discrete convex number is solved in detail. The optimization of discrete convexity approximation is an important key to the realization of the subdivision of discrete convexity and the application of discrete convexity approximation to nonlinear object relations. This year's specific research content is as follows: The concept of discrete convexity is defined in terms of number. The optimal criterion for minimizing the number of M-convexities on the top of the list is derived. The concept of the second expansion of discrete relations is introduced, and the characteristics of L convex relations and M convex relations are discussed. This feature is not unique, but it is unique. In this paper, discrete convex analysis and independence are studied. The concept of multimodularity and equality is discussed. The concept of L convexity and equality is discussed. In the above results, the L-convex and M-convex numbers of the second order are constructed by using the convex approximation method. In this paper, the general L convex,M convex number of the best convex approximation is discussed.