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.

Previous:
Understanding Lagrange Multipliers (1)

Advertisements
This entry was posted in Analysis, Applied mathematics. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s