Почему я получаю эту ошибку DCPError?

Я пытаюсь оптимизировать вектор двоичного портфеля, чтобы он был лучше, чем эталон, используя 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, даже если каждое подвыражение.

Вы пытаетесь максимизировать выпуклую функцию.

Из того, что я читал, очень сложно максимизировать выпуклую функцию, но я получил это уравнение из статьи. Я полагаю, что, должно быть, делаю что-то не так, поскольку я новичок в квадратичном программировании и CVXPY.

Спасибо!


python cvxpy quadratic-programming
person George    schedule 28.10.2019    source источник
comment
Максимизация выпуклой функции - это невыпуклая проблема. Сложно решить невыпуклые задачи в CVX PY.   -  person Rodrigo de Azevedo    schedule 29.10.2019
comment
@RodrigodeAzevedo Знаете ли вы другую библиотеку, которую я мог бы посмотреть? А может способ сделать эту задачу выпуклой?   -  person George    schedule 29.10.2019
comment
На SO нельзя задавать математические вопросы. Попробуйте scicomp.stackexchange.com (с тегом CVXPY).   -  person Rodrigo de Azevedo    schedule 29.10.2019
comment
@RodrigodeAzevedo Я только что выложил это на SciComp   -  person George    schedule 29.10.2019
comment
X-posted: scicomp.stackexchange.com/q/33671/20417   -  person Rodrigo de Azevedo    schedule 29.10.2019
comment
Невыпуклые QP сложны и требуют глобального решателя (например, Baron, Couenne, Antigone, Cplex). Также есть интересная переформулировка в задачу MIP (в основном формирование условий KKT).   -  person Erwin Kalvelagen    schedule 31.10.2019
comment
Однако мы можем использовать переменные x в двоичном формате. Это дает более простую переформулировку MIP.   -  person Erwin Kalvelagen    schedule 31.10.2019

Ответы (1)


arrow_upward
4
arrow_downward

Проблема с вашей моделью в том, что max x'Qx невыпуклый. Поскольку у нас есть двоичные переменные x, мы можем использовать хитрость.

Определять

y(i,j) = x(i)*x(j)

как дополнительная двоичная переменная. Тогда мы можем написать

sum((i,j), x(i)*Q(i,j)*x(j))

as

sum((i,j), y(i,j)*Q(i,j))

Двоичное умножение y(i,j) = x(i)*x(j) можно линеаризовать как:

 y(i,j) <= x(i)
 y(i,j) <= x(j)
 y(i,j) >= x(i)+x(j)-1

С этой переформулировкой мы получаем полностью линейную модель. Это MIP, поскольку у нас есть двоичные переменные.

Мы можем сделать это в CVXPY как:

import numpy as np
import cvxpy as cp

# 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

e = np.ones((1,n))

x = cp.Variable((n,1), "x", boolean=True)
y = cp.Variable((n,n), "y", boolean=True)


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

prob.solve(solver=cp.ECOS_BB)
print("status",prob.status)
print("obj",prob.value)
print("x",x.value)

Это дает результат:

status optimal
obj 4.765120794509871
x [[1.00000000e+00]
 [3.52931931e-10]
 [3.80644178e-10]
 [2.53300872e-10]
 [9.99999999e-01]
 [1.79871537e-10]
 [1.00000000e+00]
 [3.46298454e-10]
 [9.99999999e-01]
 [1.00172269e-09]]

Примечания:

  • Рекомендуется использовать более совершенный решатель MIP, чем ECOS_BB. Для этой модели он дает правильные результаты, но является своего рода игрушечным решателем и, как известно, создает проблемы на более сложных наборах данных.
  • Я не понимаю экономику модели. Здесь мы максимально увеличиваем риск. Возможно, будет неразумно основывать свои инвестиционные решения на результатах этой модели.
  • Обратите внимание, что некоторые высокопроизводительные решатели (например, Cplex и Gurobi) выполняют эту переформулировку автоматически. Однако CVXPY не позволит вам передать невыпуклую модель решателю.
person Erwin Kalvelagen    schedule 31.10.2019
comment
Я ценю детали этого ответа - да, с тех пор, как я опубликовал это, я понял, что мой квадратичный член невыпуклый. В итоге я использовал один из глобальных невыпуклых решателей, о которых вы упомянули в своем комментарии. Это действительно полезный трюк для превращения проблем QP в линейные, спасибо, что предупредили меня об этом :) - Наконец, экономика модели немного сложнее ... Я пытаюсь создать портфель, чтобы побить эталонный тест. E [эталонный показатель] выше любого E [портфеля], поэтому вместо минимизации риска, как вы могли бы сделать, если бы E [эталонный показатель] был ниже E [портфель], мне нужно его максимизировать. - person George; 31.10.2019
comment
Если вам интересно, я с удовольствием отправлю вам исследование, за которым следую. - person George; 31.10.2019
comment
Да, мне очень интересна основная статья. - person Erwin Kalvelagen; 31.10.2019
comment
@ErwinKalvelagen Это похоже на проблему, которую я вижу? stackoverflow.com/questions/68136486/ - person geofflittle; 26.06.2021