为什么我会收到此 DCPError?

计算科学 二次规划 简历
2021-12-12 08:00:28

我正在尝试优化二元投资组合向量,使其大于使用 CVXPY 的基准。

import cvxpy as cp
import numpy as np

# Generate a random non-trivial quadratic program.

n = 10 # number of options

np.random.seed(1)
mu = np.random.randn(n) # expected means
var_covar = np.random.randn(n,n) # variance-covariance matrix
var_covar = var_covar.T.dot(var_covar) # cont'd
bench_cov = np.random.randn(n) # n-length vector of cov(benchmark, returns)

lamd = 0.01 # risk tolerance

# Define and solve the CVXPY problem.

x = cp.Variable(n, boolean=True)

prob = cp.Problem(cp.Maximize(mu.T@x + lamd * (cp.quad_form(x, var_covar) - (2 * bench_cov.T@x))), [cp.sum(x) == 4])

prob.solve()

我使用 CVXPY 版本 1.1.0a0(直接从 github 下载)收到此错误:

DCPError:问题不遵循 DCP 规则。具体来说:

目标不是 DCP,即使每个子表达式都是。

您正在尝试最大化凸函数。

从我读过的内容来看,最大化凸函数非常困难,但我从一篇论文中得到了这个方程,该论文使用 Gurobi 的 BQP 求解器求解了相同的方程。我想我一定是做错了什么,因为我是二次规划和 CVXPY 的新手。

谢谢!

1个回答

此处列出了 cvxpy 的规范凸编程规则

值得注意的是,它指出:

DCP 规则要求问题目标具有以下两种形式之一:

最小化(凸)

最大化(凹)

实际上,如果我们删除 ,您的程序就会quad_form运行,如果我们只留下 ,则不会运行quad_form

prob = cp.Problem(cp.Maximize(cp.quad_form(x, var_covar)), [cp.sum(x) == 4])

所以它不起作用,因为你没有遵守有纪律的凸编程规则。

你怎么能解决这个问题?

  1. 修正数学。也许你犯了一个错误?
  2. cvxpy 的 DCP 实现是从原子构建的,所以你想解决的任何问题都必须在这个原子中表达。如果您认为您的程序应该可以通过 cvxpy 使用的技术来解决,那么也许您可以重新调整您的数学以使用不同的原子集来表达相同的问题。(考虑到问题的简单性,我认为这不太可能。)这也可能是 Gurobi 可以解决问题的原因:它可能可以访问更广泛的原子间操作集。
  3. 不要使用有纪律的凸编程。boolean=True意味着您已经生活在整数编程领域。据我所知,DCP 在这里帮不了你。

编辑

也许您正在阅读的论文中的矩阵是负定的。在这种情况下,您将最大化凹函数,这是允许的。在这种情况下,您只是错误地构建了示例。试试这个:

import cvxpy as cp
import numpy as np

# Generate a random non-trivial quadratic program.

n = 10 # number of options

np.random.seed(1)
mu = np.random.randn(n) # expected means
# var_covar = np.random.randn(n,n) # variance-covariance matrix
# var_covar = var_covar.T.dot(var_covar) # cont'd
bench_cov = np.random.randn(n) # n-length vector of cov(benchmark, returns)

#Make a negative definite matrix
var_covar = -np.array(range(n))
var_covar = np.diag(var_covar)

lamd = 0.01 # risk tolerance

# Define and solve the CVXPY problem.

x = cp.Variable(n)

#Ensure matrix is negative definite so we are maximizing a concave function
assert np.all(np.linalg.eigvals(var_covar) <= 0)

prob = cp.Problem(cp.Maximize(cp.quad_form(x, var_covar)), [cp.sum(x) == 4])

prob.solve()
```