Before you go, check out these stories!

0
Hackernoon logoSlsqp4j: A Java wrapper around the SLSQP nonlinear optimizer by@skewdotcom

Slsqp4j: A Java wrapper around the SLSQP nonlinear optimizer

We’re excited to open source Slsqp4j, a Java wrapper around the popular SLSQP nonlinear optimizer.

What is Slsqp4j?

SLSQP is a nonlinear optimization algorithm, included as part of SciPy’s optimize package. It was originally outlined by Dieter Kraft in [1] and implemented in [2]. SLSQP uses a sequential-quadratic-programming approach to solve nonlinear optimization problems. It can solve constrained and unconstrained as well as bounded and unbounded problems. This makes it an attractive general-purpose solver.

Slsqp4j is a Java wrapper around SLSQP. It provides an API that is similar to SciPy’s to aid in translating Python code and can solve equivalent problems an order of magnitude faster than SciPy. Slsqp4j is hosted on our Github and is also available on Maven Central.

How we use it at skew.

skew. is a market leader in cryptocurrency derivatives analytics. We provide high quality real-time analytics covering all aspects of the global cryptocurrency derivatives market.

For example, at skew.com/dashboard/bitcoin-options you can track Bitcoin options market data, and view real-time graphs such as the ATM volatility term structure shown below:

In order to provide the above term structure to our users, we need to solve a nonlinear optimization problem in real-time or near real-time.

Several of the graphs in our options dashboards rely on solving similar optimization problems in real-time. Another example of this is below. For this graph, we must fit the volatility surface (in black) based on live-ticking options market data for all the strikes of the September 20 expiry.

Much of our back-end at skew. was bootstrapped in Python, and we have been using SciPy’s SLSQP solver for the past twelve months to generate the above data. However, in order to improve performance and meet the demand of our growing user base, we have started migrating our back-end away from Python and over to Java for the majority of our data ingestion and analytics. Since we could not find a SLSQP solver for the JVM, we wrote our own.

Slsqp4j was designed to be more performant than SciPy. Objects are allocated once and reused wherever possible. Primitive types and arrays are preferred in order to reduce pointer dereferencing and improve cache access.

The result is that Slsqp4j is up to 10 times faster than SciPy at solving equivalent problems. There are additional benefits to using Slsqp4j, such as being able to take advantage of multi-threading in the JVM that is not as well supported in Python (Python’s Global-Interpreter-Lock makes true multi-threading infeasible).

How to Use Slsqp4j

In this section, I’ll show how to use Slsqp4j and outline the similarities it shares with SciPy.

Create an objective function:

public static class ObjectiveFunction implements Vector2ScalarFunc
{
    @Override
    public double apply(double[] x, double… arg)
    {
       // for example
       return x[0] * x[1];
    }
}

Specify one or more constraints:

public static final class VectorConstraintFunction implements Vector2VectorFunc
{
    @Override
    public double[] apply(double[] x, double… arg)
    {
        // for example
        return new double[] {x[0] - x[1]};
    }
}

final VectorConstraint constraint = new VectorConstraint.VectorConstraintBuilder()
 .withConstraintType(ConstraintType.EQ)
 .withConstraintFunction(new VectorConstraintFunction())
 .build();

To perform the optimization, you must construct an instance of an Slsqp object. You do this using the Builder pattern:

final Slsqp slsqp = new Slsqp.SlsqpBuilder()
 .withObjectiveFunction(new ObjectiveFunction())
 .addVectorConstraint(constraint)
 .build();

Then simply call minimize passing in an initial guess vector:

final double[] x = new double[] {1, -1};
final OptimizeResult result = slsqp.minimize(x);

The returned OptimizeResult contains information about the state of the solver. If result.success() returns true, the solver is complete and the vector contained in result.resultVec() is the point at which the function is minimized (note that this may be a local minimum).

Below is a comparison showing the complete usage of Slsqp4j’s API vs. SciPy’soptimize API.

Slsqp4j

final VectorConstraint constraint = new VectorConstraint.VectorConstraintBuilder()
    .withConstraintType(ConstraintType.INEQ)
    .withConstraintFunction((x, arg) -> x[0] — x[1])
    .build();
final Slsqp slsqp = new Slsqp.SlsqpBuilder()
    .withObjectiveFunction((x, arg) -> x[0] * x[1])
    .addVectorConstraint(constraint)
    .build();
final OptimizeResult result = slsqp.minimize(new double[]{1, -1});

SciPy

res = minimize(lambda d: d[0] * d[1], [1, -1], method='SLSQP', constraints={'type': 'ineq', 'fun': lambda x: x[0] — x[1]})

The API is slightly more verbose than SciPy’s due to Java’s type safety, but the similarities should hopefully be apparent.

Benchmarking

We benchmarked Slsqp4j against SciPy by minimizing the Rosenbrock function in N variables. Both solvers start at the same (arbitrary) point and thus follow the same path and arrive at the same minimum. The table below shows the time taken to arrive at this minimum for both Slsqp4j and SciPy, for different size input. In this case, both solvers perform 101 iterations.

As can be seen, Slsqp4j is roughly an order of magnitude faster than SciPy at minimizing the 10-variable Rosenbrock function. For the 1000-variable case, Slsqp4j is only around 2% faster. We think this is because, with 1000 variables, nearly all of the runtime is spent in the Fortran code, which is identical between SciPy and Slsqp4j. The smaller cases spend a smaller portion of the total runtime in the Fortran code and a larger portion of the runtime in the wrapper code.

The benchmarks for both Java and Python can be found at the following gist: https://gist.github.com/jamesasefa/77dc6edbe5e63c8734b235d0f72caf6f

Future Improvements

In the future we would like to include other solvers along with SLSQP, such as the low-storage BFGS.

Also, since Slsqp4j includes shared libraries that were compiled on Ubuntu 18.04, only Ubuntu users can import it directly from Maven Central. We would like to include binaries for other platforms in the future. Other users can build the project directly by checking out from Github and running a gradle build.

We hope people find Slsqp4j useful and we welcome feedback and contributions via Github. We are also hiring developers, so if you find projects such as Slsqp4j interesting, please reach out to us at careers@skew.com.

Jamie Asefa, Software Developer at skew.

References

Also published on: https://medium.com/@skew_options/slsqp4j-a-java-wrapper-around-the-slsqp-nonlinear-optimizer-eaa31540d96e

Dieter Kraft, “A software package for sequential quadratic programming”, Technical Report DFVLR-FB 88–28, Institut für Dynamik der Flugsysteme, Oberpfaffenhofen, July 1988.

Dieter Kraft, “Algorithm 733: TOMP–Fortran modules for optimal control calculations,” ACM Transactions on Mathematical Software, vol. 20, no. 3, pp. 262–281 (1994).

Tags

Join Hacker Noon

Create your free account to unlock your custom reading experience.