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\mathrm{\forall }\mathbf{u},\mathbf{v}\in V$

Closure under nonnegative-scalar multiplication

$c\mathbf{v}\in V\mathrm{\forall }\mathbf{v}\in V,\mathrm{\forall }c\in \mathbb{R}\ge 0$

---

Conical Combination

A conical combination is just a linear combination constrained to have nonnegative coefficients.

$\begin{array}{r}\sum _{i=1}^n{a}_i{x}_i\text{where}{a}_i\ge 0\end{array}$

---

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}\ge 0,\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}\ge 0,\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}}_{\mathbf{1}}+c_2{\mathbf{v}}_{\mathbf{2}}\mid c_1,c_2\in \mathbb{R}\ge 0,{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}\in {\mathbb{R}}^2\ne \mathbf{0},{\mathbf{v}}_{\mathbf{2}}=-{\mathbf{v}}_{\mathbf{1}}\}=\{c_1\mathbf{v}+c_2(-\mathbf{v})\mid c_1,c_2\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^2\ne \mathbf{0}\}$

All lines are cones.

Wedges

construction of a wedge $\mathcal{w}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2{\mathbf{v}}_{\mathbf{2}}\mid c_1,c_2\in \mathbb{R}\ge 0,{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}\in {\mathbb{R}}^2\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}$

If ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}$ are independent, then $V$ is a wedge.

If ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}$ are dependent, then ${\mathbf{v}}_{\mathbf{2}}=c{\mathbf{v}}_{\mathbf{1}}$ and this construction is reduced to that of either a ray or a line. If $c>0$, then $V$ is a ray. If $c<0$, 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}}_{\mathbf{1}}+c_2{\mathbf{v}}_{\mathbf{2}}+c_3{\mathbf{v}}_{\mathbf{3}}\mid c_1,c_2,c_3\in \mathbb{R}\ge 0,{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}\in {\mathbb{R}}^2\ne \mathbf{0},{\mathbf{v}}_{\mathbf{2}}=-{\mathbf{v}}_{\mathbf{1}}\}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3{\mathbf{v}}_{\mathbf{3}}\mid c_1,c_2,c_3\in \mathbb{R}\ge 0,{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}\in {\mathbb{R}}^2\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$

If ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{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}\ge 0,\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}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$

2D wedges $\mathcal{w}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2{\mathbf{v}}_{\mathbf{2}}\mid c_1,c_2\in \mathbb{R}\ge 0,{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}$

half planes $\mathcal{h}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3{\mathbf{v}}_{\mathbf{3}}\mid c_1,c_2,c_3\in \mathbb{R}\ge 0,{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$

Planes

A plane is usually constructed as $\mathcal{p}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2{\mathbf{v}}_{\mathbf{2}}\mid c_1,c_2\in \mathbb{R},{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}\in {\mathbb{R}}^2\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}$. But a cone is closed under nonnegative-scalar multiplication, not scalar multiplication. So a plane requires that ${\mathbf{v}}_{\mathbf{2}}$ be moved out of the half plane constructed by ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$ bounded by the line given by ${\mathbf{v}}_{\mathbf{2}}=-{\mathbf{v}}_{\mathbf{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}}_{\mathcal{1}}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3{\mathbf{v}}_{\mathbf{3}}\mid c_1,c_2,c_3\in \mathbb{R}\ge 0,{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$

${\mathcal{h}}_{\mathcal{2}}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3(-{\mathbf{v}}_{\mathbf{3}})\mid c_1,c_2,c_3\in \mathbb{R}\ge 0,{\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$

$\mathcal{p}={\mathcal{h}}_{\mathcal{1}}\cup {\mathcal{h}}_{\mathcal{2}}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3{\mathbf{v}}_{\mathbf{3}}+c_4(-{\mathbf{v}}_{\mathbf{3}})\mid c\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$

3D wedges

Construction: Tetrahedron (Trigonal Cone)

$\mathcal{w}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2{\mathbf{v}}_{\mathbf{2}}+c_3{\mathbf{v}}_{\mathbf{3}}\mid c\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$

Construction: $n$-gonal Cone

$\mathcal{w}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2{\mathbf{v}}_{\mathbf{2}}+c_3{\mathbf{v}}_{\mathbf{3}}+...+c_n{\mathbf{v}}_{\mathbf{n}}\mid c\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}\mathbf{,}{\mathbf{v}}_{\mathbf{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}}_{\mathcal{1}}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3{\mathbf{v}}_{\mathbf{2}}\mid c\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}$

${\mathcal{h}}_{\mathcal{2}}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3{\mathbf{v}}_{\mathbf{3}}\mid c\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$

$\mathcal{c}={\mathcal{h}}_{\mathcal{1}}\cup {\mathcal{h}}_{\mathcal{2}}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3{\mathbf{v}}_{\mathbf{2}}+c_4{\mathbf{v}}_{\mathbf{3}}\mid c\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{2}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$

Half Solids

Construction: Union of a plane and a ray

$\mathcal{r}=\{c{\mathbf{v}}_{\mathbf{5}}\mid c\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$

$\mathcal{p}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3{\mathbf{v}}_{\mathbf{3}}+c_4(-{\mathbf{v}}_{\mathbf{3}})\mid c\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}$

$\mathcal{s}=\mathcal{r}\cup \mathcal{p}=\{c_1{\mathbf{v}}_{\mathbf{1}}+c_2(-{\mathbf{v}}_{\mathbf{1}})+c_3{\mathbf{v}}_{\mathbf{3}}+c_4(-{\mathbf{v}}_{\mathbf{3}})+c_5{\mathbf{v}}_{\mathbf{5}}\mid c\in \mathbb{R}\ge 0,\mathbf{v}\in {\mathbb{R}}^3\ne \mathbf{0}\}$ for independent ${\mathbf{v}}_{\mathbf{1}}\mathbf{,}{\mathbf{v}}_{\mathbf{3}}\mathbf{,}{\mathbf{v}}_{\mathbf{5}}$

${\mathbb{R}}^3$

---

Dual Cone

If $V\subseteq {\mathbb{R}}^n$ is a cone, then its dual is

$V^{\ast }=\{\mathbf{u}\in {\mathbb{R}}^n\mid \mathbf{u}\cdot \mathbf{v}\ge 0\mathrm{\forall }\mathbf{v}\in V\}$

---

If $V$ is a cone, then its dual $V^{\ast }$ is also a cone.

Proof

$\begin{array}{rl}& (c_1\mathbf{u})\cdot \mathbf{v}=c_1(\mathbf{u}\cdot \mathbf{v})\\ & (c_1\ge 0)\wedge (\mathbf{u}\cdot \mathbf{v}\ge 0)⟹(c_1\mathbf{u})\cdot \mathbf{v}\ge 0\\ & ({\mathbf{u}}_{\mathbf{1}}\cdot \mathbf{v}\ge 0)\wedge ({\mathbf{u}}_{\mathbf{2}}\cdot \mathbf{v}\ge 0)⟹({\mathbf{u}}_{\mathbf{1}}+{\mathbf{u}}_{\mathbf{2}})\cdot \mathbf{v}={\mathbf{u}}_{\mathbf{1}}\cdot \mathbf{v}+{\mathbf{u}}_{\mathbf{2}}\cdot \mathbf{v}\ge 0\end{array}$

---

Examples of dual cones in ${\mathbb{R}}^2$

Wedge

$S^{\ast }=\{c_1{v}_1^{\perp }+c_2{v}_2^{\perp }\mid c_i\ge 0\}$

---

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^{\ast \ast }=V$. That is, the dual of the dual is the primal.

PROOF

$\mathbf{v}\in V⟹\mathbf{u}\cdot \mathbf{v}\ge 0\mathrm{\forall }\mathbf{u}\in V^{\ast }⟹V\subseteq V^{\ast \ast }$

Suppose $\mathbf{v}\notin V$ and let $\mathbf{w}\in V$ be a vector with minimal angle $\theta$ with $\mathbf{v}$. In other words, if ${\mathbf{w}}^{\prime }\in V$ and ${\theta }^{\prime }$ is the angle between $\mathbf{v}$ and ${\mathbf{w}}^{\prime }$, then $\theta \le {\theta }^{\prime }$.

Since $V$ is closed, $V^c$ is open $⟹\theta >0$.

Let $\mathbf{u}\in V^{\ast }\ni \mathbf{u}\cdot \mathbf{w}=0$.

Then $\mathbf{u}\cdot \mathbf{v}<0⟹\mathbf{v}\notin V^{\ast \ast }⟹V^{\ast \ast }\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^{\ast }$ 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^{\ast }$ 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{array}{r}\mathrm{\nabla }z\in V_x^{\ast }\end{array}$

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⟺$ 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 $\mathrm{\nabla }z\cdot {\mathbf{v}}_x<0$.

Therefore

$\begin{array}{r}z(x)=\underset{F}{min}z⟺\mathrm{\nabla }z\cdot {\mathbf{v}}_x\ge 0\mathrm{\forall }{\mathbf{v}}_x\in V_x\end{array}$

which, by definition, places $\mathrm{\nabla }z$ in the dual cone $V_x^{\ast }$ at $x$.

This is an important test for a minimum.

[EXERCISE]

1. Choose some feasible point $x$ (an interior point; a boundary point; a vertex).

2. Determine the cone $V_x$ of feasible directions at $x$.

3. Determine the dual cone $V_x^{\ast }$.

4. Verify that any function $z$ whose gradient $\mathrm{\nabla }z\in V_x$ has a minimum $minz$ at $x$.

5. Verify that any function $z$ whose gradient $\mathrm{\nabla }z\notin V_x$ does not have a minimum $minz$ 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{array}{r}{g}_1(x)\ge b_1,...,g_k(x)\ge b_k\end{array}$

then at any regular point $x$ the boundaries of the dual cone $V_x^{\ast }$ are the gradients

$\begin{array}{r}\mathrm{\nabla }{g}_1,...,\mathrm{\nabla }{g}_k\end{array}$

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{array}{r}{V}_x^{\ast }=\{\sum _{i=1}^n{y}_i\mathrm{\nabla }{g}_i\mid y\ge 0\wedge y\cdot s=0\}\end{array}$

PROOF

Because $y$ and $s$ are each nonnegative

$y\cdot s⟺y_i{s}_i=0\mathrm{\forall }i$

which means that

$y_i>0⟹s_i=0$

and

$s_i>0⟹y_i=0$

The condition $y\cdot s=0$ stipulates that only the gradients $\mathrm{\nabla }{g}_i$ of the active constraints $s_i=0$ can be given positive coefficients $y_i>0$.

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{array}{r}z\text{is at a minimum at a feasible point}x⟺\sum _i{y}_i\mathrm{\nabla }{g}_i\text{has a solution}y=(y_1,...,y_k)\text{satisfying}y,s\ge 0\wedge y\cdot s=0\end{array}$

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{array}{r}\mathrm{\nabla }z=\sum _i{y}_i\mathrm{\nabla }{g}_i\text{where}y\ge 0\wedge y\cdot s=0\end{array}$

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{array}{r}z\text{has a maximum at}x⟺-z\text{has a minimum at}x\end{array}$

and if the constraints are

$g_1(x)\le b_1,...,g_k(x)\le b_k$

then

$-\mathrm{\nabla }{g}_1,...,-\mathrm{\nabla }{g}_k\ni s_i=0$

are the boundaries of $V_x^{\ast }$

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

---