0
$\begingroup$

I am solving an optimization problem that uses sub-gradient method. I changed the problem and now it requires me to find Euclidean projection of a point $y$ onto following convex set:

$$S=\{(x_1,x_2,x_3,x_4):x_1+x_2+x_3-x_4=a\}$$

$a$ being a constant belonging to $\mathbb R$. All variables are in real number space. $y$ belongs to $\mathbb R^4$.

I already know that if the last term was an addition instead of subtraction, it would be a projection onto a simplex that has a straightforward algorithm to solve.

$\endgroup$
0
$\begingroup$

Hint: Try setting $x=y+t(1,1,1,-1)$ (the vector being in the direction of the normal) and find $t$ so that $x\in S$.

$\endgroup$
  • $\begingroup$ One thing that I forgot to mention is that for both $x_i$ and $y_i$ we have $x_i and y_i => 0$ $\endgroup$ – Masoud Aug 27 '16 at 17:26
  • $\begingroup$ I did imagine there might be a catch somewhere. That actually change the problem quite a lot. If the projection onto $S$ does not satisfy your criteria, then you have to compute all different orthogonal projections onto each of the subspaces $x_i=0$ and pick the one with the smallest distance. Is that sort of clear? $\endgroup$ – H. H. Rugh Aug 27 '16 at 17:36
  • $\begingroup$ You mean the projection process needs to be done for each $x_i=0$ and then pick the closest one to $y$? $\endgroup$ – Masoud Aug 27 '16 at 17:41
  • $\begingroup$ Yes, at least if, as I presume, the goal is to minimize the distance? $\endgroup$ – H. H. Rugh Aug 27 '16 at 17:44
  • $\begingroup$ Yes per definition of projection. Thanks $\endgroup$ – Masoud Aug 27 '16 at 17:47

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.