Show that for a symmetric matrix $A$:
$$\inf_{x \in \mathbb R^n} x^TAx - 2b^Tx$$
has a solution if and only if $A$ is positive semidefinite and $b$ is in the range of $A$.
This is straightforward to show by applying first order optimality conditions using the gradient of the objective. Is there some way to show this without differentiating the objective?
I think this should be possible by considering the orthogonal complement of the range of $A$ and decomposing $b$ into two components: $b = y + z$ where $y \in \text{Im}\,A$ and $z$ such that $A^Tz = 0$.
To show necessity, I am trying to argue (by contradiction) that if $z$ is not the zero vector, then the objective can be made arbitrarily negative since we can take the component of $x$ in the null space of $A$ to have a very negative inner product with $z$. This argument is intuitive, but I am having trouble formalizing it without appealing to the typical first order optimality condition.
We'll show necessity by contradiction.
Call the objective $q(x) = x^TAx - 2b^Tx$.
First let's assume that $A \succeq 0$ but that $b$ is not in the image of $A$:
Take $x = \alpha b$ for some $\alpha \in \mathbb R$. Recall that if $b \not \in \text{Im}\, A$ then $b \in \text{Ker} \, A$ so that $Ab = 0$. Now the objective is: $$q(\alpha b) = -2\alpha \|b\|^2$$
which goes to $-\infty$ as $\alpha \rightarrow \infty$ so that $q$ does not have a solution.
Next let's assume that $b \in \text{Im}\, A$ but there exists some $u \in \mathbb R^n$ such that $u^TAu <0$. Since $b \in \text{Im}\, A$, there exists some $\eta \in \mathbb R^n$ such that $b = A\eta$. Rewriting $q$ (as suggested in the comment above):
$$q(x) = (x-\eta)^T A(x-\eta) + \eta^T A \eta$$
take $x = \alpha u + \eta$ so that the first term above goes to $-\infty$ as $\alpha \rightarrow \infty$. The second term is constant. This shows that $q$ does not have a solution.