A framework of discrete DC programming by discrete convex analysis

• 成果类型: Article
• 署名作者: Maehara, Takanori; Murota, Kazuo
• 署名单位: Japan Science & Technology Agency (JST); Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan; University of Tokyo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0792-y
• 发表日期: 2015
• 页码: 435-466
• 关键词: valuated matroid intersection; submodular function; optimization; Duality

摘要

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.