×

zbMATH — the first resource for mathematics

Discrete convex analysis. (English) Zbl 0920.90103
Summary: 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.

MSC:
90C10 Integer programming
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R.E. Bixby, W.H. Cunningham, Matroid optimization and algorithms, in: R.L. Graham, M. Grötschel, L. Lovász (Eds.), Handbook of Combinatorics, vol. I, Chap. 11, Elsevier, Amsterdam, 1995, pp. 551–609. · Zbl 0848.05017
[2] A. Bouchet, W.H. Cunningham, Delta-matroids, jump systems and bisubmodular polyhedra, SIAM J. Discrete Math. 8 (1995) 17–32. · Zbl 0821.05010
[3] V. Chvátal, Linear Programming, Freeman, New York, 1983.
[4] A.W.M. Dress, W. Terhalle, Well-layered maps–A class of greedily optimizable set functions, Appl. Math. Lett. 8 (1995) 77–80. · Zbl 0853.05025
[5] A.W.M. Dress, W. Terhalle, Well-layered maps and the maximum-degreek{\(\times\)}k-subdeterminant of a matrix of rational functions, Appl. Math. Lett. 8 (1995) 19–23. · Zbl 0824.15023
[6] A.W.M. Dress, W. Tehalle, Rewarding maps–On greedy optimization of set functions, Adv. in Appl. Math. 16 (1995) 464–483. · Zbl 0851.65044
[7] A.W.M. Dress, W. Wenzel, Valuated matroid: A new look at the greedy algorithm, Appl. Math. Lett. 3 (1990) 33–35. · Zbl 0701.05014
[8] A.W.M. Dress, W. Wenzel, Valuated matroids, Adv. in Math. 93 (1992) 214–250. · Zbl 0754.05027
[9] J. Edmonds, Submodular functions, matroids and certain polyhedra, in: R. Guy, H. Hanani, N. Sauer, J. Schönheim (Eds.), Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970, pp. 69–87. · Zbl 0268.05019
[10] J. Edmonds, Matroid intersection, Ann. Discrete Math. 14 (1979) 39–49. · Zbl 0416.05025
[11] U. Faigle, Matroids in combinatorial optimization, in: N. White (Ed.), Combinatorial Geometries, Cambridge University Press, London, 1987, pp. 161–210. · Zbl 0632.05018
[12] P. Favati, F. Tardella, Convexity in nonlinear integer programming, Ricerca Operativa 53 (1990) 3–44.
[13] A. Frank, A weighted matroid intersection algorithm, J. Algorithms 2 (1981) 328–336. · Zbl 0484.05025
[14] A. Frank, An algorithm for submodular functions on graphs. Ann. Discrete Math. 16 (1982) 97–120. · Zbl 0504.05059
[15] A. Frank, E. Tardos, Generalized polymatroids and submodular flows, Math. Programming 42 (1988) 489–563. · Zbl 0665.90073
[16] S. Fujishige, Algorithms for solving the independent-flow problems, J. Oper. Res. Soc. Japan 21 (1978) 189–204. · Zbl 0388.05007
[17] S. Fujishige, Theory of submodular programs: A Fenchel-type min-max theorem and subgradients of submodular functions, Math. Programming 29 (1984) 142–155. · Zbl 0537.49005
[18] S. Fujishige, On the subdifferential of a submodular function, Math. Programming 29 (1984), 348–360. · Zbl 0543.90094
[19] S. Fujishige, Submodular Functions and Optimization, Annals of Discrete Mathematics, vol. 47, North-Holland, Amsterdam, 1991. · Zbl 0728.90056
[20] S. Fujishige, K. Murota, On the relationship between L-convex functions and submodular integrally convex functions, RIMS Preprint 1152, Kyoto University, August 1997.
[21] S. Fujishige, K. Murota, Short proofs of the separation theorems for L-convex/concave and M-convex/concave functions, RIMS Preprint 1167, Kyoto University, October 1997.
[22] D.S. Hochbaum, Lower and upper bounds for the allocation problem and other nonlinear optimization problems, Math. Oper. Res. 19 (1994) 390–409. · Zbl 0820.90082
[23] D.S. Hochbaum, S.-P. Hong, About strongly polynomial time algorithms for quadratic optimization over submodular constraints, Math. Programming 69 (1995) 269–309. · Zbl 0844.90061
[24] D.S. Hochbaum, R. Shamir, J.G. Shanthikumar, A polynomial algorithm for an integer quadratic nonseparable transporation problem, Math. Programming 55 (1992) 359–372. · Zbl 0761.90061
[25] M. Iri, N. Tomizawa, An algorithm for finding an optimal ’independent assignment’, J. Oper. Res. Soc. Japan 19 (1976) 32–57. · Zbl 0346.90062
[26] J. Kindler, Sandwich theorems for set functions, J. Math. Anal. Appl. 133 (1988) 529–542. · Zbl 0664.28001
[27] B. Korte, L. Lovász, R. Schrader, Greedoids, Springer, Berlin, 1991.
[28] S. Krogdahl, The dependence graph for bases in matroids. Discrete Math. 19 (1977) 47–59. · Zbl 0366.05024
[29] J.P.S. Kung, Basis-exchange properties, in: N. White (Ed.), Theory of Matroids, Chap. 4, Cambridge University Press, London, 1986, pp. 62–75. · Zbl 0587.05018
[30] E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976. · Zbl 0413.90040
[31] L. Lovász, Submodular functions and convexity, in: A. Bachem, M. Grötschel, B. Korte (Eds.), Mathematical Programming–The State of the Art, Springer, Berlin, 1983, pp. 235–257.
[32] M. Minoux, Solving integer minimum cost flows with separable convex objective polynomially, Math. Programming 26 (1986), 237–239. · Zbl 0588.90027
[33] K. Murota, Finding optimal minors of valuated bimatroids, Appl. Math. Lett. 8 (1995) 37–42. · Zbl 0833.05017
[34] K. Murota, Valuated matroid intersection, I: Optimality criteria, SIAM J. Discrete Math. 9 (1996) 545–561. · Zbl 0868.90132
[35] K. Murota, Valuated matroid intersection, II: Algorithms, SIAM J. Discrete Math. 9 (1996) 562–576. · Zbl 0868.90133
[36] K. Murota, Fenchel-type duality for matroid valuations, Math. Programming 82 (1998) 357–375. · Zbl 0920.90124
[37] K. Murota, Submodular flow problem with a nonseparable cost function, Report No. 95843-OR, Forschungsinstitut für Diskrete Mathematik, Universität Bonn, 1995. · Zbl 0947.90119
[38] K. Murota, Convexity and Steinitz’s exchange property, Adv. in Math. 124 (1996) 272–311. · Zbl 0867.90092
[39] K. Murota, Convexity and Steinitz’s exchange property (Extended abstract), in: W. H. Cunningham, S.T. McCormick, M. Queyranne (Eds.), Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 1084, Springer, Heidelberg, 1996, pp. 260–274. · Zbl 0867.90092
[40] K. Murota, A. Shioura, M-convex function on generalized polymatroid, Research Reports on Mathematical and Computing Sciences, Tokyo Institute of Technology, B-320, September 1996. · Zbl 0971.90073
[41] G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd (Eds.), Optimization, Handbooks in Operations Research and Management Science, vol. 1, Elsevier, Amsterdam, 1989.
[42] G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988. · Zbl 0652.90067
[43] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[44] R.T. Rockafellar, Conjugate duality and optimization, in: SIAM Regional Conference Series in Applied Mathematics 16, SIAM, Philadelphia, 1974. · Zbl 0296.90036
[45] R.T. Rockafellar, Network Flows and Monotropic Optimization, Wiley, New York, 1984. · Zbl 0596.90055
[46] A. Schrijver, Total dual integrality from directed graphs, crossing families, and sub- and supermodular functions, in: W.R. Pulleyblank (Ed.), Progress in Combinatorial Optimization, Academic Press, New York, 1984, pp. 315–361. · Zbl 0542.90068
[47] A. Schrijver, Theory of Linear and Integer Programming, Wiley, New York, 1986. · Zbl 0665.90063
[48] A. Shioura, Minimization of an M-convex function, Discrete Appl. Math. 84 (1998) 215–220. · Zbl 0902.90133
[49] J. Stoer, C. Witzgall, Convexity and Optimization in Finite Dimensions I, Springer, Berlin, 1970. · Zbl 0203.52203
[50] N. Tomizawa, Theory of hyperspaces (I)–Supermodular functions and generalization of concept of ’bases’ [in Japanese], Papers of the Technical Group on Circuit and System Theory, Institute of Electronics and Communication Engineers of Japan, CAS80-72, 1980.
[51] N. Tomizawa, M. Iri, An algorithm for determining the rank of a triple matrix product AXB with application to the problem of discerning the existence of the unique solution in a network [in Japanese], Trans. Inst. Electr. Comm. Engin. Japan 57A (1974) 834–841; English translation: Electronics and Communications in Japan, 57A (1974) 50–57.
[52] D.M. Topkis, Minimizing a submodular function on a lattice, Oper. Res. 26 (1978) 305–321. · Zbl 0379.90089
[53] D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.