3
$\begingroup$

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$:

enter image description here

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.

$\endgroup$
  • $\begingroup$ Have you drawn $X$? That should give you a pretty good idea for #1. As for #2, which necessary conditions do you know? $\endgroup$ – user251257 Nov 3 '17 at 0:21
  • $\begingroup$ @user251257 I can't really visualize $X$. I know it's supposed to be in $\mathbb{R}^{3}$, and from the way the point $\overline{x}$ is written, I assume that $x_{j}$ is the "$z$"-coordinate. So, I guess, It would look like a triangular prism? Am I right? For #2, I don't know what is applicable to this case, because I don't know if $X$ is convex or not. $\endgroup$ – ALannister Nov 3 '17 at 0:35
  • $\begingroup$ ignore $\bar x$ first. $X$ doesn't depend on $\bar x$. Try to draw $X$ for $n=3$ and $l_1=\dotsb=l_3=0$ and $u_1=\dotsb=u_3=1$. $\endgroup$ – user251257 Nov 3 '17 at 0:39
  • 1
    $\begingroup$ well in my example $X=[0,1]^3$ is the unit cube. In general $X$ is a hyper-rectangle. $\endgroup$ – user251257 Nov 3 '17 at 1:36
  • 2
    $\begingroup$ @Omnomnomnom: A typical characterisation of a first order necessary condition would be that at an optimal point $x$ we have $\langle \nabla f(x), h \rangle \ge 0 $ for all $x \in T_X(x)$. Since the constraints defining $X$ are affine, the tangent cone (or rather its polar) has a nice characterisation and the ballyhooed 'constraint qualification' is satisfied. I am guessing the goal here is to obtain something like $-\nabla f(x) \in T_X(x)^\circ$. $\endgroup$ – copper.hat Nov 5 '17 at 18:02
2
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ is the polar that Omnomnomnom calculated correct? And if so, wouldn't its polar just be $\{(x,y,z): x\leq 0, y \geq 0\}$? $\endgroup$ – ALannister Nov 6 '17 at 22:45
  • $\begingroup$ It is. It would be, and is. If you work through the formula above for $n=3$ you will end up with the same result??? You do need to some some work here! $\endgroup$ – copper.hat Nov 6 '17 at 22:48
1
$\begingroup$

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\} $$

$\endgroup$
  • $\begingroup$ (hopefully, that was enough noms), could you explain a little more how you determined that $X-\overline{x}$ was the set you provided? Thank you. $\endgroup$ – ALannister Nov 5 '17 at 15:11
  • $\begingroup$ @DaenerysDracarys I added a bit, see if that clears things up. $\endgroup$ – Omnomnomnom Nov 5 '17 at 22:55
  • $\begingroup$ don't you mean $X-\overline{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)\}$? $\endgroup$ – ALannister Nov 6 '17 at 17:05
  • $\begingroup$ @DaenerysDracarys of course! Took me a while to notice that I wrote $x$ all 3 times, sorry. $\endgroup$ – Omnomnomnom Nov 6 '17 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.