Exploitation of Applications of Discrete Convex Analysis

该研究项目的主要目的是开发由首席研究员在过去十年中提出的离散凸分析理论的应用。在这个研究项目中，我们得到了如下的各种结果。所有的研究结果都在国际会议上发表，或在国际科学期刊上发表。(1)在数理经济学领域，作为离散凸分析的应用，我们得到了三个结果。首先，我们发展了一个具有不可分割商品的经济均衡模型理论；特别地，我们研究了商品不可分割交换经济中竞争均衡存在的充分条件。其次，我们给出了在离散凸分析中起核心作用的m -凸函数的新表征。这些特征是基于数学经济学中众所周知的概念，如总替代条件和单一改进条件。第三，我们开发了一种算法，用于计算商品不可分割的交换经济中的竞争均衡。该算法基于离散凸分析中的优化问题m -凸次模流问题。(2)给出了m -凸函数最小化的邻近定理，并开发了快速算法。(3)从离散凸分析的角度讨论了工程系统中的组合结构。特别地，我们研究了以确定电路可解性为目的的三角矩阵宇称问题，并开发了一种有效的算法。(4)我们验证了离散凸分析算法在运筹学中若干问题的适用性。在此基础上，我们开发了求解网络设计问题和最大割问题的有效算法。

The main aim of this research project is to exploit applications of the theory of discrete convex analysis proposed by the head investigator in the last decade. In this research project, we obtained various results described below. All of the results are presented at refereed international conferences and/ or accepted for publications in international scientific journals.(1) In the area of mathematical economics we obtained three results as applications of discrete convex analysis. First of all, we developed a theory for economic equilibrium models with indivisible goods ; in particular, we investigated sufficient conditions for the existence of competitive equilibrium in an exchange economy with indivisible goods. Secondly, we provide new characterizations of M-convex functions which play a central role in discrete convex analysis. These characterizations are based on well-known concepts in mathematical economics such as the gross substitutes condition and the single improvement condition. Thirdly, we developed an algorithm for computing a competitive equilibrium in an exchange economy with indivisible goods. This algorithm is based on M-convex submodular flow problem which is an optimization problem in discrete convex analysis.(2) We showed a proximity theorem for M-convex function minimization and developed fast algorithms.(3) We discussed combinatorial structure in engineering system from the viewpoint of discrete convex analysis. In particular, we investigated the delta matroid parity problem with the aim of determining the solvability of electrical circuits, and developed an efficient algorithm.(4) We verified applicability of the algorithms in discrete convex analysis to several problems in operations research. Based on this result, we developed efficient algorithms for the network design problem and the max cut problem.