Optimization problems, objective functions and optimization benchmarks

Jérémie Decock (www.jdhp.org)

Type of optimization problems

  • continuous vs discrete problems (possibly combinatorial if the set of solutions is discrete and very big)
  • unconstrained vs constrained problems
  • deterministic vs stochastic problems
  • convex vs non-convex problems
  • unimodal vs multimodal problems
  • single-objective vs multi-objective problems
  • differentiable vs nondifferentiable problems
  • linear vs nonlinear problems
  • quadratic vs nonquadratic problems
  • derivative-free problems
  • multistage problems

Remark: unimodal does not imply convex...

Unimodal does not imply convex. For instance, $f(x_1, x_2) = \sqrt{|x_1|} + \sqrt{|x_2|}$ is unimodal but not convex.

Benchmarks

Here are some famous benchmarks:

Test functions for optimization

Test functions for convex deterministic unconstrained continuous single-objective optimization

The sphere function

The Sphere function is a famous convex function used to test the performance of optimization algorithms. This function is very easy to optimize and can be used as a first test to check an optimization algorithm.

$$ f(\boldsymbol{x}) = \sum_{i=1}^{n} x_{i}^2 $$

Global minimum: $$ f(\boldsymbol{0}) = 0 $$

Search domain: $$ \boldsymbol{x} \in \mathbb{R}^n $$

In [7]:
def sphere(x):
    r"""The Sphere function.
    
    Example: single 2D point
    ------------------------
    
    To evaluate $x = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$:
    
    >>> sphere( np.array([0, 0]) )
    0.0
    
    The result should be $f(x) = 0$.
    
    Example: single 3D point
    ------------------------
    
    To evaluate $x = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}$:
    
    >>> sphere( np.array([1, 1, 1]) )
    3.0
    
    The result should be $f(x) = 3.0$.
    
    Example: multiple 2D points
    ---------------------------
    
    To evaluate $x_1 = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$,
    $x_2 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$ and
    $x_3 = \begin{pmatrix} 2 \\ 2 \end{pmatrix}$ at once:
    
    >>> sphere( np.array([[0, 1, 2], [0, 1, 2]]) )
    array([   0.,    2.,  8.])
    
    The result should be $f(x_1) = 0$, $f(x_2) = 1$ and $f(x_3) = 8$.
    
    Parameters
    ----------
    x : array_like
        One dimension Numpy array of the point at which the Sphere function is to be computed
        or a two dimension Numpy array of points at which the Sphere function is to be computed.

    Returns
    -------
    float or array_like
        The value(s) of the Sphere function for the given point(s) `x`.
    """
    return sum(x**2.0)

Remark: sum(x**2.0) is equivalent to np.sum(x**2.0, axis=0)