0

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.

Rodrigo de Azevedo
  • 1
Masoud
  • 125

1 Answers1

0

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

H. H. Rugh
  • 35,236
  • One thing that I forgot to mention is that for both $x_i$ and $y_i$ we have $x_i and y_i => 0$ – Masoud Aug 27 '16 at 17:26
  • 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? – H. H. Rugh Aug 27 '16 at 17:36
  • You mean the projection process needs to be done for each $x_i=0$ and then pick the closest one to $y$? – Masoud Aug 27 '16 at 17:41
  • Yes, at least if, as I presume, the goal is to minimize the distance? – H. H. Rugh Aug 27 '16 at 17:44
  • Yes per definition of projection. Thanks – Masoud Aug 27 '16 at 17:47
  • Sorry for asking again! Just want to make sure! In this set $S$, I will have the projection of $y$ computed onto $x_2+x_3-x_4=a$ then projection of $y$ onto $x_1+x_3-x_4=a$ and so on? For each time the distance of projection point is computed to $y$ and minimum is chosen. – Masoud Aug 27 '16 at 18:33
  • Not quite sure what you mean. But take the projection of $y=(y_1,y_2,y_3,y_4)$ onto $x_1=0$. It is simply $(0,y_2,y_3,y_4)$ (the equation for $S$ doesn't enter into the game) so the distance is simply $y_1$ (assuming as you said positive). Similarly for the others. – H. H. Rugh Aug 27 '16 at 18:58