Getting to Know the Engine: an Overview

Contents





Introduction

Octeract Engine is a Deterministic Global Optimisation (DGO) solver which solves general nonlinear problems to guaranteed global optimality. The general mathematical description is encapsulated in problem \(P\) :

\begin{align} P : \min_{\substack{ x\in X \\y\in Y }} &f(x,y)\\ \textrm{s.t. } &g(x,y)\leq \ 0 \nonumber\\ &h(x,y)=\ 0 \nonumber \\ &X=[\ x^L,\ x^U]\subset\mathbb{R}^n \nonumber \\ &Y=\{0,1\}\nonumber \end{align}
The solver can solve any nonlinear function to global optimality, as long as that function has an analytical form that does not include differential expressions or integrals. For instance,

\begin{equation} \underset{x\in[-1,1]}\min\sqrt{x}\nonumber,\;\;\; \underset{x\in[-1,1]}\min\Big|-\log(\frac{1}{\tan(x)^{0.85}})\Big|,\;\;\; \underset{x\in[-1,1]}\min\sqrt{\max(x^{-1/2},1)}\nonumber,\;\;\; \nonumber \end{equation}
are valid inputs, whereas:

\begin{equation} \underset{x\in[-1,1]}\min \Gamma{(x)}\nonumber \nonumber \end{equation}
is not valid input because the expression for the Gamma function is an integral.


Note

Two important exceptions to the analytical expression rule are \(min(f(x),g(x)\) and \(max(f(x),g(x)\), which are fully supported.


Solver Highlights

No Starting Points
Users do not need to define starting points when using Octeract Engine. The solver will locate feasible solutions automatically as part of its branch-and-bound search.



Guaranteed Calculations
Octeract Engine uses a combination of Interval Arithmetic and Arbitrary Precision Arithmetic to guarantee the correctness of all internal calculations. The combination of these two paradigms enables the solver to handle extremely challenging numerics.

This is very important in Deterministic Global Optimisation, as our algorithms are always at risk of incorrectly eliminating the global solution due to bad floating-point calculations. However, Octeract Engine relies on third-party solvers in order to solve NLP and LP subproblems, meaning that it is possible for the solver to return an incorrect result due to numerical error from third-party software.

In the majority of cases, the solver compensates for such errors using conservative tolerances for external calculations, but it is important for users to be aware that the end result is still subject to third-party floating-point errors.




Symbolic Engine
Octeract Engine comes equipped with a full-fledged symbolic engine designed for optimisation mathematics, which allows it to perform symbolic manipulation of user input to an unprecedented degree.

Octeract Reformulator

The Octeract symbolic engine for optimisation math is a standalone product, a.k.a. the Octeract Reformulator. The Reformulator is an extremely flexible tool which allows users to script complicated reformulations, create reformulation libraries and apply the same reformulations to other problems, or to share them with collaborators. Octeract Engine is equipped with a special version of the Reformulator, tuned for global optimisation problems.

Because of the Reformulator, users should never need to reformulate their problems manually to make them solvable by Octeract Engine – the solver handles bad math automatically.




Accessible Parallelism
Octeract Engine can be run in parallel using MPI out of the box, for single machines and computing clusters alike.


blog/blog1003