Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Stochastic Optimization in Python

I am trying to combine cvxopt (an optimization solver) and PyMC (a sampler) to solve convex stochastic optimization problems.

For reference, installing both packages with pip is straightforward:

pip install cvxopt
pip install pymc 

Both packages work independently perfectly well. Here is an example of how to solve an LP problem with cvxopt:

# Testing that cvxopt works
from cvxopt import matrix, solvers

# Example from http://cvxopt.org/userguide/coneprog.html#linear-programming

c = matrix([-4., -5.])
G = matrix([[2., 1., -1., 0.], [1., 2., 0., -1.]])
h = matrix([3., 3., 0., 0.])
sol = solvers.lp(c, G, h)
# The solution sol['x'] is correct: (1,1)

However, when I try using it with PyMC (e.g. by putting a distribution on one of the coefficients), PyMC gives an error:

import pymc as pm
import cvxopt

c1 = pm.Normal('c1', mu=-4, tau=.5**-2)

@pm.deterministic
def my_lp_solver(c1=c1):
    c = matrix([c1, -5.])
    G = matrix([[2., 1., -1., 0.], [1., 2., 0., -1.]])
    h = matrix([3., 3., 0., 0.])
    sol = solvers.lp(c, G, h)
    solution = np.array(sol['x'],dtype=float).flatten()
    return solution

m = pm.MCMC(dict(c1=c1, x=x))
m.sample(20000, 10000, 10)

I get the following PyMC error:

<ipython-input-21-5ce2909be733> in x(c1)
     14 @pm.deterministic
     15 def x(c1=c1):
---> 16     c = matrix([c1, -5.])
     17     G = matrix([[2., 1., -1., 0.], [1., 2., 0., -1.]])
     18     h = matrix([3., 3., 0., 0.])

TypeError: invalid type in list

Why? Is there any way to make cvxoptplay nicely with PyMC?

Background:

In case anyone wonders, PyMC allows you to sample from any function of your choice. In this particular case, the function from which we sample is one that maps an LP problem to a solution. We are sampling from this function because our LP problem contains stochastic coefficients, so one cannot just apply an LP solver off-the-shelf.

More specifically in this case, a single PyMC output sample is simply a solution to the LP problem. As parameters of the LP problem vary (according to distributions of your choice), the output samples from PyMC would be different, and the hope is to get a posterior distribution.

The solution above is inspired by this answer, the only difference is that I am hoping to use a true general solver (in this case cvxopt)

like image 788
Amelio Vazquez-Reina Avatar asked Aug 01 '14 09:08

Amelio Vazquez-Reina


1 Answers

The type of c1 generated with pm.Normal is numpy array, you just need to strip it out and convert it to float(c1), then it works finely:

>>> @pm.deterministic
... def my_lp_solver(c1=c1):
...     c = matrix([float(c1), -5.])
...     G = matrix([[2., 1., -1., 0.], [1., 2., 0., -1.]])
...     h = matrix([3., 3., 0., 0.])
...     sol = solvers.lp(c, G, h)
...     solution = np.array(sol['x'],dtype=float).flatten()
...     return solution
... 
     pcost       dcost       gap    pres   dres   k/t
 0: -8.1223e+00 -1.8293e+01  4e+00  0e+00  7e-01  1e+00
 1: -8.8301e+00 -9.4605e+00  2e-01  1e-16  4e-02  3e-02
 2: -9.0229e+00 -9.0297e+00  2e-03  2e-16  5e-04  4e-04
 3: -9.0248e+00 -9.0248e+00  2e-05  3e-16  5e-06  4e-06
 4: -9.0248e+00 -9.0248e+00  2e-07  2e-16  5e-08  4e-08
Optimal solution found.
like image 89
Dalek Avatar answered Sep 23 '22 00:09

Dalek