Least-squares example.

[andre-caldas]

I am sorry if I am saying something silly. :-)

I am taking a look at the "Least-squares example", here:
https://osqp.org/docs/examples/least-squares.html

Looking at the python code, I can see that the Ad variable is the problem's $A$ matrix. Maybe we could give the problem matrix a different name, by the way. I will use $B$ for the problem's matrix.

I do not understand, in the code, why P and A were constructed the way they were. As far as I understand, problem translation to "minimize $\frac{1}{2} y^Ty$, where $y = (Bx - b)$. Implies that we want to minimize

$(Bx - b)^T (Bx - b) = x^TB^TBx - x^TB^Tb - b^TBx + b^Tb.$

We can ignore $b^Tb$, because it is constant. And since $x^TA^Tb$ is $1 \times 1$, you can transpose it to conclude that we want to minimize

$x^T(B^TB)x - 2(b^TB)x$.

That is, $q = 2b^TB$ and $P = B^TB$.

I think that instead of solving for $x$, the example is solving for $(x, b)$, so the example code constructs

$B' = \begin{bmatrix}B & -I \\ I & 0\end{bmatrix}$.

But this matrix is called A in the code!?!? Which does not seems correct. Probably it should be P.

Also, the P matrix in the code does not seem really useful, because it takes $(x,b)$ and produces the constant $(0,b)$.

I am getting anything wrong?

[goulart-paul]

If I understand your comment correctly, I think the issue is that what you describe is modelling the first of the problems at the link you gave, i.e. the one where $\frac{1}{2}|Ax - b|^2$ is minimized directly on the interval $0 \le x \le 1$.

That's completely fine to do in the solver, and as you say you just need to expand the quadratic expression into $\frac{1}{2}x^TA^TAx - b^TAx + \frac{1}{2}b^Tb$, and then use the linear and quadratic terms as appropriate when deciding what the solvers P and q arguments should me.

The suggestion though is to model it as the second problem, with variables $(x,y)$ to be solved for jointly. You will then have a pair of two-sided constraints : $b \le Ax - y \le b$ and $0 \le x \le 1$, which must be written together in a single expression to get OSQP's A, l and u arguments. The Pargument to the solver should be something like $[0, 0; 0, I]$ since only the $y$ part needs to be directly penalized.

The reason we suggest to do it that way is that 1) it avoids computing the product $A^TA$ and 2) that (probably dense) product does not end up in the problem data, so the solver's internal matrix factorisations are likely to be more sparse. Generally speaking the second way will solver faster even though the problem has more variables and constraints.

[andre-caldas]

Totally awesome!

Maybe the paragraph that reads "The problem has the following equivalent form [...]" can be reformulated to what you just described me.

Maybe, even a comment on the differences between the two techniques. I would never imagine that having so many more dimensions would be okay. :-)

I (lazily) wonder about this "probably dense" thing. I am working on a geometric constraints system, by the way.

Thank you all for the great work!

[goulart-paul]

Yes, this can make a really big difference for many problems. An extreme example would be one where $A$ is a single row of nonzeros. Then the objective term in the first case is the completely dense matrix $A^TA$. The second case is extremely sparse and hardly any bigger, since $y$ would be a scalar.