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.

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

Your Answer

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

Browse other questions tagged or ask your own question.