Efficient way of modeling a quadratic program

Hi, I'm trying to solve the following quadratic program using Gurobi via the Python API:

\[\begin{align} \min \frac{1}{2\mu}\|\sum_i \lambda_i G_i + \gamma\| - \lambda \cdot \alpha + \gamma \cdot p \\ \text{s.t. } \sum_i \lambda_i &=1 \\ \lambda &\in \mathbb{R}^r_+ \\ \gamma &\in \mathbb{R}^N_+ \end{align}\]

where \(G\) is a \(r \times N\) matrix, \(\alpha \in \mathbb{R}^r\) and \(p \in \mathbb{R}^N\).

This is how I have implemented it:

M = gp.Model("MasterProb_dual")

    # Create variables
    lamb = M.addMVar(shape = r)
    gamma = M.addMVar(shape = N)
	
	#Non negativity constraints 
    M.addConstr(lamb>=0)
    M.addConstr(gamma>=0)
    
    #Sum of lambda equals to 1
    M.addConstr(gp.quicksum(lamb[i] for i in range(r))==1)
	
	#Create \sum_i(lambda_i * G_i) + gamma
    combiG = np.zeros(N)
    for i in range(r):
        combiG += lamb[i]*G[i]
    
    combiGplusgamma = combiG + gamma


	#Definition of the three objective function terms
    obj_term1 = gp.quicksum(combiGplusgamma[j]**2 for j in range(N))/(2*mu)

    obj_term2 = gp.quicksum(lamb[i]*alpha[i] for i in range(r))

    obj_term3 = gp.quicksum(gamma[i]*p[i] for i in range(N))

	#Definition of the complete objective function
    Obj = obj_term1 - obj_term2 + obj_term3


	#Set parameters and solve the model
    M.setObjective(Obj, GRB.MINIMIZE)
    M.params.Method=0
    M.optimize()

And it works fine, I can obtain a solution that makes sense. The problem is that is extremely slow, especially when N grows. I timed the various part of the code and it seems that the slowest part is actually this:

obj_term3 = gp.quicksum(gamma[i]*p[i] for i in range(N))

which to me seems a bit strange, because it is just a scalar product between gamma and p.

For example with r=2 and N = 30011 I have

time to generate first part of objective function: 0.3226962089538574
time to generate second part of objective function: 0.0002880096435546875
time to generate third part of objective function: 1.2187278270721436

Is there something wrong with my implementation or there is no faster way to implement this quadratic problem with this kind of dimension?

Riley Clement

Gurobi Staff

2025年08月11日 00:22

Hi Benedetto,

Slow build speed is expected when you mix matrix variables with term based build statements.

To increase speed either use addVars instead of addMVar, or use matrix/vector multiplication, e.g.

obj_term3 = gamma @ p

Since your code is already built with term-based expressions I would opt for the first of these, but if you are interested in using the Matrix API please see the following resources:

- Riley

benedetto manca

2025年08月11日 11:24

Hi Riley, thank you so much for the answer. At the end i'm using the Matricial version, after changing the constraints declaration, and it's working much faster!

Efficient way of modeling a quadratic program

コメント

お探しのものを見つけられませんでしたか？