Without further examples, it's hard to suggest what one might do. But for these kinds of problems, it's often possible to apply an alternating optimization paradigm where you:

1. Fix x and optimize for n
2. Fix n and optimize for x
3. repeat till convergence

In certain settings depending on G and the feasible region, this can yield an optimal solution (for example, if you're measuring the distance between two convex polygons), but in general, it's hard to get anything except a local optimum.

Without further examples, it's hard to suggest what one might do. But for these kinds of problems, it's often possible to apply an alternating optimization paradigm where you:

1. Fix x and optimize for n
2. Fix n and optimize for x
3. repeat till convergence

In certain settings depending on G and the feasible region, this can yield an optimal solution (for example, if you're measuring the distance between two convex polygons), but in general, it's hard to get anything except a local optimum.

Update:

Based on the OP's clarification, I think a different direction might be more useful. What you're describing begins to sound like a lagrange relaxation of the constrained version of the problem (with a fixed budget). One example of this is a facility-location problem where you want to open facilities to "serve" locations, and while adding more facilities reduces the service cost, it costs more to open each one. There are also variants of this (the buy-at-bulk problem) where the cost for opening more "facilities" is a concave function. I don't understand the stochastic aspects of the problem though.