Consider an equality constrained optimization problem
$$
\underset{x\in\mathbb R^q}{\text{minimize}}f(x)\quad\text{subject to}\quad\ Ax=b,
$$
where $f:\mathbb R^q\to\mathbb R$ is a convex differentiable objective function to be minimized, $A\in\mathbb R^{p\times q}$ and $b\in\mathbb R^{p}$.
I am trying to understand the proof of the Lagrange multiplier optimality condition
$$
\nabla f(x)+A^{\mathrm T}u=0
$$
for some $u\in\mathbb R^q$. According to first-order optimality condition, the solution $x\in\mathbb R^q$ satisfies $Ax=b$ and
$$
\nabla f(x)^{\mathrm T}(y-x)\ge0
$$
for all $y\in\mathbb R^q$ such that $Ay=b$. Since $A(y-x)=0$, $y-x\in\operatorname{Null}(A)$ and hence $\nabla f(x)^{\mathrm T}v\ge0$ for some $v\in\operatorname{Null}(A)$. Why does it follow that $\nabla f(x)^{\mathrm T}(y-x)=0$ (it seems that we only have that it is greater or equal) and $\nabla f(x)^{\mathrm T}v=0$ for all $v\in\operatorname{Null}(A)$?
Thank you!
Best Answer
From $\nabla f(x)^{\mathrm T}v\ge0$, $\forall v\in\operatorname{Null}(A)$, we have that $\nabla f(x)^{\mathrm T}v=0$, $\forall v\in\operatorname{Null}(A)$ because if $v \in\operatorname{Null}(A)$, then $-v \in \operatorname{Null}(A)$.