Let $a\in\mathbb{R}^{d}$ and $K$ be an arbitrary subset of $\mathbb{R}^{d}$. My question is related to the following optimization problem: \begin{equation} \max_{x\in\mathbb{R}^{d}}~a^{\top}x\quad \text{s.t.}~~x\in K \end{equation} Is it true that the solution to the above problem is just the projection of $a$ onto $K$? Does this at least hold under some additional restriction on $K$, like convexity? If yes, how can this be shown?
Related, but unanswered: Maximizing an inner-product over a convex set.
No, it’s not just the projection, even when $K$ is convex. Let $K$ be the unit circle centered at the origin, and let $a=(2,2)$. Then the optimal solution to your proposed optimization problem is $x^*=(-1,-1)$, while the projection of $a$ onto $K$ is $(1,1)$.
Looks like the post got edited so here’s a different example. Let $K$ be the unit square in $\mathbb{R}^2$, and let $a=(1/2,1/2)$. Then the maximizer is $x^*=(1,1)$, while the projection of $a$ onto $K$ is the vector $a$ itself.
For an example with $a\not\in{K}$, let $K$ again be the unit square, and take $a=(-\varepsilon,\varepsilon)$ for some $0<\varepsilon<1$. Then the maximizer is $x^*=(0,1)$, while the projection of $a$ onto $K$ is $(0,\varepsilon)$
One more example, where $x^*$ is not a scalar multiple of $a$: let $K$ be the circle in $\mathbb{R}^2$ with radius $1$ centered at $(1,1)$ and take $a=(0,1)$. Then the maximizer is $x^*=(1,2)$.