# Maximize inner product subject to constraint

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: $$$$\max_{x\in\mathbb{R}^{d}}~a^{\top}x\quad \text{s.t.}~~x\in K$$$$ 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.

• It’s not if $K$ is a line. Maybe you want to minimize the distance to the set? – Gunnar Þór Magnússon Mar 13 at 8:23
• Sorry, there was a typo in the equation; the problem is to maximize the inner product. When $K$ is a line, it's the projection of $a$ onto $K$, right? – nemo Mar 13 at 8:33

## 1 Answer

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)$$.

• How can $(1,1)$ be the maximizer? I'm assuming by unit square you mean the $\ell_{1}$ ball, $(1,1)$ doesn't lie on it. – nemo Mar 13 at 8:42
• @nemo Sorry should have been clearer—by unit square I mean the square with corners at $(0,0)$, $(0,1)$, $(1,0)$ and $(1,1)$. – David M. Mar 13 at 8:43
• Okay, thanks for clarifying. – nemo Mar 13 at 8:51
• One more question: is the $\textit{any}$ relation between the maximizer and projection of $a$ onto $K$, say wrt Euclidean distance? Also, seems like $K$ must be bounded in some way, otherwise the inner product can be made arbitrarily large, as in your last example – nemo Mar 13 at 13:20
• @nemo If $K$ is unbounded, then the optimization problem may or may not have an infinite solution. – David M. Mar 13 at 14:22