Let $A$ be an $m \times n$ real matrix and $y \in \mathbb{R}^n$. Let $x \in \mathbb{R}^m$ be a vector with nonnegative entries that minimizes the Euclidean distance $\|y-Ax\|$ (among all nonnegative vectors $x$). Show that the vector $v=A^T(y-Ax)$ has nonnegative entries.
I've seen a solution that involves contradiction and a slight perturbation on $x$, but it doesn't really help with my intuition. Anything that would help build intuition would really help here. Thanks!
What you have here is an optimization problem where the feasible set is the positive orthant in $\mathbb{R}^n$: \begin{align} \min_x &\quad \frac{1}{2}\|y - Ax \|^2 \\ \text{such that} &\quad x \in \left(\mathbb{R}^n\right)^+. \end{align} The quantity $A^T(y-Ax)$ is the negative gradient of the objective function: $$g = \frac{d}{dx} \left(\frac{1}{2}\|y - Ax \|^2\right) = -A^T(y-Ax).$$
There are two possiblities:
The optimal point could lie in the interior of the feasible set. In that case the gradient is zero, so $-g$ is trivially non-negative.
The optimal point could lie on the boundary of the feasible set. Then the gradient is perpendicular to the feasible set, pointing outwards. Hence the quantity of interest, $-g$, points perpendicularly inward into the positive orthant, and therefore has entries that are either positive or zero.
For more details on this sort of reasoning look into Lagrange multipliers and the KKT conditions for constrained optimization.