# Minimize a function through its upper approximation

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.

• You could try to do line search where the descend direction is found using $F$ and the step size is found using $f$. Not sure however what the conditions on $F$ is for this to work and what the performance will be... May 22 '20 at 5:36

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.
• Thanks for the answer! I have forgotten to say that $F(x)$ is also convex. Can it help somehow? May 27 '20 at 4:22