<jupyter_start><jupyter_text>Why optimization is difficultThis tutorial shows why optimization is difficult and you need some knowledge in order to solve optimization problems efficiently. It is meant for people who have no previous experience with numerical optimization and wonder why there are so many optimization algorithms and still none that works for all problems. For each potential problem we highlight, we also give some ideas on how to solve it. If you simply want to know how to choose an optimization algorithm, check out [our very brief guide](which_optimizer_to_use.ipynb) or the [longer version](../how_to_guides/optimization/how_to_choose_optimizer.rst).If you simply want to learn the mechanics of doing optimization with estimagic, check out the [first optimization with estimagic tutorial](first_optimization_with_estimagic.ipynb)The message of this notebook can be summarized as follows:- The only algorithms that are guaranteed to solve all problems are grid search or other algorithms that evaluate the criterion function almost everywhere in the parameter space.- If you have more than a hand full of parameters these methods would take too long.- Thus, you have to know the properties of your optimization problem and have knowledge on different optimization algorithms in order to choose the right algorithm for your problem. This tutorial uses variants of the sphere function from the [first optimization with estimagic tutorial](first_optimization_with_estimagic.ipynb) to illustrate problems.<jupyter_code>def sphere(params):
    return (params["value"] ** 2).sum()


def sphere_gradient(params):
    return params * 2<jupyter_output><empty_output><jupyter_text>Why grid search is infeasibleSampling based optimizers and grid search require the parameter space to be bounded in all directions. Let's assume that we know the optimum of the sphere function is between -0.5 and 0.5, but don't know where it is. In order to get a precision of 2 digits with a grid search, we require the following number of function evaluations (depending on the number of parameters).<jupyter_code>dimensions = np.arange(10) + 1
n_evals = 100**dimensions
sns.lineplot(dimensions, n_evals)<jupyter_output><empty_output><jupyter_text>If you have 10 dimensions and your criterion function takes one second, you need about 3 billion years on a 1000 core cluster. Many of real world criterion functions have hundreds of parameters and take minutes to evaluate once. This is called the curse of dimensionality. Sampling based algorithms typically fix the number of criterion evaluations and try to spend them a bit smarter than searching completely randomly. However, the smart tricks only work under additional assumptions. Thus, either you need to make assumptions on your problem or you will get the curse of dimensionality through the backdoor again. For easier analysis, assume we fix the number of function evaluations in a grid search instead of a sampling based algorithm and want to know which precision we can get, depending on the dimension:For 1 million function evaluations, we can expect the following precision:<jupyter_code>dimensions = np.arange(10) + 1
precision = 1e-6 ** (1 / dimensions)
sns.lineplot(dimensions, precision)<jupyter_output><empty_output><jupyter_text>How derivatives can solve the curse of dimensionalityDerivative based methods do not try to evaluate the criterion function everywhere in the search space. Instead they start at some point and go "downhill" from there. The gradient of the criterion function indicates which direction is downhill. Then there are different ways of determining how far to go in that direction. The time it takes to evaluate a derivative increases at most linearly in the number of parameters. Using the derivative information, optimizers can often find an optimum with very few function evaluations.  How derivative based methods can failTo see how derivative based methods can fail, we use simple modifications of the sphere function.<jupyter_code>def sphere_with_noise(params):
    return sphere(params) + np.random.normal(scale=0.01)


start_params = pd.DataFrame(
    data=np.arange(5) + 1,
    columns=["value"],
    index=[f"x_{i}" for i in range(5)],
)
start_params
grid = np.linspace(-1, 1, 1000)
sns.lineplot(
    x=grid,
    y=(grid**2) + np.random.normal(scale=0.01, size=len(grid)),
)
minimize(
    criterion=sphere_with_noise,
    params=start_params,
    algorithm="scipy_lbfgsb",
    logging=False,
)<jupyter_output><empty_output><jupyter_text>So the algorithm failed, but at least tells you that it did not succed. Let's look at a different kind of numerical noise that could come from rounding.<jupyter_code>def piecewise_constant_sphere(params):
    params = params.copy(deep=True)
    params["value"] = params["value"].round(2)
    return sphere(params)
sns.lineplot(x=grid, y=grid.round(2) ** 2)
minimize(
    criterion=piecewise_constant_sphere,
    params=start_params,
    algorithm="scipy_lbfgsb",
    logging=False,
)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.05828707375099128, 'fraction_numerical': 0.009119746233148296, 'mean_word_length': 5.394169835234474, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '229685', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 1337, 'n_tokens_neox': 1253, 'n_words': 625, 'path': 'docs/source/getting_started/why_optimization_is_hard.ipynb', 'repo_name': 'janosg/estimagic', 'size': '5044'}