Let $A\in\mathbb{R}^{n\times n}$ be SPD. I want to show that the function $$\Phi(x)=\frac{1}{2}x^TAx - b^Tx$$ fulfills $\nabla\Phi(x)=Ax-b$.
My attempt:
First, we consider a pertubation of $\Phi(x)$ denoted by $\Phi(x+\delta x)$. Then I approximate with a Taylor polynomial up to linear order in $\delta x\in\mathbb{R}^n$: $$\Phi(x+\delta x) - \Phi(x)=\nabla \Phi \delta x + \mathcal{O}(\| (\delta x)^2\|)$$
Now I just use the definition of $\Phi$ and insert:
$\frac{1}{2} (x+\delta x)^T A(x+\delta x) - b^T(x+\delta x)- \frac{1}{2} x^TAx+ b^T x=\nabla\Phi(x)\delta x$
Solving and ditching the $\frac{1}{2}(\delta x)^T A\delta x$ term I get
$\frac{1}{2}x^tA\delta x + \frac{1}{2}(\delta x)^tAx - b^T\delta x = \nabla \Phi(x)\delta x$
Then I use that $AB=(B^TA^T)^T$ for two matrices and obtain
$\left ( (Ax)^T - b^T\right ) \delta x = \nabla\Phi(x)\delta x$
or equivalently
$\left ( Ax -b -\nabla \Phi(x) \right )^T\delta x=0 $
How can I conclude from this that $\nabla \Phi(x)=Ax-b$?
It seems that you have misunderstood the definition of $\nabla \Phi$. By definition, $\nabla \Phi(x)$ is the (unique) matrix $M$ such that for all perturbations $\delta x$, we have $$ \Phi(x + \delta x) - \Phi(x) = M^T \delta x + o(\|\delta x\|). $$ You have already shown (up to some rearragement of your steps) that $$ \Phi(x + \delta x) - \Phi(x) = (Ax - b)^T \delta x + o(\|\delta x\|). $$ It follows that $\nabla \Phi = Ax-b$.