##
462360 Multi-Parametric Quadratic Programming: Past, Present and Future

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.

**Extended Abstract:**File Not Uploaded

See more of this Group/Topical: Computing and Systems Technology Division