000000171 001 __ 171
000000171 005 __20140222171329.0
000000171 035 __ $a 00255610v83n3p313
000000171 041 0_ $a eng
000000171 100 1_ $a Murota, Kazuo
000000171 245 10 $a Discrete convex analysis
000000171 520 3_ $a 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..
000000171 599 __ $a recerca
000000171 653 1_ $a Convex analysis
000000171 653 1_ $a Combinatorial optimization
000000171 653 1_ $a Discrete separation theorem
000000171 653 1_ $a Integer programming
000000171 653 1_ $a Lagrange duality
000000171 653 1_ $a Submodular function
000000171 655 _4 $a Article
000000171 655 _4 $a info:eu-repo/semantics/article
000000171 655 _4 $a info:eu-repo/semantics/publishedVersion
000000171 773 __ $g vol. 83 n. 3 (1998) p. 313-371 $t Mathematical Programming $x 0025-5610
000000171 856 4_ $p 59 $s 2349166 $u http://ddd.uab.cat/uab/matpro/00255610v83n3p313.pdf
000000171 973 __ $f 313 $l 371 $m 11 $n 3 $v 83 $x 00255610v83n3 $y 1998
000000171 980 __ $a ARTPUB