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.


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

  • $\begingroup$ 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... $\endgroup$
    – user35593
    May 22 '20 at 5:36

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.

  • $\begingroup$ Thanks for the answer! I have forgotten to say that $F(x)$ is also convex. Can it help somehow? $\endgroup$ May 27 '20 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.