2.1. Multi-Parametric Programming
Overall, multi-parametric programming problems are concerned with the effect of parametric perturbations on the optimal solution of an optimisation problem. Consider the following optimisation problem:
where
stands for the vector of uncertain parameters, which is
-dimensional,
is the
-dimensional vector of continuous decision variables,
is the vector of inequality constraints and
f is the objective function as a mapping
both of which are assumed to be
(twice continuously differentiable). Problem (
1) is a multi-parametric program and its solution results in the partition of the parametric
-space into a number of regions, also know as critical regions (CRs). Within each CR, the optimal solution and the objective value are given as functions of the uncertain parameters, i.e.,
and
, respectively. Even though mp-P has been studied quite actively, the class of multi-parametric nonlinear programming problems remains one of the most challenging ones [
11,
12]. Depending on the convexity of the nonlinear functions that form Problem (
1), different solution techniques have been proposed in the literature to date.
Advances in the algorithms and theory of parametric nonlinear programs (p-NLPs) date back to the early works of Fiacco [
13] and Bank et al. [
14]. More specifically, in the books of Bank et al. [
14] and Fiacco [
13], a collection of the early research works for parametric NLPs can be found and invaluable theoretical foundations for some classes of convex p-NLPs with perturbations in the OFC and the right-hand side of the constraints are provided. Even though the term “parametric nonlinear optimisation/programming” was widely established from the aforementioned works, the early works on numerical stability analysis of NLPs by [
15,
16] and the work of Robinson [
17,
18] on generalised equations provided a significant way of studying the effect of parametric variations on the optimal solution of p-NLPs. Kyparisis [
19] studied the uniqueness and differentiability of solutions of parametric nonlinear complementarity problems while in Ralph and Dempe [
20], the directional derivatives of parametric nonlinear programs were used to characterise their explicit solution. However, the first algorithm for the multi-parametric case of convex NLPs was due to Dua and Pistikopoulos [
21]. The authors, based on the findings about the convexity properties of the parametric value function (
), devised an iterative procedure in which the integer variables were fixed by the solution of a primal mixed integer nonlinear program (MINLP) and the resulting mp-NLP was then transformed into an mp-LP following the outer approximation idea. Because of the value function’s convexity property, the maximum error of the approximation occurs at the vertices of the CRs and if the error is greater than the prespecified tolerance, the CR is partitioned again; otherwise, integer and parametric cuts are implemented and then the algorithm iterates until the primal MINLP is infeasible. The same algorithm was revisited by Acevedo and Salgueiro [
22], where the authors proposed heuristics to improve its computational efficiency while quadratic approximations were studied by Johansen [
23] and Domínguez and Pistikopoulos [
24]. An approximate algorithm for the solution of convex mp-NLPs was proposed by Johansen [
25], who proposed the consecutive subdivision of the parametric space in hyper-rectangles and the interpolation of the parametric solution through the solution of
NLPs at each step. Further approaches involve the geometric vertex search by Narciso [
26] and sub-gradient methods by Leverenz et al. [
27]. For the nonconvex cases, Dua et al. [
28] developed suitable parametric under/overestimators which were then incorporated into a spatial branch and bound routine for the global optimisation of the nonconvex problem within
—tolerance. For a more thorough discussion on the algorithms that have been proposed for the solution of mp-NLPs, the interested reader is directed to the review of Domínguez et al. [
29] while Hale [
30], in her doctoral thesis, also offers a thorough discussion on several classes of parametric optimisation. Fotiou et al. [
31,
32] initially studied the polynomial multi-parametric programming problem with application to control, however, their approach did not include the definition of final nonconvex CRs, while the mixed integer polynomial case was studied by Charitopoulos and Dua [
33] and a procedure for the computation of exact nonconvex CRs was presented. Despite the aforementioned research effort, mp-NLP problems remain one of the most difficult to tackle and, as illustrated in
Table 1, all the aforementioned algorithms can handle uncertain parameters only on the right-hand side (RHS) of the constraints. Recently, Pappas et al. [
34], by generalising the basic sensitivity theorem of Fiacco [
13], devised an algorithm for the exact solution of multi-parametric quadratically constrained quadratic programs.
Among the wide range of appplications that multi-parametric programming has been applied to, the invention of explicit model predictive control (mp-MPC) is undoubtedly the most dominant area where mp-P has had the biggest impact [
10,
12,
35]. The main concept of mp-MPC is that instead of solving the optimisation problems related to standard MPC at each sampling instance, the state of the system is treated as an uncertain parameter and an mp-P can be solved offline to derive the explicit control solution once and for all [
10,
36].
The general formulation of mp-MPC for discrete time systems is shown by (
2):
where
are the state, control input and system output vectors, respectively, at every sampling point, t, and are
-dimensional.
are matrices of appropriate dimensions and
vectors of pertinent dimensions which represent inequality constraints for the state, output and control inputs while
is a stage cost and
is a terminal cost function. The repetitive solution of Problem (
2) provides the optimal cost
and the optimisation vector, i.e., the sequence of optimal control inputs
over the finite prediction horizon
. Compared to the conventional model predictive control fashion, in which an optimisation problem is solved at each sampling point, through the mp-MPC notion, the explicit control law is calculated offline once and for all. The solution of the resulting mp-P problem results in the optimal control inputs as explicit functions of the (uncertain) parameters, i.e., the state of the system at each sampling instance, along with the corresponding CRs, as shown by Equation (
3).
For the case of MPC for linear systems, instead of solving a quadratic program at each sampling instance, the explicit MPC requires the offline solution of an mp-QP while online, so only simple function evaluations are required [
10,
37,
38]. This concept is also known as online via offline optimisation and it is shown in
Figure 3.
Even though mp-MPC is the niche area of mp-P, designing mp-MPCs of nonlinear systems for set-point tracking is still a computationally strenuous task as one has to design an mp-MPC for each set-point based on the algorithms that exist in the literature to date [
40]. Next, we review two mathematical techniques that will enable the development of novel multi set-point explicit controllers though the algorithm we propose in the present work.