1
$\begingroup$

If the objective function contains $n$ variables (e.g. $f(x_1, ..., x_n)$) in the Nelder-Mead algorithm (or other direct search methods), is there any known lower/upper bounds on how many times the algorithm needs to evaluate $f$ to achieve the desired value by precision $\epsilon$?

For instance, suppose $f(x_1,x_2) = \text{Tr}(x_1x_2)$ is defined on $2$-dimensional parameters $(x_1,x_2) \in R^2$, where $-1 \leq x_1, x_2 \leq 1$. Starting from random sets of parameters of $v = (v_1, v_2), w = (w_1, w_2), y = (y_1, y_2)$, the Nelder-Mead algorithm starts from a triangle in 2D and evaluate $f(v), f(w), f(y)$ and either reflect/expand/contract/shrink, and repeat the procedure until it converges to desired values of $|f_{target} - f| \leqslant \epsilon$. Is there theoretical bounds on how many times the algorithm evaluate $f$ until the convergence is taken?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

There are no guarantees. In the worst case, if the function $f$ is particularly unfriendly, any optimization algorithm might need to evaluate $f$ on every possible combination of values, to find the optimum. (Consider a function $f$ that is zero on all points except for a single point, where it is very large or very small.) So, in effect, there are no bounds on the number of evaluations of $f$ needed.

With some optimization algorithms, one can obtain some bounds if we have additional conditions on $f$ (e.g., that it is Lipschitz), but my sense is that these bounds are typically not terribly useful in practice.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. I'm looking into arxiv.org/pdf/1410.0390.pdf this morning, which seems to give $O(n^2/\epsilon^2)$ as the bound for minimizing gradient-free direct search algorithm for convex cost function. $\endgroup$
    – Jon Megan
    Apr 24, 2022 at 22:40
  • 1
    $\begingroup$ @JonMegan, Yup! Looks like the kind of theoretical result I was thinking of. These papers need to be read carefully -- you may have overlooked some additional assumptions made in that paper. In particular, they assume that $f$ is Lipschitz (see Section 2). See the last paragraph of my answer for my comments on that style of result. $\endgroup$
    – D.W. ♦
    Apr 24, 2022 at 23:11
  • $\begingroup$ I get it, thank you. I'm just wondering on the L-smooth function: do all smooth functions also $L$-smooth function? The reason I'm asking this is basically I have this form of function that I know it's smooth (i.e. differentiable in all domain) but I'm wondering how to prove the function is $L$-smooth, and if the statement above is true, then I can skip this proof and directly use the result from the paper. $\endgroup$
    – Jon Megan
    Apr 25, 2022 at 23:37
  • $\begingroup$ @JonMegan, I don't know whether all smooth functions are Lipschitz, but it looks like the answer might be no (please investigate and verify for yourself): en.wikipedia.org/wiki/Lipschitz_continuity#Examples, math.stackexchange.com/q/2552893/14578 $\endgroup$
    – D.W. ♦
    Apr 26, 2022 at 6:24
  • $\begingroup$ Thanks, I agree that smooth functions are not Lipschitz, but am wondering if smooth functions are Lipschitz continuous gradient. I'll examine by myself. I have one more additional question: in the Table 1 in the paper above, do you know why the goal for nonconvex function is not $||f(x) - f(x^*)|| \leq \epsilon$ but rather $||\nabla f(x) || \leq \epsilon$? $\endgroup$
    – Jon Megan
    Apr 26, 2022 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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