1

Consider the nonlinear optimization problem below:

$$p^* := \min f(x)$$

$$\textrm{s.t. }\ g_i (x) \leq 0,\ \forall i = 1,...,m$$

$$h_j (x) = 0,\ \forall j = 1,..., p$$

$$x \in D$$

where $f, g_i, h_j : D \rightarrow R, i = 1,..., m, j = 1,...,p$ are $C^2$-smooth functions and $D$ is an open subset of $R^n$.

Whitney's Theorem: for any closed subset $D \subset R^n$ there exists a $C^\infty$-smooth function $g : R^n \rightarrow R$ satisfying $D = \{x : g (x) = 0 \}$. Thus without further conditions on the constraints, we might as well be optimizing a function over any closed set - an intractable problem.

What is the significance of this theorem in nonlinear optimization?

Teodorism
  • 1,165
  • There are infinitely many functions that can contain g(x)=0 for x in D. I don't see the relation between this and the last sentence of the Theorem: "Thus ..." – Teodorism Sep 14 '17 at 22:53
  • Is it by any chance trying to say that piece-wise optimization of a function over closed sets is intractable? and so, we need to find a more efficient solution? or just suffice with local solutions? – Teodorism Sep 14 '17 at 22:58

1 Answers1

0

The authors infer from Whitney's theorem that the constraints of the form $g(x)=0$ or $g(x)\ge 0$ can result in very bad geometry of the admissible set - it can be an arbitrary closed set, like the Cantor set, or van Koch snowflake, etc. This motivates an additional assumption that will presumably be placed on $g$ after this paragraph: $$\nabla g\ne 0 \quad \text{when } g=0 \tag{1}$$ Under assumption $(1)$, the set $\{x:g(x)=0\}$ can no longer be one of the complicated things mentioned above; rather, it will be a smooth manifold (a "hypersurface" if you will).

So, the significance of the theorem in optimization is in that it justifies us placing the assumption $(1)$ on the constraint function.

  • Why do you say any arbitrary set? What if g(x) is unique? – Teodorism Sep 16 '17 at 00:59
  • What I understand from the theorem is that one can replace the last constraint, i.e., $x\in D$, with $x\in R^n$ and $g(x)=0$. How does this imply that minimizing $f(x)$ over the new set of constraints is equivalent to minimizing it over any closed set? Minimizing it over the intersection of the constraints could be a much easier problem than over any closed set. – Teodorism Sep 16 '17 at 01:06