ORBIT - optimizing expensive objective functions

Surrogate model optimization, also known as model-based derivative-free optimization, is a popular method for solving smooth nonlinear programming problems with expensive objectives that lack analytic derivatives.

The ALGLIB nonlinear programming suite includes the linearly and nonlinearly constrained ORBIT solver - one of the fastest and the most efficient surrogate optimization algorithms - alongside other nonlinear programming solvers. These are available in C++, C#, Java and several other programming languages under a dual free/commercial licensing model.

This article focuses on the specifics of the ORBIT solver. A high-level overview of the ALGLIB nonlinear programming suite (including the SQP solver, nonsmooth solver and metaheuristic solver) is available on another page. If you arrived at this page while looking for an RBF interpolation, ALGLIB also offers one.

ORBIT solver overview

Description

The ORBIT algorithm was originally proposed by Stefan M. Wild et al. for unconstrained surrogate optimization. It was independently implemented by the ALGLIB Project and extended to support linear and nonlinear constraints.

Similarly to the SQP method, the ORBIT solver builds and iteratively refines a surrogate RBF model. When solving a nonlinearly constrained problem, the solver also builds RBF models for the constraints. The minimum of the model over a trust region is a direction for the next step.

The difference between two methods is that SQP needs derivative information to update its quadratic model in a quasi-Newton fashion. In contrast, the ORBIT solver uses RBF models that do not need derivatives for their construction. Another difference is that minimizing an RBF model over trust region is generally more expensive than solving a QP subproblem. Thus, the solver is intended for problems with the following properties:

• Expensive objective and/or constraints. The cost of objective evaluation must be high enough to justify using more expensive RBF optimization subproblems.
• Limited computational budget. The focus is on finding the best solution within an upper limit on the number of objective evaluations.
• Parallel numerical differentiation is unavailable, for example due to the objective evaluation code being thread-unsafe or, alternatively, already being parallel and running at full speed.
• Medium-accuracy solution is needed. The solver excels in achieving rapid convergence to the neighborhood of the solution, with performance improvements of 4x to 10x over the SQP solver during initial convergence. While the solver can converge to a solution with any desired precision, its main strength is achieving rapid convergence with limited computational budgets.

Programming languages supported

ALGLIB supports many programming languages, including C++, C#, Java, Python, and others:

• C++ version. Highly optimized, portable (x86/x64/ARM, works on Windows, Linux, and POSIX systems), and is a self-contained library
• C# version. Unified C# API for two backends - a fully managed C# implementation and a high-performance native computational core written in C
• Java, Python and other languages. A wrapper for a high-performance native computational core written in C. Seamless integration with the target programming language

A distinctive feature of ALGLIB is that it provides exactly the same API in all programming languages. This is achieved with our exclusive technology of automatic code translation and wrapper generation.

Documentation and examples

The ORBIT algorithm is included into the minnlc subpackage of the Optimization package. It can be used interchangeably with other algorithms from the subpackage. The ALGLIB Reference Manual includes several examples on how to configure the MINNLC solver suite, as well as an example on the ORBIT specifically: minnlc_modelbased.

This article is licensed for personal use only.