QCML: Quadratic Cone Modeling Language

Who is this for?

For casual users of convex optimization, the CVXPY project is a friendlier user experience, and we recommend all beginners start there.

This project is designed primarily for developers who want to deploy optimization code. It generates a lightweight wrapper to ECOS for use in Matlab, Python, or C. This avoids repeated parsing and also allows problem dimensions to change. This means you can re-use the same optimization model in C without having to re-generate the problem.

If you are a developer looking to use optimization, feel free to contact us with issues or support. Complete documentation is available here.

Introduction

This project is a modular convex optimization framework for solving second-order cone optimization problems (SOCP). It separates the parsing and canonicalization phase from the code generation and solve phase. This allows the use of a unified (domain-specific) language in the front end to target different use cases.

For instance, a simple portfolio optimization problem can be specified as a Python string as follows:

"""
dimensions m n

variable x(n)
parameter mu(n)
parameter gamma positive
parameter F(n,m)
parameter D(n,n)
dual variable u
maximize (mu'*x - gamma*(square(norm(F'*x)) + square(norm(D*x))))
    sum(x) == 1
    u : x >= 0
"""

Our tool parses the problem and rewrites it, after which it can generate Python code or external source code. The basic workflow is as follows (assuming s stores a problem specification as above).

p.parse(s)
p.canonicalize()
p.dims = {'m': 5}
p.codegen('python')
socp_data = p.prob2socp({'mu':mu, 'gamma':1,'F':F,'D':D}, {'n': 10})
sol = ecos.solve(**socp_data)
my_vars = p.socp2prob(sol['x'], {'n': 10})

We will walk through each line:

1. parse the optimization problem and check that it is convex
2. canonicalize the problem by symbolically converting it to a second-order cone program
3. assign some dims of the problem; others can be left abstract (see [below] (#abstract-dimensions))
4. generate python code for converting parameters into SOCP data and for converting the SOCP solution into the problem variables
5. run the prob2socp conversion code on an instance of problem data, pulling in local variables such as mu, F, D; because only one dimension was specified in the codegen step (3), the other dimension must be supplied when the conversion code is run
6. call the solver ecos with the SOCP data structure
7. recover the original solution with the generated socp2prob function; again, the dimension left unspecified at codegen step (3) must be given here

For rapid prototyping, we provide the convenience function:

solution = p.solve()

This functions wraps all six steps above into a single call and assumes that all parameters and dimensions are defined in the local namespace.

Finally, you can call

p.codegen("C", name="myprob")

which will produce a directory called myprob with five files:

• myprob.h -- header file for the prob2socp and socp2prob functions
• myprob.c -- source code / implementation of the two functions
• qc_utils.h -- defines static matrices and basic data structures
• qc_utils.c -- source code for matrices and data structures
• Makefile -- sample Makefile to compile the .o files

You can include the header and source files with any project, although you must supply your own solver. The code simply stuffs the matrices for you; you are still responsible for using the proper solver and linking it. An example of how this might work is in examples/lasso.py.

The qc_utils files are static; meaning, if you have multiple sources you wish to use in a project, you only need one copy of qc_utils.h and qc_utils.c.

The generated code uses portions of CSparse, which is LGPL. Although QCML is BSD, the generated code is LGPL for this reason.

For more information, see the features section.

Prerequisites

For the most basic usage, this project requires:

• Python 2.7.2+ (no Python 3 support yet)
• PLY, the Python Lex-Yacc parsing framework. Available as python-ply or py-ply package in most distributions
• ECOS
• ECOS Python module
• NUMPY
• SCIPY

For (some) unit testing, we use Nose.

Installation

Installation should be as easy as

python setup.py install

After installation, if you have Nose installed, then typing

nosetests

should run the simple unit tests. These tests are not exhaustive at the moment.

A set of examples can be found under the examples directory.

Features

Basic types

There are three basic types in QCML:

• dimension (or dimensions for multiple)
• parameter (or parameters for multiple)
• variable (or variables for multiple)

A parameter may optionally take a sign (positive or negative). These are entirely abstract. All variables are currently assumed to be vectors, and all parameters are assumed to be (sparse) matrices. For example, the code

dimensions m n
variables x(n) y(m)
parameter A(m,n) positive
parameters b c(n)

declares two dimensions, m and n; two variables of length n and m, respectively; an elementwise positive (sparse) parameter matrix, A; the scalar parameter b; and the vector parameter c.

Furthermore, a variable may be marked as a dual variable by prefixing the declaration with dual. Thus, dual variable y (no dimensions) declares y to be a dual variable. Dual variables are associated with constraints with a colon: y : x >= 0, associates the dual variable y with the nonnegativity constraint.

Abstract dimensions

Dimensions are initially specified as abstract values, e.g. m and n in the examples above. These abstract values must be converted into concrete values before the problem can be solved. There are two ways to make dimensions concrete:

1. specified prior to code generation with a call to dims = {...}
2. specified after code generation by passing a dims dict/struct to the generated functions, e.g. prob2socp, socp2prob

Any dimensions specified using dims = {...} prior to calling codegen() will be hard-coded into the resulting problem formulation functions. Thus all problem data fed into the generated code must match these prespecified dimensions.

Alternatively, some dimensions can be left in abstract form for code generation. In this case, problems of variable size can be fed into the generated functions, but the dimensions of the input problem must be fed in at the same time. Problem dimensions must also be given at the recovery step to allow variables to be recovered from the solver output.

The user may freely mix prespecified and postspecified dimensions.

(A future release may allow some dimensions to be inferred from the size of the inputs.)

<!-- Another possible future change would remove the requirement to specify problem dimensions in the variable recovery step by embedding that information in the output of the problem formulation function. -->

Parsing and canonicalization

The parser/canonicalizer canoncializes SOCP-representable convex optimization problems into standard form:

minimize c'*x
subject to
  G*x + s == h
  A*x == b
  s in Q

where Q is a product cone of second-order cones (i.e., Q = { (t,y) | ||y|| <= t }), and x, s are the optimization variables. The parser/canonicalizer guarantees that all problems will adhere to the disciplined convex programming (DCP) ruleset and that the problem has the form

minimize aff
subject to
  aff == 0
  norm(aff) <= aff

where aff is any affine expression. This can also be a maximization or feasibility problem. If a problem is entered directly in this form, the parser/canonicalizer will not modify it; in other words, the parser/canonicalizer is idempotent with respect to SOCPs.

Generation and solve

The generator/solver can be used in prototyping or deployment mode. In prototyping mode (or solve mode), a function is generated which, when supplied with the problem parameters, will call an interior-point solver to solve the problem. In deployment mode (or code generation mode), source code (in a target language) is generated which solves problem instances.

The generated code can have problem dimensions hard-coded if dims were specified prior to codegen, or it can have [abstract dimensions] (#abstract-dimensions) to allow problems of variable size to be solved.

The valid choice of languages are:

• "python" -- emits Python source code
• "C" -- emits C source code
• "matlab" -- emits Matlab source code
• (planned) "cvx" -- emits Matlab source code that calls CVX

With the exception of the "cvx" target, the code generator will produce (at least) two functions in the target language:

• prob2socp -- takes problem parameters as input outputs SOCP data, c, G, h, A, b, and the cone descriptions
• socp2prob -- takes an SOCP solution and recovers the original variables

If it generates Python code, exec is called to create the function bytecode dynamically, allowing you to call your favorite solver.

If the target "language" is "cvx", we will generate a single Matlab file that contains the CVX-equivalent problem.

Data structures

In this sec