Multiparametric programming

See Parametric programming - Wikipedia 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 GitHub - joehuchette/PiecewiseLinearOpt.jl: Solve optimization problems containing piecewise linear functions may be related / useful). The standard tool for multiparametric programming is the Matlab toolbox MPT MPT3 Wiki | Main / HomePage, but the computationally demanding part is calls into cddlib and related computational geometry operations that there are now Julia wrappers for.

4 Likes