如何定义并求解$\mathbf{R}^n$中点集的对偶空间与对偶多面体？

Alright, let's walk through how to define dual polyhedra for arbitrary point sets in $\mathbf{R}^n$, and how to compute them for a given set $S = {x_1, x_2, ..., x_m}$ where each $x_i \in \mathbf{R}^n$.

First: The Core Definition of a Dual Polyhedron #

Dual polyhedra are fundamentally defined for convex polyhedra, but we can extend this to any point set by working with its convex hull (since the dual only depends on the convex structure of the set, not individual non-extremal points).

For a convex polyhedron $P \subset \mathbf{R}^n$, its dual polyhedron $P^$ is the set of all vectors $y \in \mathbf{R}^n$ such that the dot product of $y$ with every point in $P$ is at most 1:
$$P^ = { y \in \mathbf{R}^n \mid y \cdot x \leq 1 \text{ for all } x \in P }$$
Here, $\cdot$ denotes the standard Euclidean inner product.

Step 1: Reduce the Point Set to Its Convex Hull #

For your given point set $S$, first compute its convex hull $\text{conv}(S)$ — this is the smallest convex polyhedron containing all points in $S$. If $S$ already consists of exactly the vertices of its convex hull (no redundant points), you can skip this step and use $S$ directly.

Step 2: Define the Dual Polyhedron for $S$ #

The dual polyhedron of $S$ (denoted $S^$) is exactly the dual of its convex hull. Thanks to the properties of convex combinations, we don't need to check every point in $\text{conv}(S)$ — only the points in $S$:
$$S^ = { y \in \mathbf{R}^n \mid y \cdot x_i \leq 1 \text{ for every } x_i \in S }$$
Why does this work? Any point $x \in \text{conv}(S)$ is a convex combination of points in $S$: $x = \sum_{i=1}^m \lambda_i x_i$ where $\lambda_i \geq 0$ and $\sum_{i=1}^m \lambda_i = 1$. Then:
$$y \cdot x = \sum_{i=1}^m \lambda_i (y \cdot x_i) \leq \sum_{i=1}^m \lambda_i \cdot 1 = 1$$
So satisfying the inequality for all $x_i \in S$ automatically satisfies it for every point in the convex hull.

Step 3: Solve for $S^*$ (Express as a Convex Polyhedron) #

$S^$ is a convex polyhedron defined by the intersection of $m$ half-spaces. To write this explicitly, expand the dot product for each $x_i$:
For $x_i = (x_{i1}, x_{i2}, ..., x_{in})$, the inequality $y \cdot x_i \leq 1$ becomes:
$$x_{i1} y_1 + x_{i2} y_2 + ... + x_{in} y_n \leq 1$$
So $S^$ is the set of all $(y_1, y_2, ..., y_n) \in \mathbf{R}^n$ that satisfy all $m$ of these linear inequalities.

Key Notes on Boundedness #

The shape of $S^*$ depends on the position of the origin relative to $\text{conv}(S)$:

• If the origin lies inside $\text{conv}(S)$, $S^*$ is a bounded convex polyhedron (a convex polytope).
• If the origin lies on the boundary of $\text{conv}(S)$, $S^*$ is unbounded.
• If the origin lies outside $\text{conv}(S)$, $S^*$ is still an unbounded convex polyhedron (but never empty, since the zero vector will always satisfy all inequalities $0 \cdot x_i = 0 \leq 1$).

Dual Space Connection #

When talking about "dual space" here, we're leveraging the Riesz Representation Theorem, which identifies the algebraic dual space of $\mathbf{R}^n$ (all linear functionals on $\mathbf{R}^n$) with $\mathbf{R}^n$ itself. Each vector $y \in \mathbf{R}^n$ corresponds to the linear functional $f_y(x) = y \cdot x$. The dual polyhedron $S^*$ is just the set of all such functionals that are bounded above by 1 on every point in $S$.

Quick 2D Example #

Let's take $S = {(1,0), (0,1), (-1,-1)}$ in $\mathbf{R}^2$. Its convex hull is a triangle containing the origin. The dual polyhedron $S^*$ is defined by:
$$y_1 \leq 1$$
$$y_2 \leq 1$$
$$-y_1 - y_2 \leq 1 \implies y_1 + y_2 \geq -1$$
This is a bounded triangle with vertices at $(1,1)$, $(1,-2)$, and $(-2,1)$ — exactly the dual of the original convex hull.

内容的提问来源于stack exchange，提问作者0x90