A framework of discrete DC programming by discrete convex analysis
A framework of discrete DC programming by discrete convex analysis
复制标题
DOI：
10.1007/s10107-014-0792-y
复制
发表时间：
2014-07
影响因子：
2.7
通讯作者：
Takanori Maehara;K. Murota
中科院分区：
文献类型：
--
作者：
Takanori Maehara;K. Murota
建立了离散凸函数（离散DC函数）的差分和离散DC函数优化问题的理论框架。利用离散凸分析将连续DC理论中的标准结果导出到离散DC理论中。提出了一种离散DC算法，它是连续DC算法（机器学习中的凹凸过程）的离散模拟。该算法包含子模-超模过程作为特殊情况。利用离散凸函数的多面体结构，提出了适合于特定类型离散DC函数的算法。
A theoretical framework of difference of discrete convex functions (discrete DC functions) and optimization problems for discrete DC functions is established. Standard results in continuous DC theory are exported to the discrete DC theory with the use of discrete convex analysis. A discrete DC algorithm, which is a discrete analogue of the continuous DC algorithm (Concave–Convex procedure in machine learning) is proposed. The algorithm contains the submodular-supermodular procedure as a special case. Exploiting the polyhedral structure of discrete convex functions, the algorithms tailored to specific types of discrete DC functions are proposed.