Derivative-free optimization: a review of algorithms and comparison of software implementations

By Luis Miguel Rios, Nikolaos V. Sahinidis. 2012

1,388 citations recorded by the source corpus.

This paper addresses the solution of bound-constrained optimization problems using algorithms that require only the availability of objective function values but no derivative information. We refer to these algorithms as derivative-free algorithms. Fueled by a growing number of applications in science and engineering, the development of derivative-free optimization algorithms has long been studied, and it has found renewed interest in recent time. Along with many derivative-free algorithms, many software implementations have also appeared. The paper presents a review of derivative-free algorithms, followed by a systematic comparison of 22 related implementations using a test set of 502 problems. The test bed includes convex and nonconvex problems, smooth as well as nonsmooth problems. The algorithms were tested under the same conditions and ranked under several criteria, including their ability to find near-global solutions for nonconvex problems, improve a given starting point, and refine a near-optimal solution. A total of 112,448 problem instances were solved. We find that the ability of all these solvers to obtain good solutions diminishes with increasing problem size. For the problems used in this study, TOMLAB/MULTIMIN, TOMLAB/GLCCLUSTER, MCS and TOMLAB/LGO are better, on average, than other derivative-free solvers in terms of solution quality within 2,500 function evaluations. These global solvers outperform local solvers even for convex problems. Finally, TOMLAB/OQNLP, NEWUOA, and TOMLAB/MULTIMIN show superior performance in terms of refining a near-optimal solution.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Accessorize to a Crime: Real and Stealthy Attacks on State-of-the-Art Face Recognition (2016, background): “…over other black-box optimization meth-ods such as surrogate models [3]—which require that the adversary has the training data and enough computational resources to train an eﬀective surrogate—and genetic algorithms [2]—which though similar to PSO are much less computationally eﬃcient [15, 34].”
Google Vizier: A Service for Black-Box Optimization (2017, background): “Black–box optimization makes minimal assumptions about the problem under consideration, and thus is broadly applicable across many domains and has been studied in multiple scholarly fields under names including Bayesian Optimization [2, 25, 26], Derivative– free optimization [7, 24], Sequential Expe”
Learning surrogate models for simulation‐based optimization (2014, methodology): “As shown recently in [34], these methods are most effective in low-dimensional cases, like we have here thanks to the decomposition of the original large simulation into pieces.”
Rigorous design of distillation columns using surrogate models based on Kriging interpolation (2015, methodology): “Although DFO algorithms can be used in models with costly and/or noisy function evaluations, these methods are often constrained to models in which the number of degrees of freedom does not exceed about 10.(13) According to the framework of application, a single model of the objective function is us”
Knowledge-Defined Networking (2016, background): “Conceptually, the KDN architecture borrows many ideas from other areas, notably from black-box optimization [5], neural-network in feedback control systems [6] and autonomic self-* architectures [7].”
Deep Reinforcement Learning for Intelligent Transportation Systems: A Survey (2020, methodology): “some effective gradient-free approaches in the literature for optimizing policies in non-RL methods [14], gradient-based methods are known to be more useful for policy optimization in all types of RL algorithms.”
Connecting Large Language Models with Evolutionary Algorithms Yields Powerful Prompt Optimizers (2024, neutral): “Several conventional derivative-free algorithms are well-designed and strike a good balance between exploration and exploitation (Conn et al., 2009; Rios & Sahinidis, 2013).”
An Artificial Agent for Robust Image Registration (2016, methodology): “The transformation parameters between the image pairs are then estimated via maximization of the deﬁned matching metric using an optimizer (Rios and Sahinidis 2013).”
Large Language Models as Optimizers (2023, methodology): “Many optimization techniques are iterative: the optimization starts from an initial solution, then iteratively updates the solution to optimize the objective function (Amari, 1993; Qian, 1999; Kingma & Ba, 2015; Bäck & Schwefel, 1993; Rios & Sahinidis, 2013; Reeves, 1993).”
A Survey of Optimization Methods From a Machine Learning Perspective (2019, methodology): “The derivative-free optimization methods [11], [12] are mainly used in the case that the derivative of the objective function may not exist or be difficult to calculate.”
Black-Box Tuning for Language-Model-as-a-Service (2022, methodology): “Since gradients are unavailable, we can only invoke derivative-free optimization (DFO) 3 (Kolda et al., 2003; Conn et al., 2009; Rios & Sahinidis, 2013).”