Many non-convex optimization problems can be solved exactly or approximately via a sequence of convex optimization problems. CVXPY can easily be extended to handle such non-convex problems. The cvxpy/examples/mixed_integer package uses the Alternating Direction Method of Multipliers (ADMM) as a heuristic for mixed integer problems.
The following code performs feature selection on a linear kernel SVM classifier using a cardinality constraint:
In [ ]:
from cvxpy import *
import mixed_integer as mi
import cvxopt
# Construct problem.
gamma = Parameter(nonneg=True)
gamma.value = 0.1
# 'a' is a variable constrained to have at most 6 non-zero entries.
a = SparseVar(n,nonzeros=6)
b = Variable()
slack = [pos(1 - label*(sample.T*a - b)) for (label,sample) in data]
objective = Minimize(norm2(a) + gamma*sum(slack))
p = Problem(objective)
# Extensions can attach new solve methods to the CVXPY Problem class.
p.solve(method="admm")
# Count misclassifications.
error = 0
for label,sample in data:
if not label*(a.value.T*sample - b.value)[0] >= 0:
error += 1
print "%s misclassifications" % error
print a.value
print b.value
N = 50
M = 40
n = 10
data = []
for i in range(N):
data += [(1, cvxopt.normal(n, mean=1.0, std=2.0))]
for i in range(M):
data += [(-1, cvxopt.normal(n, mean=-1.0, std=2.0))]
# Construct problem.
gamma = Parameter(nonneg=True)
gamma.value = 0.1
# 'a' is a variable constrained to have at most 6 non-zero entries.
a = mi.SparseVar(n, nonzeros=6)
b = Variable()
slack = [pos(1 - label*(sample.T*a - b)) for (label, sample) in data]
objective = Minimize(norm(a, 2) + gamma*sum(slack))
p = Problem(objective)
# Extensions can attach new solve methods to the CVXPY Problem class.
p.solve(method="admm")
# Count misclassifications.
errors = 0
for label, sample in data:
if label*(sample.T*a - b).value < 0:
errors += 1
print "%s misclassifications" % errors
print a.value
print b.value