171
20140614130853.0
00255610v83n3p313
eng
Murota, Kazuo
Discrete convex analysis
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. Sections 1-4 extend the conjugacy relationship between submodularity and exchange ability, deepening our understanding of the relationship between convexity and submodularity investigated in the eighties by A. Frank, S. Fujishige, L. Lovász and others. Sections 5 and 6 establish duality theorems for M- and L-convex functions, namely, the Fenchel min-max duality and separation theorems. These are the generalizations of the discrete separation theorem for submodular functions due to A. Frank and the optimality criteria for the submodular flow problem due to M. Iri-N. Tomizawa, S. Fujishige, and A. Frank. A novel Lagrange duality framework is also developed in integer programming. We follow Rockafellar's conjugate duality approach to convex/nonconvex programs in nonlinear optimization, while technically relying on the fundamental theorems of matroid-theoretic nature..
Anglès.
recerca
Convex analysis
Combinatorial optimization
Discrete separation theorem
Integer programming
Lagrange duality
Submodular function
Article
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
vol. 83 n. 3 (1998) p. 313-371
Mathematical Programming
0025-5610
59
2349166
http://ddd.uab.cat/uab/matpro/00255610v83n3p313.pdf
313
371
11
3
83
00255610v83n3
1998
ARTPUB