1

我正在使用 cvxpy 来解决一些简单的投资组合优化问题。我无法理解的唯一约束是非零投资组合持有数量的基数约束。我尝试了两种方法，一种 MIP 方法和一种传统的凸方法。

这是一个有效的传统示例的一些虚拟代码。

import numpy as np
import cvxpy as cvx

np.random.seed(12345)
n = 10
k = 6
mu = np.abs(np.random.randn(n, 1))
Sigma = np.random.randn(n, n)
Sigma = Sigma.T.dot(Sigma)
w = cvx.Variable(n)

ret = mu.T*w 
risk = cvx.quad_form(w, Sigma)
objective = cvx.Maximize(ret - risk)

constraints = [cvx.sum_entries(w) == 1, w>= 0, cvx.sum_smallest(w, n-k) >= 0,  cvx.sum_largest(w, k) <=1 ]

prob = cvx.Problem(objective, constraints)  
prob.solve()

print prob.status

output = []
for i in range(len(w.value)):
    output.append(round(w[i].value,2))


print 'Number of non-zero elements : ',sum(1 for i in output if i > 0)

我有想法使用 sum_smallest 和 sum_largest ( cvxpy manual ) 我的想法是将最小的 nk 个条目限制为 0 并让我的目标范围 k 总和为 1，我知道我不能按顺序改变不等式的方向保持凸面，但也许任何人都知道一种在保持简单的同时约束问题的聪明方法。

我的第二个想法是把它变成一个混合整数问题，s.th沿着线

import numpy as np
import cvxpy as cvx

np.random.seed(12345)
n = 10
k = 6
mu = np.abs(np.random.randn(n, 1))
Sigma = np.random.randn(n, n)
Sigma = Sigma.T.dot(Sigma)
w = cvx.Variable(n)

binary = cvx.Bool(n)
integer = cvx.Int(n)

ret = mu.T*w 
risk = cvx.quad_form(w, Sigma)
objective = cvx.Maximize(ret - risk)

constraints = [cvx.sum_entries(w) == 1, w>= 0, cvx.sum_entries(binary) == k ]

prob = cvx.Problem(objective, constraints)  
prob.solve()

print prob.status

output = []
for i in range(len(w.value)):
    output.append(round(w[i].value,2))


print sum(1 for i in output if i > 0)

for i in range(len(w.value)):
    print round(binary[i].value,2)

print output

查看我的二进制向量，它似乎在做正确的事情，但 sum_entries 约束不起作用，查看二进制向量值我注意到 0 不是 0 它非常小，例如 xxe^-20 我认为这会搞砸向上。如果这是正确的方法，任何人都可以给我任何指导吗？如果有帮助，我可以使用标准求解器以及 Mosek。我更喜欢非 MIP 实现，因为我知道这是一个组合问题，对于更大的问题会变得非常慢。最终，我想限制目标持股的确切数量或范围，例如 20-30。

cvxpy 中围绕 MIP 的文档也很短。谢谢

4

2 回答 2

4

有点乱，这个问题。

所以首先：这种基数约束是 NP 难的。这意味着，如果不使用整数编程，就不能使用 cvxpy 来表达它（否则它会暗示 P=NP）！

话虽如此，如果有一个纯代码版本而不试图制定这个约束，那就更好了。我只是假设这是第一个没有sum_smallestandsum_largest约束的代码。

因此，让我们解决 MIP 方法：

  • 您尝试执行此操作的代码毫无意义
    • 您引入了一些二进制变量，但它们与任何其他变量根本没有联系（因此对其总和的约束是无用的）！
    • 您介绍了一些整数变量，但它们根本没有任何用处！

所以这是一个 MIP 方法：

import numpy as np
import cvxpy as cvx

np.random.seed(12345)
n = 10
k = 6
mu = np.abs(np.random.randn(n, 1))
Sigma = np.random.randn(n, n)
Sigma = Sigma.T.dot(Sigma)
w = cvx.Variable(n)

ret = mu.T*w
risk = cvx.quad_form(w, Sigma)
objective = cvx.Maximize(ret - risk)

binary = cvx.Bool(n)  # !!!

constraints = [cvx.sum_entries(w) == 1, w>= 0, w - binary <= 0., cvx.sum_entries(binary) == k] # !!!

prob = cvx.Problem(objective, constraints)
prob.solve(verbose=True)

print(prob.status)

output = []
for i in range(len(w.value)):
    output.append(round(w[i].value,2))


print('Number of non-zero elements : ',sum(1 for i in output if i > 0))

所以我们只是添加了一些二进制变量并将它们连接起来w以指示 if w is nonzero or not。

如果w is nonzero：

  • w由于约束，将 > 0w>= 0
  • binary必须为 1，否则w - binary <= 0.不满足约束

所以它只是介绍这些二进制文件和这个指标约束。

现在cvx.sum_entries(binary) == k做它应该做的。

小心我们在这里使用的暗示方向。在更改 k 上的约束（如 <=）时，它可能是相关的。

请记住，默认的 MIP 求解器很糟糕。我也担心 Mosek 的界面（在 cvxpy 中不是最佳的）不能解决这个问题，但我可能错了。

编辑：您的范围内可以很容易地使用另外两个指标来制定：

  • (k >= a) <= ind_0
  • (k <= b) <= ind_1

并添加一个等于logical_and的约束：

  • ind_0 + ind_1 >= 2
于 2017-07-27T12:30:45.950 回答
0

我有一个类似的问题，我的权重可能是负数并且不需要总和为 1（但仍需要有界），所以我修改了 sascha 的示例以适应使用 CVXpy 绝对值函数放松这些约束。这应该允许一种更通用的方法来使用 MIP 解决基数约束

import numpy as np
import cvxpy as cvx

np.random.seed(12345)
n = 10
k = 6
mu = np.abs(np.random.randn(n, 1))
Sigma = np.random.randn(n, n)
Sigma = Sigma.T.dot(Sigma)
w = cvx.Variable(n)

ret = mu.T*w
risk = cvx.quad_form(w, Sigma)
objective = cvx.Maximize(ret - risk)

binary = cvx.Variable(n,boolean=True)  # !!!
maxabsw=2
constraints = [ w>= -maxabsw,w<=maxabsw, cvx.abs(w)/maxabsw - binary <= 0., cvx.sum(binary) == k] # !!!

prob = cvx.Problem(objective, constraints)
prob.solve(verbose=True)

print(prob.status)

output = []
for i in range(len(w.value)):
    output.append(round(w[i].value,2))


print('Number of non-zero elements : ',sum(1 for i in output if i > 0))
于 2019-10-08T17:50:45.427 回答