Multi-Parametric Quadratic Programming: Past, Present and Future

In multi-parametric programming (mp-P), an optimization problem is solved for a range and as a function of certain parameters [1]. Due to its wide variety of applications, there has been a significant interest within the research community to solve mp-P problems efficiently. The most common class of mp-P problems are thereby multi-parametric quadratic programming (mp-QP) problems, as they arise in areas such as explicit model predictive control [2] of discrete-time linear systems and bilevel programming [3]. In this work, we examine the current state-of-the-art for mp-QP theory and algorithms. In particular, we draw upon a historical description of the evolution of the theory and algorithms related to mp-QP problems in order to highlight the current state-of-the-art and the research direction forwards with respect to mp-QP problems. The first comprehensive solution approach for mp-QP problems was presented in 2002 [2], where the geometrical interpretation of the parameter space was used to move from one region, where an active set is optimal, to another. However, as this approach introduces a large number of artificial cuts, several researchers have proposed modifications, including a variable step-size approach [4], inferring the active set of the adjacent critical regions from the irredundant constraints [5] and a combination thereof [6]. Each region of optimality, called critical region, is uniquely identified by its active set. Thus, soon after [2] appeared, researchers suggested the exhaustive enumeration of all active sets in order to solve mp-QP problems [7]. However, this combinatorial approach only became computationally tractable in 2011, when a branch-and-bound algorithm was suggested, which used the fact that if a candidate active set is infeasible, so is its superset [8]. The efficiency of the approach was refined in [9] by considering symmetry elements.

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.