nonnegativity constraint?

[ralm...@quantitativebrokers.com]

In my problem, the constraints are all of the form x >= 0, on some or all of the components of the vector x. Of course I can model this with OSQP by setting A = I, l=0, and u=+Inf. But would it be more efficient if nonnegativity constraints could be specified directly? Would that be worth adding in future versions?

Also, I have had some difficulties in getting the polishing step to converge. From my quick read of the paper, it seems that the algorithm does a projection into the polyhedron l <= A x <= u. That projection is much more complicated for general A than it is for the simple case x >= 0. There also, would it be simpler and more efficient to add the case x >= 0 as a specific constraint?

For example (I think this is a standard way that other packages handle this), provide a either logical vector or a list of indices indicating which components of x are required to be nonnegative.

In any case, much appreciation for a very effective solver.

[Goran Banjac]

Hi,

We do not project onto the polyhedron l <= Ax <= u, but only on the box l <= z <= u. Please check the paper again.

I agree that there is an alternative way to deal with bounds on x. However, I don't think that modeling nonnegativity constraints as you described is inefficient. It adds an additional constraint with A=I, but this matrix is very sparse and can be efficiently handled by sparse linear system solvers used by OSQP.

Best,

Goran

[ralm...@quantitativebrokers.com]

Thank you, that makes sense.

[Bartolomeo Stellato]

There are many parsers in python, julia and matlab that convert the nonnegativity constraints into the OSQP canonical form for you. Which language are you using?

I agree with Goran that since we are solving sparse QPs, there is a negligible complexity increase in handling bound constraints.

Have you tried to decrease the tolerance levels eps_abs and eps_rel to make sure the polishing step converges? We could have a look at your problem if you like.

Bartolomeo

[ralm...@quantitativebrokers.com]

Thanks very much for the offer. I am using R, so I just do

O <- solve_osqp( P=A, q=-b,
A=sparseMatrix( i=1:n, j=1:n, x=1 ), l=rep(0,n), u=rep(+Inf,n),
pars=osqp_settings )

I think I had thought from reading the paper, that the algorithm could be simpler if A = I so that z = x. But I guess in practice the difference is negligible.

Let me see if I can find a clear case where I have difficulty with the polishing, and then I can share the matrices.