0

First-Order Necessary Condition (FONC)

Let $\Omega$ be a subset of $\mathbb{R}^n$ and $f\in\cal{C}^1$ a real-valued function on $\Omega$. If $\mathbf{x}^*$ is a local minimizer of $f$ over $\Omega$, then for any feasible direction $\mathbf{d}$ at $\mathbf{x}^*$, we have $$\mathbf{d}^{T}\nabla f\left(\mathbf{x}^*\right) \ge 0,$$ where $f\in\cal{C}^i$ means that a function $f$ is $i$ times continuously differentiable, a point $\mathbf{x}^*\in\Omega$ is a local minimizer of $f$ over $\Omega$ if there exists $\varepsilon\gt0$ such that $f(\mathbf{x})\ge f(\mathbf{x}^*)$ for all $\mathbf{x}\in\Omega\setminus\{\mathbf{x}^*\}$ and $\Vert\mathbf{x} - \mathbf{x}^* \Vert \lt \varepsilon$, a vector $\mathbf{d}\in\mathbb{R}^n$, $\mathbf{d}\ne\mathbf{0}$ is a feasible direction at $\mathbf{x}\in\Omega$ if there exists $\alpha_0\gt0$ such that $\mathbf{x}+\alpha\mathbf{d}\in\Omega$ for all $\alpha\in [0,\alpha_0]$, and $\mathbf{x}^T$ represents a transpose of $\mathbf{x}$ that every elements' row and column are changed from $x_{ij}$ to $x_{ji}$.

Let us consider the set-constrained problem $$\text{minimize} \quad f(\mathbf{x})$$ $$\text{subject to}\quad \mathbf{x}\in\Omega,$$ where $\Omega = \left\{ \left[x_1, x_2\right]^T : x_1^2+x_2^2=1\right\}$.

In this problem, because there are no feasible directions at any $\mathbf{x}^*$, all points in $\Omega$ satisfy the FONC for this set-constrained problem.

Why???

I do not understand this answer.

Danny_Kim
  • 3,423

1 Answers1

1

In this case, since the feasible set expresses the boundary of the unit circle, all points except $\bar{x}$ on any line passing through or being tangent to a point $\bar{x}$ in the feasible set, will lie outside the boundary. Hence, there are no nonzero feasible directions at any point on the boundary. Thus, the only feasible direction is the zero direction and we have $d^t\nabla f(\bar{x})=0\geq 0$ for all feasible directions $d$, as the only feasible direction is the zero direction. Since $\bar{x}$ was arbitrary, this holds for all elements in the feasible set. So the FONC is satisfied at all points in the feasible set.

Elias
  • 362