\documentclass[11pt]{article}

\usepackage{amsmath}
\usepackage{indentfirst}
\usepackage{natbib}

\DeclareMathOperator{\cl}{cl}
\DeclareMathOperator{\pos}{pos}

\newcommand{\set}[1]{\{\, #1 \,\}}
\newcommand{\inner}[1]{\langle #1 \rangle}

\begin{document}

\title{Tangent Cones and Normal Cones in RCDD}

\author{Charles J. Geyer}

\maketitle

\section{Introduction}

The \emph{tangent cone} of a convex set $C$ at a point $x \in C$ 
is given by
$$
   T_C(x) = \cl \set{ s (y - x) : \text{$y \in C$ and $s \ge 0$} }
$$
\citep[Theorem~6.9]{raw}.  Note that the closure is necessary (consider
a closed ball).  It is not necessary to consider arbitrary sequences;
as always in convex analysis it is enough to consider line segments.
The \emph{normal cone} of a convex set $C$ at a point $x \in C$ 
is given by
\begin{align*}
   N_C(x)
   & =
   T_C(x)^*
   \\
   & =
   \set{ w : \text{$\inner{w, y - x} \le 0$,  $y \in C$} }
\end{align*}
\citep[Theorem~6.9]{raw}.

Specializing these to the polyhedral convex set
$$
   C = \set{ x : \text{$\inner{a_i, x} \le b_i$, $i \in I$, and
   $\inner{a_i, x} = b_i$, $i \in E$} }
$$
we have
$$
   T_C(x) =
   \set{ x : \text{$\inner{a_i, x} \le 0$, $i \in A$, and
   $\inner{a_i, x} = 0$, $i \in E$} }
$$
where
$$
   A = \set{ i \in I : \inner{a_i, x} = b_i }
$$
is the active set of inequality constraints
(in essence, we drop the inactive constraints and make $x$ the new origin).
We also have
$$
   N_C(x) = \pos \bigl( \set{ a_i : i \in A \cup E }
   \cup \set{ - a_i : i \in E } \bigr)
$$

In the language of the \texttt{rcdd} package, we have an H-representation
for the tangent cone and a V-representation of the normal cone.

\section{Example: Cube}

<<foo,include=FALSE,echo=FALSE>>=
options(keep.source = TRUE, width = 65)
@

Let us consider a very simple example, the unit cube in three dimensions.
Let us start with a V-representation for it.

<<cube-v>>=
v <- rbind(c(0, 0, 0),
           c(0, 0, 1),
           c(0, 1, 0),
           c(0, 1, 1),
           c(1, 0, 0),
           c(1, 0, 1),
           c(1, 1, 0),
           c(1, 1, 1))
m <- cbind(0, 1, v)
m
@

Then we convert to the H-representation.
<<cube-h>>=
library(rcdd)
out <- scdd(m, representation = "V")
out$output
@
A cube has six facets, and we have one constraint for each.

\subsection{At a Vertex}

Now suppose we want to calculate the tangent cone at $(1, 1, 1)$.
We need to calculate the active set.
<<cube-active-111>>=
l <- out$output[ , 1]
b <- out$output[ , 2]
v <- out$output[ , - c(1, 2)]
active <- v %*% c(1, 1, 1) + b == 0
active
@
Hence the tangent cone at $(1, 1, 1)$ has the following H-representation.
<<cube-tangent-111>>=
tan111 <- out$output[active, ]
tan111[ , 2] <- 0
tan111
@
The cone represented is the negative orthant.

To turn this into the V-representation of the normal cone, we must obtain
the vectors $a_i$, which are the rows of $A$ where the H-representation
has the form $\begin{pmatrix} l & b & - A \end{pmatrix}$.  Since we also
want $(0, 0)$ for the first two columns of the V-representation (to represent
rays) we can just negate the H-representation
<<cube-normal-111>>=
nor111 <- - tan111
nor111 <- redundant(nor111, representation = "V")
nor111
@
(We ran through the \texttt{redundant} function just in case.)

\subsection{On an Edge}

Now let us consider $(0, 0, 1 / 2)$.
We need to calculate the active set.
<<cube-active-005>>=
l <- out$output[ , 1]
b <- out$output[ , 2]
v <- out$output[ , - c(1, 2)]
active <- v %*% c(0, 0, 1 / 2) + b == 0
active
@
Hence the tangent cone at $(0, 0, 1 / 2)$ has the following H-representation.
<<cube-tangent-005>>=
tan005 <- out$output[active, ]
tan005[ , 2] <- 0
tan005
@

As with the preceding example, the V-representation of the normal cone is 
just the negative of the H-representation of the tangent cone.

\section{Example: Square}

In the preceding example, the polyhedron and all of its tangent cones
have full dimension.  The normal cones may or may not have full dimension
(the first example at a vertex does, the second example on an edge doesn't).

Here we consider an example, the unit square in three dimensions,
where the polyhedron and its tangent cones do not have full dimension
Let us start with a V-representation for it.

<<square-v>>=
v <- rbind(c(0, 0, 0),
           c(0, 0, 1),
           c(0, 1, 0),
           c(0, 1, 1))
m <- cbind(0, 1, v)
m
@

Then we convert to the H-representation.
<<square-h>>=
library(rcdd)
out <- scdd(m, representation = "V")
out$output
@
A cube has six facets, and we have one constraint for each.

\subsection{At a Vertex}

Now suppose we want to calculate the tangent cone at $(0, 1, 1)$.
We need to calculate the active set.
<<square-active-011>>=
l <- out$output[ , 1]
b <- out$output[ , 2]
v <- out$output[ , - c(1, 2)]
active <- v %*% c(0, 1, 1) + b == 0
active
@
Hence the tangent cone at $(0, 1, 1)$ has the following H-representation.
<<square-tangent-011>>=
tan011 <- out$output[active, ]
tan011[ , 2] <- 0
tan011
@
Note that the code we used is exactly the same as in the other case.
Our code is perfectly general (seems to work for all cases).
The only difference is that this time our H-representation for the
tangent cone has an equality constraint; hence the tangent cone is
contained in a hyperplane; hence it is less than full dimension.

To turn this into the V-representation of the normal cone, we must obtain
the vectors $a_i$, which are the rows of $A$ where the H-representation
has the form $\begin{pmatrix} l & b & - A \end{pmatrix}$.  Since we also
want $(0, 0)$ for the first two columns of the V-representation (to represent
rays) we can just negate the H-representation
<<square-normal-011>>=
nor011 <- - tan011
nor011[ , 1] <- tan011[ , 1]
nor011 <- redundant(nor011, representation = "V")
nor011
@
Oops!  Our code was not perfectly general here.  We should only change
the sign of columns 2 on in the H-representation.

The normal cone is full dimensional.

\begin{thebibliography}{}

\bibitem[Rockafellar and Wets(2004)]{raw}
Rockafellar, R.~T. and Wets, R. J.-B. (2004).
\newblock \emph{Variational Analysis}, corr.\ 2nd printing.
\newblock Berlin: Springer-Verlag.

\end{thebibliography}

\end{document}