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

Discrete Optimization Algorithms based on Discrete Convex Analysis

基于离散凸分析的离散优化算法

基本信息

批准号：
10205212
负责人：
MUROTA Kazuo
金额：
$ 3.71万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

项目摘要

In the area of nonlinear programming, the theory of convex analysis provides a unified framework for well-solved problems. In the area of discrete optimization, on the other hand, we do not have such a unified framework. Matroidal structure, however, is known to be a well-behaved structure in discrete optimization. The theory of "discrete convex analysis" is proposed by the head investigator with a view to capturing the continuous optimization and the discrete optimization from a common viewpoint. Discrete convex analysis is a theoretical framework connecting the theory of convex analysis and the theory of matroids.It is often the case that discrete optimization problems appearing in the real world do not have nice combinatorial structure such as matroids. Therefore, we need to use enumeration-type algorithms such as the branch-and-bound method or approximation algorithms such as meta heuristics. In either approach, it is essential to extract tractable part from the discrete structure … More of the problems to be solved. For example, it is often effective to extract network-like structure as subproblems when we solve general discrete optimization problems.The fundamental idea of our research is to extract certain structure which can be dealt with discrete convex analysis as subproblems when we solve general discrete optimization problems. We summarize the main results as follows :・The concepts of M-convex and L-convex functions play a central role in the framework of discrete convex analysis. We showed various properties of these functions.・We proposed efficient algorithms for the minimization of M-convex functions.・We extended the concepts of M-convex and L-convex functions defined over the integer lattice to functions over the real space.・We generalized the concepts of M-convex and L-convex functions to quasi M-convex/L-convex functions.・We obtained some results on the application of discrete convex analysis to economic equilibrium such as the equivalence of gross substitutes property and M-convexity. Less

在非线性规划领域，凸分析理论为解决问题提供了统一的框架。另一方面，在离散优化领域，我们没有这样一个统一的框架。然而，众所周知，拟阵结构在离散优化中是一种表现良好的结构。首席研究员提出了“离散凸分析”理论，旨在从共同的角度捕捉连续优化和离散优化。离散凸分析是连接凸分析理论和拟阵理论的一个理论框架。现实世界中出现的离散优化问题常常不具有拟阵等良好的组合结构。因此，我们需要使用分支定界法等枚举型算法或元启发式等近似算法。无论哪种方法，都必须从离散结构中提取易于处理的部分……更多要解决的问题。例如，在解决一般离散优化问题时，提取网络状结构作为子问题往往是有效的。我们研究的基本思想是在解决一般离散优化问题时，提取某些可以进行离散凸分析的结构作为子问题。我们将主要结果总结如下：·M凸函数和L凸函数的概念在离散凸分析框架中发挥着核心作用。我们展示了这些函数的各种性质。・我们提出了最小化 M 凸函数的有效算法。・我们将整数格上定义的 M 凸和 L 凸函数的概念扩展到实空间上的函数。・我们将 M 凸和 L 凸函数的概念推广到拟 M 凸/L 凸函数・我们得到了一些关于离散凸分析在经济均衡中的应用的结果，例如总替代性和M凸的等价性。较少的