View on GitHub

QCML

Quadratic cone modeling language

Download this project as a .zip file Download this project as a tar.gz file

Quadratic Cone Modeling Language (QCML)

This repository is currently a work in progress If you wish to use this in your project, please contact us.

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)
maximize (mu'*x - gamma*(square(norm(F'*x)) + square(norm(D*x))))
    sum(x) == 1
    x >= 0
"""

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

p.parse(s)
p.canonicalize()
p.set_dims({'m': m, 'n': n})
p.codegen("cvxopt")
solution = p.solver({'gamma':1,'F':F,'D':D})

The third line sets the dimensions of the problem and the last line calls the (Python) solver generated in the codegen step. This solver requires that the user specify the parameters in their optimization model. For rapid prototyping, we provide the convenience function:

solution = p.solve(locals())

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

Prerequisites

For the most basic usage, this project requires:

For (some) unit testing, we use Nose.

Depending on the type of code you generate, you may also need:

PDOS is an experimental first-order solver, and we recommend CVXOPT or ECOS over it.

Installation

Installation should be as easy as

cd src
python setup.py install

After installation, if you have Nose installed, then typing

nosetests scoop

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

The only working sample scripts are qcml_example.py and main.py. The others refer to an older implementation. The main.py script takes command line arguments and emits Matlab code used to call ECOS.

Features

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 a particular problem instance with fixed dimensions.

In prototyping mode, the problem data may change with each invocation of the generated function. If problem dimensions change, you must set the dimensions of the QCML object and codegen the Python function again. In deployment mode, the problem dimensions are fixed, but problem data is allowed to change.

The valid choice of solvers are:

When these solvers are supplied as arguments to the code generator, it produces code of the appropriate language (Python or Matlab). If it generates Python code, exec is called to create the function bytecode dynamically, allowing you to call the solver.

Use as embedded language

Although QCML's original intent was to be used to parse files with problems specified in QCML, its Python API has been exposed for use in Python. It operates similarly to a safe eval in Python. Problems can be passed as strings to the API and prototyping functions can be used to evaluate the model before asking QCML to generate a solver in a more efficient langauge, such as in C or CUDA.

Example

As an example, consider the Lasso problem,

# this entire line is a comment!
dimensions m n
variable x(n)
parameter A(m,n)
parameter lambda positive

minimize sum(square(A*x - 4)) + lambda*norm(x)

Note that dimenions are named, but abstract (they do not refer to any numbrs). Similarly, variables and parameters are abstract, their shape is denoted only by references to named dimensions. Although matrix variable declarations are possible, QCML's behavior is undefined (and may possibly fail). Matrix variables (along with for loops, concatenation, and slicing) are planned for a future release.

QCML canonicalizes this problem to an SOCP.

Inside Python, the code might look like

from scoop import QCML
if __name__ == '__main__':
    p = QCML()

    p.parse("""
      # this entire line is a comment!
      dimension n
      dimension m
      variable x(n)
      parameter A(m,n)
      parameter lambda positive

      minimize sum(square(A*x - 4)) + lambda*norm(x)
    """)

    p.canonicalize()
    p.set_dims({'m':m, 'n':n})
    p.prettyprint()

Thsis will canonicalize the problem and build an internal problem parse tree inside Python. Once the problem has been canonicalized, the user can decide to either generate a function to prototype problems or generate source code. For instance, the following three lines will create a solver function f and call the solver, with the parameter arguments supplied.

p.codegen("cvxopt")  # this creates a solver in Python calling CVXOPT
f = p.solver
f({'A': A, 'lambda':0.01})

Note that this is not possible with one of the Matlab code generators.

Operators and atoms

QCML provides a set of linear operators and atoms for use with modeling. Since an SOCP only consists of affine functions and second-order cone inequalities, we only provide linear operators and operators for constructing second-order cones. All other atoms are implemented as macros. Whenever the parser encounters an atom, it simply expands its definition.

Operators

The standard linear operators are:

The operators used for constructing second-order cones are:

Atoms

The atoms we provide are:

Roadmap

In no particular order, the future of this project...

Support

This project is supported in large part by an XDATA grant, supported by the Air Force Research Laboratory grant FA8750-12-2-0306.