Setting NonConvex Parameter to 2 takes too much computation power
AnsweredHi,
I have been trying to run the following optimization model. To explain the parameters:
- stocks_returns is a matrix (list of lists)
- desired_var is a simple float value
- The rest (stocks_names, stocks_means, stocks_std_devs, stocks_vars) are simple lists with same length
The function works well with 10 and less parameters (So the length of parameter lists can be at most 10). I can confirm that the results obtained are correct. I call the function several times with different desired_var values with a for-loop, in order to append the different obtained values into another list.
def PortfolioOptimizer(stocks_names, stocks_returns, stocks_means, stocks_std_devs, stocks_vars, desired_var):
print("ENTRY")
# Create the model
m = Model('Asset_Optimizer')
# Set parameters
m.setParam('OutputFlag',False)
#Setting nonConvex parameter to 2
#Algorithm takes too much (never successfully ended) if set to 2
#m.params.NonConvex = 2
n = len(stocks_names)
# Variables
#Weights to be assigned to every stock (between 0-1)
stock_weights = m.addVars(n, lb=0, ub=1 , vtype=GRB.CONTINUOUS, name=stocks_names)
# Set Objective
# Maximize total return
m.setObjective( quicksum(stock_weights[i] * stocks_means[i] for i in range(n)), GRB.MAXIMIZE)
# Constraints
# Sum of stock weights should equal 1
m.addConstr( quicksum(stock_weights[i] for i in range(n)) == 1)
# Portfolio std dev should be smaller than desired standard deviation
m.addConstr(quicksum(stock_weights[i] * stock_weights[i] * stocks_std_devs[i] * stocks_std_devs[i] for i in range(n))
+ quicksum(stock_weights[k] * stock_weights[l] * FindCovariance(stocks_returns[k], stocks_returns[l])
for l in range(n) for k in range(n) if l!=k) <= desired_var)
# Optimize the model
m.optimize()
stock_weights, expected_return = Output(m)
return stock_weights, expected_return
The problem starts after 10 variables. If the length of the lists in parameter go beyond 10, the function obviously needs to create more than 10 variables. When NonConvex parameter is not equal to 2, I would get the error "Constraint Q not PSD (diagonal adjustment of 1.5e+00 would be required). Set NonConvex parameter to 2 to solve model".
So I set the NonConvex parameter to 2. When I call the function with more than 11 variables my CPU usage jumps to 96%, it takes incredibely long to optimize the problem, and it does not get out of the for-loop that I call this function from, as it gets stuck in one of the times this function is called.
Generally if I call this function 100 times in a for-loop, it will get stuck somewhere around 20th-30th repetition. To mention: Each time the function is called, desired_var increases just a bit.
Is this normal because I try to call the function too many times, or is there another issue? Even if this is normal and this will take enormous computation power, is there any workaround without setting the NonConvex parameter to 2?
Thank you, and sorry for the long explanation.
-
Hi Murat,
The Error "Constraint Q not PSD" means that your problem is nonconvex. If you expect your model to be convex in every iteration, then you should definitely double check the coefficients of your quadratic matrix and make sure that this matrix is PSD.
Setting the NonConvex parameter to 2 makes Gurobi solve the problem even if it is a nonconvex one. Nonconvex problems are in general way harder than convex problems. Thus, it is not surprising that solving the nonconvex problem suddenly takes a lot more time than solving all the convex problems in the first 10 iterations.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment