Let $a,b\neq \vec{0}$ be vectors in $\mathbb{R}^d$. Let $A=aa^T$ be the matrix formed by the outer product of $a$ with itself. Suppose $b\notin C(A)$, the column space of $A$. Consider maximizing the function $$g(x)=b^T x-\frac12 x^T A x$$
Then $\nabla g(x)=b-Ax$ and $\nabla^2 g(x) = -A=-aa^T$ and thus for any vector $v\in \mathbb{R}^d$, $v^T \nabla g(x) v = -v^T A v=-v^T aa^T v = -(v^Ta)(a^T v) = -(v^T a)^2 \leq 0$ hence $g$ is concave so a maximum exists on $\mathbb{R}^d$, right?
Solving the first order condition gives $b-Ax=0$ or $Ax=b$ i.e. $aa^T x = b$. This only has a solution if $b=\lambda a$ for some $\lambda$ otherwise $b$ is not in the column space of $aa^T$. But we assumed $b$ wasn't. So there is no solution for $b\notin C(A)$--but then doesn't this contradict the existence of a maximum?
So my questions are:
- Have I made a mistake? (is first order condition for maximum only sufficient, not necessary? I thought it was both under concavity and $C^2$...)
- What is the solution of this optimization problem? (Clearly $A=aa^T$ has rank 1 and is not invertible, otherwise we would just find $x=A^{-1}b$)