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:
This is actually just a direct representation of the GAMS model:
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:
where the first meq constraints are equalities. We quite literally need to build up a matrix A:
The generated matrix A looks like:
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.
Also note that this quadprog solves a slightly different problem:
The documentation for the Matlab functions is excellent:
- http://www.mathworks.com/help/optim/ug/quadprog.html
- http://www.mathworks.com/help/optim/examples/using-quadratic-programming-on-portfolio-optimization-problems.html
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):
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:
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.
No comments:
Post a Comment