Kardinalitätseinschränkung in der Portfoliooptimierung

Question

Ich verwende cvxpy, um an einem einfachen Problem der Portfoliooptimierung zu arbeiten. Die einzige Einschränkung, die ich nicht verstehen kann, ist die Kardinalitätseinschränkung für die Anzahl der Portfoliopositionen, die nicht Null sind. Ich habe zwei Ansätze ausprobiert, einen MIP-Ansatz und einen traditionellen konvexen Ansatz.

Hier ist ein Dummy-Code für ein funktionierendes traditionelles Beispiel.

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) 

hatte ich die Idee zu verwenden, sum_smallest und sum_largest (cvxpy manual) mein Gedanke war es, die kleinsten nk Einträge auf 0 bis Constraint und mein Zielbereich k Summe lassen bis zu einem, ich weiß, ich kann nicht ändern Richtung der Ungleichung, um konvex zu bleiben, aber vielleicht weiß jemand über eine clevere Art, das Problem zu beschränken, während es immer noch einfach bleibt.

Mein zweiter Gedanke war dies ein gemischt-ganzzahlige Problem zu machen, s.th entlang der Linien von

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 

an meinem binären Vektor suchen scheint es, das Richtige zu tun, sondern die sum_entries Einschränkung nicht arbeite, schaue in die binären Vektorwerte Ich habe festgestellt, dass 0 nicht 0 ist, es ist sehr klein zB xxe^-20 Ich nehme an, dies wird Dinge durcheinander bringen. Kann mir jemand eine Anleitung geben, wenn das der richtige Weg ist? Ich kann die Standard-Löser verwenden, genauso wie Mosek, wenn das hilft. Ich würde lieber eine Nicht-MIP-Implementierung haben, da ich weiß, dass dies ein kombinatorisches Problem ist und bei größeren Problemen sehr langsam werden wird. Letztendlich möchte ich entweder die genaue Anzahl der Zielbestände einschränken oder einen Bereich, z. 20-30.

Auch die Dokumentation in cvxpy rund um MIP ist sehr kurz. Danke

Answer 1

Ein bisschen chaotisch, diese Frage.

Also zuerst: Diese Art der Kardinalitätsbeschränkung ist NP-schwer. Das heißt, Sie können es nicht mit cvxpy ausdrücken, ohne Integer-Programmierung zu verwenden (sonst würde es P = NP implizieren)!

Das sagte, es wäre schöner gewesen, wenn es eine reine Version des Codes geben würde, ohne zu versuchen, diese Einschränkung zu formulieren. Ich nehme an, es ist der erste Code ohne die sum_smallest und sum_largest Einschränkungen.

wir also den MIP-Ansatz angehen:

• Ihr Code versucht, dies zu tun, macht keinen Sinn, auf allen
  • Sie einige binary-Vars vorstellen, aber sie haben keine Verbindung zu einem anderen Variablen überhaupt (so ist eine Beschränkung auf seine Summe nutzlos)!
  • Sie stellen einige Ganzzahl-Vars vor, aber sie haben überhaupt keine Verwendung!

So, hier ist ein MIP-Ansatz:

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)) 

So einfach haben wir einige binary-Variablen und verbunden sie w wenn w is nonzero or not anzuzeigen.

Wenn w is nonzero:

• w> 0 wegen Einschränkung sein w>= 0
• binary Bedürfnisse zu 1, oder auch Einschränkung w - binary <= 0. nicht

So erfüllt es die Einführung gerade diese Binärdateien und diese eine Indikatorbeschränkung.

Jetzt macht das cvx.sum_entries(binary) == k was es tun soll.

Seien Sie vorsichtig mit der Implikationsrichtung, die wir hier verwendet haben. Es könnte relevant sein, wenn Sie die Einschränkung für k suchen (wie < =).

Denken Sie daran, dass der Standard-MIP-Löser schrecklich ist. Ich befürchte auch, dass Moseks Interface (suboptimal innerhalb von cvxpy) dies nicht lösen wird, aber ich könnte falsch liegen.

Edit: Ihr in-Bereich leicht formuliert werden kann, zwei weitere Indikatoren für:

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

und das Hinzufügen einer Beschränkung, die eine logical_and entspricht:

• ind_0 + ind_1> = 2