Skip to content

Potential breaking changes for a v3 #273

Open

Description

@franckgaga

I'm raising an issue to list the possible breaking changes for a future release of a v2 v3 library:

  • Removing oracle keyword argument and code in the two legacy.jl files
  • Adding the slack $\epsilon$ in the signature of $J_E$ function (to support non-quadratic weighting)
  • Consider changing the default arguments of UnscentedKalmanFilter
  • Consider changing the default value of transcription in NonLinMPC to MultilpleShooting

Activity

  1. franckgaga commented on Nov 10, 2025

    @franckgaga
    MemberAuthor

    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).
  2. franckgaga commented on Nov 12, 2025

    @franckgaga
    MemberAuthor

    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:

    # ====== transcription=SingleShooting(), hessian=false =============
    btime_NMPC_track_solver_IP = median(bm) = TrialEstimate(374.487 ms)
    btime_NMPC_regul_solver_IP = median(bm) = TrialEstimate(327.766 ms)
    btime_EMPC_track_solver_IP = median(bm) = TrialEstimate(364.620 ms)
    btime_EMPC_regul_solver_IP = median(bm) = TrialEstimate(363.225 ms)
    
    # ======= transcription=SingleShooting(), hessian=true =============
    btime_NMPC_track_solver_IP = median(bm) = TrialEstimate(133.406 ms)
    btime_NMPC_regul_solver_IP = median(bm) = TrialEstimate(119.391 ms)
    btime_EMPC_track_solver_IP = median(bm) = TrialEstimate(136.490 ms)
    btime_EMPC_regul_solver_IP = median(bm) = TrialEstimate(119.599 ms)
    
    # ====== transcription=MultipleShooting(), hessian=false ============
    btime_NMPC_track_solver_IP = median(bm) = TrialEstimate(251.237 ms)
    btime_NMPC_regul_solver_IP = median(bm) = TrialEstimate(214.630 ms)
    btime_EMPC_track_solver_IP = median(bm) = TrialEstimate(274.271 ms)
    btime_EMPC_regul_solver_IP = median(bm) = TrialEstimate(318.969 ms)
    
    # ====== transcription=MultipleShooting(), hessian=true ============
    btime_NMPC_track_solver_IP = median(bm) = TrialEstimate(334.286 ms)
    btime_NMPC_regul_solver_IP = median(bm) = TrialEstimate(269.657 ms)
    btime_EMPC_track_solver_IP = median(bm) = TrialEstimate(951.969 ms)
    btime_EMPC_regul_solver_IP = median(bm) = TrialEstimate(935.775 ms)

    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.

    What's your opinion @baggepinnen ?

  3. baggepinnen commented on Nov 14, 2025

    @baggepinnen
    Member

    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.

  4. franckgaga commented on Nov 14, 2025

    @franckgaga
    MemberAuthor

    Yep, I'll verify if it's really the Hessian that take this much time. ⌛️

  5. franckgaga commented on Nov 14, 2025

    @franckgaga
    MemberAuthor
    • optim default to Model(() -> UnoSolver.Optimizer(preset="filtersqp")); ?
  6. baggepinnen commented on Nov 14, 2025

    @baggepinnen
    Member

    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

  7. franckgaga commented on Nov 14, 2025

    @franckgaga
    MemberAuthor

    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.

  8. franckgaga commented on Nov 15, 2025

    @franckgaga
    MemberAuthor

    Yep, I'll verify if it's really the Hessian that take this much time. ⌛️

    Yep, all the the time is spent in the sparse Hessian computation of the objective function.

    Image

    The number of colors is way higher than all the other cases:

    ncolors(∇²J_prep) = 39
    62×62 SparseArrays.SparseMatrixCSC{Bool, Int64} with 294 stored entries:
    ⎡⡿⣯⠉⠉⠉⠉⠉⠉⠉⠉⠉⠉⠉⠁⎤
    ⎢⡇⠀⠱⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
    ⎢⡇⠀⠀⠀⠱⣦⠀⠀⠀⠀⠀⠀⠀⠀⎥
    ⎢⡇⠀⠀⠀⠀⠀⠱⣦⡀⠀⠀⠀⠀⠀⎥
    ⎢⡇⠀⠀⠀⠀⠀⠀⠈⠱⣦⡀⠀⠀⠀⎥
    ⎢⡇⠀⠀⠀⠀⠀⠀⠀⠀⠈⠱⣦⡀⠀⎥
    ⎣⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠱⣦⎦
    

    I will experiment with other coloring orders...

  9. baggepinnen commented on Nov 15, 2025

    @baggepinnen
    Member

    The hessian has an arrow shape? IIRC @gdalle and friends have some special trick with mixed-mode AD that can handle such cases?

  10. baggepinnen commented on Nov 15, 2025

    @baggepinnen
    Member

    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?

  11. gdalle commented on Nov 15, 2025

    @gdalle
    Contributor

    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

    In order words, I'd recommend going from

    GreedyColoringAlgorithm()

    to

    GreedyColoringAlgorithm(
        (
            NaturalOrder(),
            LargestFirst(),
            SmallestLast(),
            IncidenceDegree(),
            DynamicLargestFirst(),
            RandomOrder(StableRNG(0), 0)
        ),
        decompression=:substitution
    )

    to see if it does anything.

  12. franckgaga commented on Nov 15, 2025

    @franckgaga
    MemberAuthor

    Oh wow, the RandomOrder(StableRNG(0), 0) does the trick: 4 colors! Right now my default sparse Jacobian (edit: and Hessian) backend is:

    AutoSparse(
        AutoForwardDiff(); 
        sparsity_detector  = TracerSparsityDetector(), 
        coloring_algorithm = GreedyColoringAlgorithm(
            (
              NaturalOrder(),
              LargestFirst(),
              SmallestLast(),
              IncidenceDegree(),
              DynamicLargestFirst()
            ), 
        postprocessing = true
        )
    )

    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:

    1. 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.
    2. What's the pros and cons of using ranges from Random instead of StableRNGs (to avoid new dependencies) ?
  13. franckgaga commented on Nov 15, 2025

    @franckgaga
    MemberAuthor

    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:

    ncolors(∇²J_prep) = 2
    62×62 SparseArrays.SparseMatrixCSC{Bool, Int64} with 142 stored entries:
    ⎡⠱⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎤
    ⎢⠀⠀⠱⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
    ⎢⠀⠀⠀⠀⠱⣦⠀⠀⠀⠀⠀⠀⠀⠀⎥
    ⎢⠀⠀⠀⠀⠀⠀⠱⣦⡀⠀⠀⠀⠀⠀⎥
    ⎢⠀⠀⠀⠀⠀⠀⠀⠈⠱⣦⡀⠀⠀⠀⎥
    ⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠱⣦⡀⠀⎥
    ⎣⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠱⣦⎦

    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.

  14. gdalle commented on Nov 15, 2025

    @gdalle
    Contributor

    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

  15. franckgaga commented on Nov 15, 2025

    @franckgaga
    MemberAuthor

    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.

  16. 3 remaining items

  17. amontoison commented on Dec 13, 2025

    @amontoison

    @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.

  18. franckgaga commented on Feb 12, 2026

    @franckgaga
    MemberAuthor

    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):

    $$\mathbf{Z} = \begin{bmatrix} \mathbf{\Delta u}(k+0) \\\ \mathbf{\hat{x}_0}(k+0) \\\ \mathbf{\Delta u}(k+1) \\\ \mathbf{\hat{x}_0}(k+1) \\\ \vdots \end{bmatrix}$$

    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.

  19. franckgaga commented on Feb 12, 2026

    @franckgaga
    MemberAuthor

    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.

  20. franckgaga commented on Feb 13, 2026

    @franckgaga
    MemberAuthor

    What's your take @baggepinnen should I put time on this refactor ?

  21. baggepinnen commented on Feb 14, 2026

    @baggepinnen
    Member

    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

  22. franckgaga commented on Feb 14, 2026

    @franckgaga
    MemberAuthor

    Alright, I'll put my time on the new OrthogonalCollocation. Thanks for the answer!

  23. franckgaga commented on Mar 3, 2026

    @franckgaga
    MemberAuthor

    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.

    I will mention these in the release message.

  24. amontoison commented on Mar 3, 2026

    @amontoison

    @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.

  25. franckgaga commented on Mar 3, 2026

    @franckgaga
    MemberAuthor

    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.

  26. amontoison commented on Mar 3, 2026

    @amontoison

    The last paper is this one: MadNCL.

    The problem is degenerated if:

    • 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.

  27. gdalle commented on Mar 4, 2026

    @gdalle
    Contributor

    I'm going to unsubscribe from this issue, ping me if you need me

  28. franckgaga commented on Mar 4, 2026

    @franckgaga
    MemberAuthor

    The last paper is this one: MadNCL.

    The problem is degenerated if:

    * 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.

  29. changed the title [-]Breaking changes for v2[/-] [+]Breaking changes for v3[/+] on Mar 4, 2026
  30. changed the title [-]Breaking changes for v3[/-] [+]Potential breaking changes for v3[/+] on Jul 5, 2026
  31. changed the title [-]Potential breaking changes for v3[/-] [+]Potential breaking changes for a v3[/+] on Jul 5, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions