For continuous optimizations, what is the condition that says an optimal value lies on the boundary and not in the interior?

130 Views Asked by At

Suppose I want to solve the problem

\begin{equation} \min_{x \in \mathcal{X}} f(x) \end{equation} where $f$ is assumed to be continuously differentiable, and $\mathcal{X}$ is closed and possibly compact.

I know that an interior optimal point $x^*$ satisfies $\nabla f(x^*) = 0$

And in general, optimal points satisfies $\nabla f(x^\star)^T (x - x^*) \geq 0, \forall x \in \mathcal{X}$

But what about points that only lie on the boundary $\partial \mathcal{X}$? What is a condition that characterizes these points?

I am thinking of a condition that reads,

$\nabla f(x^\star)^T (x - x^*) \geq 0, \forall x \in \mathcal{X}$ and $\nabla f(x^\star) \neq 0$

However, $\nabla f$ cannot be evaluated on the boundary. So this condition doesn't actually make any sense.

Does anyone know how to reconcile the non-existence of $\nabla f$ and characterization of boundary optimal points?

2

There are 2 best solutions below

0
On

For me personally, this setting only makes sense if $ \nabla f$ can be evaluated on the boundary of $\mathcal{X}$ for the following reason: If $\mathcal{X}$ is a closed set then we need to be able to evaluate $f$ for all $x \in \mathcal{X}$ to be able to solve the optimization problem. Hence, the domain of $f$ should be a superset of $\mathcal{X}$. Further, if $f$ is continuously differentiable then (by definition) its domain is some open set $D$ and we get $f \colon D \supseteq \mathcal{X} \to \mathbb{R}$. For such a function $f$ we can evaluate $\nabla f$ on the boundary of $\mathcal{X}$.

If we don't know anything about $\mathcal{X}$ then a necessary optimality condition would be as follows: If $\bar{x} \in \mathcal{X}$ is an optimal solution of the optimization problem, it holds that $\nabla f(\bar{x})^\top d \geq 0 \;\forall d \in T(\mathcal{X},\bar{x})$ where $T$ stands for the tangent cone.

If $\mathcal{X}$ is given by some equality and inequality constraints, then under certain regularity assumptions the Karush-Kuhn-Tucker (KKT) conditions would be a necessary optimality cirterion.

0
On

You need differentiability of $f$ on an open set containing $\mathcal X$ or uniform continuity of $\nabla f$.

Consider $\min \sqrt x$ subject to $x\ge0$. Then $x=0$ is a solution but $\nabla f(0)$ does not exist.