Establishment of Discrete Convexity Paradigm

本研究计划的主要目的是透过将离散凸分析理论应用于经济学、系统工程、运筹学、优化、演算法科学等领域的基本问题，建立一个新的离散凸性范例。在这个研究项目中，我们获得了以下一些结果。所有研究结果均在国际学术会议上发表，或在国际科学期刊上发表。(1)对于与离散凸性相关的优化问题（特别是具有m -凸代价函数的次模流问题），我们使用容量缩放技术开发了许多有效的算法。所得算法具有已知的最大复杂度界。(2)我们指出了独立于离散凸分析的多模函数的概念本质上等同于l -凸函数的概念。在这个观察的基础上，我们得到了一些性质，包括离散分离。(3)揭示了m -凸函数与树度量之间的密切关系。具体地说，我们证明了二次m -凸函数的Hessian矩阵本质上与树度量矩阵的负数相同。(4)建立了积分凸集上函数的离散不动点定理。这个定理在数学经济学和博弈论中都有应用。(5)根据数学经济学中已知的总替换和单改进性质，给出了m -凸函数的新表征。(6)作为离散凸分析在数理经济学中的应用，我们建立了一个具有不可分商品的经济均衡模型理论。我们还利用m -凸子模流问题的框架开发了一种计算竞争均衡的算法。

The main aim of this research project is to establish a novel paradigm of discrete convexity by exploiting applications of the theory of discrete convex analysis to fundamental problems in economics, system engineering, operations research, optimization, algorithm science, and others. In this research project, we obtained a number of results described below. All of the results are presented at refereed international conference or accepted for publications in international scientific journals.(1)For optimization problems related to discrete convexity (in particular, for the submodular flow problem with M-convex cost function), we developed a number of efficient algorithms using the capacity scaling technique. The obtained algorithm has the best known complexity bound.(2)We pointed out that the concept of multimodular functions, which had been conceived independently of discrete convex analysis, is essentially equivalent to the concept of L-convex functions. On the basis of this observation we derived some properties including discrete separation.(3)We revealed a close relationship between M-convex functions and tree metrics. Specifically, we proved that the Hessian matrix of a quadratic M-convex function is essentially the same as the negative of the tree metric matrix.(4)We established a discrete fixed point theorem for functions defined on integrally convex sets. The theorem finds applications in mathematical economics and game theory.(5)We provided new characterizations of M-convex functions in terms of gross substitution and single improvement property known in mathematical economics.(6)As applications of discrete convex analysis to mathematical economics, we developed a theory for economic equilibrium models with indivisible goods. We also developed an algorithm for computing a competitive equilibrium using the framework of M-convex submodular flow problem.