(373u) Approximate Solution to Multi-Parametric Programming Problem Using Robust Optimization

Multi-parametric programming technique computes the explicit optimal solution to a mathematical optimization problem with changing parameters. Over the last two decades, multi-parametric programming has received many studies for various type of optimization problems [1]. While many algorithms target the exact solution of multi-parametric programming problems, approximate solution methods to multiparametric programming received limited attention. To name a few, Johansen and Grancharova [2] proposed an offline computation method for the approximate solution to linear constrained explicit MPC problems, where the solution is defined on an orthogonal partition of the state space. The work was later extended to nonlinear constrained problems [3]. Bemporad and Filippi [4] proposed an algorithm for the approximate solution of convex multiparametric nonlinear programming problems, where the approximate solution is expressed as a piecewise affine function over a simplicial partition of a given set.

In this work, we propose a different method for generating the approximate solution to the multi-parametric programming problem. We use the adaptive robust optimization technique to solve the problem. All the decision variables in the multiparametric optimization problem are treated as adaptive variables and approximated using decision rule (a function of the parameters with unknown coefficients to be optimized). The uncertainty set for the parameters is identified from the given bounds of the uncertain parameter and the constraints of the original problem. With some sample points of the parameters, the deterministic optimization problem is solved first to get corresponding optimal objective values. The objective of the robust optimization model is to minimize the total error between the optimal objective values and the objective calculated using the decision rule. The constraints of the optimization problem are further converted to their deterministic counterpart after the variables are replaced using decision rule. Finally, the robust optimization problem is converted to a deterministic optimization problem which is solved to obtain the decision rule as an approximate solution to the multiparametric programming problem.

To obtain a good approximate quality of the solution to the original multiparametric programming problem, we further lift the uncertain parameters based on pre-defined breakpoints. Then piecewise linear decision rule is obtained by applying linear decision rule over the lifted space. The approximation quality is adjustable based on the number of breakpoints. The proposed method can also handle a large number of uncertain parameters. The proposed method only requires the solution of the original deterministic optimization problem with some fixed parameter values and a single adaptive robust optimization problem. We demonstrate the efficiency of the proposed method through simple numerical examples and also applications in explicit model predictive control.

References:

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

[2] Johansen, T. A., & Grancharova, A. (2003). Approximate explicit constrained linear model predictive control via orthogonal search tree. IEEE Transactions on Automatic Control, 48(5), 810-815.

[3] Johansen, T. A. (2004). Approximate explicit receding horizon control of constrained nonlinear systems. Automatica, 40(2), 293-300.

[4] Bemporad, A., & Filippi, C. (2006). An algorithm for approximate multiparametric convex programming. Computational optimization and applications, 35(1), 87-108.