Download Discrete Convex Analysis by Kazuo Murota PDF

By Kazuo Murota

Discrete Convex research is a unique paradigm for discrete optimization that mixes the information in non-stop optimization (convex research) and combinatorial optimization (matroid/submodular functionality concept) to set up a unified theoretical framework for nonlinear discrete optimization. The learn of this concept is increasing with the advance of effective algorithms and functions to a few various disciplines like matrix thought, operations examine, and economics. This self-contained publication is designed to supply a unique perception into optimization on discrete constructions and may demonstrate unforeseen hyperlinks between varied disciplines. it's the first and in simple terms English-language monograph at the concept and purposes of discrete convex research.

The concept of discrete convex research has attracted the curiosity of many researchers within the box of optimization. Discrete Convex research presents the knowledge that execs in optimization might want to "catch up" with this new theoretical improvement. It additionally offers an unforeseen connection among matroid thought and mathematical economics and expounds a deeper connection among matrices and matroids than most traditional textbooks. pros in parts except optimization will take pleasure in employing those new mathematical strategies and ideas to their very own difficulties.

Show description

Read or Download Discrete Convex Analysis PDF

Best discrete mathematics books

Comprehensive Mathematics for Computer Scientists

  This two-volume textbook accomplished arithmetic for the operating desktop Scientist is a self-contained entire presentation of arithmetic together with units, numbers, graphs, algebra, common sense, grammars, machines, linear geometry, calculus, ODEs, and certain topics reminiscent of neural networks, Fourier conception, wavelets, numerical concerns, records, different types, and manifolds.

Algebraic Semantics of Imperative Programs

Algebraic Semantics of vital courses provides a self-contained and novel "executable" advent to formal reasoning approximately crucial courses. The authors' basic target is to enhance programming skill by way of enhancing instinct approximately what courses suggest and the way they run. The semantics of principal courses is laid out in a proper, carried out notation, the language OBJ; this makes the semantics hugely rigorous but basic, and offers aid for the mechanical verification of software homes.

Structured Matrices in Mathematics, Computer Science, and Engineering II

Many vital difficulties in technologies, arithmetic, and engineering may be lowered to matrix difficulties. furthermore, numerous functions frequently introduce a unique constitution into the corresponding matrices, in order that their entries should be defined by means of a definite compact formulation. vintage examples comprise Toeplitz matrices, Hankel matrices, Vandermonde matrices, Cauchy matrices, decide matrices, Bezoutians, controllability and observability matrices, and others.

An Engineer’s Guide to Mathematica

An Engineers consultant to Mathematica allows the reader to achieve the abilities to create Mathematica nine courses that resolve quite a lot of engineering difficulties and that show the implications with annotated pics. This ebook can be utilized to profit Mathematica, as a spouse to engineering texts, and in addition as a reference for acquiring numerical and symbolic ideas to a variety of engineering issues.

Additional info for Discrete Convex Analysis

Sample text

This implies the optimality of x by virtue of the min-max theorem. 2. Useful Properties of Convex Functions 13 a certificate for the optimality of x. It is emphasized that the min-max theorem guarantees the existence of such a certificate p for any optimal solution x. It is also mentioned that the min-max theorem does not tell us how to find optimal solutions x and p. It is one of the recurrent themes in discrete convexity how the conjugacy and the duality above should be adapted in discrete settings.

21 is due to Frank [54]. M-convex functions are introduced in Murota [137], followed by L-convex functions in Murota [140]. 16) in [137], [140]. 24) are due to [140]. M-convexity Chapter 1. 2. Operations for discrete convex sets and functions (/: function, S: set; Q: Yes [cf. ], x: No). 9) of integer-valued function / and L-convexity are investigated also for functions in real variables for polyhedral, quadratic, and closed convex functions in Murota-Shioura [152], [155], [156], [157]. M^-convex functions are introduced by Murota-Shioura [151] and L''-convex functions by Pujishige—Murota [68].

15. Classes of discrete convex functions (M^-convex n L''-convex = M^-convex n L^-convex = separable convex). end of Chapter 3, and those for network flow theory and matroid theory are in Chapter 2. Pujishige [65] is a standard reference for submodular functions, and Narayanan [165] and Topkis [203] cover some other topics related to electrical networks and economics, respectively. 7, connecting submodularity and convexity, is due to Lovasz [123], and the name "Lovasz extension" was coined by Fujishige [63], [65].

Download PDF sample

Rated 4.02 of 5 – based on 39 votes