Minimize a function through its upper approximation

Question

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.

Answer 1

If the derivatives are not known, you can use any constrained optimizer where the derivatives are approximated. Otherwise, I can recommended stochastic/blackbox/global optimization methods. The derivatives are not estimated and only function evaluations are needed.

But because your function is convex and has such a relatively high domain space, I would discourage stochastic optimization methods.

If it is not known how close $F(x)$ is to $f(x)$ for all $x \in \mathbb{R}^n$, then you cannot imply that $x^* = argmin F(x) = argminf(x)$.

To answer your question: the minimization of $F(x)$ will imply the minimization of $f(x)$ if $|F(x)-f(x)| = 0$ $\forall x \in \mathbb{R}^n$.

$F(x)$ can be quasiconvex, meaning it can have multiple local minima and the global minimum is not necessarily where the minima of $f(x)$ lies.