Normal cone of the complement of an ellipsoid

convex-analysisellipsoids

On page 68, exercise 2.38 in Boyd & Vanderberghe's book, Convex Optimization, a normal cone of a boundary point $x$ of a set $C$ is defined as

$$\mathcal N_C(x) := \left\{ g \mid g^T x \ge g^T y, \quad \forall y\in C \right\}$$

My questions are:

  1. Do we need the convexity of the set $C$ in the normal cone definition above or not?

  2. If $C$ does indeed need to be convex (and for some unknown reasons the authors did not mention it in the definition), what is the definition of a normal cone at a boundary point of a non-convex set $C$?

  3. Assuming that the given definition does not ask for the convexity of the set $C$, what is the normal cone of a boundary point of $C= \{ x \mid x^T A x \ge 1 \}$ in which $A$ is a positive definite matrix?

My attempts show that the normal cone for this scenario is actually the zero set, which is a bit fishy to me because it is independent of $A$! But why $\mathcal N_C(x)=\{0\}$ for $x$ with $x^TAx=1$ and $C=\{ x \, | \, x^TAx\ge 1\}$:

if $y\in C$, then $-y\in C$. Thus, we can say that $\mathcal N_C(x):=\{g\, | \, g^Tx\ge |g^Ty|, \ \ \forall y\in C\}$. Further, if $y\in C$, then $\lambda y\in C$ for $\lambda \ge 1$. Thus, for a nonzero $g$ to be inside $\mathcal N_C (x)$, we must have $g^Tx\ge \lambda |g^Tx| $ for all $\lambda \ge 1$. Since a boundary point $x$ of $C$ is not zero, we must have $\pm 1= g^Tx/|g^Tx|\ge \lambda$ for any $\lambda \ge 1.$ This is impossible so that $\mathcal N_{C}(x)=\{0\}$.

Please confirm or let me know where my mistake is! Thank you so much in advance.

Best Answer

The book Convex Optimization by Rockafellar requires convexity of $C$ in the definition:

A vector $x^*$ is said to be normal to a convex set $C$ at a point $a$, where $a \in C$, if $x^*$ does not make an acute angle with any line segment in $C$ with $a$ as endpoint, i.e. if $\langle x-a, x^*\rangle \leq 0$ for every $x\in C$. For instance, if $C$ is a half-space $\left\{x | \langle x,b\rangle \leq \beta \right\}$ and $a$ satisfies $\langle a,b\rangle = \beta$, then $b$ is normal to $C$ at $a$. In general, the set of all vectors $x^*$ normal to $C$ at $a$ is called the normal cone to $C$ at $a$. The reader can verify easily that this cone is always convex.

With this definition, Rockafellar states the following theorem (27.4):

Let $h$ be a proper convex function, and let $C$ be a non-empty convex set. In order that $x$ be a point where the infimum of $h$ relative to $C$ is attained, it is sufficient that there exist a vector $x^* \in \partial h(x)$ such that $-x^*$ is normal to $C$ at $x$. This condition is necessary, as well as sufficient, if $\text{ri} (\text{dom} \; h)$ intersects $\text{ri} \; C$, or if $C$ is polyhedral and $\text{ri} (\text{dom} \; h)$ merely intersects $C$.

Here, $\partial h(x)$ is the subgradient of $h$ at $x$, ri is the relative interior, and dom is the subset of the domain where the objective value is finite. In other words, the normal cone can be used to characterize the minimum of a convex function over a convex set.

You could argue that it is not surprising that a book titled Convex Optimization requires a set to be convex, and that you could extend the definition of a normal cone to nonconvex sets $C$. However, a definition by itself is useless and only comes to life if it is useful somewhere. As far as I know, the normal cone for a nonconvex set is not used in any meaningful theorem.

Related Question