Hessian conditioning problem about acado HOT 17 CLOSED

@ferreau Do you know something more about this bug? Have you ever worked on this one?

from acado.

Milan, if i remember correctly, i talked to borris about this bug. It is related to the fact that the integrator grid is determined suitable for the trajectory, but not necessarily suitable for the derivative (IND demands to use the same grid though). I believe we decided to postpone/ignore this bug, since the example is rather pathetic.

I will dig up my old mail later and I can fill you in on the details.

Cheers,

Janick

Sent from my iPad

On 18 Sep 2013, at 04:10, Milan Vukov [email protected] wrote:

@ferreau Do you know something more about this bug? Have you ever worked on this one?

—
Reply to this email directly or view it on GitHub.

from acado.

I remember it the same way as Janick: we struggled with this issue about two years ago, understood the reason and decided not to follow it up.

@jfrasch: It would indeed be better the compute the condition number of the Hessian matrix more exactly; the check for very large entries is only a quick-and-dirty heuristic that avoids heavy computations. In any case, this check should stay there to prevent passing rubbish to the QP solver.

from acado.

OK, basically the problem is not solved. IMO. We can at least give more intuitive reason what is happening inside the solver? This is in case code is OK, and the "only" problem is related to numerics.

I was kinda afraid of the last paragraphs from Janick's email, but if you think the code is fine, I can be relaxed.

After all, this is a problem that many of us in the group have faced. At least once. In that situations, we were more/less hopeless.

I agree that we should estimate somehow the condition number of the Hessian matrix.

BTW, what was Boris's recommendation for this type of situations?

from acado.

Besides the problem mentioned above, here is another one. The example controller/getting_started fails on OSX Lion (64bit system). However, this works fine on 32-bit (Travis-CI) and 64-bit Linux (my office machine). Here is the output log:

^[[0m[ACADO] ^[[1;33mWarning: Hessian matrix is not symmetric, proceeding with symmetrized Hessian^[[0m
  Code: (RET_NONSYMMETRIC_HESSIAN_MATRIX)
  File: /Users/madwolf/Work/GIT/acado/src/conic_solver/condensing_based_cp_solver.cpp
  Line: 407

^[[0m[ACADO] ^[[1;31mError: Hessian matrix is too ill-conditioned to continue^[[0m
  Code: (RET_ILLFORMED_HESSIAN_MATRIX)
  File: /Users/madwolf/Work/GIT/acado/src/conic_solver/condensing_based_cp_solver.cpp
  Line: 436

^[[0m[ACADO] ^[[1;31mError: Solution of banded CP failed^[[0m
  Code: (RET_BANDED_CP_SOLUTION_FAILED)
  File: /Users/madwolf/Work/GIT/acado/src/conic_solver/condensing_based_cp_solver.cpp
  Line: 232

...

This is quite fishy, and it smells like some bad memory allocation or indexing problem.

from acado.

This is btw very similar to the fail sequence of the example that @jfrasch presented.

from acado.

@jfrasch As far as I can remember, you had a not-so-trivial OCP which you wanted to solve when you spotted this problem. How did you solve this problem? -- if you managed to solve it at all...

from acado.

As far as I can remember I modified the initial guess to avoid this problem…took me a bit though.

On Oct 1, 2013, at 3:50 PM, Milan Vukov [email protected] wrote:

@jfrasch As far as I can remember, you had a not-so-trivial OCP which you wanted to solve when you spotted this problem. How did you solve this problem? -- if you managed to solve it at all...

—
Reply to this email directly or view it on GitHub.

from acado.

Again, it was me introducing this non-symmetry test. I also had the feeling that it is related to bad indexing but could not spot the reason. Hope you have a better intuition (or more luck).

from acado.

@jfrasch Yes, it can be related to bad initial guess.
@ferreau It still smells me like some bad indexing.

BTW, simulation_environment/crane_mpc3_stepped_test example sometimes fails on OS X, same as already mentioned controller/getting_started.

from acado.

On OS X, new STLification branch (see #66) I get funny behavor of the controller/getting_started

madwolf@Milans-MacBook-Pro:controller (stlification *)$ ./getting_started

ACADO Toolkit::SCPmethod -- A Sequential Quadratic Programming Algorithm.
Copyright (C) 2008-2013 by Boris Houska, Hans Joachim Ferreau,
Milan Vukov, Rien Quirynen, KU Leuven.
Developed within the Optimization in Engineering Center (OPTEC)
under supervision of Moritz Diehl. All rights reserved.

ACADO Toolkit is distributed under the terms of the GNU Lesser
General Public License 3 in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.

INFO ((null), /Users/madwolf/Work/GIT/acado-stlification/external_packages/qpOASES-3.0beta/src/QProblemB.cpp:966):  Print level changed
[ACADO] Warning: Hessian matrix is not symmetric, proceeding with symmetrized Hessian
  Code: (RET_NONSYMMETRIC_HESSIAN_MATRIX)
  File: /Users/madwolf/Work/GIT/acado-stlification/src/conic_solver/condensing_based_cp_solver.cpp
  Line: 407

[ACADO] Error: Hessian matrix is too ill-conditioned to continue
  Code: (RET_ILLFORMED_HESSIAN_MATRIX)
  File: /Users/madwolf/Work/GIT/acado-stlification/src/conic_solver/condensing_based_cp_solver.cpp
  Line: 436

madwolf@Milans-MacBook-Pro:controller (stlification *)$ ./getting_started

ACADO Toolkit::SCPmethod -- A Sequential Quadratic Programming Algorithm.
Copyright (C) 2008-2013 by Boris Houska, Hans Joachim Ferreau,
Milan Vukov, Rien Quirynen, KU Leuven.
Developed within the Optimization in Engineering Center (OPTEC)
under supervision of Moritz Diehl. All rights reserved.

ACADO Toolkit is distributed under the terms of the GNU Lesser
General Public License 3 in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.

INFO ((null), /Users/madwolf/Work/GIT/acado-stlification/external_packages/qpOASES-3.0beta/src/QProblemB.cpp:966):  Print level changed
[ACADO] Warning: Hessian matrix is not symmetric, proceeding with symmetrized Hessian
  Code: (RET_NONSYMMETRIC_HESSIAN_MATRIX)
  File: /Users/madwolf/Work/GIT/acado-stlification/src/conic_solver/condensing_based_cp_solver.cpp
  Line: 407

sqp it | qp its |       kkt tol |       obj val |     merit val |      ls param |
     1 |      0 |  8.443811e-11 |  2.233535e-04 |  2.233536e-04 |  1.000000e+00 |
madwolf@Milans-MacBook-Pro:controller (stlification *)$ ./getting_started

ACADO Toolkit::SCPmethod -- A Sequential Quadratic Programming Algorithm.
Copyright (C) 2008-2013 by Boris Houska, Hans Joachim Ferreau,
Milan Vukov, Rien Quirynen, KU Leuven.
Developed within the Optimization in Engineering Center (OPTEC)
under supervision of Moritz Diehl. All rights reserved.

ACADO Toolkit is distributed under the terms of the GNU Lesser
General Public License 3 in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.

INFO ((null), /Users/madwolf/Work/GIT/acado-stlification/external_packages/qpOASES-3.0beta/src/QProblemB.cpp:966):  Print level changed
sqp it | qp its |       kkt tol |       obj val |     merit val |      ls param |
     1 |      0 |  2.198532e-11 |  2.272464e-04 |  2.272464e-04 |  1.000000e+00 |

3 runs of the same program, and very different behavior. This is fishy and I guess that there is a memory management problem, e.g. some copy ctor fails to do the job...

from acado.

Introducing changes in VectorspaceElement and derived classes, cf. 3ee42d2, I get consistent behavior of examples/controller/getting_started and other friend apps on OS X that failed before. It works. I believe there was a mem. management problem which is solved by introducing std::vector as storage container for those classes. In particular, VectorspaceElement::append and copy ctor were fishy.

When I check other examples I will report again...

from acado.

you're doing god's work

from acado.

Milan, great that you spend time on cleaning up the basic structures of ACADO! I used to see strange controller behaviour sometimes but valgrind was unable to spot the problem. Great that this is fixed now!

from acado.

At the moment, I am experimenting with Eigen3, and trying to replace ACADO matrix/vector code with this advanced library. Once this works, we will be able to use SVD-based condition number estimation for Hessians...

Another user spotted some fishy behavior with valgrind in ACADO::LSQTerm::setGrid(ACADO::Grid const&) (lsq_term.ipp:84) in the stable branch.

from acado.

After reinventing hot water for a few days, I deliberately decided to rebase all matrix/vector/linear algebra on Eigen3
library. Now we check condition number of condensed Hessian based on SVD.

Moreover, instead of nagging a user with an error, a warning is given if conditioning is bad.

from acado.

I think there is nothing more to do for now. I will close this and whoever feels something can be added here can open 😄

from acado.