Ratio of number of equations and variables that is not solvable by osqp

[yeasmin62]

Hi,
I know that system if equations can be determined (equal number of equations and variables), underdetermined ( Number of Equations is less than number of Variables) and overdetermined (number of Equations is greater than variables).

1. What is the maximum number of equations and variables solvable by the osqp?
2. Is there any ratio of Equations and variables in underdetermined and overdetermined systems to get the correct result in osqp? Lets say, if we have 100 Equations and 50 variables, we can get correct results but with 100 equations and 10 variables, its not possible to get correct result.

Thank you very much in advance

[imciner2]

Hi @yeasmin62, I think you are confusing OSQP with a linear equation solver. OSQP solves a quadratic optimization problem, where we minimize a quadratic function over a set of linear constraints. In this case, we don't really have "overdetermined" or "underdetermined" systems, but instead we focus on feasibility (a solution exists that satisfies all the constraints) and infeasibility (there is no solution that satisfies all the constraints).

OSQP can be used to solve the least squares problems, where you try to find the best $x$ that makes the quantity $Ax - b$ closest to 0, or you could even tell OSQP that its constraints are $Ax = b$ directly and ask it to find $x$. In either case, though, it doesn't really make sense to talk about ratios of equations to variables as determining if the problem can be solved.

[yeasmin62]

Hi, thank you very much for your answer. However, is there any limitation of the number of constraints or number variables?
Let say, when I work with large number of variables (e.g., 24000 constraints containing 250000 variables), I get memory error.

[imciner2]

OSQP's algorithm (ADMM) has no inherint limit to the size of the problem, but the computer you use to run OSQP will limit the size and a larger problem will take longer to run (both because the operations such as vector operations and the linear system solve take longer, and also because a larger problem is more likely to be ill-conditioned and require more iterations for convergence).

We use sparse matrices and dense vectors to represent the data, so any limits are going to be very problem-dependent and we can't really give an answer for what the limitation would be. If you have a very sparse constraint matrix (such as only upper/lower bounds) it won't use as much space as a dense one so you could have a lot more variables, but if you have a dense constraint matrix then you would be able to have fewer variables when using the same amount of memory.