betaFeedback

WorksMathematics

On Universal Minkowski Classes of Polytopes: Theory and Applications

Abstract

This paper establishes the existence, in every dimension, of universal Minkowski classes of configuration-constrained polytopes, with direct applications to set-theoretic control. For any prescribed accuracy, such a class contains an approximation of every compact convex set to that accuracy and admits a jointly affine parameterization of facets and vertices. The construction is explicit and relies on a combinatorial averaging procedure that produces minimal configuration enclosures. In control, these polytopic templates enable convex reformulations of otherwise non-convex problems, including invariant-set computation and control Lyapunov function design. Tutorial examples illustrate both the geometric construction and its control applications.

Introduction

Set-theoretic methods are widely used in the analysis and control of constrained dynamical systems [5]. Many of these methods rely on polyhedral computing [14, 25], since polytopes admit finite-dimensional representations, interact naturally with linear and convex optimization, and can approximate arbitrary compact convex sets to any prescribed accuracy [41]. In principle, modern optimization software makes it possible to manipulate polytopes with very large numbers of facets or vertices. Nevertheless, the optimization of a polytope itself remains difficult whenever both its facet and vertex representations enter the problem simultaneously.

This difficulty is fundamental in several set-theoretic control problems. Examples include the computation of robust control invariant sets, the construction of piecewise affine control Lyapunov functions, and the optimization of polytopic tubes in model predictive control [22, 21, 47, 26, 25]. In such problems, one would often like to parameterize a candidate polytope through its facet offsets, while dynamical conditions must be imposed at its vertices. However, the vertices generally depend nonlinearly and combinatorially on the facet offsets. Consequently, even when the underlying system is linear, the resulting optimization problem is typically non-convex.

For example, consider the computation of a robust control invariant set for a discrete-time linear system subject to additive disturbances. A natural candidate set can be described by fixing its facet normals and optimizing the corresponding offsets. The invariance conditions, however, must be verified at the vertices of the candidate polytope, whose locations and incidence structure vary with the offsets. The feasible set of offsets is therefore generally non-convex. For uncontrolled systems, this difficulty can sometimes be circumvented through specialized constructions [46]; in the controlled case, the simultaneous dependence on facets, vertices, and control actions remains a central obstacle.

Configuration-constrained polytopes provide a way to separate this geometric difficulty from the subsequent control optimization [47, 26]. Their defining feature is that the relevant facet–vertex incidence structure is fixed in advance. Within a prescribed configuration, both the facet offsets and the vertex coordinates admit a joint affine parameterization. As a result, conditions involving both representations can be expressed through convex constraints. Once an appropriate configuration has been selected, a number of otherwise non-convex set-theoretic control problems can therefore be reformulated as convex optimization problems.

This observation raises a fundamental approximation question. Fixing the configuration improves tractability, but it also restricts the admissible polytope geometries. It is therefore not immediate whether configuration-constrained polytopes retain enough flexibility to approximate arbitrary compact convex sets. Without such an approximation property, the restriction to a prescribed configuration could introduce an irreducible geometric conservatism, independently of the efficiency with which the resulting optimization problem is solved.

Figure 1. The set of polytopes that have the same facet normals as the left polytope is contained in the Hausdorff closure of the set of polytopes that have the same facet normals and the same face configuration as the right polytope. Therefore, we call the right polytope a configuration enclosure of the left polytope. In this paper, we show that every polytope admits such configuration enclosures, a result that can be used to address a variety of open problems in set-based robust and optimal control.

The main purpose of this paper is to resolve this question. In particular, it resolves the geometric approximation issue left open by the configuration-constrained tube-MPC and control-Lyapunov-function constructions in [47, 26]. We establish the existence, in every dimension, of universal Minkowski classes of configuration-constrained polytopes. More precisely, for every prescribed accuracy, we show that there exists a Minkowski class whose members admit a joint affine facet–vertex parameterization and approximate every compact convex set of unit diameter to within that accuracy. Thus, the geometric flexibility required for universal approximation is compatible with the fixed combinatorial structure needed for convex optimization.

Background and Related Work

The mathematical foundations of polyhedral theory originate in the work of Minkowski [35], Weyl [48], Carathéodory [8], and Farkas [11], among others. Subsequent developments revealed deep connections between convex polytopes, linear programming, combinatorics, and algebraic geometry [16, 9, 32]. Standard references on the geometric and combinatorial theory of polytopes include the monographs by Grünbaum [20] and Ziegler [49].

From a computational perspective, the conversion between facet and vertex representations is a central operation in polyhedral computing [18, 14]. Classical approaches include the double-description method [36], beneath-and-beyond procedures [44], and later refinements for vertex and facet enumeration [15]. Reverse-search methods introduced by Avis and co-workers provide an alternative framework for enumerating polyhedral objects while controlling memory requirements [1, 2]. These tools are highly developed, but their purpose is generally to enumerate or manipulate the geometry of a given polyhedron. They do not, by themselves, remove the non-convex dependence between the facets and vertices of a polytope whose geometry is being optimized.

Polyhedral methods have played a similarly important role in control. Gutman and Cwikel derived foundational vertex-based characterizations of control invariance for constrained linear systems [22, 21], while Bitsoris developed related algebraic conditions for invariant polytopes [3]. These results form part of the broader theory of set invariance developed and surveyed by Blanchini [4, 5]. More recently, Trodden showed that minimal robust positively invariant polytopes can be computed through convex optimization for an important class of uncontrolled uncertain systems [46]. Polyhedral techniques are also central to the analysis of parametric optimization problems arising in model-based control [27, 23].

In model predictive control [39], polytopes are routinely used to describe state and input constraints, terminal sets, reachable sets, and uncertainty tubes. Different restrictions on the geometry of the tube cross-sections lead to rigid, homothetic, elastic, and configuration-constrained tube MPC formulations [29, 37, 38, 47]. A recent survey of polyhedral methods in control, including their use in tube MPC and set-theoretic design, is provided in [25]. The present paper complements this literature by addressing a prior geometric question: whether the tractable class of configuration-constrained polytopes can, in principle, retain the universal approximation capabilities of unrestricted polytopes.

Contributions and Scope

The primary contribution of this paper is a foundational result in convex and polyhedral geometry. We prove that, for every dimension d≥1d \ge1 and every accuracy ϵ>0\epsilon> 0, there exists a Minkowski class of configuration-constrained dd-polytopes that is ϵ\epsilon-dense in the family of compact convex subsets of Rd\mathbb{R}^{d} with diameter 1. This result, stated in Theorem 1, shows that fixing a suitable facet–vertex configuration does not preclude approximation to arbitrary prescribed accuracy.

The proof is constructive. In particular, we introduce a combinatorial averaging procedure that generates minimal configuration enclosures and thereby produces the universal Minkowski classes used in the approximation theorem. The construction is presented in Algorithm 1 and analyzed in Theorem 2. Its role in this paper is primarily theoretical: it provides a finite and systematic construction establishing the existence of the required classes in every dimension. The procedure is deliberately general and is not intended as an optimized implementation. Its computational cost can be substantial, particularly in dimensions d≥3d \ge3, and the development of specialized algorithms and data structures is left for future work.

The relevance to set-theoretic control arises after this offline construction has been completed. The resulting configuration-constrained templates combine two properties that are usually in tension: they admit a joint affine parameterization of facets and vertices, and they can approximate arbitrary compact convex sets to any prescribed accuracy. The first property enables convex reformulations of problems involving simultaneous facet and vertex constraints, while the second ensures that the use of such templates need not impose an intrinsic approximation barrier. In particular, the templates can be used in convex formulations for robust control invariant-set computation, control Lyapunov function design, and related polytopic optimization problems.

The construction is performed once, offline, for a given dimension and approximation accuracy. The resulting templates can then be stored and reused across different systems and control-design problems of the same dimension. Accordingly, the main contribution is not a new online control algorithm, nor a claim that the general construction is already computationally optimal. Rather, it is the constructive existence of universal configuration-constrained Minkowski classes and, through this result, a theoretical justification for using jointly parameterized polytopic templates in convex set-theoretic control formulations. The main developments are illustrated by means of tutorial examples.

Notation

Throughout this article, the standard terminology for sets is used. In particular, we use the following symbols:

  • Rd\mathbb{R}^{d} denotes the dd-dimensional Euclidean space, and

  • Cd\mathcal{C}^{d} denotes the set of nonempty compact convex sets in Rd\mathbb{R}^{d}.

Additionally, the notion of partially ordered sets (posets) is used to describe the structure of set collections, such as the faces of a polyhedron. We use the standard notational conventions as in [49 Def. 2.5]. The Hausdorff distance, diameter, and Minkowski sum of X,Y∈CdX,Y \in\mathcal{C}^{d} are defined, as usual, by

dH(X,Y):=max⁡{max⁡x∈Xmin⁡y∈Y∥x−y∥,max⁡y∈Ymin⁡x∈X∥x−y∥}.d_{\mathrm{H}}(X,Y) := \max\left\{ \max_{x \in X} \min_{y \in Y} \lVert x-y \rVert, \max_{y \in Y} \min_{x \in X} \lVert x-y \rVert\right\}.
diam⁡(X):=max⁡x,y∈X∥x−y∥,\operatorname{diam}(X) := \max_{x,y \in X} \lVert x-y \rVert,

and

X+Y:={x+y∣x∈X, y∈Y}.X + Y := \left\{ x+y \mid x \in X,\ y \in Y \right\}.

Moreover, we recall the following standard definitions of Minkowski classes, see also [42 Chap. 3.5].

Definition 1 A set of compact convex sets X⊆Cd\mathcal{X} \subseteq\mathcal{C}^{d} is called a Minkowski class if it is closed in the Hausdorff metric and satisfies

X+Y∈XandαX∈XX + Y \in\mathcal{X} \qquad\text{and} \qquad\alpha X \in\mathcal{X}

for all X,Y∈XX,Y \in\mathcal{X} and all α≥0\alpha\ge0.

Examples of Minkowski classes include the set Cd\mathcal{C}^{d} itself, the class of centrally symmetric compact convex sets, and the set of zonoids; that is, the set of sets that can be approximated by a sum of line segments [43].

Definition 2. Let X,Y⊆Cd\mathcal{X},\mathcal{Y} \subseteq\mathbb{C}^{d} be two given set collections with X⊆Y\mathcal{X} \subseteq\mathcal{Y}. We say that X\mathcal{X} is ϵ\epsilon-dense in Y\mathcal{Y}, for a given ϵ>0\epsilon> 0, if

∀Y∈Y, ∃X∈X:dH(X,Y)≤ϵ⋅diam⁡(Y).\forall Y \in\mathcal{Y},\ \exists X \in\mathcal{X}:\quad d_{\mathrm{H}}(X,Y) \leq\epsilon\cdot\operatorname{diam}(Y).

The latter definition is important for analyzing generic numerical set approximation methods. Namely, in the context of approximating a set Y∈YY \in\mathcal{Y} with a set X∈XX \in\mathcal{X}, the constant ϵ\epsilon in the above definition can be interpreted as a relative numerical approximation accuracy. Alternatively, if one scales the set YY such that diam⁡(Y)=1\operatorname{diam}(Y) = 1, the constant ϵ\epsilon can be interpreted as the absolute approximation accuracy.

Finally, the symbol 1\mathbf{1} denotes an all-ones vector whose dimension is clear from context. For vectors a1,a2,…,an∈Rda_1, a_2, \ldots, a_n \in\mathbb{R}^{d}, we use the notation

conv⁡(a1,a2,…,an):={∑i=1nθiai ∣ θi≥0, 1Tθ=1}.\operatorname{conv}(a_1,a_2,\ldots,a_n) := \left\{ \left. \sum_{i=1}^{n} \theta_i a_i \ \right| \ \theta_i \geq0,\ \mathbf{1}^{\mathsf{T}}\theta= 1 \right\}.

to denote the convex hull. This notation is also used for matrices, where conv⁡(A)\operatorname{conv}(A) denotes the convex hull of the columns of A∈Rd×nA \in\mathbb{R}^{d \times n}.

Polytopes

The goal of this section is to introduce the basic definitions and properties of general polytopes and their face configuration.

Faces of Polytopes

Throughout this paper, we are interested in polytopes of dimension dd with at most nn facets. Let

A(n,d):={A∈Rn×d ∣ ∀i∈{1,…,n}, Ai≠0,0∈int⁡(conv⁡(AT)),∀i,j∈{1,…,n}, i≠j,∥Ai∥Aj≠∥Aj∥Ai}\mathcal{A}(n,d) := \left\{ \left. A \in\mathbb{R}^{n \times d} \ \right| \ \begin{aligned} &\forall i \in\{1,\ldots,n\},\ A_i \neq0,\\ &0 \in\operatorname{int}\bigl(\operatorname{conv}(A^{\mathsf{T}})\bigr),\\ &\forall i,j \in\{1,\ldots,n\},\ i \neq j,\\ &\lVert A_i\rVert A_j \neq\lVert A_j\rVert A_i \end{aligned} \right\}

denote the corresponding set of admissible facet matrices. The conditions require every row of AA to be nonzero and exclude positively collinear distinct rows. These restrictions involve no loss of generality when facet directions are prescribed, because zero normals and repeated positive directions can be removed. In this context, a polytope with facet matrix A∈A(n,d)A \in\mathcal{A}(n,d) is a (potentially empty) set of the form

P(A,b):={x∈Rd∣Ax≤b},P(A,b) := \{x \in\mathbb{R}^{d} \mid Ax \leq b\},

for some vector b∈Rnb \in\mathbb{R}^{n}. In this context, the condition 0∈int⁡(conv⁡(AT))0 \in\operatorname{int}\bigl(\operatorname{conv}(A^{\mathsf{T}})\bigr) in the definition of A(n,d)\mathcal{A}(n,d) is exactly the boundedness condition: it says that the facet normals A1,…,AnA_1,\ldots,A_n positively span Rd\mathbb{R}^{d}, or equivalently that the recession cone {x∈Rd∣Ax≤0}\{x \in\mathbb{R}^{d} \mid Ax \leq0\} is {0}\{0\}. Thus, P(A,b)P(A,b) has no nonzero direction in which it can be unbounded; whenever it is nonempty, it is a bounded polyhedron, hence a polytope. As usual, we associate with each index set I⊆{1,…,n}I \subseteq\{1,\ldots,n\} a face of P(A,b)P(A,b), defined by

F(I,A,b):={x∈P(A,b)∣∀i∈I, Aix=bi}.F(I,A,b) := \{x \in P(A,b) \mid\forall i \in I,\ A_i x = b_i\}.

Faces of dimensions 00, 11, kk, and d−1d-1 are called vertices, edges, kk-faces, and facets. The number of kk-faces of P(A,b)P(A,b) is denoted by fk(A,b)f_k(A,b). They are the components of the so-called ff-vector. Moreover, we recall that the faces of a polytope are a bounded and graded poset with respect to inclusion. It is called the face lattice of P(A,b)P(A,b). In particular, we have

I⊆J⟹F(I,A,b)⊇F(J,A,b).I \subseteq J \qquad\Longrightarrow\qquad F(I,A,b) \supseteq F(J,A,b).

Generally, two polytopes are called combinatorially equivalent if their face lattices are isomorphic, see also [49 Chap. 2] for an in-depth discussion. Similarly, the following definitions are commonly used in almost all the literature on polytopes, see [20] and [49] for details.

Definition 3. A polytope in Rd\mathbb{R}^{d} is called simple if all of its vertices are in exactly dd facets.

Definition 4. The facet representation P=P(A,b)\mathsf{P}=\mathsf{P}(A,b) with A∈A(n,d)A\in\mathcal{A}(n,d) is called minimal, if fd−1(A,b)=nf_{d-1}(A,b)=n.

We further recall that if P(A,b)\mathsf{P}(A,b) is a minimal representation of a simple polytope, then the polytopes P(A,c)\mathsf{P}(A,c) and P(A,b)\mathsf{P}(A,b) are combinatorially equivalent for all vectors cc in a sufficiently small open neighborhood of bb, see [20 Section 4.5], [49 Section 2.5], and compare also [47 Cor. 2]. In other words, simple polytopes are locally configuration stable.

Configuration Posets

Throughout, we assume that A∈A(n,d)A\in\mathcal{A}(n,d) is a given admissible facet matrix. We associate with each index set I⊆{1,…,n}I\subseteq\{1,\ldots,n\} a nonempty convex cone,

C(I,A):={b∈Rn | ∃x∈Rd: ∀i∈I, Ax≤b, Aix=bi}.\mathcal{C}(I,A):=\left\{b\in\mathbb{R}^{n}\,\middle|\,\exists x\in\mathbb{R}^{d}:\ \forall i\in I,\ Ax\leq b,\ A_i x=b_i\right\}.

In words, C(I,A)\mathcal{C}(I,A) denotes the set of all parameters bb for which the face F(I,A,b)\mathsf{F}(I,A,b) is nonempty. Note that C(I,A)\mathcal{C}(I,A) is a closed polyhedral cone, whose lineality space is given by

lin⁡(C(I,A))=Im⁡(A).\operatorname{lin}(\mathcal{C}(I,A))=\operatorname{Im}(A).

To verify the inclusion lin⁡(C(I,A))⊆Im⁡(A)\operatorname{lin}(\mathcal{C}(I,A))\subseteq\operatorname{Im}(A), pick any v∈lin⁡(C(I,A))v\in\operatorname{lin}(\mathcal{C}(I,A)), such that v∈C(I,A)v\in\mathcal{C}(I,A) and −v∈C(I,A)-v\in\mathcal{C}(I,A). Then we can write

v=Ax+sand−v=Ay+tv=Ax+s\quad\text{and}\quad-v=Ay+t

for some s,t≥0s,t\geq0. Adding these two identities gives

0=A(x+y)+s+t.0=A(x+y)+s+t.

Choosing w∈R++nw\in\mathbb{R}^{n}_{++} with ATw=0A^{\mathsf{T}}w=0, which exists because 0∈int⁡(conv⁡(AT))0\in\operatorname{int}(\operatorname{conv}(A^{\mathsf{T}})), yields wT(s+t)=0w^{\mathsf{T}}(s+t)=0 and, hence, s=t=0s=t=0. Therefore, v∈Im⁡(A)v\in\operatorname{Im}(A); see also [25]. Conversely, if v∈Im⁡(A)v\in\operatorname{Im}(A), say v=Axv=Ax, then v∈C(I,A)v\in\mathcal{C}(I,A) via xx and −v∈C(I,A)-v\in\mathcal{C}(I,A) via −x-x. Hence v∈lin⁡(C(I,A))v\in\operatorname{lin}(\mathcal{C}(I,A)). Therefore,

lin⁡(C(I,A))=Im⁡(A).\operatorname{lin}(\mathcal{C}(I,A))=\operatorname{Im}(A).

Moreover, the set C(∅,A)\mathcal{C}(\varnothing,A) corresponds to the set of parameters bb for which P(A,b)≠∅\mathsf{P}(A,b)\ne\varnothing. Additionally, we introduce the shorthand

C‾(A):=⋂i∈{1,…,n}C({i},A).\overline{\mathcal{C}}(A):=\bigcap_{i\in\{1,\ldots,n\}}\mathcal{C}(\{i\},A).

The set C‾(A)\overline{\mathcal{C}}(A) is a convex cone and is the natural parameter domain for nonempty polytopes. Indeed, if P(A,b)≠∅\mathsf{P}(A,b)\ne\varnothing, the support vector b′∈Rnb'\in\mathbb{R}^{n} defined by

bi′:=max⁡x∈P(A,b)Aix,i∈{1,…,n},b'_i:=\max_{x\in\mathsf{P}(A,b)}A_i x,\qquad i\in\{1,\ldots,n\},

belongs to C‾(A)\overline{\mathcal{C}}(A) and satisfies P(A,b)=P(A,b′)\mathsf{P}(A,b)=\mathsf{P}(A,b'). These cones can be used to analyze polytope configurations through the index-set collection

I(A,b):={I⊆{1,…,n} | F(I,A,b)≠∅}.\mathcal{I}(A,b):=\left\{I\subseteq\{1,\ldots,n\}\,\middle|\,\mathsf{F}(I,A,b)\ne\varnothing\right\}.

In words, I(A,b)\mathcal{I}(A,b) denotes the collection of all index sets that correspond to the nonempty faces of a given polytope P(A,b)\mathsf{P}(A,b).

Definition 5. Let A∈A(n,d)A\in\mathcal{A}(n,d) and b∈C‾(A)b\in\overline{\mathcal{C}}(A) be given. The configuration cone of a polytope P(A,b)\mathsf{P}(A,b) is defined as

K(A,b):=⋂I∈I(A,b)C(I,A).\mathcal{K}(A,b):=\bigcap_{I\in\mathcal{I}(A,b)}\mathcal{C}(I,A).

Additionally, two polytopes P(A,b)\mathsf{P}(A,b) and P(A,c)\mathsf{P}(A,c) with parameters b,c∈C‾(A)b,c\in\overline{\mathcal{C}}(A) are called configuration-equivalent for the given matrix AA, if K(A,b)=K(A,c)\mathcal{K}(A,b)=\mathcal{K}(A,c).

Remark 1 Let P⊆RdP \subseteq\mathbb{R}^{d} be a polytope and let FF be a nonempty face of PP. Its normal cone is

{p∈Rd∣∀x∈P, ∀y∈F, pT(x−y)≤0}.\{p \in\mathbb{R}^{d} \mid\forall x \in P,\ \forall y \in F,\ p^{\mathsf{T}}(x-y) \le0\}.

The collection of the normal cones of all faces is the normal fan. A fan N1\mathcal{N}_{1} refines a fan N2\mathcal{N}_{2} if every cone of N1\mathcal{N}_{1} is contained in a cone of N2\mathcal{N}_{2}; equivalently, N2\mathcal{N}_{2} is a coarsening of N1\mathcal{N}_{1}. Thus, refinement subdivides normal cones, whereas coarsening merges adjacent normal cones. For fixed facet-normal labels, parameters in the relative interior of one configuration cone have the same labeled normal fan. Moving to its boundary can merge normal cones, create additional facet incidences, make inequalities redundant, or produce a lower-dimensional degeneration. These notions are standard in the deformation- and type-cone literature; see [49, 42], [12 Sec. 1.1 and Cor. 1.42], and [25].

In the terminology of Remark 1, if P(A,b)P(A,b) is minimally represented, then c∈K(A,b)c \in K(A,b) precisely when the labeled normal fan of P(A,b)P(A,b) refines that of P(A,c)P(A,c). The relative interior of K(A,b)K(A,b) therefore consists of parameters with the same labeled normal fan, whereas its boundary contains coarsenings, including cases with redundant inequalities or lower-dimensional degenerations. This is the configuration-cone form of the classical deformation/type-cone description; see [31 Thms. 8 and 10], [12 Cor. 1.42, Lem. 1.43, and Rem. 1.45], and [25]. Configuration-equivalent polytopes are necessarily combinatorially equivalent, but the converse need not hold; see Example 1. Moreover, configuration-equivalence is label-dependent. For example, if A~\widetilde{A} is obtained by permuting the rows of AA, then P(A~,1)=P(A,1)P(\widetilde{A},\mathbf{1})=P(A,\mathbf{1}), although the indexed facet representation has changed. This dependence is natural in polyhedral computation, where the rows of the facet matrix and the corresponding face-index lists are stored explicitly.

The family of configuration cones is closed under finite intersections. In the type-cone description, the intersection of two chamber closures is either empty or a common face; whenever it is nonempty, that face is itself represented by the incidences active at a parameter in its relative interior. Thus,

K(A,b)∩K(A,c)K(A,b) \cap K(A,c)

is again a configuration cone. This construction and the definition below follow the type-cone-complex viewpoint of [31].

Definition 6 The poset of configuration cones associated with a matrix A∈A(n,d)A \in\mathcal{A}(n,d),

K(A):={K(A,b)∣b∈C‾(A)},\mathcal{K}(A) := \{K(A,b) \mid b \in\overline{\mathcal{C}}(A)\},

partially ordered with respect to inclusion, is called the configuration poset of AA.

The poset K(A)\mathcal{K}(A) is finite, because only finitely many collections J(A,b)\mathcal{J}(A,b) can occur. Every configuration cone is a closed polyhedral cone with linearity space Im⁡(A)\operatorname{Im}(A). Moreover, Im⁡(A)\operatorname{Im}(A) is the unique minimal element: every configuration cone contains it, while K(A,Ay)=Im⁡(A)K(A,Ay)=\operatorname{Im}(A) for every y∈Rdy \in\mathbb{R}^{d}. Here, dim⁡(Im⁡(A))=d\dim(\operatorname{Im}(A))=d because 0∈int⁡(conv⁡(AT))0 \in\operatorname{int}(\operatorname{conv}(A^{\mathsf{T}})) implies rank⁡(A)=d\operatorname{rank}(A)=d. In contrast to a lattice, K(A)\mathcal{K}(A) may have several maximal elements. We denote their number by σ(A)∈N\sigma(A) \in\mathbb{N}.

Every maximal element Mi\mathcal{M}_{i} has nonempty interior and can be written as

Mi=K(A,bi),bi∈int⁡(Mi),i∈{1,…,σ(A)}.\mathcal{M}_{i}=K(A,b_{i}), \qquad b_{i} \in\operatorname{int}(\mathcal{M}_{i}), \qquad i \in\{1,\ldots,\sigma(A)\}.

The representative bib_{i} can be chosen so that P(A,bi)P(A,b_{i}) is a simple polytope with a minimal facet representation. These standard deformation/type-cone properties follow from [31, 12, 47, 25].

Configuration-Constrained Polytopes

Configuration-constrained polytopes were originally introduced in [47]. Using the notation of the current paper, they are defined as follows.

Definition 7 Let A∈A(n,d)A \in\mathcal{A}(n,d) be a given facet matrix. For any b∈C‾(A)b \in\overline{\mathcal{C}}(A), the associated class of configuration-constrained polytopes is

P(A,b):={P(A,c)∣c∈K(A,b)}.\mathfrak{P}(A,b):=\{P(A,c)\mid c\in K(A,b)\}.

The class P(A,b)\mathfrak{P}(A,b) is nonempty because b∈K(A,b)b \in K(A,b). It may, however, contain no simple polytopes unless bb represents a maximal element of K(A)\mathcal{K}(A). Regardless of simplicity, P(A,b)\mathfrak{P}(A,b) admits a double description: there exist vertex matrices V1,V2,…,Vc∈Rd×nV_{1},V_{2},\ldots,V_{c} \in\mathbb{R}^{d \times n} such that

P(A,b)={conv⁡(V1c,…,Vcc)∣c∈K(A,b)}.(1)\mathfrak{P}(A,b)=\{\operatorname{conv}(V_{1}c,\ldots,V_{c}c)\mid c\in K(A,b)\}. \tag*{(1)}

This was proved for maximal configuration cones in [47 Thm. 2] and extended to arbitrary configuration cones in [24 Prop. 1]. The following technical lemma summarizes a simple but relevant consequence of these results.

Lemma 1. Let A∈A(n,d)A \in\mathcal{A}(n,d) and b∈C‾(A)b \in\overline{\mathcal{C}}(A) be given. Then P(A,b)\mathcal{P}(A,b) is a Minkowski class (see Definition 1).

Proof. We first verify closedness. Let P(A,cℓ)∈P(A,b)\mathcal{P}(A,c^\ell) \in\mathcal{P}(A,b) converge in the Hausdorff metric to P∈Cd\mathbb{P} \in\mathcal{C}^d. Since cℓ∈K(A,b)⊆C‾(A)c^\ell\in K(A,b) \subseteq\overline{\mathcal{C}}(A), every row of AA is supporting and

ciℓ=max⁡x∈P(A,cℓ)Aix,i∈{1,…,n}.c_i^\ell= \max_{x \in\mathcal{P}(A,c^\ell)} A_i x,\qquad i \in\{1,\ldots,n\}.

Continuity of support functions under Hausdorff convergence implies cℓ→cc^\ell\to c, where ci=max⁡x∈PAixc_i = \max_{x \in\mathbb{P}} A_i x. The cone K(A,b)K(A,b) is closed, so c∈K(A,b)c \in K(A,b). Passing to the limit in the common vertex representation (1) yields P=P(A,c)∈P(A,b)\mathbb{P} = \mathcal{P}(A,c) \in\mathcal{P}(A,b).

It remains to prove closure under Minkowski addition and nonnegative scaling. Let c1,c2∈K(A,b)c_1,c_2 \in K(A,b). Since K(A,b)K(A,b) is a convex cone, c1+c2∈K(A,b)c_1+c_2 \in K(A,b). For every i∈{1,…,n}i \in\{1,\ldots,n\},

max⁡x∈P(A,c1)+P(A,c2)Aix≤max⁡x1∈P(A,c1)Aix1+max⁡x2∈P(A,c2)Aix2=(c1+c2)i.\max_{x \in\mathcal{P}(A,c_1)+\mathcal{P}(A,c_2)} A_i x \le\max_{x_1 \in\mathcal{P}(A,c_1)} A_i x_1+\max_{x_2 \in\mathcal{P}(A,c_2)} A_i x_2 = (c_1+c_2)_i.

which implies

P(A,c1)+P(A,c2)⊆P(A,c1+c2).\mathcal{P}(A,c_1)+\mathcal{P}(A,c_2) \subseteq\mathcal{P}(A,c_1+c_2).

Conversely, the common vertex matrices in (1) imply that every x∈P(A,c1+c2)x \in\mathcal{P}(A,c_1+c_2) can be written as

x=∑i=1vλiVi(c1+c2)x=\sum_{i=1}^{v}\lambda_i V_i(c_1+c_2)
=∑i=1vλiVic1+∑i=1vλiVic2∈P(A,c1)+P(A,c2),=\sum_{i=1}^{v}\lambda_i V_i c_1+\sum_{i=1}^{v}\lambda_i V_i c_2 \in\mathcal{P}(A,c_1)+\mathcal{P}(A,c_2),

for suitable λi≥0\lambda_i \ge0 with ∑iλi=1\sum_i \lambda_i=1. Hence,

P(A,c1)+P(A,c2)=P(A,c1+c2).\mathcal{P}(A,c_1)+\mathcal{P}(A,c_2)=\mathcal{P}(A,c_1+c_2).

Finally, since K(A,b)K(A,b) is a cone, αc∈K(A,b)\alpha c \in K(A,b) for every c∈K(A,b)c \in K(A,b) and every α≥0\alpha\ge0. The same representation therefore gives

αP(A,c)=P(A,αc)∈P(A,b),\alpha\mathcal{P}(A,c)=\mathcal{P}(A,\alpha c)\in\mathcal{P}(A,b),

which proves closure under nonnegative scaling. □

Configuration Enclosures

While configuration-constrained polytopes provide a practical joint facet–vertex representation, it remains to determine whether such classes are sufficiently flexible to approximate arbitrary compact convex sets. The primary objective of this paper is to show that suitable configuration-constrained classes do possess this approximation property. Our main result can be formulated as follows.

Theorem 1. There exists for every ϵ>0\epsilon>0 and every dimension d≥1d\ge1 an integer n≥1n\ge1 and a matrix A∈A(n,d)A\in\mathcal{A}(n,d) for which the Minkowski class P(A,1)\mathcal{P}(A,1) is ϵ\epsilon-dense in Cd\mathcal{C}^d.

The proof of Theorem 1 is given in § 4.3. We first introduce the concept of configuration enclosures.

Outline of the Main Technical Idea

The main technical idea for proving Theorem 1 is to start with an arbitrary facet matrix A∈A(n,d)A \in\mathcal{A}(n,d) and replace it with a configuration enclosure, defined as follows.

Definition 8. A facet matrix B∈A(m,d)B \in\mathcal{A}(m,d) with 1∈C‾(B)1 \in\overline{\mathcal{C}}(B) is called a configuration enclosure of A∈A(n,d)A \in\mathcal{A}(n,d) if

∀b∈C(∅,A),∃c∈K(B,1):P(A,b)=P(B,c).\forall b \in\mathcal{C}(\varnothing,A),\quad\exists c \in K(B,1):\quad\mathcal{P}(A,b)=\mathcal{P}(B,c).

A given matrix AA may have many configuration enclosures; the enclosure matrix BB has mm facet normals. As follows from the normal-fan argument below, an enclosure must contain the original normal directions up to positive scaling, and hence m≥nm \ge n. In the context of practical applications, however, we are interested in keeping the number of new facet normals, m−nm-n, as small as possible. Therefore, the following definition of minimal configuration enclosures is useful.

Definition 9. We call B∈A(m,d)B \in\mathcal{A}(m,d) a minimal configuration enclosure of A∈A(n,d)A \in\mathcal{A}(n,d) if there is no other configuration enclosure of AA that has fewer rows than BB.

Given these definitions, our strategy for proving Theorem 1 is to (i) recall the well-known fact that general polytopes can approximate arbitrary compact convex sets arbitrarily well [41] and (ii) replace such arbitrary polytopes by their configuration enclosures.

Monotypic Polytopes

It is useful to distinguish facet-normal configurations for which one maximal configuration class already contains every polytope representable with those normal directions. We call such configurations monotypic.

Definition 10. We call a matrix A∈A(n,d)A \in\mathcal{A}(n,d) monotypic if it satisfies σ(A)=1\sigma(A)=1.

In words, monotypic polytopes are precisely those whose configuration poset has a unique maximal element. A polytope P(A,b)\mathcal{P}(A,b) is called monotypic if bb represents this unique maximal element M\mathcal{M}, that is, M=K(A,b)\mathcal{M}=K(A,b). Notice that Definition 10 is equivalent to the notion of monotype introduced in [33] relative to the set of normals of induced by the rows of AA.

Remark 2. Monotypy should be distinguished from strong monotypy, which requires the facet normals to determine the combinatorial type of the complete affine arrangement of the facet hyperplanes and therefore implies monotypy. Strong monotypy is equivalent to the generating property: every nonempty intersection of translates of the polytope is a Minkowski summand of the polytope [7, 34].

Some important examples of monotypic polytopes are collected in the proposition below.

Proposition 1. Every matrix A∈A(n,d)A \in\mathcal{A}(n,d) is monotypic in each of the following cases:

  • d=1d=1 and n=2n=2, or

  • d=2d=2 and n≥3n \ge3, or

  • d≥3d \ge3 and n=d+1n=d+1, or

  • d≥3d \ge3, n=2dn=2d, and A=[Id −Id]TA=[I_d\ -I_d]^{\mathsf{T}}.

The corresponding monotypic polytopes are, respectively, all intervals with nonempty interior in R1\mathbb{R}^{1}, all simple polytopes in R2\mathbb{R}^{2}, all simplices with nonempty interior in any dimension, and all axis-aligned rectangular boxes with nonempty interior in any dimension.

Proof. The case d=1d=1 and n=2n=2 is trivial, as all intervals in R1\mathbb{R}^{1} with nonempty interior are configuration equivalent. Moreover, the fact that all simple polytopes in R2\mathbb{R}^{2} are monotypic follows from [47 Rem. 3]. Polytopes with n=d+1n=d+1 facets and nonempty interior in Rd\mathbb{R}^{d} are necessarily simplices, which can only have one possible configuration: any dd facets have a joint vertex. Finally, axis-aligned boxes are monotypic because every such dd-box is a direct product of dd one-dimensional intervals, reducing this case to the one-dimensional setting. □

Unfortunately, as much as it is remarkable that all simple polytopes in R2\mathbb{R}^{2} are monotypic, it turns out that the situation in dimension d≥3d \ge3 is very different. Namely, in dimensions d≥3d \ge3, however, monotypy imposes nontrivial restrictions on the facet-normal configuration, and arbitrary normal configurations need not be monotypic. The following minimal example illustrates this obstruction.

Example 1 (Minimal non-monotypic polytope). Given Proposition 1, the simplest possible non-monotypic facet matrix must have d≥3d \ge3 columns and n≥d+2≥5n \ge d + 2 \ge5 rows, because simplices are monotypic. One such matrix with the minimum possible numbers of rows and columns is

A=(0−1100000−11−11111)T.A = \begin{pmatrix} 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 1 \\ -1 & 1 & 1 & 1 & 1 \end{pmatrix}^{\mathsf{T}}.

Namely, for this matrix, the sets P(A,b1)\mathrm{P}(A,b_1) and P(A,b2)\mathrm{P}(A,b_2) with

b1=(0,3,3,1,1)Tb_1 = (0,3,3,1,1)^{\mathsf{T}}

and

b2=(0,1,1,3,3)Tb_2 = (0,1,1,3,3)^{\mathsf{T}}

are both simple polytopes, but they are not configuration-equivalent1, as visualized below:

Figure 1 (PDF p. 9). P(A,b1)\mathrm{P}(A,b_1).

Figure 2. P(A,b2)\mathrm{P}(A,b_2).

The second and third facets of the left polytope have no joint vertex, whereas the second and third facets of the right polytope have two joint vertices. Of course, for such simple examples, we can still use our “geometric intuition” to construct a configuration enclosure. For instance, we can add one row to AA to construct the new matrix

B=(0−11000000−110−111111)T,B = \begin{pmatrix} 0 & -1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 & 1 & 0 \\ -1 & 1 & 1 & 1 & 1 & 1 \end{pmatrix}^{\mathsf{T}},

which turns out to be a minimal configuration enclosure of AA. In fact, BB is even monotypic. For example, an associated monotypic polytope P(B,c)\mathrm{P}(B,c) is obtained for c=(0,2,2,2,2,1)Tc=(0,2,2,2,2,1)^{\mathsf{T}},

Figure 3. P(B,c)\mathrm{P}(B,c).

In addition to being monotypic, this polytope represents the Minkowski average

P(B,c)=P(A,b1)+P(A,b2)2.\mathrm{P}(B,c)=\frac{\mathrm{P}(A,b_1)+\mathrm{P}(A,b_2)}{2}.

This example anticipates the Minkowski-averaging construction of minimal configuration enclosures developed next.

Combinatorial Averaging

This section develops a general method for constructing configuration enclosures and thereby provides a constructive proof of Theorem 1.

Minkowski Sums

Let P1,…,Ps⊆Rd\mathrm{P}_1,\ldots,\mathrm{P}_s \subseteq\mathbb{R}^d be full-dimensional polytopes that admit a (potentially nonminimal) facet representation Pi=P(A,bi)\mathrm{P}_i=\mathrm{P}(A,b_i), i∈{1,…,s}i\in\{1,\ldots,s\}. For λ∈R++\lambda\in\mathbb{R}_{++}, consider the weighted Minkowski average

P‾λ:=1s∑i=1sλiPi.\overline{\mathrm{P}}_{\lambda}:=\frac{1}{s}\sum_{i=1}^{s}\lambda_i\mathrm{P}_i.

The normal fan of a Minkowski sum is the common refinement of the normal fans of its summands. Consequently, the normal fan of P‾λ\overline{P}_{\lambda} is independent of the positive weights λ\lambda; see [31 Sec. 6] and [42 Sec. 3.1]. Choose z∈int⁡(P‾1)z \in\operatorname{int}(\overline{P}_1). After translating by −z-z and positively scaling the inequalities in a minimal facet representation, we may write

P‾1−z=P(B,1).(2)\overline{P}_1-z=\mathbb{P}(B,1). \tag*{(2)}

This normalization changes neither the normal fan nor the number of facets. The common-refinement property and the normal-fan characterization of configuration cones then imply

∀λ∈R++s, ∃c∈K(B,1):P‾λ=P(B,c).(3)\forall\lambda\in\mathbb{R}^{s}_{++},\ \exists c \in K(B,1):\quad\overline{P}_{\lambda}=\mathbb{P}(B,c). \tag*{(3)}

The following proposition records the corresponding boundary cases.

Proposition 2 Let Pi=P(A,bi)P_i=\mathbb{P}(A,b_i), i∈{1,…,s}i\in\{1,\ldots,s\}, be full-dimensional polytopes with A∈A(n,d)A\in\mathcal{A}(n,d), and let B∈A(m,d)B\in\mathcal{A}(m,d) be a normalized minimal facet matrix satisfying (2). Then there exist vectors ci∈K(B,1)c_i\in K(B,1) such that

Pi=P(A,bi)=P(B,ci),i∈{1,…,s}.P_i=\mathbb{P}(A,b_i)=\mathbb{P}(B,c_i),\qquad i\in\{1,\ldots,s\}.

Proof. The normal fan of P(B,1)\mathbb{P}(B,1) is the common refinement of the normal fans of the summands and therefore refines the normal fan of each PiP_i. Define the BB-support vector of PiP_i by

(ci)j:=max⁡x∈PiBjx,j∈{1,…,m}.(c_i)_j:=\max_{x\in P_i} B_jx,\qquad j\in\{1,\ldots,m\}.

Every facet-normal ray of PiP_i is a ray of the common refinement, so P(B,ci)=Pi\mathbb{P}(B,c_i)=P_i. The normal-fan characterization of configuration cones further gives ci∈K(B,1)c_i\in K(B,1); see [31 Thm. 8] and [25]. □\square

Combinatorial Averaging

The core strategy for constructing configuration enclosures of an arbitrary matrix A∈A(n,d)A\in\mathcal{A}(n,d) is to construct the Minkowski average of its configurations. The corresponding method is summarized in Algorithm 1. The following

Algorithm 1 Combinatorial Averaging

  1. Start with any matrix A∈A(n,d)A\in\mathcal{A}(n,d).

  2. Pick for each maximal element Mi∈R(A)M_i\in\mathcal{R}(A) a representative bi∈int⁡(Mi)b_i\in\operatorname{int}(M_i) such that Mi=K(A,bi)M_i=K(A,b_i).

  3. Form the Minkowski average

P‾:=1σ(A)∑i=1σ(A)P(A,bi),\overline{P}:=\frac{1}{\sigma(A)}\sum_{i=1}^{\sigma(A)}\mathbb{P}(A,b_i),

choose z∈int⁡(P‾)z\in\operatorname{int}(\overline{P}), and compute a normalized minimal facet representation

P(B,1)=P‾−z.\mathbb{P}(B,1)=\overline{P}-z.
  1. Return the matrix BB.

theorem establishes the fact that this procedure returns the minimal configuration enclosure of any given facet matrix.

Theorem 2 Algorithm 1 returns a minimal configuration enclosure of any given input matrix A∈A(n,d)A\in\mathcal{A}(n,d).*

Proof. Let Pi:=P(A,bi)P_i:=\mathbb{P}(A,b_i), i∈{1,…,σ(A)}i\in\{1,\ldots,\sigma(A)\}, and let P(B,1)\mathbb{P}(B,1) be the normalized translate of their Minkowski average constructed in Step 3 of Algorithm 1. Proposition 2 implies that every PiP_i belongs to P(B,1)\mathbb{P}(B,1).

Because bi∈int⁡(Mi)b_i\in\operatorname{int}(M_i), each PiP_i is simple and minimally represented by AA. Hence every ray generated by a row of AA is a ray of the normal fan of each PiP_i. The normal fan of P(B,1)\mathbb{P}(B,1) is their common refinement and retains these rays. After a row permutation, we may therefore write

B=(DAB^),D=diag⁡(ρ1,…,ρn),ρi>0.B=\begin{pmatrix}DA\\ \widehat{B}\end{pmatrix},\qquad D=\operatorname{diag}(\rho_1,\ldots,\rho_n),\qquad\rho_i>0.
Eight original configurations and their Minkowski average

Figure 2 (PDF p. 11). LEFT: Eight simple polytopes, Pi=P(A,bi)P_i = \mathcal{P}(A,b_i), which are not configuration equivalent. They correspond to all possible configurations that can be obtained for the facet matrix A=[1 −1,1]T∈R7×3A = [1\ -1,1]^{\mathsf{T}} \in\mathbb{R}^{7 \times3}. RIGHT: the Minkowski average of these polytopes. To develop a geometric understanding of the exceptional adaptability of the face arrangement of the Minkowski average polytope depicted on the right, it is helpful to explore basic geometric manipulations achievable by pressing specific facets inward. Initially, consider the lower right polytope in the left panel, which has a triangular facet, oriented towards the viewer. By pressing this triangle inward, its vertices will eventually be blocked by the opposing vertices of the facet of the backside of the polytope. In stark contrast, pressing the hexagonal facet of the polytope on the right panel results in the convergence of the opposite edges of the adjacent rectangular facets. As the compression continues, these edges elongate until the three visible pentagonal facets degrade into points. Throughout this process, additional configuration constraints become active, but sufficient flexibility remains to further press the facet inwards, ultimately causing the entire polytope to degrade into a single point. It is worth noting that similar manipulations can be applied to other facets, allowing for the recovery of all eight polytopes on the left through a continuous deformation of the polytope on the right, without violating any configuration constraints.

Let c∈Rnc \in\mathbb{R}^{n} satisfy P(A,c)≠∅\mathcal{P}(A,c) \ne\varnothing. Replacing cc by its support vector, if necessary, does not change the polytope and ensures c∈C‾(A)c \in\overline{\mathcal{C}}(A). Since the configuration poset is finite, K(A,c)K(A,c) is contained in a maximal element Mk=K(A,bk)M_k = K(A,b_k). Thus c∈Mkc \in M_k, and the normal fan of PkP_k refines that of P(A,c)\mathcal{P}(A,c). By the common-refinement property, the normal fan of P(B,1)\mathcal{P}(B,1) also refines that of P(A,c)\mathcal{P}(A,c). Define

c^j:=max⁡x∈P(A,c)Bjx,j∈{1,…,m}.\widehat{c}_j := \max_{x \in\mathcal{P}(A,c)} B_jx,\qquad j \in\{1,\ldots,m\}.

Since the rows of BB include positive multiples of all rows of AA, the additional inequalities are valid support inequalities and P(B,c^)=P(A,c)\mathcal{P}(B,\widehat{c}) = \mathcal{P}(A,c). The normal-fan characterization gives c^∈K(B,1)\widehat{c} \in K(B,1). Therefore, BB is a configuration enclosure of AA; see [31 Thm. 8] and [25].

It remains to prove minimality. Let D∈A(r,d)D \in\mathcal{A}(r,d) be any configuration enclosure of AA. Then M(D,1)\mathcal{M}(D,1) contains every PiP_i. Lemma 1, together with closure under nonnegative scaling, implies that this class contains their Minkowski average. It is also translation invariant because Im⁡(D)\operatorname{Im}(D) is the lineality space of K(D,1)K(D,1). Hence, it contains the normalized translate P(B,1)\mathcal{P}(B,1) from Step 3. Thus, DD provides an rr-row facet representation of P(B,1)\mathcal{P}(B,1). Since BB is a minimal facet representation of this polytope, m≤rm \le r. Therefore, no configuration enclosure of AA has fewer rows than BB. □\square

In particular, the proof shows that the enclosure matrix contains every original normal direction, possibly with a positive rescaling.

Example 2 (A configuration enclosure) The steps of Algorithm 1 are illustrated by the matrix

A=(100−10010100−10100100−11)T.A = \begin{pmatrix} 1 & 0 & 0 & -1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & -1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & -1 & 1 \end{pmatrix}^{\mathsf{T}}.

The first six rows of this matrix are the facet normals of the unit cube in R3\mathbb{R}^{3}, while the seventh row vector of AA is orthogonal to the convex hull of the first three row vectors of AA. Consequently, AA can be used to represent, for

example, the unit cube, and many other geometric objects that can be obtained by intersecting the unit cube with a coordinate-aligned simplex. A more in-depth analysis shows that there are 8 configuration cones with nonempty interior, corresponding to the 8 maximal elements of the poset R(A)\mathcal{R}(A). For example, the vectors

b1=(2,2,2,0,0,0,3)T,b2=(1,3,3,0,0,0,5)T,b3=(3,1,3,0,0,0,5)T,b4=(3,3,1,0,0,0,5)T,b5=(2,2,4,0,0,0,5)T,b6=(4,2,2,0,0,0,5)T,b7=(2,4,2,0,0,0,5)T,and  b8=(2,2,2,0,0,0,5)T\begin{aligned} b_{1} &= (2,2,2,0,0,0,3)^{\mathsf{T}},\\ b_{2} &= (1,3,3,0,0,0,5)^{\mathsf{T}},\\ b_{3} &= (3,1,3,0,0,0,5)^{\mathsf{T}},\\ b_{4} &= (3,3,1,0,0,0,5)^{\mathsf{T}},\\ b_{5} &= (2,2,4,0,0,0,5)^{\mathsf{T}},\\ b_{6} &= (4,2,2,0,0,0,5)^{\mathsf{T}},\\ b_{7} &= (2,4,2,0,0,0,5)^{\mathsf{T}},\\ \text{and }\ b_{8} &= (2,2,2,0,0,0,5)^{\mathsf{T}} \end{aligned}

represent 8 different polytopes P(A,bi)P(A,b_i), i∈{1,…,8}i \in\{1,\ldots,8\}. These polytopes are all simple and pairwise configuration-inequivalent with respect to the fixed row labels of AA, although some of them are combinatorially equivalent after relabeling their facets. Thus, if we initialize Algorithm 1 with AA, we can pick these vectors as representatives of the maximal elements of R(A)\mathcal{R}(A). Next, we work out the Minkowski average in Step 3) of Algorithm 1. After scaling the rows of BB appropriately, this yields

B=(100−10010110100−10110100100−11110)T.B=\begin{pmatrix} 1&0&0&-1&0&0&1&0&1&1\\ 0&1&0&0&-1&0&1&1&0&1\\ 0&0&1&0&0&-1&1&1&1&0 \end{pmatrix}^{\mathsf{T}}.

A corresponding (appropriately scaled) representative vector is given by

c⋆=(3 3 3 0 0 0 6 5 5 5)T,c^{\star}=(3\ 3\ 3\ 0\ 0\ 0\ 6\ 5\ 5\ 5)^{\mathsf{T}},

where P(B,c⋆)\mathcal{P}(B,c^{\star}) contains the Minkowski average polytope. The translation and positive row scaling used in Step 3 merely normalize an interior representative to 1 and do not change these enclosure directions or the represented family. All simple polytopes in the Minkowski class P(B,c⋆)\mathcal{P}(B,c^{\star}) have 10 facets in total. These facets always consist of 1 hexagon, 6 pentagons, and 3 rectangles; see Figure 2.

Remark 3 Minimal configuration enclosures need not be monotypic. In Example 1, the minimal configuration enclosure is monotypic, whereas the minimal configuration enclosure obtained in Example 2 is not, since R(B)\mathcal{R}(B) admits more than one maximal element. In particular, the polytope P(B,c~)P(B,\widetilde{c}) with c~=(4,4,4,0,0,0,7,5,5,5)T\widetilde{c}=(4,4,4,0,0,0,7,5,5,5)^{\mathsf{T}} is simple and minimally represented by all rows of BB but it is not configuration-equivalent to P(B,c⋆)P(B,c^{\star}), hence σ(B)>1\sigma(B)>1.

Proof of Theorem 1

Let

C1d:={X∈Cd∣0∈X, diam⁡(X)=1}.\mathcal{C}_{1}^{d}:=\{X\in\mathcal{C}^{d}\mid0\in X,\ \operatorname{diam}(X)=1\}.

The Blaschke selection theorem implies that C1d\mathcal{C}_{1}^{d} is compact in the Hausdorff metric; see [42 Sec. 1.8]. For each X∈C1dX\in\mathcal{C}_{1}^{d}, classical polytope-approximation results provide a full-dimensional polytope QXQ_X satisfying

dH(X,QX)<ϵ/2;d_H(X,Q_X)<\epsilon/2;

see [10, 6, 41]. Compactness yields finitely many sets X1,…,XN∈C1dX_1,\ldots,X_N\in\mathcal{C}_{1}^{d} whose Hausdorff balls of radius ϵ/2\epsilon/2 cover C1d\mathcal{C}_{1}^{d}. Let AA collect all outward facet normals of the finitely many polytopes QX1,…,QXNQ_{X_1},\ldots,Q_{X_N}, after repeated positive directions have been removed. Since each QXkQ_{X_k} is bounded and full-dimensional, its facet normals positively span Rd\mathbb{R}^{d}; hence, A∈A(n,d)A\in A(n,d) for some nn. Assigning the additional inequalities their support values gives a representation QXk=P(A,bk)Q_{X_k}=P(A,b_k) for every kk. Hence, for every X∈C1dX\in\mathcal{C}_{1}^{d}, some kk satisfies

dH(X,P(A,bk))≤dH(X,Xk)+dH(Xk,QXk)<ϵ.d_H(X,P(A,b_k))\leq d_H(X,X_k)+d_H(X_k,Q_{X_k})<\epsilon.

Translation and positive scaling extend this estimate to every Y∈CdY \in\mathbb{C}^{d} with positive diameter: for y∈Yy \in Y, apply the normalized result to (Y−y)/diam⁡(Y)(Y-y)/\operatorname{diam}(Y) and use

αP(A,b)+y=P(A,αb+Ay).\alpha P(A,b)+y=P(A,\alpha b+Ay).

Singletons are represented exactly because P(A,Ay)={y}P(A,Ay)=\{y\}. Thus, the family of all polytopes P(A,⋅)P(A,\cdot) is ϵ\epsilon-dense in Cd\mathbb{C}^{d}. Finally, Theorem 2 provides a configuration enclosure BB of AA. By definition, P(B,1)\mathcal{P}(B,1) contains every nonempty polytope representable with AA and is therefore also ϵ\epsilon-dense in Cd\mathbb{C}^{d}. Renaming BB as AA proves the theorem. □\square

Computational Scope and Offline Construction

Algorithm 1 has a primarily theoretical role. Together with Theorem 2, it provides a finite construction of a minimal configuration enclosure for every admissible facet matrix. As shown in the preceding subsection, this construction also completes the constructive proof of Theorem 1. Thus, Algorithm 1 establishes not only the existence of universal Minkowski classes, but also that they can, in principle, be generated by a finite procedure.

To make the enumeration step explicit, quotient the parameter space by the translation lineality Im⁡(A)\operatorname{Im}(A) and fix one positive scale. The maximal elements of K(A)\mathcal{K}(A) then appear as the maximal cells of a finite type-cone, or chamber, subdivision. Two maximal elements are adjacent when their normalized cells share a codimension-one face. The resulting adjacency graph is finite and connected: the chamber fan is the normal fan of a secondary polyhedron, and its maximal cones are connected through facet adjacencies [12 Cor. 1.42 and Rem. 1.45]. A generic parameter in the relative interior of the normalized admissible domain supplies an initial maximal cell. Starting from this cell, one may therefore enumerate all maximal elements by generating the neighboring cells across its irredundant facets and traversing this graph with breadth-first or depth-first search; reverse search provides a memory-efficient alternative [2]. This supplies a finite enumeration scheme in principle, although constructing efficient local adjacency oracles and output-sensitive implementations remains beyond the scope of this paper.

This constructive result should not be interpreted as a claim that combinatorial averaging is the most efficient method for computing configuration enclosures. The desired object is the enclosure matrix BB, rather than the enumeration or the Minkowski average itself. Consequently, alternative constructions might generate a configuration enclosure—possibly a minimal one—without explicitly enumerating all maximal elements of K(A)\mathcal{K}(A) or forming their complete Minkowski average.

The relevant computational tasks belong to a broad and active research area on output-sensitive enumeration methods for combinatorial and polyhedral problems. Representative developments include pivoting and reverse-search methods for polyhedra and hyperplane arrangements [1, 2], algorithms and complexity results for Minkowski sums [19, 13], and region-enumeration procedures in multiparametric programming [45]. These methods indicate several possible directions for specialized implementations of Algorithm 1, but developing and comparing such implementations is beyond the scope of this article.

The computational burden of Algorithm 1 has two principal sources: the enumeration of the σ(A)\sigma(A) maximal elements of K(A)\mathcal{K}(A) and the construction of a minimal facet representation of their Minkowski average. A coarse bound on the size of the latter output can nevertheless be obtained. Since all representative polytopes P(A,bi)P(A,b_i) share the same facet matrix AA, every edge direction is orthogonal to d−1d-1 linearly independent rows of AA. Hence, the number of possible unoriented edge directions is at most

Ne≤(nd−1).N_e \le\binom{n}{d-1}.

Moreover, every edge direction of the Minkowski average is inherited from an edge direction of one of its summands. Since a facet contains d−1d-1 linearly independent edge directions, its normal line is determined by at most d−1d-1 elements of this set. Therefore, the number m‾\overline{m} of candidate facet-normal lines, where opposite normals are identified, satisfies

m‾≤(Ned−1)≤((nd−1)d−1).\overline{m} \le\binom{N_e}{d-1} \le\binom{\binom{n}{d-1}}{d-1}.

Consequently, without identifying opposite facet normals, the number mm of rows of BB admits the conservative bound

m≤2((nd−1)d−1).m \le2\binom{\binom{n}{d-1}}{d-1}.

This is only an output-size estimate. In particular, it does not bound σ(A)\sigma(A), the cost of enumerating the maximal configuration cones, or the possible growth of intermediate representations during the Minkowski-sum computation. It should therefore not be interpreted as a complete runtime-complexity bound for Algorithm 1.

Visualization of a dodecahedron (left) and its minimal configuration enclosure (right). ORIGINAL POLYTOPE. Facets: 12 pentagons. Edges: 30 line seg. Vertices: 20 points. CONF. ENCLOSURE. Facets: 12 decagons, 20 hexagons, 30 rectangles. Edges: 180 line seg. Vertices: 120 points.

Figure 3 (PDF p. 14). Visualization of a dodecahedron (left) and its minimal configuration enclosure (right). The closure of the set of polytopes that are configuration equivalent to the right polytope contains, beside many other interesting geometric objects, the famous ”soccer ball polytope”, consisting of 12 pentagonal and 20 hexagonal facets. It is obtained by pressing the hexagonal facets of the right polytope inwards, initially without changing the face lattice, until the opposite edges of the rectangular facets merge in the limit.

Example 3 (Dodecahedron). The conservatism of the preceding estimate is illustrated by Figure 3. The original dodecahedron has dimension d=3d = 3 and n=12n = 12 facets. Thus,

Ne≤(122)=66,(Ne2)≤(662)=2145.N_{\mathrm{e}} \le\binom{12}{2} = 66,\qquad\binom{N_{\mathrm{e}}}{2} \le\binom{66}{2} = 2145.

Equivalently, the general oriented-normal estimate gives

m≤2(662)=4290.m \le2\binom{66}{2} = 4290.

In contrast, Algorithm 1 returns a minimal configuration enclosure with only

m=62m = 62

facets. The enclosure consists of 12 decagonal, 20 hexagonal, and 30 rectangular facets. This example shows that the combinatorial estimate may overstate the actual output size by several orders of magnitude.

Once a suitable enclosure has been computed, the combinatorial construction need not be repeated in subsequent control applications. The resulting facet and vertex coefficient matrices can be stored and reused for different systems of the same dimension, or distributed as precomputed template libraries. The online polytopic optimization problems then use only the resulting jointly affine facet–vertex parameterization and do not invoke Algorithm 1.

Randomized exploration, symmetry reduction, incremental Minkowski-sum updates, and partial averaging may all be useful for reducing the practical computational effort. However, the exact guarantee of Theorem 2 relies on accounting for every maximal element of K(A)\mathcal{K}(A); averaging only a sampled subset generally produces an uncertified candidate rather than a configuration enclosure. Finding efficient, preferably output-sensitive methods for computing minimal configuration enclosures therefore remains an open problem and is beyond the scope of the present manuscript.

Open Problem: Adversarial Convex Bodies

Theorem 1 establishes the existence of configuration-constrained Minkowski classes with arbitrarily small approximation error. For a prescribed class P(A,b)\mathcal{P}(A,b), its worst-case approximation error can be defined as

γ(A,b):=sup⁡Y∈Cddiam⁡(Y)>0inf⁡c∈K(A,b)dH(Y,P(A,c))diam⁡(Y).\gamma(A,b) := \sup_{\substack{Y \in\mathcal{C}^{d}\\ \operatorname{diam}(Y)>0}}\inf_{c \in\mathcal{K}(A,b)}\frac{d_{\mathrm{H}}(Y,\mathcal{P}(A,c))}{\operatorname{diam}(Y)}.

Since P(A,b)\mathcal{P}(A,b) is invariant under translations and positive scalings, the outer supremum may equivalently be restricted to sets satisfying

0∈Yanddiam⁡(Y)=1.0 \in\mathcal{Y} \qquad\text{and}\qquad\operatorname{diam}(\mathcal{Y})=1.

This normalized family is compact in the Hausdorff metric, while the distance to the closed class P(A,b)\mathcal{P}(A,b) is continuous. Consequently, the supremum is attained. We call any corresponding maximizer Y⋆∈Cd\mathcal{Y}^{\star} \in\mathcal{C}^{d} an adversarial convex body for the class P(A,b)\mathcal{P}(A,b).

The geometric properties of such adversarial convex bodies remain largely open. In particular, it is not clear whether an adversarial convex body can always be chosen to be polyhedral, whether its dimension or combinatorial complexity can be bounded in terms of AA and K(A,b)K(A,b), or how its exposed directions are related to the prescribed facet configuration. For a fixed Y\mathcal{Y}, the inner minimization can be treated using the joint facet–vertex parameterization (1). The principal difficulty is the global optimization over Y∈Cd\mathcal{Y} \in\mathcal{C}^{d}. Structural characterizations and certified computational methods for determining γ(A,b)\gamma(A,b) would provide a quantitative basis for comparing different configuration cones and their configuration enclosures.

Applications of Universal Minkowski Classes

Optimization over compact convex sets arises in shape optimization, robust design, uncertainty quantification, and learning-based safety; see, for example, the Galerkin framework in [40] and set-based approaches to safe learning in [28, 30]. The main focus of this article, however, is set-theoretic control, where polytopes are routinely used to represent invariant sets, reachable sets, robust tubes, and polyhedral control Lyapunov functions.

This section explains how the approximation result of Theorem 1 connects with convex computational methods in control. The key object is a configuration triple (A,E,V)(A,E,V), which provides a finite-dimensional parameterization in which both facets and vertices depend affinely on the same decision variables. A broader account of the corresponding control formulations can be found in [25, 26].

Minkowski-Convex Set Optimization

Consider an optimization problem whose decision variable is a compact convex set,

minimize⁡Y∈CdG0(Y)subject toGj(Y)≤0,j∈{1,…,q}.(4)\begin{aligned} &\underset{\mathcal{Y}\in\mathcal{C}^{d}}{\operatorname{minimize}} && G_0(\mathcal{Y})\\ &\text{subject to} && G_j(\mathcal{Y})\leq0,\qquad j\in\{1,\ldots,q\}. \tag*{(4)} \end{aligned}

A functional G:Cd→RG:\mathcal{C}^{d}\to\mathbb{R} is called Minkowski-convex if

G(θY1+(1−θ)Y2)≤θG(Y1)+(1−θ)G(Y2)(5)G(\theta\mathcal{Y}_1+(1-\theta)\mathcal{Y}_2)\leq\theta G(\mathcal{Y}_1)+(1-\theta)G(\mathcal{Y}_2) \tag*{(5)}

for all Y1,Y2∈Cd\mathcal{Y}_1,\mathcal{Y}_2\in\mathcal{C}^{d} and θ∈[0,1]\theta\in[0,1]. Problem (4) is therefore a convex optimization problem in the natural linear structure induced by Minkowski addition and nonnegative set scaling. Several relevant examples are collected below.

Example 4 (Polytopic inclusions) For a fixed direction p∈Rdp\in\mathbb{R}^{d}, the support function

hY(p):=max⁡x∈YpTxh_{\mathcal{Y}}(p):=\max_{x\in\mathcal{Y}}p^{\mathsf{T}}x

is Minkowski-affine, because

hθY1+(1−θ)Y2(p)=θhY1(p)+(1−θ)hY2(p).h_{\theta\mathcal{Y}_1+(1-\theta)\mathcal{Y}_2}(p)=\theta h_{\mathcal{Y}_1}(p)+(1-\theta)h_{\mathcal{Y}_2}(p).

Consequently, maxima of affine expressions involving support functions are Minkowski-convex. This observation is particularly useful for representing set-containment constraints. For example, if

X={x∈Rd∣Hx≤h},\mathcal{X}=\{x\in\mathbb{R}^{d}\mid Hx\leq h\},

then the functional

Ginc(Y):=max⁡i{hY(HiT)−hi}G_{\mathrm{inc}}(\mathcal{Y}):=\max_i\{h_{\mathcal{Y}}(H_i^{\mathsf{T}})-h_i\}

is Minkowski-convex and satisfies

Ginc(Y)≤0⟺Y⊆X.G_{\mathrm{inc}}(\mathcal{Y})\leq0 \quad\Longleftrightarrow\quad\mathcal{Y}\subseteq\mathcal{X}.

Example 5 (Volume functionals). A standard objective to maximize the volume of sets in Rd\mathbb{R}^{d} is given by

Gvol(Y):=−vol⁡(Y)1/d.\mathcal{G}_{\mathrm{vol}}(\mathbb{Y}) := -\operatorname{vol}(\mathbb{Y})^{1/d}.

The Brunn–Minkowski inequality implies [17, 42]

vol⁡(θY1+(1−θ)Y2)1/d≥θvol⁡(Y1)1/d+(1−θ)vol⁡(Y2)1/d.\operatorname{vol}\left(\theta\mathbb{Y}_{1}+(1-\theta)\mathbb{Y}_{2}\right)^{1/d} \geq\theta\operatorname{vol}(\mathbb{Y}_{1})^{1/d}+(1-\theta)\operatorname{vol}(\mathbb{Y}_{2})^{1/d}.

Thus, Gvol\mathcal{G}_{\mathrm{vol}} is Minkowski-convex. Notice that the negative volume itself is not, in general, Minkowski-convex when d>1d>1.

Example 6 (Distance functionals). For a fixed point x∈Rdx\in\mathbb{R}^{d}, the set-distance functional

Gx(Y):=d(x,Y)=min⁡y∈Y∥x−y∥\mathcal{G}_{x}(\mathbb{Y}) := d(x,\mathbb{Y})=\min_{y\in\mathbb{Y}}\lVert x-y\rVert

is Minkowski-convex. Indeed, choosing yi∈Yiy_i\in\mathbb{Y}_i as nearest points to xx gives

d(x,θY1+(1−θ)Y2)≤∥θ(x−y1)+(1−θ)(x−y2)∥≤θd(x,Y1)+(1−θ)d(x,Y2).\begin{aligned} d\left(x,\theta\mathbb{Y}_{1}+(1-\theta)\mathbb{Y}_{2}\right) &\leq\left\lVert\theta(x-y_{1})+(1-\theta)(x-y_{2})\right\rVert\\ &\leq\theta d(x,\mathbb{Y}_{1})+(1-\theta)d(x,\mathbb{Y}_{2}). \end{aligned}

More generally, for a fixed compact convex set X\mathbb{X}, both the directed set distance

max⁡x∈Xd(x,Y)\max_{x\in\mathbb{X}}d(x,\mathbb{Y})

and the Hausdorff distance

dH(X,Y)d_{\mathrm{H}}(\mathbb{X},\mathbb{Y})

are Minkowski-convex as functions of Y\mathbb{Y}. These functionals provide natural measures of set-inclusion violation and geometric approximation error; see also [40].

Example 7 (Invariance constraints). The preceding properties can be combined to formulate robust control-invariance conditions. Consider

x+=Fx+Gu+w,u∈U,w∈W,x^{+}=Fx+Gu+w,\qquad u\in\mathbb{U},\quad w\in\mathbb{W},

where U\mathbb{U} and W\mathbb{W} are compact and U\mathbb{U} is convex. Define

Grci(Y):=max⁡x∈Ymin⁡u∈Umax⁡w∈Wd(Fx+Gu+w,Y).(6)\mathcal{G}_{\mathrm{rci}}(\mathbb{Y}):=\max_{x\in\mathbb{Y}}\min_{u\in\mathbb{U}}\max_{w\in\mathbb{W}}d(Fx+Gu+w,\mathbb{Y}). \tag*{(6)}

This functional is Minkowski-convex. To see this, let

Yθ=θY1+(1−θ)Y2\mathbb{Y}_{\theta}=\theta\mathbb{Y}_{1}+(1-\theta)\mathbb{Y}_{2}

and write an arbitrary xθ∈Yθx_{\theta}\in\mathbb{Y}_{\theta} as

xθ=θx1+(1−θ)x2,xi∈Yi.x_{\theta}=\theta x_{1}+(1-\theta)x_{2},\qquad x_i\in\mathbb{Y}_i.

For controls ui∈Uu_i\in\mathbb{U} that attain, or arbitrarily closely approximate, the inner minima, define

uθ=θu1+(1−θ)u2∈U.u_{\theta}=\theta u_{1}+(1-\theta)u_{2}\in\mathbb{U}.

For every w∈Ww\in\mathbb{W}, convexity of the distance under simultaneous Minkowski combinations yields

d(Fxθ+Guθ+w,Yθ)≤θd(Fx1+Gu1+w,Y1)+(1−θ)d(Fx2+Gu2+w,Y2).\begin{aligned} d(Fx_{\theta}+Gu_{\theta}+w,\mathbb{Y}_{\theta}) &\leq\theta d(Fx_{1}+Gu_{1}+w,\mathbb{Y}_{1})\\ &\quad+(1-\theta)d(Fx_{2}+Gu_{2}+w,\mathbb{Y}_{2}). \end{aligned}

Taking successively the maximum over ww, the minimum over the control, and the maximum over the state gives

Grci(Yθ)≤θGrci(Y1)+(1−θ)Grci(Y2).\mathcal{G}_{\mathrm{rci}}(\mathbb{Y}_{\theta}) \leq\theta\mathcal{G}_{\mathrm{rci}}(\mathbb{Y}_{1})+(1-\theta)\mathcal{G}_{\mathrm{rci}}(\mathbb{Y}_{2}).

Moreover, since the distance is nonnegative, it holds that

Grci(Y)≤0⟺{∀x∈Y, ∃u∈U: ∀w∈WFx+Gu+w∈Y.\mathcal{G}_{\mathrm{rci}}(\mathbb{Y})\leq0 \Longleftrightarrow \begin{cases} \forall x\in\mathbb{Y},\ \exists u\in\mathbb{U}:\ \forall w\in\mathbb{W}\\ Fx+Gu+w\in\mathbb{Y}. \end{cases}

These examples cover the main ingredients of many set-theoretic control problems: geometric size objectives, approximation errors, state-set containment, and robust invariance. Thus, such problems can often be expressed in the Minkowski-convex form (4); see [47, 25] for further examples. The remaining difficulty is that optimization over Cd\mathbb{C}^{d} is infinite-dimensional. The following subsection explains how universal configuration-constrained Minkowski classes provide finite-dimensional convex discretizations of these problems.

Restoring Convexity to Polytopic Parameterizations

Problem (4) is infinite-dimensional. A natural finite-dimensional approximation is obtained by fixing a facet matrix A∈Rn×dA \in\mathbb{R}^{n \times d} and parameterizing the decision set as Y=P(A,b)\mathcal{Y} = \mathcal{P}(A,b). This yields

minimize⁡b∈RnG0(P(A,b))subject toGj(P(A,b))≤0,j∈{1,…,q}.(7)\begin{aligned} \underset{b \in\mathbb{R}^{n}}{\operatorname{minimize}}\quad& \mathcal{G}_0(\mathcal{P}(A,b)) \\ \text{subject to}\quad& \mathcal{G}_j(\mathcal{P}(A,b)) \le0,\qquad j \in\{1,\ldots,q\}. \tag*{(7)} \end{aligned}

Although finite-dimensional, this problem is generally non-convex. Indeed, as bb varies, the vertices and face-incidence structure of P(A,b)\mathcal{P}(A,b) may change. Functionals involving both its facet and vertex representations therefore become piecewise-defined or disjunctive in the parameter bb.

This difficulty is removed by restricting the parameters to a configuration cone. Let

K(A,1)={b∈Rn∣Eb≤0}.\mathbb{K}(A,\mathbf{1}) = \{b \in\mathbb{R}^{n} \mid Eb \le0\}.

Such a finite polyhedral representation follows from the configuration-cone construction; see [47, 25]. The resulting discretization is

minimize⁡b∈RnG0(P(A,b))subject toGj(P(A,b))≤0,j∈{1,…,q},Eb≤0.(8)\begin{aligned} \underset{b \in\mathbb{R}^{n}}{\operatorname{minimize}}\quad& \mathcal{G}_0(\mathcal{P}(A,b)) \\ \text{subject to}\quad& \mathcal{G}_j(\mathcal{P}(A,b)) \le0,\qquad j \in\{1,\ldots,q\}, \\ & Eb \le0. \tag*{(8)} \end{aligned}

On K(A,1)\mathbb{K}(A,\mathbf{1}), the facets and vertices of P(A,b)\mathcal{P}(A,b) admit a joint affine parameterization. More fundamentally, the set-valued mapping b↦P(A,b)b \mapsto\mathcal{P}(A,b) is affine with respect to Minkowski combinations:

P(A,θb+(1−θ)c)=θP(A,b)+(1−θ)P(A,c)(9)\mathcal{P}(A,\theta b + (1-\theta)c) = \theta\mathcal{P}(A,b) + (1-\theta)\mathcal{P}(A,c) \tag*{(9)}

for all b,c∈K(A,1)b,c \in\mathbb{K}(A,\mathbf{1}) and θ∈[0,1]\theta\in[0,1]. Hence, every Minkowski-convex functional Gj\mathcal{G}_j induces a convex function

b↦Gj(P(A,b))b \mapsto\mathcal{G}_j(\mathcal{P}(A,b))

on the configuration cone. Consequently, Problem (8) is a finite-dimensional convex optimization problem. For many problems in set-theoretic control, its objective and constraints additionally admit explicit linear or conic representations.

Theorem 1 shows that imposing a configuration constraint does not create an intrinsic geometric approximation barrier: suitably chosen configuration-constrained Minkowski classes can approximate every compact convex set to arbitrary accuracy. Suppose that the functionals Gj\mathcal{G}_j are Hausdorff-continuous, the feasible sets lie in a common Hausdorff-compact family, an optimal solution exists, and Problem (4) admits a strictly feasible solution. Minkowski combinations of an optimal and a strictly feasible solution yield strictly feasible sets with objective values arbitrarily close to the optimum. Density and continuity then imply convergence of the optimal values of increasingly accurate universal-template discretizations. Configuration constraints thus restore convexity without fundamentally sacrificing geometric expressiveness.

Example 8 (CI polytopes: convex formulation). We illustrate the use of configuration templates by computing control invariant inner approximations of the maximal control invariant set for the three-dimensional system

x+=Fx+u,withF=(001cos⁡(7)−sin⁡(7)0sin⁡(7)cos⁡(7)0)3x^{+}=Fx+u,\qquad\text{with}\quad F=\begin{pmatrix}0&0&1\\ \cos(7)&-\sin(7)&0\\ \sin(7)&\cos(7)&0\end{pmatrix}^{3}

where the angle is measured in radians. The state and control constraints are given by

X={x∈R3∣x≥0, 1Tx≤1}andU=[−110,110]3,\mathbb{X}=\left\{x\in\mathbb{R}^{3}\mid x\ge0,\ \mathbf{1}^{\mathsf{T}}x\le1\right\}\quad\text{and}\quad\mathbb{U}=\left[-\frac{1}{10},\frac{1}{10}\right]^{3},

respectively.

The computation of a maximal control invariant set can be formulated as a Minkowski-convex optimization problem over compact convex subsets of X\mathbb{X}. In this formulation, state-set containment and control invariance are imposed through the functionals introduced in Examples 4 and 7, respectively, while the objective is chosen as the volume functional

Gvol(Y)=−vol⁡(Y)1/3\mathcal{G}_{\mathrm{vol}}(\mathbb{Y})=-\operatorname{vol}(\mathbb{Y})^{1/3}

from Example 5.

As described in the preceding section, a finite-dimensional convex discretization is obtained by restricting the decision set to a Minkowski class P(C,c)\mathbb{P}(\mathcal{C},c). Using the equivalences in Examples 4 and 7, with W={0}\mathbb{W}=\{0\}, the feasible region

{Y∈P(C,c)∣Grci(Y)≤0, Ginc(Y)≤0}\left\{\mathbb{Y}\in\mathbb{P}(\mathcal{C},c)\mid\mathcal{G}_{\mathrm{rci}}(\mathbb{Y})\le0,\ \mathcal{G}_{\mathrm{inc}}(\mathbb{Y})\le0\right\}

corresponds to the finite-dimensional polyhedron

F={b∈Rc | ∃u1,…,uv∈U: ∀i∈{1,…,v},C(FVib+ui)≤b,1TVib≤1, Vib≥0,Eb≤0}.\mathbb{F}=\left\{b\in\mathbb{R}^{c}\ \middle|\ \begin{gathered}\exists u_{1},\ldots,u_{v}\in\mathbb{U}:\ \forall i\in\{1,\ldots,v\},\\ C(FV_{i}b+u_{i})\le b,\\ \mathbf{1}^{\mathsf{T}}V_{i}b\le1,\ V_{i}b\ge0,\\ Eb\le0\end{gathered}\right\}.

Here, the vertex matrices V1,…,VvV_{1},\ldots,V_{v} provide the joint facet–vertex representation of the selected configuration class, which is represented by the matrix EE, compare [47 Sect. 3.5]. The first constraint enforces the invariance condition at the vertices, which is equivalent to enforcing Grci(P(C,b))≤0\mathcal{G}_{\mathrm{rci}}(\mathbb{P}(\mathcal{C},b))\le0, with W={0}\mathbb{W}=\{0\}; see also [25]. In this context, the constraint Eb≤0Eb\le0 restricts bb to the chosen configuration cone, and the constraints on uiu_i ensure admissibility of the associated vertex controls. Similarly, Vib≥0V_i b\ge0 and 1TVib≤1\mathbf{1}^{\mathsf{T}}V_i b\le1 for all vertices are equivalent to P(C,b)⊆X\mathbb{P}(\mathcal{C},b)\subseteq\mathbb{X}; that is Ginc(P(C,b))≤0\mathcal{G}_{\mathrm{inc}}(\mathbb{P}(\mathcal{C},b))\le0.

Let T\mathcal{T} be a set of index tuples enumerating the vertices of the simplices σ\sigma of a tetrahedralization of a representative polytope in the relative interior of the configuration cone. For each index tuple τ=(i0,i1,i2,i3)∈T\tau=(i_0,i_1,i_2,i_3)\in\mathcal{T} of a tetrahedron, order its vertices such that the corresponding determinant is positive at the representative, and define

Dτ,j:=Vij−Vi0,j∈{1,2,3}.D_{\tau,j}:=V_{i_j}-V_{i_0},\qquad j\in\{1,2,3\}.

Since the labeled face configuration is constant on the relative interior, the same vertex-index tetrahedralization applies there and

vol⁡(P(C,b))=16∑τ∈Tdet⁡[Dτ,1bDτ,2bDτ,3b].\operatorname{vol}(\mathbb{P}(\mathcal{C},b))=\frac{1}{6}\sum_{\tau\in\mathcal{T}}\det\begin{bmatrix}D_{\tau,1}b&D_{\tau,2}b&D_{\tau,3}b\end{bmatrix}.

Thus, vol⁡(P(C,b))\operatorname{vol}(\mathcal{P}(C,b)) is a homogeneous cubic polynomial in bb, which extends continuously to the boundary of the configuration cone. Although this polynomial is not concave in general, its cube root is concave by the Brunn–Minkowski inequality.

Therefore, for each candidate class, the problem

maximize⁡b∈Fvol⁡(P(C,b))1/3.(10)\underset{b \in\mathcal{F}}{\operatorname{maximize}}\quad\operatorname{vol}(\mathcal{P}(C,b))^{1/3}. \tag*{(10)}

returns a control invariant set with maximal volume. Here, we solve it for each of the eight maximal configuration cones

Mq=K(A,bq),q∈{1,…,8},\mathcal{M}_q = \mathcal{K}(A,b_q), \qquad q \in\{1,\ldots,8\},

in Example 2 and its configuration enclosure. Consequently, every feasible solution of (10) defines a certified control invariant inner approximation of the maximal control invariant set. Alternative set-size objectives can also be used to select control invariant sets while preserving a linear-programming formulation; see, e.g., [25 Sections 3.1 and 3.2] for examples applied to reachable and positive invariant polytopes. Such objectives may be useful when a computationally simpler selection criterion is preferred over the volume-based objective.

Figure 4 shows the resulting control invariant inner approximations. The lighter enclosing polytope is the maximal control invariant set, while the darker polytopes are the inner approximations, of maximal volume, obtained from the eight maximal configuration cones of AA. The optimizer associated with

Eight nested polytope configurations

Figure 4. Eight nested polytope configurations. The inner polytopes are shown in gray, while their enclosing outer polytopes are displayed using a lighter gray and lower opacity.

M1=K(A,b1)\mathcal{M}_1 = \mathcal{K}(A,b_1)

is the top-left polytope in Figure 4 and has seven facets and ten vertices.

In this example, the optimizer obtained from the configuration-enclosure class happens to coincide with the optimizer obtained from the first configuration cone M1\mathcal{M}_1. Although a generic polytope in the enclosure class has ten facets, the optimal parameter lies on the boundary of its configuration cone. At this boundary point, some facet inequalities become redundant, and the resulting polytope reduces to the seven-facet configuration associated with M1\mathcal{M}_1. The results in Figure 4 show that for this example optimizing over the configuration enclosure yields a control invariant set whose volume is at least as large as that of the polytopes obtained from the basis configurations.

Conclusion

This paper has established that prescribing a fixed facet–vertex configuration creates no intrinsic geometric approximation barrier. For every dimension d≥1d \ge1 and every accuracy ϵ>0\epsilon> 0, Theorem 1 provides a configuration-constrained Minkowski class that is ϵ\epsilon-dense in the compact convex sets. The combinatorial-averaging construction produces such classes through minimal configuration enclosures while retaining the joint affine facet–vertex parameterization required for convex computation. In set-theoretic control, this resolves a geometric question left open by earlier configuration-constrained tube-MPC and control-Lyapunov-function constructions [47, 26]: restricting a parametric polytope to one suitably chosen fixed configuration does not inherently sacrifice universal approximation capability.

The final section showed how invariant-set and related control problems can be cast as Minkowski-convex set-optimization problems and discretized through finite-dimensional convex parameterizations by configuration-constrained polytopes. More broadly, the theoretical results establish that such parameterizations can be made arbitrarily expressive and open several directions for further research, including the efficient construction of universal Minkowski classes, the structural and computational characterization of adversarial convex bodies, and the output-sensitive enumeration of maximal configuration cones.

Acknowledgement

The authors would like to thank Colin Jones for inspiring discussions during the first author’s research stay at EPFL in 2023. During these discussions, Colin Jones raised the question whether configuration-constraints fundamentally obstruct the approximation of convex bodies to arbitrary accuracy. This motivated the central problem addressed in this work. Our results confirm that, provided the configuration templates are chosen appropriately, no such obstruction exists.

References

  1. [1]D. Avis and K. Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Computational Geometry, 8:295–313, 1992.
  2. [2]D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65:21–46, 1996.DOI
  3. [3]G. Bitsoris. On the positive invariance of polyhedral sets for discrete-time systems. Systems and Control Letter, 11(3):243–248, 1988.DOI
  4. [4]F. Blanchini. Set invariance in control. Automatica, 35(11):1747–1767, 1999.DOI
  5. [5]F. Blanchini and S. Miani. Set-theoretic methods in control. Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston, MA, 2015.
  6. [6]E.M. Bronshtein and L. D. Ivanov. The approximation of convex sets by polyhedra. Siberian Mathematical Journal, 16(5):852–853, 1975.
  7. [7]Vuong Bui. Every generating polytope is strongly monotypic. Discrete & Computational Geometry, 73(1):49–61, 2025.
  8. [8]C. Carathéodory. Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen. Rend. Circ. Mat. Palermo, 32:193–217, 1911.DOI
  9. [9]G.B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1963.
  10. [10]R.M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. Journal of Approximation Theory, 10(3):227–236, 1974.
  11. [11]J. Farkas. Theorie der einfachen Ungleichungen. Journal für die reine und angewandte Mathematik, 124:1–27, 1902.DOI
  12. [12]F. Fillastre and I. Izmestiev. Shapes of polyhedra, mixed volumes and hyperbolic geometry. Mathematika, 63(1):124–183, 2017.
  13. [13]K. Fukuda. From the zonotope construction to the minkowski addition of convex polytopes. Journal of Symbolic Computation, 38(4):1261–1272, 2004.DOI
  14. [14]K Fukuda. Polyhedral Computation. ETH Zürich Research Collection, 2020.DOI
  15. [15]K. Fukuda and A. Prodon. Double description method revisited. In M. Deza, R. Euler, and I. Manoussakis, editors, Combinatorics and Computer Science, pages 91–111. Springer, 1996.DOI
  16. [16]D. Gale. The Theory of Linear Economic Models. McGraw-Hill, New York, 1960.
  17. [17]R.J. Gardner. The brunn–minkowski inequality. Bulletin of the American Mathematical Society, 39(3):355–405, 2002.DOI
  18. [18]R. Graham and F. Yao. A whirlwind tour of computational geometry. American Mathematical Monthly, 97(8):687–701, 1990.DOI
  19. [19]P. Gritzmann and B. Sturmfels. Minkowski addition of polytopes: Computational complexity and applications to gröbner bases. SIAM Journal on Discrete Mathematics, 6(2):246–269, 1993.DOI
  20. [20]B. Grünbaum. Convex Polytopes. John Wiley & Sons, 1967.
  21. [21]P.-O. Gutman and M. Cwikel. An algorithm to find maximal state constraint sets for discrete-time linear dynamical systems with bounded controls and states. IEEE Transactions on Automatic Control, 32:251–254, 1987.DOI
  22. [22]P.O. Gutman and M. Cwikel. Admissible sets and feedback control for discrete-time linear dynamical systems with bounded controls and states. IEEE Transactions on Automatic Control, 31(4):373–376, 1986.
  23. [23]M. Herceg, M. Kvasnica, C. Jones, and M. Morari. Multi-parametric toolbox 3.0. In Proceedings of European Control Conference (ECC), pages 502–510, 2013.DOI
  24. [24]B. Houska, M.A. Muller, and M.E. Villanueva. On stabilizing terminal costs and regions for configuration-constrained tube MPC. IEEE Control Systems Letters, 8:1961–1966, 2024.DOI
  25. [25]B. Houska, M.A. Muller, and M.E. Villanueva. Polyhedral control design: Theory and methods. Annual Reviews in Control, 60:100992, 2025.arxiv.org/abs/2412.13082
  26. [26]B. Houska, M.A. Muller, and M.E. Villanueva. Control Lyapunov function design via configuration-constrained polyhedral computing. Automatica, 188:112896, 2026.arxiv.org/abs/2503.16076
  27. [27]C.N. Jones. Polyhedral Tools for Control. PhD thesis, University of Cambridge, 2005.
  28. [28]T. Koller, F. Berkenkamp, M. Turchetta, and A. Krause. Learning-based model predictive control for safe exploration. In Proceedings of the 57th IEEE Conference on Decision and Control, pages 6059–6066, 2018.arxiv.org/abs/1803.08287
  29. [29]W. Langson, I. Chryssоchoos, S.V. Raković, and D.Q. Mayne. Robust model predictive control using tubes. Automatica, 40(1):125–133, 2004.DOI
  30. [30]Y. Li, J. Yu, L. Conger, T. Kargin, and A. Wierman. Learning the uncertainty sets of linear control systems via set membership: A non-asymptotic analysis. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 29234–29265. PMLR, 2024.arxiv.org/abs/2309.14648
  31. [31]P. McMullen. Representations of polytopes and polyhedral sets. Geometriae Dedicata, 2:83–99, 1973.DOI
  32. [32]P. McMullen. The polytope algebra. Advances in Mathematics, 78(1):76–130, 1989.DOI
  33. [33]P McMullen, R Schneider, and GC Shephard. Monotypic polytopes and their intersection properties. Geometriae Dedicata, 3(1):99–129, 1974.DOI
  34. [34]Peter McMullen. On monotypic polytopes: P. mcmullen. Discrete & Computational Geometry, pages 1–16, 2026.DOI
  35. [35]H. Minkowski. Allgemeine Lehrsätze über die konvexen Polyeder, pages 121–139. Springer Vienna, Vienna, 1989.
  36. [36]S. Motzkin, H. Raiffa, G.L. Thompson, and R.M. Thrall. The double description method. In H.W. Kuhn and A.W. Tucker, editors, Contributions to Theory of Games, volume 2. Princeton University Press, 1953.
  37. [37]S. Raković, B. Kouvaritakis, and M. Cannon. Equi-normalization and exact scaling dynamics in homothetic tube model predictive control. Systems & Control Letters, 62(2):209–217, 2013.DOI
  38. [38]S. Raković, W.S. Levine, and B. Açıkmeşe. Elastic tube model predictive control. In American Control Conference (ACC), 2016, pages 3594–3599. IEEE, 2016.DOI
  39. [39]J.B. Rawlings, D.Q. Mayne, and M.M. Diehl. Model Predictive Control: Theory and Design. Madison, WI: Nob Hill Publishing, 2015.
  40. [40]J. Rieger. A Galerkin approach to optimization in the space of convex and compact subsets of ℝ^d. Journal of Global Optimization, 79:593–615, 2021.
  41. [41]R. Schneider. Zur optimalen Approximation konvexer Hyperflächen durch Polyeder. Mathematische Annalen, 256:289–301, 1981.DOI
  42. [42]R. Schneider. Convex bodies: the Brunn–Minkowski theory, volume 151. Cambridge University Press, 2013.
  43. [43]R. Schneider and W. Weil. Zonoids and related topics. In P.M. Gruber and J.M. Wills, editors, Convexity and Its Applications, pages 296–317. Birkhäuser, Basel, 1983.DOI
  44. [44]R. Seidel. A convex hull algorithm optimal for joint sets in even dimensions. Technical Report, University of British, Columbia Dept. of Computer Science Vancouver, 1981.
  45. [45]P. Tøndel, T.A. Johansen, and A. Bemporad. An algorithm for multi-parametric quadratic programming and explicit MPC solutions. Automatica, 39(3):489–497, 2003.
  46. [46]P.A. Trodden. A one-step approach to computing a polytopic robust positively invariant set. IEEE Transactions on Automatic Control, 61(12):4100–4105, 2016.DOI
  47. [47]M.E. Villanueva, M.A. Müller, and B. Houska. Configuration-constrained tube MPC. Automatica, 163:111543, 2024.arxiv.org/abs/2208.12554
  48. [48]H. Weyl. Elementare Theorie der konvexen Polyeder. Commentarii Mathematici Helvetici, 7:290–306, 1934.DOI
  49. [49]G.M. Ziegler. Lectures on Polytopes. Springer, 1995.

Paper details

vlnc:W_tkv7vm42
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents