Discrete convex analysis / Kazuo Murota.

Format:

Book

Author/Creator:

Murota, Kazuo, 1955-

Contributor:

Rosengarten Family Fund.

Series:

SIAM monographs on discrete mathematics and applications

SIAM monographs on discrete mathematics and applications.

Language:

English

Subjects (All):

Convex functions.

Convex sets.

Mathematical analysis.

Physical Description:

xxii, 389 pages : illustrations ; 26 cm.

Place of Publication:

Philadelphia : Society for Industrial and Applied Mathematics, [2003]

Contents:

1.1 Aim and History of Discrete Convex Analysis 1

1.2 Useful Properties of Convex Functions 9

1.3 Submodular Functions and Base Polyhedra 15

1.4 Discrete Convex Functions 21

1.4.1 L-Convex Functions 21

1.4.2 M-Convex Functions 25

1.4.3 Conjugacy 29

1.4.4 Duality 32

1.4.5 Classes of Discrete Convex Functions 36

2 Convex Functions with Combinatorial Structures 39

2.1 Quadratic Functions 39

2.1.1 Convex Quadratic Functions 39

2.1.2 Symmetric M-Matrices 41

2.1.3 Combinatorial Property of Conjugate Functions 47

2.1.4 General Quadratic L-/M-Convex Functions 51

2.2 Nonlinear Networks 52

2.2.1 Real-Valued Flows 52

2.2.2 Integer-Valued Flows 56

2.2.3 Technical Supplements 58

2.3 Substitutes and Complements in Network Flows 61

2.3.1 Convexity and Submodularity 61

2.3.2 Technical Supplements 63

2.4 Matroids 68

2.4.1 From Matrices to Matroids 68

2.4.2 From Polynomial Matrices to Valuated Matroids 71

3 Convex Analysis, Linear Programming, and Integrality 77

3.3 Integrality for a Pair of Integral Polyhedra 90

3.4 Integrally Convex Functions 92

4 M-Convex Sets and Submodular Set Functions 101

4.2 Exchange Axioms 102

4.3 Submodular Functions and Base Polyhedra 103

4.4 Polyhedral Description of M-Convex Sets 108

4.5 Submodular Functions as Discrete Convex Functions 111

4.6 M-Convex Sets as Discrete Convex Sets 114

4.7 M-Convex Sets 116

4.8 M-Convex Polyhedra 118

5 L-Convex Sets and Distance Functions 121

5.2 Distance Functions and Associated Polyhedra 122

5.3 Polyhedral Description of L-Convex Sets 123

5.4 L-Convex Sets as Discrete Convex Sets 125

5.5 L-Convex Sets 128

5.6 L-Convex Polyhedra 131

6 M-Convex Functions 133

6.1 M-Convex Functions and M-Convex Functions 133

6.2 Local Exchange Axiom 135

6.5 Supermodularity 145

6.6 Descent Directions 146

6.7 Minimizers 148

6.8 Gross Substitutes Property 152

6.9 Proximity Theorem 156

6.10 Convex Extension 158

6.11 Polyhedral M-Convex Functions 160

6.12 Positively Homogeneous M-Convex Functions 164

6.13 Directional Derivatives and Subgradients 166

6.14 Quasi M-Convex Functions 168

7 L-Convex Functions 177

7.1 L-Convex Functions and L[sharp]-Convex Functions 177

7.2 Discrete Midpoint Convexity 180

7.5 Minimizers 185

7.6 Proximity Theorem 186

7.7 Convex Extension 187

7.8 Polyhedral L-Convex Functions 189

7.9 Positively Homogeneous L-Convex Functions 193

7.10 Directional Derivatives and Subgradients 196

7.11 Quasi L-Convex Functions 198

8 Conjugacy and Duality 205

8.1 Conjugacy 205

8.1.1 Submodularity under Conjugacy 206

8.1.2 Polyhedral M-/L-Convex Functions 208

8.1.3 Integral M-/L-Convex Functions 212

8.2 Duality 216

8.2.1 Separation Theorems 216

8.2.2 Fenchel-Type Duality Theorem 221

8.2.3 Implications 224

8.3 M[subscript 2]-Convex Functions and L[subscript 2]-Convex Functions 226

8.3.1 M[subscript 2]-Convex Functions 226

8.3.2 L[subscript 2]-Convex Functions 229

8.3.3 Relationship 234

8.4 Lagrange Duality for Optimization 234

8.4.2 General Duality Framework 235

8.4.3 Lagrangian Function Based on M-Convexity 238

8.4.4 Symmetry in Duality 241

9 Network Flows 245

9.1 Minimum Cost Flow and Fenchel Duality 245

9.1.1 Minimum Cost Flow Problem 245

9.1.2 Feasibility 247

9.1.3 Optimality Criteria 248

9.1.4 Relationship to Fenchel Duality 253

9.2 M-Convex Submodular Flow Problem 255

9.3 Feasibility of Submodular Flow Problem 258

9.4 Optimality Criterion by Potentials 260

9.5 Optimality Criterion by Negative Cycles 263

9.5.1 Negative-Cycle Criterion 263

9.5.2 Cycle Cancellation 265

9.6 Network Duality 268

9.6.1 Transformation by Networks 269

9.6.2 Technical Supplements 273

10 Algorithms 281

10.1 Minimization of M-Convex Functions 281

10.1.1 Steepest Descent Algorithm 281

10.1.2 Steepest Descent Scaling Algorithm 283

10.1.3 Domain Reduction Algorithm 284

10.1.4 Domain Reduction Scaling Algorithm 286

10.2 Minimization of Submodular Set Functions 288

10.2.1 Basic Framework 288

10.2.2 Schrijver's Algorithm 293

10.2.3 Iwata-Fleischer-Fujishige's Algorithm 296

10.3 Minimization of L-Convex Functions 305

10.3.1 Steepest Descent Algorithm 305

10.3.2 Steepest Descent Scaling Algorithm 308

10.3.3 Reduction to Submodular Function Minimization 308

10.4 Algorithms for M-Convex Submodular Flows 308

10.4.1 Two-Stage Algorithm 309

10.4.2 Successive Shortest Path Algorithm 311

10.4.3 Cycle-Canceling Algorithm 312

10.4.4 Primal-Dual Algorithm 313

10.4.5 Conjugate Scaling Algorithm 318

11 Application to Mathematical Economics 323

11.1 Economic Model with Indivisible Commodities 323

11.2 Difficulty with Indivisibility 327

11.3 M[sharp]-Concave Utility Functions 330

11.4 Existence of Equilibria 334

11.4.1 General Case 334

11.4.2 M[sharp]-Convex Case 337

11.5 Computation of Equilibria 340

12 Application to Systems Analysis by Mixed Matrices 347

12.1 Two Kinds of Numbers 347

12.2 Mixed Matrices and Mixed Polynomial Matrices 353

12.3 Rank of Mixed Matrices 356

12.4 Degree of Determinant of Mixed Polynomial Matrices 359.

Notes:

Includes bibliographical references (pages 363-377) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Rosengarten Family Fund.

ISBN:

0898715407

OCLC:

51559058