Cones & Dual Cones#
Definition of a Cone#
A cone \(V\subseteq\mathbb{R}^n\) is a set of vectors that is closed under both vector addition and nonnegative-scalar multiplication.
Closure under vector addition
\( \mathbf{u}+\mathbf{v}\in V\,\,\,\forall \mathbf{u},\mathbf{v}\in V \)
Closure under nonnegative-scalar multiplication
\( c\mathbf{v}\in V\,\,\,\forall \mathbf{v}\in V,\forall c\in\mathbb{R}\ge0 \)
Conical Combination#
A conical combination is just a linear combination constrained to have nonnegative coefficients.
\( \begin{aligned} \sum_{i=1}^n a_ix_i\,\,\,\text{where}\,a_i\ge0 \end{aligned} \)
Cones in \(\mathbb{R}^n\)#
Space |
Cones |
|---|---|
\(\mathbb{R}\) |
\(\{\mathbf{0}\}\), rays, \(\mathbb{R}\) |
\(\mathbb{R}^2\) |
\(\{\mathbf{0}\}\), rays, lines, wedges, half planes, \(\mathbb{R}^2\) |
\(\mathbb{R}^3\) |
\(\{\mathbf{0}\}\), rays, lines, 2D wedges, half planes, planes, 3D wedges, half solids, \(\mathbb{R}^3\) |
\(\mathbb{R}^4\) |
\(\{\mathbf{0}\}\), rays, lines, 2D wedges, half planes, planes, 3D wedges, half solids, solids, 4D wedges, half hyper solids, \(\mathbb{R}^4\) |
Cones in \(\mathbb{R}\)#
The zero vector \(\{\mathbf{0}\}\) is a cone.
All rays are cones.
construction of a ray \( \mathcal{r}=\{c\mathbf{v}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}\ne\mathbf{0}\} \)
\(\mathbb{R}\) is a cone.
Cones in \(\mathbb{R}^2\)#
The zero vector#
The zero vector \(\{\mathbf{0}\}\) is a cone.
Rays#
construction of a ray \( \mathcal{r}=\{c\mathbf{v}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^2\ne\mathbf{0}\} \)
All rays are cones.
Lines#
A line is usually constructed as \( \ell=\{c\mathbf{v}\mid c\in\mathbb{R},\mathbf{v}\in\mathbb{R}^2\ne\mathbf{0}\} \). But a cone is closed under nonnegative-scalar multiplication, not scalar multiplication. So a line is constructed as the union of two rays pointing in opposite directions.
construction of a line \( \ell =\{c_1\mathbf{v_1}+c_2\mathbf{v_2}\mid c_1,c_2\in\mathbb{R}\ge0,\mathbf{v_1,v_2}\in\mathbb{R}^2\ne\mathbf{0},\mathbf{v_2}=-\mathbf{v_1}\} =\{c_1\mathbf{v}+c_2(-\mathbf{v})\mid c_1,c_2\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^2\ne\mathbf{0}\} \)
All lines are cones.
Wedges#
construction of a wedge \( \mathcal{w}=\{c_1\mathbf{v_1}+c_2\mathbf{v_2}\mid c_1,c_2\in\mathbb{R}\ge0,\mathbf{v_1,v_2}\in\mathbb{R}^2\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_2}\)
If \(\mathbf{v_1,v_2}\) are independent, then \(V\) is a wedge.
If \(\mathbf{v_1,v_2}\) are dependent, then \(\mathbf{v_2}=c\mathbf{v_1}\) and this construction is reduced to that of either a ray or a line. If \(c\gt0\), then \(V\) is a ray. If \(c\lt0\), then \(V\) is the union of two rays pointing in opposite directions and so is a line.
All wedges are cones.
Half Planes#
construction of a half plane \( H =\{c_1\mathbf{v_1}+c_2\mathbf{v_2}+c_3\mathbf{v_3}\mid c_1,c_2,c_3\in\mathbb{R}\ge0,\mathbf{v_1,v_2,v_3}\in\mathbb{R}^2\ne\mathbf{0},\mathbf{v_2}=-\mathbf{v_1}\} =\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3\mathbf{v_3}\mid c_1,c_2,c_3\in\mathbb{R}\ge0,\mathbf{v_1,v_3}\in\mathbb{R}^2\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_3}\)
If \(\mathbf{v_1,v_3}\) are independent, then \(V\) is a half plane.
All half planes are cones.
\(\mathbb{R}^2\)#
Cones in \(\mathbb{R}^3\)#
the zero vector \( \{\mathbf{0}\} \)
rays \( \mathcal{r}=\{c\mathbf{v}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \)
lines \( \ell=\{c_1\mathbf{v}+c_2(-\mathbf{v})\mid c_1,c_2\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \)
2D wedges \( \mathcal{w}=\{c_1\mathbf{v_1}+c_2\mathbf{v_2}\mid c_1,c_2\in\mathbb{R}\ge0,\mathbf{v_1,v_2}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_2}\)
half planes \( \mathcal{h}=\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3\mathbf{v_3}\mid c_1,c_2,c_3\in\mathbb{R}\ge0,\mathbf{v_1,v_3}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_3}\)
Planes#
A plane is usually constructed as \( \mathcal{p}=\{c_1\mathbf{v_1}+c_2\mathbf{v_2}\mid c_1,c_2\in\mathbb{R},\mathbf{v_1,v_2}\in\mathbb{R}^2\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_2}\). But a cone is closed under nonnegative-scalar multiplication, not scalar multiplication. So a plane requires that \(\mathbf{v_2}\) be moved out of the half plane constructed by \(\mathbf{v_1,v_2,v_3}\) bounded by the line given by \(\mathbf{v_2}=-\mathbf{v_1}\).
All planes are cones.
Plane Construction: Union of two half planes with two independent generating vectors#
One way to construct a plane is to take the union of two half planes with a common boundary line and which share two independent generating vectors.
\( \mathcal{h_1}=\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3\mathbf{v_3}\mid c_1,c_2,c_3\in\mathbb{R}\ge0,\mathbf{v_1,v_3}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_3}\)
\( \mathcal{h_2}=\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3(-\mathbf{v_3})\mid c_1,c_2,c_3\in\mathbb{R}\ge0,\mathbf{v_1,v_3}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_3}\)
\( \mathcal{p} =\mathcal{h_1}\cup\mathcal{h_2} =\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3\mathbf{v_3}+c_4(-\mathbf{v_3})\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_3}\)
3D wedges#
Construction: Tetrahedron (Trigonal Cone)#
\( \mathcal{w}=\{c_1\mathbf{v_1}+c_2\mathbf{v_2}+c_3\mathbf{v_3}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_2,v_3}\)
Construction: \(n\)-gonal Cone#
\( \mathcal{w}=\{c_1\mathbf{v_1}+c_2\mathbf{v_2}+c_3\mathbf{v_3}+...+c_n\mathbf{v_n}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_2,v_3}\)
Pyramidal Cone
Pentagonal Cone
Hexagonal Cone
Heptagonal Cone
Octogonal Cone
Nonogonal Cone
Decagonal Cone
…
Circular Cone
Construction: Circular Cones#
Rotate two independent vectors around their bisector to generate a circular cone in \(\mathbb{R}^3\).
Construction: Cylinders (Fans?)#
\( \mathcal{h_1}=\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3\mathbf{v_2}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_2}\)
\( \mathcal{h_2}=\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3\mathbf{v_3}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_3}\)
\( \mathcal{c} =\mathcal{h_1}\cup\mathcal{h_2} =\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3\mathbf{v_2}+c_4\mathbf{v_3}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_2,v_3}\)
Half Solids#
Construction: Union of a plane and a ray#
\( \mathcal{r}=\{c\mathbf{v_5}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \)
\( \mathcal{p} =\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3\mathbf{v_3}+c_4(-\mathbf{v_3})\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_3}\)
\( \mathcal{s} =\mathcal{r}\cup\mathcal{p} =\{c_1\mathbf{v_1}+c_2(-\mathbf{v_1})+c_3\mathbf{v_3}+c_4(-\mathbf{v_3})+c_5\mathbf{v_5}\mid c\in\mathbb{R}\ge0,\mathbf{v}\in\mathbb{R}^3\ne\mathbf{0}\} \) for independent \(\mathbf{v_1,v_3,v_5}\)
\(\mathbb{R}^3\)#
Dual Cone#
If \(V\subseteq\mathbb{R}^n\) is a cone, then its dual is
\(V^*=\{\mathbf{u}\in\mathbb{R}^n\mid\mathbf{u}\cdot\mathbf{v}\ge0\,\forall\mathbf{v}\in V\}\)
If \(V\) is a cone, then its dual \(V^*\) is also a cone.
Proof
\( \begin{aligned} &(c_1\mathbf{u})\cdot\mathbf{v} =c_1(\mathbf{u}\cdot\mathbf{v})\\ &(c_1\ge0)\land(\mathbf{u}\cdot\mathbf{v}\ge0) \implies (c_1\mathbf{u})\cdot\mathbf{v}\ge0\\ &(\mathbf{u_1}\cdot\mathbf{v}\ge0)\land(\mathbf{u_2}\cdot\mathbf{v}\ge0) \implies (\mathbf{u_1}+\mathbf{u_2})\cdot\mathbf{v} =\mathbf{u_1}\cdot\mathbf{v}+\mathbf{u_2}\cdot\mathbf{v}\ge0 \end{aligned} \)
Examples of dual cones in \(\mathbb{R}^2\)#
Wedge
\( S^*=\{c_1v_1^\perp+c_2v_2^\perp\mid c_i\ge0\} \)
Summary of cones in \(\mathbb{R}^2\) and their duals#
Cone |
Dual |
|---|---|
\(\{\mathbf{0}\}\) |
\(\mathbb{R}^2\) |
ray |
half plane |
line |
perpendicular line |
wedge |
wedge |
half plane |
ray |
\(\mathbb{R}^2\) |
\(\{\mathbf{0}\}\) |
[PROPOSITION]
If \(V\) is a closed cone, then \(V^{**}=V\). That is, the dual of the dual is the primal.
PROOF
\( \mathbf{v}\in V \implies \mathbf{u\cdot v}\ge0\,\forall\mathbf{u}\in V^* \implies V\subseteq V^{**} \)
Suppose \(\mathbf{v}\not\in V\) and let \(\mathbf{w}\in V\) be a vector with minimal angle \(\theta\) with \(\mathbf{v}\). In other words, if \(\mathbf{w}'\in V\) and \(\theta'\) is the angle between \(\mathbf{v}\) and \(\mathbf{w}'\), then \(\theta\le\theta'\).
Since \(V\) is closed, \(V^c\) is open \(\implies\theta\gt0\).
Let \(\mathbf{u}\in V^*\ni\mathbf{u\cdot w}=0\).
Then \( \mathbf{u\cdot v}\lt0 \implies \mathbf{v}\not\in V^{**} \implies V^{**}\subseteq V \)
The dual cone is always closed; so, the dual of the dual is closed.
The only truly open cone in \(\mathbb{R}^n\) is \(\mathbb{R}^n\) itself, which is both open and closed.
There are cones which are neither open nor closed because they need not contain all their boundary points to satisfy the closure requirements that define a cone. But the dual is defined by weak inequalities that necessarily result in a closed set; so, the dual of the dual includes the primal and all the boundary points of the primal, which is called the closure of the primal.
[EXAMPLE OF UNCLOSED CONE]
If \(V\) is the union of the zero vector along with the interior of a namesake cone, then \(V\) is a cone.
The dual cone \(V^*\) picks up boundary vectors, as does the dual of the dual.
[EXAMPLE OF UNCLOSED CONE]
If \(V\) is the union of the zero vector along with the interior of a half plane cone, then \(V\) is a cone.
The dual cone \(V^*\) is the ray normal to the half plane. The dual fo the dual includes the full half plane.
[FEASIBLE DIRECTION & CONE OF FEASIBLE DIRECTIONS]
Consider a feasible point \(x\) in the control space of an LP and let \(\mathbf{v}_x\) be a vector with origin at \(x\).
Regardless of its magnitude, \(\mathbf{v}_x\) can be considered to define a direction. Call the direction defined by \(\mathbf{v}_x\) a feasible direction if there exists another feasible point \(y\) in the direction \(\mathbf{v}_x\) from \(x\), at any positive distance from \(x\) not necessarily at the terminus of \(\mathbf{v}_x\).
For any feasible point \(x\), define the set \(V_x=\{\mathbf{v}_x\mid\mathbf{v}_x\,\text{represents a feasible direction from}\,x\}\)
[PROPOSITION]
\(V_x\) is a cone.
PROOF
Follows from the convexity of the feasible set.
[PROPOSITION]
If \(F\) is the feasible set of an LP and the objective function \(z\) has a minimum at \(x\), then
\( \begin{aligned} \nabla z\in V_x^* \end{aligned} \)
That is, it is a necessary condition for a minimum at a feasible point \(x\) that the gradient of the objective function be in the dual cone of the cone of feasible directions at the point \(x\).
PROOF
Starting at \(x\), \(z\) gets smaller on the set \(F\iff\) there is a feasible direction in which \(z\) has a negative directional derivative; that is, a feasible direction \(\mathbf{v}_x\in V_x\) such that \(\nabla z\cdot\mathbf{v}_x\lt0\).
Therefore
\( \begin{aligned} z(x)=\underset{F}{\min} z \iff \nabla z\cdot\mathbf{v}_x\ge0\,\forall\mathbf{v}_x\in V_x \end{aligned} \)
which, by definition, places \(\nabla z\) in the dual cone \(V_x^*\) at \(x\).
This is an important test for a minimum.
[EXERCISE]
Choose some feasible point \(x\) (an interior point; a boundary point; a vertex).
Determine the cone \(V_x\) of feasible directions at \(x\).
Determine the dual cone \(V_x^*\).
Verify that any function \(z\) whose gradient \(\nabla z\in V_x\) has a minimum \(\min z\) at \(x\).
Verify that any function \(z\) whose gradient \(\nabla z\not\in V_x\) does not have a minimum \(\min z\) at \(x\).
[EXAMPLE]
Suppose \(x\) is an interior point of the feasible set.
Then the cone of feasible directions is \(\mathbb{R}^n\) and the dual is just the zero vector.
In other words, only a constant function has a minimum at an interior point.
[PROPOSITION]
If the feasible set of an LP is defined by greater-than-or-equal-to constraints
\( \begin{aligned} g_1(x)\ge b_1,...,g_k(x)\ge b_k \end{aligned} \)
then at any regular point \(x\) the boundaries of the dual cone \(V_x^*\) are the gradients
\( \begin{aligned} \nabla g_1,...,\nabla g_k \end{aligned} \)
of the active constraints at \(x\)
[PROPOSITION]
Let \(x\) be a feasible point in the control space of an LP and let \(s\) be the nonnegative vector of slack variables at \(x\).
Then the dual cone
\( \begin{aligned} V_x^* =\left\{\sum_{i=1}^ny_i\nabla g_i\mid y\ge0\land y\cdot s=0\right\} \end{aligned} \)
PROOF
Because \(y\) and \(s\) are each nonnegative
\( y\cdot s \iff y_is_i=0\,\forall i \)
which means that
\( y_i\gt0 \implies s_i=0 \)
and
\( s_i\gt0 \implies y_i=0 \)
The condition \(y\cdot s=0\) stipulates that only the gradients \(\nabla g_i\) of the active constraints \(s_i=0\) can be given positive coefficients \(y_i\gt0\).
If \(x\) is a regular point, then there is a unique solution for \(y\).
If \(x\) is not a regular point, then there are redundant active constraints for which \(s_i=0\) and these provide extra, unnecessary gradients yielding multiple solutions for \(y\). But these extra gradients are already in the dual cone which is not changed by their inclusion in the generating set.
[PROPOSITION] special case of KKT Karush Kuhn Tucker conditions
\( \begin{aligned} z \,\text{is at a minimum at a feasible point}\, x \iff \sum_iy_i\nabla g_i \,\text{has a solution}\, y=(y_1,...,y_k) \,\text{satisfying}\, y,s\ge0\land y\cdot s=0 \end{aligned} \)
This enables solving the primal minimization problem by finding all feasible points \(x\) at which the objective gradient is in the dual cone of the cone of feasible directions at \(x\).
[COROLLARY]
The test
\( \begin{aligned} \nabla z =\sum_iy_i\nabla g_i \,\text{where}\, y\ge0\land y\cdot s=0 \end{aligned} \)
applies to a maximization problem with less-than-or-equal-to constraints, just like it
applies to a minimization problem with greater-than-or-equal-to constraints.
PROOF
\( \begin{aligned} z \,\text{has a maximum at}\, x \iff -z \,\text{has a minimum at}\, x \end{aligned} \)
and if the constraints are
\( g_1(x)\le b_1,...,g_k(x)\le b_k \)
then
\( -\nabla g_1,...,-\nabla g_k\ni s_i=0 \)
are the boundaries of \(V_x^*\)
The other two cases
maximization problem with greater-than-or-equal-to constraints
minimization problem with less-than-or-equal-to constraints
require a sign change of either RHS or LHS or an equivalent reformulation of the contraints.
Terms#
[W] Cone
[W] Cone, topology
[W] Conical Combination
[W] Conical Hull
[W] Conical Surface
[W] Convex Cone
[W] Half Line
[W] Half Plane
[W] Half Space
[W] Hypercone
[W] Normal Fan
[W] Polyhedral Complex
[W] Ray
[W] Simplicial Complex