Cvxpy: A portfolio optimization problem cannot be reduced to a QP

[gbanjac]

I am trying to solve a simple portfolio optimization problem using OSQP:

import cvxpy as cp
import numpy as np
import scipy as sp
import scipy.sparse as sparse

# Generate problem data
sp.random.seed(1)
n = 100
k = 10
F = sparse.random(n, k, density=0.7, format='csc')
D = sparse.diags(np.random.rand(n) * np.sqrt(k), format='csc')
mu = np.random.randn(n)
gamma = 1
Sigma = F.dot(F.T) + D

# Define problem
x = cp.Variable(n)
objective = cp.Maximize(mu.T*x - gamma * cp.quad_form(x,Sigma))
constraints = [cp.sum(x) == 1, x >= 0]
prob = cp.Problem(objective, constraints)

# Solve with OSQP
result = prob.solve(solver=cp.OSQP)

and I am getting the following error:

SolverError: Problem could not be reduced to a QP, and no conic solvers exist among candidate solvers (['OSQP']).

I am using CVXPY 1.0.6 on Windows.

[sunilshah]

In cvxpy 1.0.6. in python 3.7 on Mac OS, OSQP works on minimization of negative of the same objective function.

import cvxpy as cp
import numpy as np

# Generate problem data
np.random.seed(1)
n=4
F=np.random.randn(n,n)
mu = np.random.randn(n)
gamma = 1
Sigma = F.T@F


# Define problem
x = cp.Variable(n)
retn=mu.T*x
risk= -gamma*cp.quad_form(x,Sigma)
objMin = cp.Minimize(-retn - risk)
objMax = cp.Maximize(retn + risk)
constraints = [cp.sum(x) == 1, x >= 0]
probMin = cp.Problem(objMin, constraints)
probMax = cp.Problem(objMax,constraints)
# Solve with OSQP
resultMin = probMin.solve(solver=cp.OSQP)
print("OSQP  *** \n  Min x \n ", x.value)
print("OSQP *** \n resultMin \n ", resultMin)
resultMax = probMax.solve(solver=cp.ECOS)
print("ECOS  **** \n  Max x  \n",x.value)
print("ECOS *** \n resultMax \n",resultMax)
try:
     resultMax = probMax.solve(solver=cp.OSQP)
     print("OSQP *** \n  Max x \n",x.value)
     print("OSQP *** \n resultMax \n",resultMax)
except  cp.SolverError: 
    print("OSQP failed")

exec(open("portfolio.py").read())
OSQP *
Min x
[ 1.79515026e-01 1.73645255e-01 -8.65776941e-22 3.63062274e-01
2.83777445e-01]
OSQP
resultMin
0.299508465833006
ECOS *
Max x
[1.79517525e-01 1.73643230e-01 2.59439902e-10 3.63069125e-01
2.83770120e-01]
ECOS *
resultMax
-0.2995084627594934
OSQP failed

[rileyjmurray]

OSQP is unique among the solvers you have tested, because it operates explicitly on quadratic forms (as opposed to equivalent second-order-cone representations). So it looks like cvxpy's default parser for quadratic forms is missing some basic checks.

[rileyjmurray]

I've figured out how to fix it.

The issue was the accepts function in qp2symbolic_qp.py. The current implementation explicitly checks that the objective is Minimize. All I had to do was remove that check, and everything works fine.

Here's your example now:

/home/rmurray/anaconda2/envs/dev36/bin/python /usr/local/pycharm-2017.1.4/helpers/pydev/pydevconsole.py 53453 42167
PyDev console: starting.
import sys; print('Python %s on %s' % (sys.version, sys.platform))
sys.path.extend(['/home/rmurray/Documents/Research/cvxpyfork'])
Python 3.6.5 | packaged by conda-forge | (default, Apr  6 2018, 13:39:56) 
[GCC 4.8.2 20140120 (Red Hat 4.8.2-15)] on linux
import cvxpy as cp
import numpy as np
# Generate problem data
np.random.seed(1)
n=4
F=np.random.randn(n,n)
mu = np.random.randn(n)
gamma = 1
Sigma = F.T@F
# Define problem
x = cp.Variable(n)
retn=mu.T*x
risk= -gamma*cp.quad_form(x,Sigma)
objMin = cp.Minimize(-retn - risk)
objMax = cp.Maximize(retn + risk)
constraints = [cp.sum(x) == 1, x >= 0]
probMin = cp.Problem(objMin, constraints)
probMax = cp.Problem(objMax,constraints)
# Solve with OSQP
resultMin = probMin.solve(solver=cp.OSQP)
print("OSQP  *** \n  Min x \n ", x.value)
print("OSQP *** \n resultMin \n ", resultMin)
resultMax = probMax.solve(solver=cp.ECOS)
print("ECOS  **** \n  Max x  \n",x.value)
print("ECOS *** \n resultMax \n",resultMax)
try:
     resultMax = probMax.solve(solver=cp.OSQP)
     print("OSQP *** \n  Max x \n",x.value)
     print("OSQP *** \n resultMax \n",resultMax)
except  cp.SolverError: 
    print("OSQP failed")

OSQP  *** 
  Min x 
  [0.27132853 0.13112859 0.29669518 0.30084771]
OSQP *** 
 resultMin 
  0.07231131831567134
ECOS  **** 
  Max x  
 [0.27132872 0.13112867 0.29669509 0.30084752]
ECOS *** 
 resultMax 
 -0.07231131811475044
OSQP *** 
  Max x 
 [0.27132853 0.13112859 0.29669518 0.30084771]
OSQP *** 
 resultMax 
 -0.07231131831567134

Specifically, I propose that lines 40 - 42 of qp2symbolic_qp.py be changed from

return ((type(problem.objective) == Minimize
                  and problem.objective.expr.is_qpwa())
                 or problem.objective.expr.is_affine())
                 ...

to

return (problem.objective.expr.is_qpwa()
            ....

I've run unittests on 2.7, 3.5, 3.6, and the proposed change does not break anything.

[sunilshah]

Yes, the fix works correctly on my system with python 3.7 as well.

Thanks.

[gbanjac]

Great, thanks for looking into this! Would you mind making a PR with this fix?

[bstellato]

@rileyjmurray can you still detect if there is a non convex problem with that deletion? I mean cases where the cost is quadratic of piecewise affine but not positive semidefinite.

[rileyjmurray]

@bstellato the quad_form atom will reject any matrix that is not PSD or NSD. The only way it might fail would be if the user tried to minimize a concave quadratic, or maximize a convex quadratic. I suspect that basic DCP checking will catch this independent of my changes, but I will check just to be sure.

[SteveDiamond]

@rileyjmurray we can remove the requirement that the problem be minimize. All the reductions in fact assume that it's been converted to a minimization problem. Converting minimize to maximize is one of the first steps of canonicalization. DCP checking is separate and indeed will prevent any non convex problems from being canonicalized.

[rileyjmurray]

I've made the change on my fork of cvxpy; it'll be included in my next pull request.