Murota K. — Discrete convex analysis :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Murota K. — Discrete convex analysis

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Discrete convex analysis

Автор: Murota K.

Аннотация:

Discrete Convex Analysis is a novel paradigm for discrete optimization that combines the ideas in continuous optimization (convex analysis) and combinatorial optimization (matroid/submodular function theory) to establish a unified theoretical framework for nonlinear discrete optimization. The study of this theory is expanding with the development of efficient algorithms and applications to a number of diverse disciplines like matrix theory, operations research, and economics. This self-contained book is designed to provide a novel insight into optimization on discrete structures and should reveal unexpected links among different disciplines. It is the first and only English-language monograph on the theory and applications of discrete convex analysis.

Язык:

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2003

Количество страниц: 389

Добавлена в каталог: 19.10.2010

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

${L}^{2}_{\natural}$ -convex set      128
${L}^{\natural}$ -convex function      8 23 178
${L}^{\natural}$ -convex function, integral polyhedral      192
${L}^{\natural}$ -convex function, polyhedral      192
${L}^{\natural}$ -convex function, quadratic      48 52 182
${L}^{\natural}$ -convex polyhedron      129 131
${L}^{\natural}$ -convex set      121 128
${L}^{\natural}_{2}$ -convex function      229
${L}^{\natural}_{2}$ -convex set      129
${L}_{2}$ -optimality criterion      232
${L}_{2}$ -proximity theorem      232
${L}_{2}^{\natural}$ -convex function      229
${M}^{2}_{\natural}$ -convex set      117
${M}^{\natural}$ -convex function      8 27 134
${M}^{\natural}$ -convex function, integral polyhedral      162
${M}^{\natural}$ -convex function, polyhedral      161
${M}^{\natural}$ -convex function, quadratic      48 52 139
${M}^{\natural}$ -convex polyhedron      117 118
${M}^{\natural}$ -convex set      102 117
${M}_{2}$ -convex function      226
${M}_{2}$ -optimality criterion      227 228
${M}_{2}$ -proximity theorem      228
${M}_{2}^{\natural}$ -convex function      226
${M}_{2}^{\natural}$ -convex set      116
Accurate number      347
Active triple      297
Acyclic      107
Admissible potential      122
Affine hull      78
Agent      324
Aggregate cost function      335
Aggregation, by network transformation      272
Aggregation, of function to subset      143 162
Algebraically independent      354
Algorithm, competitive equilibrium      344
Algorithm, conjugate scaling      320
Algorithm, cycle-canceling      313
Algorithm, domain reduction      284
Algorithm, domain reduction scaling      287
Algorithm, fully combinatorial      290
Algorithm, greedy      3 108
Algorithm, IFF fixing      300
Algorithm, IFF scaling      299
Algorithm, L-convex function minimization      305 306 308
Algorithm, M-convex function minimization      281 283 284 287
Algorithm, primal-dual      315
Algorithm, pseudopolynomial      288
Algorithm, Schrijver's      293
Algorithm, steepest descent      281 305 306
Algorithm, steepest descent scaling      283 308
Algorithm, strongly polynomial      288
Algorithm, submodular function minimization      293 299 300
Algorithm, successive shortest path      312
Algorithm, two-stage      310
Algorithm, weakly polynomial      288
ARC      52
Arc, entering      53
Arc, leaving      52
Augmenting path      60 273 274
Augmenting path, $\delta -$       297
Auxiliary network      252 263
Base      105
Base family, matrix      69
Base family, matroid      70
Base family, valuated matroid      72
Base polyhedron      18 105
Base polyhedron, integral      18
Base, extreme      105
Base, matrix      69
Base, matroid      70
Biconjugate function      82
Biconjugate function, integer      212
Bipartite graph      89
Bipartite matching      89
BirkhofF's representation theorem      292
Boolean lattice      104
Boundary      53
Branch      52
Budget set      324
Certificate of optimality      12
Chain      88
Characteristic curve      54 251
Characteristic curve, discrete      57
Characteristic vector      16
Chemical process      349
Choquet integral      16 104
Closed convex function      79
Closed convex hull      78
Closed interval      77
Closure, concave function      216
Closure, convex function      93
Closure, convex set      78
Coboundary      53 248
Coboundary, another convention      253
Cocontent      55
Combinatorial optimization      3
Commodity, divisible      327
Commodity, indivisible      323
Compartmental matrix      43
Competitive economy      324
Competitive equilibrium      325
Complementarity      88
Complements      62
Concave closure      216
Concave conjugate      11 81
Concave conjugate, discrete      212
Concave extensible      93
Concave extension      93
Concave function      9 78
Concave function, quasi-separable      334
Concave function, separable      333
Cone, conductance      41
Cone, cone      78
Cone, convex      78
Cone, L-convex      131
Cone, M-convex      119
Cone, polar      82
Conformal decomposition      64
Conjugacy theorem, closed proper M-/L-convex      210
Conjugacy theorem, discrete M-/L-convex      30 212
Conjugacy theorem, in convex analysis      11 82
Conjugacy theorem, polyhedral M-/L-convex      209
Conjugate function, concave      81 212
Conjugate function, convex      81 212
Conjugate scaling      319
Conjugate scaling algorithm      320
Conservation law      54
Constitutive equation      54 349
Constraint      1
Consumer      323
consumption      323
Content      55
Contraction, normal      45
Contraction, unit      45
Convex closure, function      93
Convex closure, set      78
Convex combination      78
Convex cone      78
Convex conjugate      10 81
Convex conjugate, discrete      212
Convex extensible      93
Convex extension      93
Convex extension, local      93
Convex function      2 9 77
Convex function, closed      79
Convex function, dual-integral polyhedral      161
Convex function, integral polyhedral      161
Convex function, laminar      141
Convex function, polyhedral      80
Convex function, positively homogeneous      82

Convex function, proper      77
Convex function, quadratic      40
Convex function, quasi      168
Convex function, quasi-separable      140
Convex function, separable      10 95 140 182
Convex function, strictly      77
Convex function, univariate      10
Convex hull      78
Convex hull, closed      78
Convex polyhedron      78
Convex program      2
Convex program, M-      235
Convex set      2 78
Convexity, discrete midpoint      23 129 180
Convexity, function      77
Convexity, in intersection      92
Convexity, in Minkowski sum      92
Convexity, midpoint      9
Convexity, quasi      168
Convexity, set      78
Convolution, by network transformation      272
Convolution, infimal      80
Convolution, integer infimal      143
Cost function, aggregate      335
Cost function, flow      53 246 255 256
Cost function, flow boundary      256
Cost function, producer's      324
Cost function, reduced      249
Cost function, tension      53
Current      41 53
Current potential      55
Cut capacity function      247
Cycle, negative      122 252 263
Cycle, simple      62
Cycle-canceling algorithm      313
Decreasing marginal return      330
Demand, correspondence      325
Demand, set      325
Descent direction      147
Diagonal dominance      41
Directed graph      52 88
Directional derivative      80
Dirichlet form      45
Discrete Legendre — Fenchel transformation      13 212
Discrete midpoint convexity, function      23 180
Discrete midpoint convexity, set      129
Discrete separation theorem, generic form      13 216
Discrete separation theorem, L-convex function      218
Discrete separation theorem, L-convex set      36 126
Discrete separation theorem, M-convex function      217
Discrete separation theorem, M-convex set      36 114
Discrete separation theorem, submodular function      17 111
Discrete separation theorem, submodular function (as special case of L-separation)      33 224
Discreteness, in direction      10
Discreteness, in value      13
Distance function      122
Distributive lattice      292
Distributive law      292
Divisible commodity      327
Domain reduction algorithm      284
Domain reduction scaling algorithm      287
Dual integrality, intersection theorem      20 114
Dual integrality, linear programming      89
Dual integrality, minimum cost flow problem      252
Dual integrality, polyhedral convex function      161
Dual integrality, polyhedral L-convex function      191
Dual integrality, polyhedral M-convex function      161
Dual integrality, submodular flow problem      261
Dual linear program      87
Dual problem      87
Dual variable      53
Dual-integral polyhedral, convex function      161
Dual-integral polyhedral, L-convex function      191
Dual-integral polyhedral, M-convex function      161
Duality      2 11
Duality, Edmonds's intersection theorem      20
Duality, Fenchel      85
Duality, Fenchel-type      222 225
Duality, L-separation      218
Duality, linear programming      87
Duality, M-separation      217
Duality, matroid intersection      225
Duality, separation for convex functions      84
Duality, separation for convex sets      35 83
Duality, separation for L-convex functions      218
Duality, separation for M-convex functions      217
Duality, separation for submodular functions      17 111
Duality, strong      87
Duality, valuated matroid intersection      225
Duality, weak      87
Duality, weight splitting      34 225
Dynamical degree      352
Economy of Arrow — Debreu type      323
Edmonds's intersection theorem      3 20 112
Edmonds's intersection theorem, (as special case of Fenchel-type duality)      34 224
Effective domain, function over ${R}^{n}$       9 21 77
Effective domain, function over ${Z}^{n}$       21
Effective domain, set function      103
Electrical network      41 43 348
Electrical network, multiterminal      53
Elementary vector      64
Entering arc      53
Epigraph      79
Equilibrium, competitive      325
Equilibrium, economy      325
Equilibrium, electrical network      55
Exchange axiom,       118
Exchange axiom, $({B-EXC}_{+}[R])$       118
Exchange axiom, $({B-EXC}_{+}[Z])$       102
Exchange axiom, $({B-EXC}_{w}[Z])$       103
Exchange axiom, $({B-EXC}_{_}[Z])$       103
Exchange axiom, $({B}^{\natural}-EXC[R])$       118
Exchange axiom, $({B}^{\natural}-EXC[Z])$       117
Exchange axiom, $({M-EXCW}_{w}[Z])$       137
Exchange axiom, $({M-EXC}_{loc}[Z])$       135
Exchange axiom, ${M}^{\natural}$ -convex function      27 134
Exchange axiom, ${M}^{\natural}$ -convex polyhedron      118
Exchange axiom, ${M}^{\natural}$ -convex set      117
Exchange axiom, ( ${M}^{\natural}$ -EXC'[R])      162
Exchange axiom, ( ${M}^{\natural}$ -EXC'[Z])      134
Exchange axiom, ( ${M}^{\natural}$ -EXC[R])      29 47 162
Exchange axiom, ( ${M}^{\natural}$ -EXC[Z])      27 134
Exchange axiom, ( ${M}^{\natural}$ -{EXC}^{+}[R])      48
Exchange axiom, (- ${M}^{\natural}$ -EXC[Z])      330
Exchange axiom, (B-EXC[Z])      18 101
Exchange axiom, (M-EXC'[R])      160
Exchange axiom, (M-EXC'[Z])      26 133
Exchange axiom, (M-EXC[R])      29 56 160
Exchange axiom, (M-EXC[Z])      26 58 133
Exchange axiom, local      135
Exchange axiom, M-convex function      26 58 133
Exchange axiom, M-convex polyhedron      118
Exchange axiom, M-convex set      18 101
Exchange axiom, matroid      69
Exchange axiom, multiple      333
Exchange axiom, polyhedral ${M}^{\natural}$ -convex function      29 47 162
Exchange axiom, polyhedral M-convex function      29 56 160
Exchange axiom, simultaneous      69
Exchange axiom, weak      137
Exchange capacity      284 312
Exchange economy      327
Extension, concave      93
Extension, convex      93
Extension, distance function      165
Extension, local convex      93
Extension, Lovasz      16 104 111
Extension, partial order      108
Extension, set function      16 104
Extreme base      105
Farkas lemma      50 87

1 2 3

О проекте