Strona główna » Matematyka » Convex extensions on combinatorial configurations

Convex extensions on combinatorial configurations

Theory and optimization methods

Autor: Sergiy Yakovlev

Autor: Liudmyla Koliechkina

Autor: Olha Matsyi

Autor: Oksana Pichugina

Liczba stron: 192

Rok wydania: 2026

ISBN: 978-83-8445-114-4

e-ISBN: 978-83-8445-115-1

Format e-book: pdf

Otwarty dostęp

Pobierz bezpłatnie

Przejdź do publikacji

Poleć znajomemu

Opis produktu
Spis treści
Recenzje produktu (0)

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

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

Nikt jeszcze nie napisał recenzji do tego produktu. Bądź pierwszy i napisz recenzję.

Tylko zarejestrowani klienci mogą pisać recenzje do produktów. Jeżeli posiadasz konto w naszym sklepie zaloguj się na nie, jeżeli nie załóż bezpłatne konto i napisz recenzję.

Pozostałe książki z kategorii

Sklep internetowy shopGold

Convex extensions on combinatorial configurations

Matematyka stosowana

Analytic and Algebraic Geometry 1

Modern Real Analysis