ConvexSolver Performance

We're often asked about how large problems/models the ojAlgo mathematical programming solvers can handle. In particular we get this question in relation to the MarkowitzModel class.

To examine this we've created this simple test. It creates a simplified streamlined version of a Markowitz portfolio optimisation model.

Compared to using ojAlgo's MarkowitzModel class, and the performance you could expect with it, there are 3 things to remember:

1. The MarkowitzModel class can be used in 3 different ways; "target variance", "target return" and "risk aversion". The model here corresponds to the "risk aversion" problem formulation. The "target variance" and "target return" use cases could be something like 10 times slower, because they actually solve a sequence of optimisation problems.
2. The covariance matrix used here is much simplified compared to a realistic one - it's a diagonal matrix. This structure could be exploited by a solver to greatly increase performance, but ojAlgo does not have that feature. Therefore we assume performance will be similar to that of a more realistic case.
3. Compared to these timings the MarkowitzModel class would have additional overhead in creating the optimisation model. Apart from creating a somewhat simplified model, the model creation time is not measured here at all.

Example code

import static org.ojalgo.constant.BigMath.*;

import org.ojalgo.OjAlgoUtils;
import org.ojalgo.netio.BasicLogger;
import org.ojalgo.optimisation.Expression;
import org.ojalgo.optimisation.ExpressionsBasedModel;
import org.ojalgo.optimisation.Optimisation.Result;
import org.ojalgo.optimisation.Optimisation.State;
import org.ojalgo.optimisation.Variable;
import org.ojalgo.random.Uniform;

/**
 * This example creates random/simple quadratic programming (QP) problems - similar to what the MarkowitzModel
 * portfolio optimiser would create - at increasing sizes. The execution speed is measured for each problem
 * size. The problem size is doubled for every iteration. Theoretically, regardless of how long you're willing
 * to wait, the ojAlgo convex solvers have an absolute limit somewhere around 20000 variables.
 *
 * @author apete
 */
public class ConvexSolverPerformance {

    /**
     * Random number [0.0%,20.0%)
     */
    private static final Uniform UNIFORM_20 = new Uniform(0.0, 0.2);

    public static void main(final String[] args) {

        BasicLogger.debug();
        BasicLogger.debug(ConvexSolverPerformance.class.getSimpleName());
        BasicLogger.debug(OjAlgoUtils.getTitle());
        BasicLogger.debug(OjAlgoUtils.getDate());
        BasicLogger.debug();

        for (int exp = 1; exp <= 12; exp++) {
            final int tmpNumberOfVariables = (int) Math.pow(2, exp);

            final ExpressionsBasedModel tmpModel = ConvexSolverPerformance.buildModel(tmpNumberOfVariables);

            final long tmpBefore = System.nanoTime();
            final Result tmpResult = tmpModel.minimise();
            final long tmpAfter = System.nanoTime();

            final State tmpState = tmpResult.getState();
            final double tmpTime = (tmpAfter - tmpBefore) / 1_000_000_000.0;

            BasicLogger.debug(); // Log the problem size, execution time and result state
            BasicLogger.debug("{} variables =>\t{} in {}s", tmpNumberOfVariables, tmpState, tmpTime);

            // If the problem is small; also print the entire model
            if (tmpNumberOfVariables <= 10) {
                BasicLogger.debug(tmpModel);
            }
        }
    }

    private static ExpressionsBasedModel buildModel(final int numberOfVariables) {

        final Variable[] tmpVariables = new Variable[numberOfVariables];
        for (int i = 0; i < numberOfVariables; i++) {
            tmpVariables[i] = Variable.make("V" + Integer.toString(i)).lower(ZERO).weight(-UNIFORM_20.doubleValue());
        }

        final ExpressionsBasedModel retVal = new ExpressionsBasedModel(tmpVariables);

        final Expression tmp100P = retVal.addExpression("Balance");
        for (final Variable tmpVariable : tmpVariables) {
            tmp100P.setLinearFactor(tmpVariable, ONE);
        }
        tmp100P.level(ONE);

        final Expression tmpVar = retVal.addExpression("Variance");
        for (final Variable tmpVariable : tmpVariables) {
            tmpVar.setQuadraticFactor(tmpVariable, tmpVariable, UNIFORM_20);
        }
        tmpVar.weight(TWO);

        return retVal;
    }

}

Console output

ConvexSolverPerformance
ojAlgo
2015-02-28


2 variables =>  OPTIMAL in 0.135668217s
############################################
0 <= V0: 0.409057 (-0.039568)
0 <= V1: 0.590943 (-0.059210)
1.000000 <= Balance: 1.0 <= 1.000000
Variance: 0.057609 (2.000000)
############################################


4 variables =>  OPTIMAL in 0.004440233s
############################################
0 <= V0: 0.571081 (-0.109783)
0 <= V1: 0.123390 (-0.083583)
0 <= V2: 0.054572 (-0.022376)
0 <= V3: 0.250957 (-0.144587)
1.000000 <= Balance: 1.0 <= 1.000000
Variance: 0.027543 (2.000000)
############################################


8 variables =>  OPTIMAL in 0.009055943s
############################################
0 <= V0: 0.061132 (-0.082050)
0 <= V1: 0 (-0.058770)
0 <= V2: 0.000990 (-0.068060)
0 <= V3: 0.223310 (-0.164476)
0 <= V4: 0.616204 (-0.167632)
0 <= V5: 0.052287 (-0.101037)
0 <= V6: 0.046077 (-0.091844)
0 <= V7: 0 (-0.047347)
1.000000 <= Balance: 1.0 <= 1.000000
Variance: 0.021807 (2.000000)
############################################


16 variables => OPTIMAL in 0.012746123s

32 variables => OPTIMAL in 0.031890699s

64 variables => OPTIMAL in 0.113378838s

128 variables =>    OPTIMAL in 0.136877527s

256 variables =>    OPTIMAL in 0.614879036s

512 variables =>    OPTIMAL in 2.984121601s

1024 variables =>   OPTIMAL in 31.028329649s

2048 variables =>   OPTIMAL in 274.184578823s

4096 variables =>   OPTIMAL in 4249.644597523s