You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
About the new exact Hessian feature, this could be a breaking change:
Consider changing the default value of hessian in NonLinMPC and MovingHorizonEstimator to true (or perhaps hessian=oracle, since it is only supported if oracle==true).
If I compare the benchmarks of our arXiv paper with Ipopt.jl v1.13.0 (that include a performance improvement for modifying the constant vector in linear constraints when exact Hessian is activated) and ModelPredictiveControl.jl v1.13.2, on the inverted pendulum:
The fastest approach seems to be SingleShooting() and hessian=true. But sparse Hessian computation performances is highly problem-dependent. Actually, the Hessian of the economic MPC with multiple shooting seems to be weirdly more expensive.
In conclusion, I'm not totally convinced that changing the default of these two keyword arguments is worth it.
I don't have a strong opinion either way. The pendulum example may be too small to serve as the only deciding example, it's quite fast in either case, what happens to a much larger model? If MS+hessian makes a larger model take infinitely long to compile or otherwise, it may not be the best default.
That's also my feeling but I did not hit cases in which the poor initial guesses led to divergence. I think MATLAB default to interior point for nlmpc in the past, but now it's an SQP algorithm by default.
Wait, how can the hessian have an arrow shape with multiple shooting? I tend to get block-diagonal hessians in this case. The arrow shape indicates that there is some variable that interacts with all other variables, is this a minimum-time problem or something?
The hessian has an arrow shape? IIRC @gdalle and friends have some special trick with mixed-mode AD that can handle such cases?
Mixed mode is only for Jacobians, for which you can compute rows with reverse mode or columns with forward mode. By symmetry, computing a row of the Hessian is the same as computing a column.
Here are a few things that can help:
trying out different coloring orders (or trying them all)
switching to a substitution-based decompression
postprocessing won't help here since the diagonal seems full
that is, I did not included RandomOrder in the tuple. I was scared of including this by default. In my mind it could lead to weird non-deterministic performance issues. I'm also trying to avoid new dependencies in the package if they are not strictly necessary. Two questions on RandomOrder:
If I include it in the tuple above, id there a risk that someone has e.g. a low amount of color one day, and a high amount of color the day after. I'm not sure I understand how the pseudo-random generator is used in this algorithm.
What's the pros and cons of using ranges from Random instead of StableRNGs (to avoid new dependencies) ?
Wait, how can the hessian have an arrow shape with multiple shooting? I tend to get block-diagonal hessians in this case. The arrow shape indicates that there is some variable that interacts with all other variables, is this a minimum-time problem or something?
The objective function is the sum of the tracking term, the move suppression term and the energy consumption term, as described here. There is no slacking variable $\epsilon$ since Cwt=Inf. The energy consumption term is the product of a state with the manipulated input. I'm still not sure why it gives an arrow shape right now...
edit: So the arrow shape is related to the (non-quadratic) energy consumption term, since if I do Ewt=0, I get:
edit2: it may be related to the fact that the decision variables are the manipulated input increments over the control horizon and the states over the prediction horizon.
Note that postprocessing doesn't do anything for unidirectional Jacobians. Like the decompression by substitution, it only applies to Hessians or bidirectional Jacobians.
The API of RandomOrder is a bit clumsy: first you give the generator, then you give the seed to reset it with before each coloring. If you don't give that seed, you will see different numbers of colors at every run of the preparation. So as long as you provide that seed, results are reproducible... up to Julia version. Indeed, Random (the stdlib) doesn't guarantee stability of the exact stream of random numbers produced from one Julia version to the next. Hence my recommendation to use StableRNGs instead for full reproducibility.
As a side note, the zero inside StableRNG(0) doesn't matter because the generator will be re-seeded anyway.
If you're curious you can look at the code, it is dead simple: https://github.com/gdalle/SparseMatrixColorings.jl/blob/main/src/order.jl#L57-L64
Note that postprocessing doesn't do anything for unidirectional Jacobians. Like the decompression by substitution, it only applies to Hessians or bidirectional Jacobians.
Okay, I just used the same default sparse backend for the Jacbians and for the Hessians to avoid code duplication (i.e. don't repeat yourself). I understand that these options will be just ignored for the Jacobians, which is okay with me.
The API of RandomOrder is a bit clumsy: first you give the generator, then you give the seed to reset it with before each coloring. If you don't give that seed, you will see different numbers of colors at every run of the preparation. So as long as you provide that seed, results are reproducible... up to Julia version. Indeed, Random (the stdlib) doesn't guarantee stability of the exact stream of random numbers produced from one Julia version to the next. Hence my recommendation to use StableRNGs instead for full reproducibility.
As a side note, the zero inside StableRNG(0) doesn't matter because the generator will be re-seeded anyway.
If you're curious you can look at the code, it is dead simple: https://github.com/gdalle/SparseMatrixColorings.jl/blob/main/src/order.jl#L57-L64
Alright. 190 lines of code for StableRNGs: it seems very lightweight. I will add RandomOrder in the tuple and the StableRNGs dependency.
@franckgaga Don't forget to use decompression=:substitution for the Hessian :)
It works better in practice (less colors) than the default algorithm (star coloring).
It is more expensive but for optimization solvers where we reuse it multiple times, I highly recommend it.
Wait, how can the hessian have an arrow shape with multiple shooting? I tend to get block-diagonal hessians in this case. The arrow shape indicates that there is some variable that interacts with all other variables, is this a minimum-time problem or something?
So by working on orthogonal collocation, I understood that it may be caused by something else. Right now for multiple shooting, the decision vector is a concatenation of the manipulated input vector $\mathbf{\Delta U}$ and the state vector $\mathbf{\hat{X}_0}$. This is presumably less efficient than having both "interlaced", i.e. (for the sparsity, both for differentiation but inside Ipopt as well, it seems):
TBH, I drastically prefer my way of working in terms of code readability. I'm annoyed that most efficient solution is the "messiest". Moving to interlaced decision vector will be particularly messy for the construction of the prediction matrices for LinModel. edit: this is also probably why the OSQP.jl documentation rely on "concatenated" decision vector, that is, for clarity.
The refactor job for migrating to "interlaced" decision vector would be substantial. Not to mention that the equations in the documentation of the internals would be way longer and messier, since the prediction matrices would be no longer "perfectly separated" block matrices.
I'm really not sure if I should put time on this refactor. If the answer is yes, it clearly needs to be done before implementing a new transcription method. It seems that the SparseMatrixColoring package is able to efficiently handle arrow-shaped Hessians and Jacobians (with adequate ordering algorithms). I'm also aware that many sparse linear solvers do permutation before solving the system. I'm not sure if the default MUMPS of Ipopt does that, although.
Obviously the only way to know would be to implement it and benchmark it. But I expect that I would not see much difference on the small pendulum case study.
I wouldn't bother with such a refactor, I also use the same layout as you and haven't noticed any benefits of the other layout. There may be marginal benefits that play a role when everything else is optimized to the max, but unless you cantrol the solver completely it's hard to reach there
Now that most relevant nonlinear solvers support the VectorNonlinearOracle (e.g. Ipopt.jl, MadNLP.jl, KNITRO.jl and UnoSolver.jl), I will remove the oracle keyword argument (that is: always use oracles) and also the legacy code that uses the splatting syntax. It is just too complex, too slow, and no longer tested in the suite. It's also annoying to always set oracle=true in all cases. I personally forget it frequently.
It means that the next release will be a breaking change. If there are people that use NLopt.jl for example, they will need to stick to an older version of the package.
While I'm at it, I will also add the slack $\epsilon$ in the custom economic function signature, which is another breaking change but it might be useful for non-quadratic weighting.
@franckgaga Do you have degenerate problems or MPEC problems to solve?
It may be relevant that I do the JuMP interface for MadNCL.jl if it is the case.
I don't think so. To be honest, I'm not sure I understand what are degenerate problems or MPEC in the context of nonlinear programming for model predictive control. By reading quickly about NCL, I understand it applies to problems with large amounts of constraints? If so, I don't think it's relevant for typical model predictive control.
* failure of LICQ at a solution (gradient of the constraints of linearly dependent at the solution)
* absence of strict complementarity (both constraint and multipliers are 0)
If you have more constraints than variables, LICQ doesn't hold but it can happen for other reasons and you don't need a lot of constraints.
Okay I see that it was shown to be a bit more robust than Ipopt.jl and MadNLP.jl on some problem instances. In that case, yes a JuMP interface might be interesting for MPC.jl.
Activity
franckgaga commentedon Nov 10, 2025
About the new exact Hessian feature, this could be a breaking change:
hessianinNonLinMPCandMovingHorizonEstimatortotrue(or perhapshessian=oracle, since it is only supported iforacle==true).franckgaga commentedon Nov 12, 2025
If I compare the benchmarks of our arXiv paper with
Ipopt.jl v1.13.0(that include a performance improvement for modifying the constant vector in linear constraints when exact Hessian is activated) andModelPredictiveControl.jl v1.13.2, on the inverted pendulum:The fastest approach seems to be
SingleShooting()andhessian=true. But sparse Hessian computation performances is highly problem-dependent. Actually, the Hessian of the economic MPC with multiple shooting seems to be weirdly more expensive.In conclusion, I'm not totally convinced that changing the default of these two keyword arguments is worth it.
What's your opinion @baggepinnen ?
baggepinnen commentedon Nov 14, 2025
I don't have a strong opinion either way. The pendulum example may be too small to serve as the only deciding example, it's quite fast in either case, what happens to a much larger model? If MS+hessian makes a larger model take infinitely long to compile or otherwise, it may not be the best default.
franckgaga commentedon Nov 14, 2025
Yep, I'll verify if it's really the Hessian that take this much time. ⌛️
franckgaga commentedon Nov 14, 2025
optimdefault toModel(() -> UnoSolver.Optimizer(preset="filtersqp"));?baggepinnen commentedon Nov 14, 2025
I expect filtersqp to be faster in most cases, but I also expect it to be less robust when the initial guess for the first optimization is poor
franckgaga commentedon Nov 14, 2025
That's also my feeling but I did not hit cases in which the poor initial guesses led to divergence. I think MATLAB default to interior point for
nlmpcin the past, but now it's an SQP algorithm by default.franckgaga commentedon Nov 15, 2025
Yep, all the the time is spent in the sparse Hessian computation of the objective function.
The number of colors is way higher than all the other cases:
I will experiment with other coloring orders...
baggepinnen commentedon Nov 15, 2025
The hessian has an arrow shape? IIRC @gdalle and friends have some special trick with mixed-mode AD that can handle such cases?
baggepinnen commentedon Nov 15, 2025
Wait, how can the hessian have an arrow shape with multiple shooting? I tend to get block-diagonal hessians in this case. The arrow shape indicates that there is some variable that interacts with all other variables, is this a minimum-time problem or something?
gdalle commentedon Nov 15, 2025
Mixed mode is only for Jacobians, for which you can compute rows with reverse mode or columns with forward mode. By symmetry, computing a row of the Hessian is the same as computing a column.
Here are a few things that can help:
In order words, I'd recommend going from
GreedyColoringAlgorithm()to
to see if it does anything.
franckgaga commentedon Nov 15, 2025
Oh wow, the
RandomOrder(StableRNG(0), 0)does the trick: 4 colors! Right now my default sparse Jacobian (edit: and Hessian) backend is:that is, I did not included
RandomOrderin the tuple. I was scared of including this by default. In my mind it could lead to weird non-deterministic performance issues. I'm also trying to avoid new dependencies in the package if they are not strictly necessary. Two questions onRandomOrder:Randominstead ofStableRNGs(to avoid new dependencies) ?franckgaga commentedon Nov 15, 2025
The objective function is the sum of the tracking term, the move suppression term and the energy consumption term, as described here. There is no slacking variable$\epsilon$ since
Cwt=Inf. The energy consumption term is the product of a state with the manipulated input. I'm still not sure why it gives an arrow shape right now...edit: So the arrow shape is related to the (non-quadratic) energy consumption term, since if I do
Ewt=0, I get:edit2: it may be related to the fact that the decision variables are the manipulated input increments over the control horizon and the states over the prediction horizon.
gdalle commentedon Nov 15, 2025
Note that postprocessing doesn't do anything for unidirectional Jacobians. Like the decompression by substitution, it only applies to Hessians or bidirectional Jacobians.
The API of RandomOrder is a bit clumsy: first you give the generator, then you give the seed to reset it with before each coloring. If you don't give that seed, you will see different numbers of colors at every run of the preparation. So as long as you provide that seed, results are reproducible... up to Julia version. Indeed, Random (the stdlib) doesn't guarantee stability of the exact stream of random numbers produced from one Julia version to the next. Hence my recommendation to use StableRNGs instead for full reproducibility.
As a side note, the zero inside
StableRNG(0)doesn't matter because the generator will be re-seeded anyway.If you're curious you can look at the code, it is dead simple: https://github.com/gdalle/SparseMatrixColorings.jl/blob/main/src/order.jl#L57-L64
franckgaga commentedon Nov 15, 2025
Okay, I just used the same default sparse backend for the Jacbians and for the Hessians to avoid code duplication (i.e. don't repeat yourself). I understand that these options will be just ignored for the Jacobians, which is okay with me.
Alright. 190 lines of code for
StableRNGs: it seems very lightweight. I will addRandomOrderin the tuple and theStableRNGsdependency.3 remaining items
amontoison commentedon Dec 13, 2025
@franckgaga Don't forget to use
decompression=:substitutionfor the Hessian :)It works better in practice (less colors) than the default algorithm (star coloring).
It is more expensive but for optimization solvers where we reuse it multiple times, I highly recommend it.
franckgaga commentedon Feb 12, 2026
So by working on orthogonal collocation, I understood that it may be caused by something else. Right now for multiple shooting, the decision vector is a concatenation of the manipulated input vector$\mathbf{\Delta U}$ and the state vector $\mathbf{\hat{X}_0}$ . This is presumably less efficient than having both "interlaced", i.e. (for the sparsity, both for differentiation but inside Ipopt as well, it seems):
TBH, I drastically prefer my way of working in terms of code readability. I'm annoyed that most efficient solution is the "messiest". Moving to interlaced decision vector will be particularly messy for the construction of the prediction matrices for
LinModel. edit: this is also probably why the OSQP.jl documentation rely on "concatenated" decision vector, that is, for clarity.franckgaga commentedon Feb 12, 2026
The refactor job for migrating to "interlaced" decision vector would be substantial. Not to mention that the equations in the documentation of the internals would be way longer and messier, since the prediction matrices would be no longer "perfectly separated" block matrices.
I'm really not sure if I should put time on this refactor. If the answer is yes, it clearly needs to be done before implementing a new transcription method. It seems that the
SparseMatrixColoringpackage is able to efficiently handle arrow-shaped Hessians and Jacobians (with adequate ordering algorithms). I'm also aware that many sparse linear solvers do permutation before solving the system. I'm not sure if the default MUMPS of Ipopt does that, although.Obviously the only way to know would be to implement it and benchmark it. But I expect that I would not see much difference on the small pendulum case study.
franckgaga commentedon Feb 13, 2026
What's your take @baggepinnen should I put time on this refactor ?
baggepinnen commentedon Feb 14, 2026
I wouldn't bother with such a refactor, I also use the same layout as you and haven't noticed any benefits of the other layout. There may be marginal benefits that play a role when everything else is optimized to the max, but unless you cantrol the solver completely it's hard to reach there
franckgaga commentedon Feb 14, 2026
Alright, I'll put my time on the new
OrthogonalCollocation. Thanks for the answer!franckgaga commentedon Mar 3, 2026
Now that most relevant nonlinear solvers support the
VectorNonlinearOracle(e.g.Ipopt.jl,MadNLP.jl,KNITRO.jlandUnoSolver.jl), I will remove theoraclekeyword argument (that is: always use oracles) and also the legacy code that uses the splatting syntax. It is just too complex, too slow, and no longer tested in the suite. It's also annoying to always setoracle=truein all cases. I personally forget it frequently.It means that the next release will be a breaking change. If there are people that use
NLopt.jlfor example, they will need to stick to an older version of the package.While I'm at it, I will also add the slack$\epsilon$ in the custom economic function signature, which is another breaking change but it might be useful for non-quadratic weighting.
I will mention these in the release message.
amontoison commentedon Mar 3, 2026
@franckgaga Do you have degenerate problems or MPEC problems to solve?
It may be relevant that I do the JuMP interface for
MadNCL.jlif it is the case.franckgaga commentedon Mar 3, 2026
I don't think so. To be honest, I'm not sure I understand what are degenerate problems or MPEC in the context of nonlinear programming for model predictive control. By reading quickly about NCL, I understand it applies to problems with large amounts of constraints? If so, I don't think it's relevant for typical model predictive control.
amontoison commentedon Mar 3, 2026
The last paper is this one: MadNCL.
The problem is degenerated if:
If you have more constraints than variables, LICQ doesn't hold but it can happen for other reasons and you don't need a lot of constraints.
gdalle commentedon Mar 4, 2026
I'm going to unsubscribe from this issue, ping me if you need me
franckgaga commentedon Mar 4, 2026
Okay I see that it was shown to be a bit more robust than Ipopt.jl and MadNLP.jl on some problem instances. In that case, yes a JuMP interface might be interesting for MPC.jl.
[-]Breaking changes for v2[/-][+]Breaking changes for v3[/+][-]Breaking changes for v3[/-][+]Potential breaking changes for v3[/+][-]Potential breaking changes for v3[/-][+]Potential breaking changes for a v3[/+]