Discrete Convex Analysis（离散凸分析）.pdf-资料库

fae05ee3-8f97-4c4b-9731-3d276a798bd5.pdf-第1页.png

第1页 / 共412页

fae05ee3-8f97-4c4b-9731-3d276a798bd5.pdf-第2页.png

第2页 / 共412页

fae05ee3-8f97-4c4b-9731-3d276a798bd5.pdf-第3页.png

第3页 / 共412页

fae05ee3-8f97-4c4b-9731-3d276a798bd5.pdf-第4页.png

第4页 / 共412页

fae05ee3-8f97-4c4b-9731-3d276a798bd5.pdf-第5页.png

第5页 / 共412页

fae05ee3-8f97-4c4b-9731-3d276a798bd5.pdf-第6页.png

第6页 / 共412页

fae05ee3-8f97-4c4b-9731-3d276a798bd5.pdf-第7页.png

第7页 / 共412页

fae05ee3-8f97-4c4b-9731-3d276a798bd5.pdf-第8页.png

第8页 / 共412页

DISCRETE CONVEX ANALYSIS

SIAM Monographs on Discrete Mathematics and Applications The series includes advanced monographs reporting on the most recent theoretical, computational, or applied developments in the field; introductory volumes aimed at mathematicians and other mathematically motivated readers interested in understanding certain areas of pure or applied combinatorics; and graduate textbooks. The volumes are devoted to various areas of discrete mathematics and its applications. Mathematicians, computer scientists, operations researchers, computationally oriented natural and social scientists, engineers, medical researchers, and other practitioners will find the volumes of interest. Editor-in-Chief Peter L. Hammer, RUTCOR, Rutgers, The State University of New Jersey Editorial Board M. Aigner, Freie Universitat Berlin, Germany N. Alon, Tel Aviv University, Israel E. Balas, Carnegie Mellon University, USA J- C. Bermond, UniversitedeNice-SophiaAntipolis, France J. Berstel, Universite Marne-la-Vallee, France N. L. Biggs, The London School of Economics, United Kingdom B. Bollobas, University of Memphis, USA R. E. Burkard, Technische Universitat Graz, Austria D. G. Cornell, University of Toronto, Canada I. Gessel, Brandeis University, USA F. Glover, University of Colorado, USA M. C. Golumbic, Bar-Han University, Israel R. L. Graham, AT&T Research, USA A. J. Hoffman, IBM T. J. Watson Research Center, USA T. Ibaraki, Kyoto University, Japan H. Imai, University of Tokyo, Japan M. Karoriski, Adam Mickiewicz University, Poland, and Emory University, USA R. M. Karp, University of Washington, USA V. Klee, University of Washington, USA K. M. Koh, National University of Singapore, Republic of Singapore B. Korte, Universitat Bonn, Germany A. V. Kostochka, Siberian Branch of the Russian Academy of Sciences, Russia F. T. Leighton, Massachusetts Institute of Technology, USA T. Lengauer, Gesellschaft fur Mathematik und Datenverarbeitung mbH, Germany S. Martello, DEIS University of Bologna, Italy M. Minoux, Universite Pierre et Marie Curie, France R. Mb'hring, Technische Universitat Berlin, Germany C. L. Monma, Bellcore, USA J. Nesetril, Charles University, Czech Republic W. R. Pulleyblank, IBM T. J. Watson Research Center, USA A. Recski, Technical University of Budapest, Hungary C. C. Ribeiro, Catholic University of Rio de Janeiro, Brazil H. Sachs, Technische Universitat llmenau, Germany A. Schrijver, CWI, The Netherlands R. Shamir, Tel Aviv University, Israel N. J. A. Sloane, AT&T Research, USA W. T. Trotter, Arizona State University, USA D. J. A. Welsh, University of Oxford, United Kingdom D. de Werra, Ecole Polytechnique Federate de Lausanne, Switzerland P. M. Winkler, Bell Labs, Lucent Technologies, USA Yue Minyi, Academia Sinica, People's Republic of China Series Volumes Murota, K., Discrete Convex Analysis Toth, P. and Vigo, D., The Vehicle Routing Problem Anthony, M., Discrete Mathematics of Neural Networks: Selected Topics Creignou, N., Khanna, S., and Sudan, M., Complexity Classifications of Boolean Constraint Satisfaction Problems Hubert, L., Arable, P., and Meulman, J., Combinatorial Data Analysis: Optimization by Dynamic Programming Peleg, D., Distributed Computing: A Locality-Sensitive Approach Wegener, I., Branching Programs and Binary Decision Diagrams: Theory and Applications Brandstadt, A., Le, V. B., and Spinrad, J. P., Graph Classes: A Survey McKee, T. A. and McMorris, F. R., Topics in Intersection Graph Theory Grilli di Cortona, P., Manzi, C., Pennisi, A., Ricca, R, and Simeone, B., Evaluation and Optimization of Electoral Systems

DISCRETE CONVEX ANALYSIS KAZUO MUROTA University of Tokyo; PRESTO, JST Tokyo, Japan Society for Industrial and Applied Mathematics Philadelphia

Copyright © 2003 by the Society for Industrial and Applied Mathematics. 10 9 8 7 6 5 4 3 21 All rights reserved. Printed in the United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688. library of Congress Cataloging-in-Publication Data Murota, Kazuo, 1955- Discrete convex analysis / Kazuo Murota. p. cm. — (SIAM monographs on discrete mathematics and applications) Includes bibliographical references and index. ISBN 0-89871-540-7 1. Convex functions. 2. Convex sets. 3. Mathematical analysis. I. Title. II. Series. QA331.5.M87 2003 515'.8—dc21 2003042468 is a registered trademark.

Contents List of Figures Notation Preface 1 Introduction to the Central Concepts 1.1 1.2 1.3 1.4 Aim History Aim and History of Discrete Convex Analysis 1.1.1 1.1.2 Useful Properties of Convex Functions Submodular Functions and Base Polyhedra Submodular Functions 1.3.1 1.3.2 Base Polyhedra Discrete Convex Functions 1.4.1 1.4.2 1.4.3 1.4.4 1.4.5 L-Convex Functions M-Convex Functions Conjugacy Duality Classes of Discrete Convex Functions Bibliographical Notes 2 Convex Functions with Combinatorial Structures 2.1 2.2 2.3 Convex Quadratic Functions Symmetric M-Matrices Combinatorial Property of Conjugate Functions General Quadratic L-/M-Convex Functions Quadratic Functions 2.1.1 2.1.2 2.1.3 2.1.4 Nonlinear Networks 2.2.1 2.2.2 2.2.3 Substitutes and Complements in Network Flows 2.3.1 Real-Valued Flows Integer-Valued Flows Technical Supplements Convexity and Submodularity v xi xiii xxi 1 1 1 5 9 15 16 18 21 21 25 29 32 36 36 39 39 39 41 . . 47 51 52 52 56 58 61 61

vi Contents 2.3.2 2.4 Matroids 2.4.1 2.4.2 Bibliographical Notes Technical Supplements 63 68 Prom Matrices to Matroids 68 From Polynomial Matrices to Valuated Matroids . . 71 74 3 Convex Analysis, Linear Programming, and Integrality Convex Analysis Linear Programming Integrality for a Pair of Integral Polyhedra Integrally Convex Functions 3.1 3.2 3.3 3.4 Bibliographical Notes 4 M-Convex Sets and Submodular Set Functions Definition Exchange Axioms Submodular Functions and Base Polyhedra Polyhedral Description of M-Convex Sets Submodular Functions as Discrete Convex Functions 4.1 4.2 4.3 4.4 4.5 4.6 M-Convex Sets as Discrete Convex Sets 4.7 4.8 M-Convex Polyhedra Bibliographical Notes M^-Convex Sets 5 L-Convex Sets and Distance Functions 5.1 5.2 5.3 5.4 5.5 5.6 Bibliographical Notes Definition Distance Functions and Associated Polyhedra Polyhedral Description of L-Convex Sets L-Convex Sets as Discrete Convex Sets L^-Convex Sets L-Convex Polyhedra 6 M-Convex Functions Local Exchange Axiom Examples Basic Operations Supermodularity Descent Directions 6.1 M-Convex Functions and M^-Conyex Functions 6.2 6.3 6.4 6.5 6.6 6.7 Minimizers 6.8 6.9 6.10 Convex Extension 6.11 6.12 Polyhedral M-Convex Functions Positively Homogeneous M-Convex Functions Gross Substitutes Property Proximity Theorem 77 77 86 90 92 99 101 101 102 103 108 Ill 114 116 118 119 121 121 122 123 125 128 131 131 133 133 135 138 142 145 146 148 152 156 158 160 164

Contents 6.13 Directional Derivatives and Subgradients 6.14 Quasi M-Convex Functions Bibliographical Notes 7 L-Convex Functions and L''-Convex Functions Discrete Midpoint Convexity Examples Basic Operations L-Convex Functions 7.1 7.2 7.3 7.4 7.5 Minimizers 7.6 7.7 7.8 7.9 7.10 Directional Derivatives and Subgradients 7.11 Quasi L-Convex Functions Bibliographical Notes Proximity Theorem Convex Extension Polyhedral L-Convex Functions Positively Homogeneous L-Convex Functions 8 Conjugacy and Duality 8.1 8.2 Conjugacy 8.1.1 8.1.2 8.1.3 Duality 8.2.1 8.2.2 8.2.3 Submodularity under Conjugacy Polyhedral M-/L-Convex Functions Integral M-/L-Convex Functions Separation Theorems Fenchel-Type Duality Theorem Implications 8.3 M2-Convex Functions and L2-Convex Functions 8.4 M2-Convex Functions L2-Convex Functions Relationship 8.3.1 8.3.2 8.3.3 Lagrange Duality for Optimization 8.4.1 8.4.2 8.4.3 8.4.4 Outline General Duality Framework Lagrangian Function Based on M-Convexity Symmetry in Duality Bibliographical Notes 9 Network Flows 9.1 Minimum Cost Flow and Fenchel Duality Minimum Cost Flow Problem Feasibility Optimality Criteria Relationship to Fenchel Duality 9.1.1 9.1.2 9.1.3 9.1.4 9.2 M-Convex Submodular Flow Problem 9.3 Feasibility of Submodular Flow Problem vii 166 168 175 177 177 180 181 183 185 186 187 189 193 196 198 202 205 205 206 208 212 216 216 221 224 226 226 229 234 234 234 235 . . .. 238 241 244 245 245 245 247 248 253 255 258

资料库

Discrete Convex Analysis（离散凸分析）.pdf

相关推荐

行业

热门标签

最新资料