Tangent cone to a set at a given point and first-order necessary optimality conditions

Consider the problem of minimizing a continuously differentiable function $f: \mathbb{R}^{n} \to \mathbb{R}$ with respect to $x$ in the set $$X = \{x: l_{j} \leq x_{j} \leq u_{j}, \, j=1,\cdots , n\}. $$

I need to do the following two things:

1. For $n =3$, I need to describe the tangent cone to $X$ at the point $\overline{x}=(l_{1},u_{2},a)^{T}$, where $l_{3}<a<u_{3}$.
2. Derive first-order necessary conditions of optimality for this problem.

For #1: My notes/text defines the tangent cone as the set $T_{X}(x)$ of all tangent directions for $X \subset \mathbb{R}^{n}$ at $x\in X$. And, a direction $d$ is called tangent to a set $X \subset \mathbb{R}^{n}$ at the point $x \in X$ and scalars $\tau_{k}>0$, $k = 1,2, \cdots $ such that $\tau_{k} \downarrow 0$ and $$d = \lim_{k \to \infty}\frac{x^{k}-x}{\tau_{k}}.$$

It also defines the tangent cone as the closure of the cone of feasible directions at $x \in X$: $$ T_{X}(x) = \overline{K_{X}(x)}= \overline{cone(X-x)}, $$ where $cone(X-x)$ is the cone generated by the convex set $X$. The set $X$ given in this problem seems to be convex by construction, but I do not know how to find the cone of feasible directions, and then determine its closure.

In fact, below is a graph of the feasible region in the specific case when $0 \leq x_{1} \leq 2$, $-1 \leq x_{2} \leq 4$, and $\frac{1}{2} \leq x_{3} \leq 1$:

For #2: I am not really sure what to do. I don't know if the system $$ \text{minimize}_{x \in X} f(x) \\ \text{subject to} \\ x_{1} \geq l_{1} \\ x_{2} \geq l_{2} \\ x_{3} \geq l_{3} \\ x_{1} \leq u_{1} \\ x_{2} \leq u_{2} \\ x_{3} \leq u_{3} $$has metric regularity, so I don't know if there are any results that I can apply or even generally how to find the first-order necessary conditions. There are some results that I have seen for functions that are twice differentiable, but we are not guaranteed of that here - only that $f$ is continuously first differentiable.

Could somebody please help me? I am extremely lost, and not really understanding what to do. Thank you.

Solution 1:

You will need to do some work to follow this answer.

The idea behind the tangent cone is to have a model of the constraint space $X$ that shows the directions we can move from a particular point $x$ and remain in the constraint space.

Be aware that there are various definitions of tangent cones, not all are the same. The following is specific to the particular definition used in the question.

Since $X$ is convex, the tangent cone is convex. From the definition it follows that the tangent cone is closed.

It is not hard to show (assuming that $f$ is $C^1$ at $x$) that if $\langle \nabla f(x), d \rangle < 0$ for some $d \in T_X(x)$, then there is some (nearby) $y \in X$ such that $f(y) < f(x)$. Hence if $x$ is a local minimiser, we must have $\langle \nabla f(x), d \rangle \ge 0$ for all $d \in T_X(x)$ or, in other words, $-\nabla f (x) \in T_X(x)^\circ$.

Note: Most first order conditions boil down to something of this form, but usually more work is needed to make this condition 'usable'.

A small amount of work is needed to compute $T_X(x)$ and its polar.

This can be done directly, or by using Lemma 3.13 of Ruszczynski's "Nonlinear Optimization" which states that when $X$ is convex $T_X(x) = \overline{K_X(x)}$, the closure of the cone of feasible directions. (Since $X$ is a box with straight edges, we see that, in fact, $T_X(x) = K_X(x)$.)

Working with an interval first illustrates the idea: Suppose $n=1$ and $X=[l,u]$. If $x=l$ then clearly we can only change in a positive direction and so $T_X(l) = [0,\infty)$, and similarly, if $x=u$ we can only change in a negative direction, so $T_X(u) = (-\infty,0]$. If $x \in (l,u)$ then we can move either way so $T_X(x) = (-\infty,\infty)$.

Note that $T_X(l)^\circ = (-\infty,0]$, $T_X(x)^\circ = \{0\}$ and $T_X(u)^\circ = [0,\infty)$ (with $x \in (l,u)$). In particular, if $x$ is a local minimiser of $f$ for this one dimensional problem, then if $x=l$ we must have $f'(l) \ge 0$, if $x \in (l,u)$ we must have $f'(x) = 0$ and if $x=u$ we must have $f'(u) \le 0$.

For the $X$ given in the question, note that since the edges of the box are parallel to the axes, a direction $d$ at a point $x\in X$ is a feasible direction iff each individual component $d_k$ is a feasible direction for the corresponding constraint $l_k \le x_k \le u_k$.

Let $L(x) = \{ k | x = l_k \}, U(x) = \{ k | x = u_k \}$. Note that $L(x),U(x)$ are always disjoint and may be empty.

In particular, $d$ is a feasible direction iff for all $k$ we have $d _k \in \begin{cases} [0,\infty),& k \in L(x) \\ (-\infty,0],& k \in U(x) \\ (-\infty,\infty),& \text{otherwise} \end{cases}$. Lemma 3.13 tells us that this is, in fact, $T_X(x)$.

We can compute $T_X(x)^\circ$ from this. Note that $\langle y , t \rangle \le 0$ for all $t \in T_X(x)$ iff $y _k \in \begin{cases} (-\infty,0],& k \in L(x) \\ [0,\infty),& k \in U(x) \\ \{0\},& \text{otherwise} \end{cases}$.

From this, we see that if $x$ is a local minimiser, then we must have ${\partial f(x) \over \partial x_k } \in \begin{cases} [0,\infty),& k \in L(x) \\ (-\infty,0],& k \in U(x) \\ \{0\},& \text{otherwise} \end{cases}$.

As a sanity check, note that if the upper and lower bound constraints are inactive, this boils down to $\nabla f(x) = 0$ which is the unconstrained first order condition.

Two final notes:

(i) There are different definitions of the tangent cone, some more liberal, some more stringent. In practice, if $X$ is convex, they typically end up being the same thing.

(ii) In many cases, the gradient inclusion first order condition provides less information that might appear at first glance. For example, the problem $\min \{ f (x) | x^2 = 0 \}$ ends up with $T_X(0) = \{0\}$ and hence $T_X(0)^\circ = \mathbb{R}$, hence it does not place any constraints on $f$ at all. Sometimes people add 'constraint qualifications' that allow the polar cone to be written in a nicer fashion.

Solution 2:

For #1: the region $X - \bar x$ will simply be $$ X - \bar x = \{(x,y,z) : 0 \leq x \leq (u_1 - l_1),(l_2 - u_2) \leq y \leq 0,(l_3 - a) \leq z \leq (u_3 - a) \} $$ To see why, it may help to note that $X - \bar x$ is simply $\{y - \bar x : y \in X\}$. To that end, we find that $$ X - (a_1,a_2,a_3) = \left\{(x,y,z) : \begin{array}{c}(l_1 - a_1) \leq x \leq (u_1 - a_1)\\(l_1 - a_2) \leq y \leq (u_2 - a_2)\\(l_3 - a_3) \leq z \leq (u_3 - a_3)\end{array} \right\} $$

The closed convex cone generated by this region is the smallest set containing $X - \bar x$ which is closed under multiplication by positive scalars and addition. Because $X - \bar x$ is already convex, finding the closed convex cone simply amounts to extending all rays indefinitely, then taking the closure.

In this case, $$ T_X(\bar x) = \{(x,y,z) : x \geq 0, y \leq 0\} $$