CODEWITHSUNDEEP
c++optimizationmathematical-optimization
Quirion
Quirion

Reputation: 119

Efficient evaluation of arbitrary functions given as data, in C++

Consider the following goal:

Create a program that solves: minimize f(x) for an arbitrary f and x supplied as input.

How could one design a C++ program that could receive a description of f and x and process it efficiently?

If the program was actually a C++ library then one could explicitly write the code for f and x (probably inheriting from some base function class for f and state class for x). However, what should one do if the program is for example a service, and the user is sending the description of f and x in some high level representation, e.g. a JSON object?

Ideas that come to mind 1- Convert f into an internal function representation (e.g. a list of basic operations). Apply those whenever f is evaluated. Problems: inefficient unless each operation is a batch operation (e.g. if we are doing vector or matrix operations with large vectors / matrices).

2- Somehow generate C++ code and compile the code for representing x and computing f. Is there a way to restrict compilation so that only that code needs to be compiled, but the rest of the code is 'pre-compiled' already?

Upvotes: 1

Views: 91

Answers (1)

vitaut
vitaut

Reputation: 55554

The usual approach used by the mp library and others is to create an expression tree (or DAG) and use some kind of a nonlinear optimization method that normally relies on derivative information which can be computed using automatic or numeric differentiation.

An expression tree can be efficiently traversed for evaluation using a generic visitor pattern. Using JIT might be an overkill unless the time taken for evaluating a function takes substantial fraction of the optimization time.

Upvotes: 1

Related Questions