## Understanding Lagrange Multipliers (2)

SECTION 2     TANGENT CONES AND NORMAL CONES

In this section, we first try to solve the Question 1 and Question 3 of the last post, Understanding Lagrange Multipliers (1). The approach we adopt is to use a broader and more general theory to look at the nonlinear programming problems. Probably this theory is named by R.T.Rockafellar (Ralph Tyrrell Rockafellar), who is one of the founders of convex analysis. We call this theory “Variational Analysis”. The word “variational” comes from calculus of variations. Briefly, variational analysis is the study of variations of a point.

The first tool we need is tangent cones. Let us recall something learnt in differential geometry of curves and surfaces.

2.1     Tangent Space and contingent cone

Let $S$ be a regular surface in $\mathbb{R}^3$. If you don’t know what is a regular surface, then just think of $S$ as a hemisphere (say). Given a point $p\in S$ , we can define the tangent space of $S$ at $p$ to be $T_p(S)=\{v\in\mathbb{R}^3:\gamma:(-\varepsilon,\varepsilon)\rightarrow S\text{, smooth, }\gamma (0)=p\text{, }\gamma '(0)=v\}$. We call the $v$ a tangent vector of $S$ at $p$. Notice that by the definition of derivative, $\displaystyle v=\gamma '(0)=\lim_{t\rightarrow 0}{\frac{\gamma(t)-\gamma(0)}{t}}=\lim_{t\rightarrow 0}{\frac{\gamma(t)-p}{t}}$. This means, for any sequence $t_n\rightarrow 0$, and let $y_n=\gamma(t_n)\in S$, we have $\displaystyle\lim_{n\rightarrow\infty}{\frac{y_n-p}{t_n}}=v$. Note the above shows the following:

Proposition 2.1 If $v$ is a tangent vector of $S$ at $p$, then there exist $t_n\downarrow 0$ and $y_n\in S$ such that $\displaystyle\frac{y_n-p}{t_n}\rightarrow v$.

——————————-

It is the time to define the tangent cone. There are many types of tangent cones. The classical one is called contingent cone introduced by (Georges) Bouligand and independently (Francesco) Severi.

Without otherwise specified, we assume $X$ to be a real normed vector space under norm topology. If you do not know what is meant by normed vector space, you may let $X$ be $\mathbb{R}^n$ with the standard Euclidean norm, that is, $\|(a_1,\cdots,a_n)\|=\sqrt{a_1^2+\cdots+a_n^2}$. On top of that, from here onwards, basic knowledge on point set topology is assumed.

Definition 2.2 Let $S$ be a nonempty subset of $X$, and $x_0\in S$.   $x\in X$ is said to be a tangent vector of $S$ at $x_0$ if there exist $t_n\downarrow 0$ and $x_n\in X$ such that $x_n\rightarrow x$ and $x_0+t_n x_n\in S$ (If we put $y_n=x_0+t_n x_n$, then $y_n\in S$ and $\displaystyle\frac{y_n-x_0}{t_n}\rightarrow x$). The collection of all tangent vectors of $S$ at $x_0$ is called the contingent cone, denoted by $T(S,x_0)$.

Remark 2.3
(1) Proposition 2.1 implies $T_{x_0}(S)\subseteq T(S,x_0)$. From now on, tangent vector means the one in Definition 2.2.

(2) A subset $C$ of $X$ is called a cone if it is closed under nonnegative scalar multiplication, i.e. for any $x\in C$ and $\alpha\geq 0$, we have $\alpha x\in C$. In other words, $\displaystyle C=\bigcup_{\alpha\geq 0}{\alpha C}$. It follows that $T(S,x_0)$ is a cone.

We are interested in whether the contingent cone is a closed convex cone, which is an object interested by “optimizationist”. We denote $\mathbb{R}_{+}:=\{t\in\mathbb{R}:t\geq 0\}$ and the conic hull of a set $S$ to be $cone(S)=\mathbb{R}_{+}S$.

Proposition 2.4
(1) $T(S,x_0)$ is a closed cone.

(2) If $S$ is starshaped at $x_0$, then $T(S,x_0)=cl(cone(S-\{x_0\}))$. Hence if $S$ is convex, then so is $T(S,x_0)$.

Proof.
(1) Let $\{z_k\}_{k\in\mathbb{N}}$ be a sequence in $T(S,x_0)$ convergent to some $x\in X$. By definition, for any tangent vector $z_k$, we can find  $\{t_{k,n}\}_{n\in\mathbb{N}}\downarrow 0$ and $\{x_{k,n}\}_{n\in\mathbb{N}}\rightarrow z_k$ such that $x_0+t_{k,n}x_{k,n}\in S$. Hence for any $k\in\mathbb{N}$, there exists $n(k)\in\mathbb{N}$ such that

$\displaystyle |t_{k,n(k)}|<\frac{1}{k}\text{ and }\|x_{k,n(k)}-z_k\|<\frac{1}{k}$.

It follows that $\{t_{k,n(k)}\}_{k\in\mathbb{N}}\downarrow 0$, $\{x_{k,n(k)}\}_{k\in\mathbb{N}}\rightarrow x$, and $x_0+t_{k,n(k)}x_{k,n(k)}\in S$, implying that $x\in T(S,x_0)$. So $T(S,x_0)$ is closed. It is a cone by the preceding remark.

(2) The inclusion “$\subset$” is clear, and it does not require the starshapedness of $S$. For the reverse inclusion, readers should be able to see that since $T(S,x_0)$ is a closed cone, it suffices to show $S-\{x_0\}\subset T(S,x_0)$. Indeed, let $x\in S$. Owing to the starshapedness of $S$ at $x_0$, for all $n$, $\displaystyle x_0+\frac{1}{n}(x-x_0)=\frac{1}{n}x+(1-\frac{1}{n})x_0\in S$. Consequently, $x-x_0\in T(S,x_0)$ by definition. Since the conic hull of a convex set is convex, $T(S,x_0)$ is a convex set if $S$ is convex. $\Box$

One significance of a convex cone $C\subset X$ in optimization is that, it induces a reflexive, antisymmetric order $\leq_C$ on the space $X$ defined by: $x\leq_C y\iff y-x\in C$. Some minimality notion called “proper minimality” is defined in terms of the order induced by some contingent cone.

Some “pictures” of tangent cones will be here later.