Multiparametric programming


#1

Hi all,

Has there been any work on multiparametric programming in Julia? I’m starting to look into it for my own research, and it would be nice to build on any existing work there might be. Googling around and looking inside JuliaOpt has not turned up anything so far.

Cheers,
Robin


#2

I am not the guy who is gonna answer your question because I probably don’t have the expertise in your field. But you could add links to what you meant by “multiparametric programming” so that other people can help.


#3

See https://en.wikipedia.org/wiki/Parametric_programming and https://application.wiley-vch.de/books/sample/3527316914_c01.pdf. In linear or convex-quadratic constrained optimization problems, if the linear coefficients of the objective function and/or the right-hand-side of the constraints are linear functions of some parameter vector, you can enumerate all the possible optimal active sets and express the optimal solution (w.r.t. the parameter vector) as a piecewise-affine function over polyhedral regions. It’s a really neat application of computational geometry, reducing the solutions to a whole parametric family of optimization problems to a lookup table.

I’m not sure whether there’s any mature Julia package for doing this yet, but many of the pieces that you’d need have been put together in https://github.com/JuliaPolyhedra (cc @blegat if he’s on discourse, also @joehuchette’s https://github.com/joehuchette/PiecewiseLinearOpt.jl may be related / useful). The standard tool for multiparametric programming is the Matlab toolbox MPT http://people.ee.ethz.ch/~mpt/3/, but the computationally demanding part is calls into cddlib and related computational geometry operations that there are now Julia wrappers for.


#4

Thanks @tkelman! I’ll post back here if I end up with anything worth sharing.


#5

@rdeits Anything worth sharing yet ? I am currently looking into Model Predictive Control :stuck_out_tongue:


#6

For the record, I ended up implementing the basic stuff myself in ExplicitQPs.jl. It’s unregistered and undocumented since it’s only used in my current research code, but it at least has some tests that illustrate what’s possible: https://github.com/rdeits/ExplicitQPs.jl/blob/master/test/runtests.jl


#7

Apologies for the necro-post but hopefully it’s helpful. I created a section for MPT3 in the Julia for MATLAB Users wiki that I’m putting together. I’m watching this thread and will add more resources posted here but it’s a wiki so don’t hesitate to go ahead and edit it yourself! :slight_smile:

https://en.wikibooks.org/wiki/Julia_for_MATLAB_Users/Index#The_Multi-Parametric_Toolbox_(MPT)