Finding many different minima of nonlinear cost function
Suppose you have already found $x_0,\dots,x_{k-1}$ and now  your goal is to find $x_k$.  Let $\mathcal{R}$ denote the region of points that are orthogonal to $x_0,\dots,x_{k-1}$.  Then your problem is to minimize $G(x_k)$ subject to the requirement $x_k \in \mathcal{R}$.  This is a straightforward equality constraint in optimization, and can be handled in a number of ways.  Probably the simplest is to use projected gradient descent, which is like gradient descent but in each step you project the point onto the hyperplane $\mathcal{R}$.  Given how you have defined $\mathcal{R}$, the projection operation in this case is easy.