# How to show equivalence between two programs?

Consider the following space $$A = \{(x_1,x_2,x_3)\in \mathbb{R}^3|x_1+x_2+x_3 = 1\}.$$ Then say that we want to minimize a function $$J(y):\mathbb{R}^{3}\to \mathbb{R}$$ subjected to the constraint that $$y\in A.$$ A version of gradient descent suggests to start with a guess $$y_0\in \mathbb{R}^3$$ and then perform the following iteration $$y_{i+1} = \Pi_{A}(y_{i}-\lambda_i \nabla J(y_i))$$ where $$\Pi_{A}$$ is the usual projection on the plane $$A.$$

However, note that if we start with a point $$y_0\in A$$ then the point, $$y_1 = y_{0}-\Pi_{B}[\lambda_0 \nabla J(y_0)]\in A$$ where $$B=\{(x_1,x_2,x_3)\in \mathbb{R}^3|x_1+x_2+x_3 = 0\}.$$ This is because the sum of componenets of the vector $$y_0$$ is $$1$$ while the sum of the componenets from the other vector (which is a projection of the gradient) is $$0$$ and so resultant sum of components is still $$1.$$ So $$y_1 \in A.$$

We can thus show by induction that $$y_i\in A$$ for all $$i\geq 0.$$ I now want to argue that this update rule $$y_{i+1} = y_{i}-\Pi_{B}[\lambda_i\nabla J(y_i)]$$ leads to the same answer as the one mentioned earlier.

From our observation, we can say that, $$y_{i+1} = y_{i}-\Pi_{B}[\lambda_i\nabla J(y_i)] = \Pi_{A}( y_{i}-\Pi_{B}[\lambda_i\nabla J(y_i)]).$$

So I guess that maybe we want to show that, $$\Pi_A(\Pi_B[\nabla J(y_i)])= \Pi_A(\nabla J(y_i))$$ but I am not sure if this is the right thing to do. Any suggestions would be much appreciated.

• You can show that projections onto A and B of the gradient are parallel. Then minimization over lambda will make the updates be equal. – VorKir May 27 at 0:18