ebook Convex extensions on combinatorial configurations Theory and optimization methods Sergiy Yakovlev, Liudmyla Koliechkina, Oksana Pichugina

Name: Convex extensions on combinatorial configurations
SKU: 9D3BF26CEB
Availability: InStock
Author: Sergiy Yakovlev
ISBN: 9788384451151

Wydawca: Wydawnictwo Uniwersytetu Łódzkiego

Rok wydania: 2026

The present monograph develops a mathematical theory at the interface of combinatorial optimization, convex analysis, and Euclidean geometry. Its central subject is the behaviour of functions defined on finite point configurations embedded in Euclidean space and their use in solving combinatorial optimization problems.
By choosing the Euclidean immersion so that the image of the combinatorial feasible set coincides with the vertex set of its convex hull, a discrete optimization problem is transformed into a continuous one without loss of information. This property provides both the condition for the existence of convex extensions and the basis for the optimization methods developed in the monograph.
The theoretical core of the work is a theory of convex extensions of functions defined on vertex-located configurations, including existence theorems for convex, strongly convex, and differentiable extensions, constructive schemes for obtaining explicit formulas, and computable estimates and optimality conditions. The theory is applied to permutation, multipermutation, partial permutation, and Boolean configurations and to the characterization of their associated polytopes.
Building on this foundation, the monograph develops optimization methods including polyhedral and spherical relaxations, branchand- bound schemes, and penalty function methods, all exploiting the geometry of combinatorial feasible sets.
The book is intended for researchers and graduate students in combinatorial optimization, convex analysis, and discrete mathematics, as well as practitioners working on optimization problems in scheduling, assignment, logistics, and engineering design.

Spis treści ebooka Convex extensions on combinatorial configurations

Introduction 7

Chapter 1
Geometric and Analytical Foundations of Finite Point Configurations 13
§1.1. Finite Point Configurations and Associated Polytopes 14
§1.2. Decompositions of Point Configurations and Their Convex Hulls 19
§1.3. Decompositions of Finite Point Configurations by Convex Surfaces 22
§1.4. Functional Representations of Point Configurations 27

Chapter 2
Convex Extensions of Functions on Finite Point Configurations 35
§2.1. Functions on Finite Point Configurations and Convex Extension Framework 36
§2.2. Existence of Convex Extensions on Vertex-Located Configurations 39
§2.3. Structural Properties and Geometric Interpretation of Convex Extensions 46
§2.4. Extremal Properties of Convex Extensions on Vertex-Located Configurations 53
§2.5. Convex Extensions of Functions on a Hypersphere 57

Chapter 3
Combinatorial Point Configurations and Their Polyhedral Geometry 61
§3.1. Ordered Combinatorial Point Configurations and Their Euclidean Immersion 62
§3.2. Permutation and Multipermutation Point Configurations 66
§3.3. Geometry of the Permutohedron and Ordered Partitions 72
§3.4. Partial Multipermutation Point Configurations 76
§3.5. Partial Multipermutohedra 80
§3.6. Partial Permutation Point Configurations 85
§3.7. Unbounded Configurations and Boolean Point Sets 89

Chapter 4
Extremal Properties and Convex Extensions on Combinatorial Point Configurations 95
§4.1. Convex Extension Schemes on Multipermutation Point Configurations 96
§4.2. Extremal Properties of Special Functions on Multipermutation Point Configurations 104
§4.3. Extremal Properties of General Functions on Multipermutation Point Configurations 110
§4.4. Extremal Properties of Special Functions on Partial Permutation Point Configurations 117
§4.5. Lower Bounds and Optimality Conditions for Convex Extensions on Partial Permutation Point Configurations 121
§4.6. Extremal Properties of Convex Functions on Unbounded Partial Multipermutation Point Configurations 128
§4.7. Convex Extensions on Special Partial Point Configurations 133

Chapter 5
Optimization Methods on Combinatorial Point Configurations 139
§5.1. Problem Statement and Nonlinear Programming Models 140
§5.2. Polyhedral Relaxation for Polyhedral-Spherical Configurations 145
§5.3. Spherical Relaxation for Polyhedral-Spherical Configurations 152
§5.4. Dimension Reduction and Branch-and-Bound Scheme for Multipermutation Point Configurations 162
§5.5. Dimension Reduction and Branch-and-Bound Scheme for Unbounded Partial Multipermutation Point Configurations 169
§5.6. A Penalty-Function Method for Optimization on Polyhedral-Spherical Configurations 175

Conclusions 181
References 187
Abstract 191