1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It’s not if $K$ is a line. Maybe you want to minimize the distance to the set? $\endgroup$ – Gunnar Þór Magnússon Mar 13 at 8:23
  • $\begingroup$ 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? $\endgroup$ – nemo Mar 13 at 8:33
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – nemo Mar 13 at 8:42
  • $\begingroup$ @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)$. $\endgroup$ – David M. Mar 13 at 8:43
  • $\begingroup$ Okay, thanks for clarifying. $\endgroup$ – nemo Mar 13 at 8:51
  • $\begingroup$ 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 $\endgroup$ – nemo Mar 13 at 13:20
  • $\begingroup$ @nemo If $K$ is unbounded, then the optimization problem may or may not have an infinite solution. $\endgroup$ – David M. Mar 13 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.