In [85]:

    

import pylab as pl
import numpy as np
from cvxpy import *


    

In [86]:

    

n = 100
m = 300
np.random.seed(0)
A = np.matrix(np.random.rand(m, n))
b = A * np.ones((n, 1)) / 2.0
c = -np.random.rand(n, 1)


    

In [87]:

    

x = Variable(n)
objective = Minimize( c.T * x)
constraints = [A * x <= b, x >= 0, x <= 1]
p = Problem(objective, constraints)
L = p.solve()


    

In [88]:

    

print 'Lower bound: {}'.format(L)


    

    




Lower bound: -34.4172236278

In [89]:

    

x_rlx = np.matrix(p.variables()[0].value)


    

In [90]:

    

N_t = 100
tvalues = np.linspace(0, 1, 100)
J = np.empty(N_t)
max_constr_violation = np.empty(N_t)
feasible = np.nan * np.zeros(N_t)

for i, t in enumerate(tvalues):
    x_hat = x_rlx > t
    J[i] = c.T * x_hat
    max_constr_violation[i] = np.max(A * x_hat - b)
    if max_constr_violation[i] <= 0:
        feasible[i] = 0


    

In [94]:

    

pl.plot(tvalues, J, label='objective')
pl.plot(tvalues, max_constr_violation,
        label='max constraint violation')
pl.plot(tvalues, feasible -15, lw=2, c='k',
        label='feasible range')
pl.xlabel('t')
pl.legend(frameon=False)


    

    
Out[94]:





<matplotlib.legend.Legend at 0x5083ed0>






    

In [92]:

    

U = np.min(J[np.where(max_constr_violation <= 0)])
print('Upper bound: {}'.format(U))
print('Gap: {}'.format(U - L))


    

    




Upper bound: -33.5772513453
Gap: 0.839972282506