Thursday, December 10, 2015

Modeling languages vs Matrix Generators

A famous paper by Bob Fourer “Modeling languages versus matrix generators for linear programming  (ACM TOMS, 1983) discusses the advantages of a modeling language (AMPL) versus the (then) traditional way of building models: write some fortran code that generates MPS files. The “matrix generator” approach (now “matrix” taken literally) seems to enjoy somewhat of a comeback with languages like R and Matlab. Here are a few examples.

GAMS vs R/QuadProg

A standard portfolio optimization model minimizing risk can be stated as:

image

This is actually just a direct representation of the GAMS model:

image

The GAMS formulation is very close to the mathematical model. This model can be solved with any number of solvers, such as Cplex, Gurobi, Mosek, Conopt, Knitro, IPOPT, Minos and Snopt. They all accept the same formulation.

When we solve the same model using R and its QP solver from the QuadProg package, we need to look at how exactly the solver expects its input. Quadprog solves a problem of the form:

image

where the first meq constraints are equalities. We quite literally need to build up a matrix A:

image 

The generated matrix A looks like:

image

GAMS vs Matlab/QuadProg

In Matlab there is a similar function quadprog, but it has facilities to specify bounds on the variables. That allows us to simplify the setup somewhat.

image

Also note that this quadprog solves a slightly different problem:

image 

The documentation for the Matlab functions is excellent:

GAMS vs R/cccp

A different model deals with a nonlinearly constrained problem. Instead of only having a budget equation (sum of asset allocations is one) we also add a 2-norm inequality: ||x||2 ≤ δ. Such a norm constraint is discussed here. We could model this as a quadratically constrained problem (we get rid of the square root to make the model quadratic):

image

The GAMS representation is very much the same.

In R general purpose nonlinear programming problems are not so easy to set up as we need to worry about gradients etc. However we can solve this problem as a cone programming problem. A port of the CVXOPT system is available under R as cccp (Cone Constrained Convex Problems). Again, this means setting up matrices:

image 

This is very compact but not very self-explanatory. In addition we see that two very similar models but for different solvers require a very different approach.