(621e) An Algorithm for the Exact Solution of Multiparametric Quadratically Constrained Quadratic Programming Problems

Multiparametric programming has proven to be an invaluable strategy to solve optimization problems which involve uncertainty and variability in their formulation [1]. Motivated by the benefits and applicability of multiparametric programming in a wide variety of applications, several algorithms for the exact solution of multiparametric linear and quadratic programming problems and their mixed-integer counterparts have been developed [2,3].

Quadratically Constrained Quadratic Programming problems comprise an important class of problems encountered in several applications, including optimal control problems with ellipsoid invariant sets [4], pooling problems [5], sensor network localization [6] and min-max model predictive control problems [7]. In the case where bounded uncertainty is part of the optimization formulation, a multiparametric Quadratically Constrained Quadratic Programming (mpQCQP) problem is formed [8]. The efforts in the literature to solve mpQCQPs has been through the construction of algorithms to solve general multiparametric Nonlinear Programming problems (mpNLPs). However, the derivation of the optimal solution of mpNLPs is challenging and linear or quadratic approximations of the original problem formulation have been primarily proposed [9], for which exact algorithms exist and software for their solution is readily available [10].

In this work, we present an algorithm for the exact solution of convex mpQCQPs. Utilizing a second-order Taylor approach to the Basic Sensitivity Theorem, we propose an active-set exploration strategy to implicitly explore the feasible parameter space. Firstly, the feasible active-sets are identified, while a pruning criterion is adopted to avoid the explosion of possible active-set combinations. Based on the KKT optimality conditions, from the remaining feasible candidate active sets, the optimal active sets are found. As a result, the determination of the optimal solution of convex mpQCQPs for every feasible parameter realization reduces to a nonlinear function evaluation and the complete map of parametric solutions is constructed. The algorithm is implemented for the optimal control of a chemical engineering application to illustrate the benefits of the proposed approach.

References:

[1] Oberdieck, R., Diangelakis, N. A., Nascu, I., Papathanasiou, M. M., Sun, M., Avraamidou, S., & Pistikopoulos, E. N. On multi-parametric programming and its applications in process systems engineering. Chemical Engineering Research and Design, 2016, 116, 61-82.

[2] Acevedo, J., & Pistikopoulos, E. N. A multiparametric programming approach for linear process engineering problems under uncertainty. Industrial & Engineering Chemistry Research, 1997, 36(3), 717-728.

[3] Gupta, A., Bhartiya, S., & Nataraj, P. S. V. A novel approach to multiparametric quadratic programming. Automatica, 2011, 47(9), 2112-2117.

[4] Blanchini, F. Set invariance in control. Automatica, 1999, 35(11), 1747-1767.

[5] Misener, R., & Floudas, C. A. Advances for the pooling problem: Modeling, global optimization, and computational studies. Applied and Computational Mathematics, 2009, 8(1), 3-22.

[6] Biswas, P., Lian, T. C., Wang, T. C., & Ye, Y. Semidefinite programming based algorithms for sensor network localization. ACM Transactions on Sensor Networks (TOSN), 2006, 2(2), 188-220.

[7] Diehl, M. Formulation of closed-loop min–max MPC as a quadratically constrained quadratic program. IEEE Transactions on Automatic Control, 2007, 52(2), 339-343.

[8] Diangelakis, N. A., Pappas, I. S., & Pistikopoulos, E. N. On multiparametric/explicit NMPC for Quadratically Constrained Problems. IFAC-PapersOnLine, 2018, 51(20), 400-405.

[9] Domínguez, L. F., Narciso, D. A., & Pistikopoulos, E. N. Recent advances in multiparametric nonlinear programming. Computers & Chemical Engineering, 2010, 34(5), 707-716.

[10] Oberdieck, R., Diangelakis, N. A., Papathanasiou, M. M., Nascu, I., & Pistikopoulos, E. N. POP–Parametric OPtimization toolbox. Industrial & Engineering Chemistry Research, 2016, 55(33), 8979-8991.