1

The first-order necessary condition for the constrained problem $\underset{x \in \Omega}{\min} f(x)$ is $$\nabla f(x^*)^Tp \geq 0$$ for all feasible directions $p$ at the solution $x^*$. Intuitively it makes sense that there are no descent directions at $x^*$.

It's not clear to me why the above condition reduces to $\nabla f(x^*)^Tp = 0$ for linear constraints $\Omega = \{x :Ax=b \}$. Could you clarify the intermediate steps? Why should the gradient be orthogonal to all feasible $p$?

harisf
  • 329

1 Answers1

1

Key observation: all feasible directions $p$ are tangent to the contours defined by the linear constraints (otherwise $p$ would lead us off the contours, and hence not be a feasible direction): $A^T p = 0$.

And since $A^T = \lambda^* \nabla f(x^*)$, it follows that $\nabla f(x^*)^T p = 0$.

harisf
  • 329