I have some function $f(x) : \mathbb{R}^n \to \mathbb{R}$ (n is about several thousands, say $1000 \leq n \leq 10000$) to minimize over some constraints $g(x) \leq 0$ (by the way, $g$ is quadratic over $x$).

$f(x)$ is convex, differentiable (but not twice differentiable), nonnegative for all $x \in \mathbb{R}^n$, but its formula is too complicated (from the computational point of view). Thus I'm not able to write down its derivatives and pass them to the solver (or I can but have a strong opinion that it will not work).

But: there is an upper approximation $F(x)$ such as $F(x) \geq f(x) \geq 0$ for all $x \in \mathbb{R}^n$ which is somewhat "close" to $f(x)$ (though it is not yet proved *how much close*) and its formula is much better and it is much more convenient to optimize, and it has derivatives of all degrees.

For which condition on the quality of approximation ($|F(x) - f(x)|$) the minimization of $F(x)$ will imply the minimization of $f(x)$?

Sorry if this seems too trivial! But I cannot easily figure out in what direction to dig this problem but at the same time have a strong feeling that it should be some commonly known problem.

UPDATE:

Both $f(x)$ and $F(x)$ are convex.