Discrete convex analysis(<Special Topics>Applied mathematics in optimization problem)

Bibliographic Information

Other Title
  • 離散凸解析(<特集>最適化の数理)
  • 離散凸解析
  • リサン トツカイセキ

Search this article

Description

A theory of "discrete convex analysis" is developed for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, subgradients, the Fenchel min-max duality, separation theorems and the Lagrange duality framework for convex/nonconvex optimization. The technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms. This paper extends our understanding of the relationship between convex functions and submodular functions investigated in the eighties by A. Frank, S. Fujishige, L. Lovasz and others, and also explores a novel duality framework in nonlinear integer programming.

Journal

Citations (1)*help

See more

References(12)*help

See more

Details 詳細情報について

Report a problem

Back to top