Possible bug in qpOASES when using equality constraints

[gabrielenava]

It seems there is a bug inside the qpOASES algorithm when performing a constrained optimization with equality constraints. In particular, consider the following optimization problem:

 min |u|^2

   s.t. Au = 0

where u is a [29 * 1] vector and A is a [6 * 29] matrix with rank 6. In theory, this problem is well posed and the solution is u = 0.

However, for some valid constraint matrices A qpOASES cannot find a solution, and returns the following error:

ERROR:  Division by zero
->ERROR:  Abnormal termination due to TQ factorisation
  ->ERROR:  Determination of step direction failed
    ->ERROR:  Abnormal termination due to TQ factorisation
      ->ERROR:  Initialisation failed! QP could not be solved!

Attached to this script there is a matlab code with an example. The constraint matrix is stored in a .mat file (attached to the issue, too) and is of the form:

A = [   0         0         0    1.0000   -0.0000    0.0000         0         0         0     0         0         0         0         0         0         0         0   -0.0000     1.0000    0.0003   -0.0000    0.0000    1.0000         0         0         0         0     0    0
        0         0         0   -0.0000    1.0000    0.0000         0         0         0     0         0         0         0         0         0         0         0   -1.0000    -0.0000    0.0001   -1.0000    1.0000   -0.0000         0         0         0         0     0    0
        0         0         0    0.0000    0.0000    1.0000         0         0         0     0         0         0         0         0         0         0         0    0.0001    -0.0003    1.0000    0.0001   -0.0001   -0.0000         0         0         0         0     0    0
        0         0         0    1.0000   -0.0000    0.0000         0         0         0     0         0         0         0         0         0         0         0         0          0         0         0         0         0         0         0         0         0     0    0
        0         0         0   -0.0000    1.0000    0.0000         0         0         0     0         0         0         0         0         0         0         0         0          0         0         0         0         0         0         0         0         0     0    0
        0         0         0    0.0000    0.0000    1.0000         0         0         0     0         0         0         0         0         0         0         0         0          0         0         0         0         0         0         0         0         0     0    0 ]

The matrix is full rank, as it is possible to see by looking at the singular values after SVD decomposition:

    sigma = [ 2.0743
              1.8478
              1.6180
              0.8350
              0.7654
              0.6180 ]

Also, relaxing the problem with inequality constraints of the form:

min |u|^2

s.t. -eps < Au < eps
       eps >0

did not solve the issue. As an additional information, note that in case the problem is unfeasible the error from qpOASES is different.

testQPOASES.zip

[gabrielenava]

cc @traversaro @S-Dafarra

[traversaro]

The first step I would consider is to update the qpOASES version, as we are currently an outdated fork : #1 .

[traversaro]

It is worth to check the commit history of qpOASES:
https://projects.coin-or.org/qpOASES/log/trunk
the open issues:
https://projects.coin-or.org/qpOASES/report/1
and also the closed issues:
https://projects.coin-or.org/qpOASES/report/3 .

[traversaro]

It is also worth checking directly the code:

qpOASES/src/QProblem.cpp

Line 4592 in 6fd1bfa

return THROWERROR( RET_STEPDIRECTION_FAILED_TQ );

.

[S-Dafarra]

We took a look at the code, and apparently that error is thrown when at least one element of the anti diagonal of a so-called matrix TT is in modulus less than a tolerance. We dig a big further to understand what TT is, and apparently it is macro with which they access a vector called T (apparently it is the row wise vectorisation of TT). We weren't able to discern how T was filled.

[traversaro]

To update qpOASES, you just need to get the latest version from https://projects.coin-or.org/qpOASES/wiki/QpoasesDownload and extract it in the repo, with the exception of the CMake files.

As you may notice by this comparison:
6fa1e4f...master
the only thing that this fork changed are the CMake configuration files.

[DanielePucci]

Yes, let's try to update qpOASES anyways.

Just as a curiosity: did you try to approximate the matrix A with either ceiling or floor?

[DanielePucci]

CC @gabrielenava

[traversaro]

Just as a curiosity: did you try to approximate the matrix A with either ceiling or floor?

From the last part of the original issue, it seems that the answer to this question is yes, and it not solved the problem.

[traversaro]

This problem could be related : https://projects.coin-or.org/qpOASES/ticket/69 .

[gabrielenava]

I'm trying to update qpOASES. I downloaded the latest version from here. I modified/added the configuration files according to 6fa1e4f...master. I did only one modification with respect to our branch. In the CMakeLists.txt, I selected the package version 3.2.0. I'll test the new qpOASES now.

[gabrielenava]

Related PR: #5

[gabrielenava]

I completed the update. On matlab, this is the mex file I'm reading:

in the install folder, the mex files have the number 3.2 instead of 3.1 as before so I think qpOASES has been correctly updated.

However, the bug is still there. It is sufficient to run the test above:

We can anyway update, but this didn't solve the issue.

[traversaro]

We can anyway update, but this didn't solve the issue.

Yes, let's proceed with the update anyway.

[S-Dafarra]

cc @GiulioRomualdi

[traversaro]

It we understood that this is a problem in qpOASES, the first step would be to open a ticket in qpOASES bug tracker: https://projects.coin-or.org/qpOASES/report .

[DanielePucci]

@gabrielenava @S-Dafarra
Did we open a tick in qpOASES bug tracker?

[gabrielenava]

Not yet. I can take care of this the next week.

[gabrielenava]

Error reported: see https://projects.coin-or.org/qpOASES/ticket/85

[gabrielenava]

Error reported: see https://projects.coin-or.org/qpOASES/ticket/85

Six months passed, and it doesn't seem to me they replied to the issue I opened.

[traversaro]

Indeed, if the upstream does not solve the problem, we are not able to solve it either and there are better alternatives (OSQP?) we should simply stop using qpOASES and start using only OSQP.

cc @diegoferigo @kourosh @gabrielenava @S-Dafarra @GiulioRomualdi

[diegoferigo]

Adding the support of OSQP into wb-toolbox is quite easy, and it can be done in more or less one day even from someone not familiar with the toolbox.

The block specifications (inputs / outputs) and the mask can be taken 1:1 from QpOases. Then, substituting QpOasis methods with those of OSQP should do the job.

[GiulioRomualdi]

Sometimes osqp generates a solution that is outside the boundary. I've noticed this behaviour when the problem is ill conditioned. @MiladShafiee

[traversaro]

Sometimes osqp generates a solution that is outside the boundary. I've noticed this behaviour when the problem is ill conditioned. @MiladShafiee

Thanks a lot, this seems to be a bug in OSQP. If we have the specific instance, we can report the problem to OSQP developers.
Just to understand, in those cases qpOASES instead works fine?

[GiulioRomualdi]

Yes, in this case qpOASES found the solution without problem

[traversaro]

Do we have instances of the optimization problems, so that we can submit them to OSQP?
In this way, if they are able to fix the problem, we can have a single QP solver that works in all cases, instead of two QP solver that on some instances create problems. : )

[MiladShafiee]

As I remember during debugging the code, we reached to certain point that we assured that code is correct but osqp gave us some solutions that weren’t inside the feasible area and we were looking for some bugs and when we changed the solver the problem solved! We should try it again with osqp to see now it reproduces that bug or no! Because we changed it a lot after that point!

[traversaro]

@diegoferigo @GiulioRomualdi @MiladShafiee for future discussions of problems or features of OSQP w.r.t. to all our repo, feel free to move the discussion to robotology/robotology-superbuild#239, that is more related to this issue, where this issue is dealing with the specific problem in qpOASES described in https://projects.coin-or.org/qpOASES/ticket/85 .

[traversaro]

Error reported: see https://projects.coin-or.org/qpOASES/ticket/85

The qpOASES issue tracker has been moved to GitHub, and now the issue is tracked in coin-or/qpOASES#85 .

[traversaro]

It is possible that this problem can be solved by simply changing the option with which we call qpOASES, see coin-or/qpOASES#85 and robotology/wb-toolbox#202 . However, as the issue is tracked in coin-or/qpOASES#85 I think we can close the issue.