2016 AIChE Annual Meeting
(514b) Multi-Parametric Quadratic Programming: Past, Present and Future
Authors
Although both approaches solve the same problem, so far no attempt has been made to unify the properties underpinning these algorithms. In this work, we discuss such a unified strategy by proving that the solution to a mp-QP problem is given by a connected graph. Each node is thereby an active set and a connection between two nodes is generated based on geometrical arguments which indicate adjacency. Combined with the branch-and-bound approach in [8], this novel approach limits the number of candidate active sets to be considered. In the case of primal and dual degeneracy, it can be proven that there exists a single graph which solves the problem, resulting in a set of disjoint critical regions. This new development, part of our POP toolbox, is demonstrated through a unique computational study, where the computational abilities of state-of-the-art geometrical, combinatorial and connected-graph algorithm implementations are shown and compared. In addition, these results are compared with the latest version of the MPT toolbox [10], a software tool which solves mp-QP problems by reformulating them as multi-parametric linear complementarity problems. Based on these developments, we investigate the future research directions for mp-QP algorithms. In particular, we highlight the ability to apply parallelization strategies, the limitation of storage requirements and the extension of these results to general multi-parametric non-linear programming.
References
[1] Pistikopoulos, E. N.; Diangelakis, N. A.; Oberdieck, R.; Papathanasiou, M. M.; Nascu, I.; Sun, M. (2015) PAROC - an Integrated Framework and Software Platform for the Optimization and Advanced Model-Based Control of Process Systems. Chemical Engineering Science, 136, 115 â?? 138.
[2] Bemporad, A.; Morari, M.; Dua, V.; Pistikopoulos, E. N. (2002) The explicit linear quadratic regulator for constrained systems. Automatica, 38(1), 3 â?? 20.
[3] Faisca, N. P.; Dua, V.; Rustem, B.; Saraiva, P. M.; Pistikopoulos, E. N. (2007) Parametric global optimisation for bilevel programming. Journal of Global Optimization, 38(4), 609 â?? 623.
[4] Baotic, M. (2002) An Efficient Algorithm for Multiparametric Quadratic Programming. Technical Report, ETH Zurich.
[5] Tondel, P.; Johansen, T. A.; Bemporad, A. (2003) An algorithm for multi-parametric quadratic programming and explicit MPC solutions. Automatica, 39(3), 489 â?? 497.
[6] Spjotvold, J.; Kerrigan, E. C.; Jones, C. N.; Tondel, P.; Johansen, T. A. (2006) On the facet-to-facet property of solutions to convex parametric quadratic programs. Automatica, 42(12), 2209 â?? 2214.
[7] Seron, M. M.; Goodwin, G. C.; de Dona, J. A. (2002) Finitely parameterised implementation of receding horizon control for constrained linear systems. Proceedings of the American Control Conference, vol. 6, 4481 â?? 4486.
[8] Gupta, A.; Bhartiya, S.; Nataraj, P. S. V. (2011) A novel approach to multiparametric quadratic programming. Automatica, 47(9), 2112 â?? 2117.
[9] Feller, C.; Johansen, T. A.; Olaru, S. (2013) An improved algorithm for combinatorial multi-parametric quadratic programming. Automatica, 49(5), 1370 â?? 1376.
[10] Herceg, M.; Jones, C. N.; Kvasnica, M.; Morari, M. (2015) Enumeration-based approach to solving parametric linear complementarity problems. Automatica, 62, 243 â?? 248.