Multi-parametric Optimization and Control. Efstratios N. Pistikopoulos

of the projection are the following:

       Solving a multi‐parametric linear programming (mp‐LP) problem (see e.g. [8])

       Performing a Fourier–Motzkin (FM) elimination (see, e.g. [9])

      In addition, the concept of a hybrid projection is introduced:

      Definition 1.12 (Hybrid Projection)

      Consider the set . Then, the hybrid projection of onto is defined as

      (1.34)

      By inspection it is clear that (i) is obtained by performing at most projections, one for each combination of the binary variables and consequently (ii) is generally a union of at most possibly overlapping polytopes.

      A hybrid projection can thereby be performed by solving a multi‐parametric mixed‐integer programming problem purely based on feasibility requirements.

      1.3.3 Modeling of the Union of Polytopes

      The aim is to represent a union of polytopes as a single set of linear inequality constraints in order to seamlessly include them within multi‐parametric programming problems. However, in order to address the possible non‐convexity within unions of polytopes, the introduction of suitable binary variables is required. First, consider that a point if and only if there exists at least one such that . Thus, one binary variable is defined such that

      (1.35a)

      (1.35b)

Let and denote the th row and element of and , respectively. Then, the statement holds if and only if , . Thus, one binary variable per row of , is defined such that

(1.36a)

      (1.36b)

(1.36c)

Based on [10,11], Eqs. (1.36a)–(1.36c) are reformulated as

      (1.37a)

      (1.37b)

      (1.37c)

      (1.37d)

      where , . Thus, the final formulation of the union as a set of linear inequality constraints featuring binary variables is given as

      (1.38)

1.4 Organization of the Book

The remainder of this book is organized in two parts. In the first part, the theoretical and algorithmic essentials of multi‐parametric programming problems will be established. These include algorithms for the solution of multi‐parametric linear programming (mp‐LP), multi‐parametric quadratic programming (mp‐QP), multi‐parametric mixed‐integer linear programming (mp‐MILP), and multi‐parametric mixed‐integer quadratic programming (mp‐MIQP) problems. On the other hand, the latter of these parts is focused on the applications of multi‐parametric programming and specifically on its utilization to provide solutions to receding horizon optimization problems such as model predictive control.

References

      1 1 Fiacco, A.V. (1983) Introduction to sensitivity and stability analysis in nonlinear programming, Mathematics in science and engineering, vol. v, 165, Academic Press, New York.

      2 2 Boyd, S.P. and Vandenberghe, L. (2004) Convex optimization, Cambridge University Press, Cambridge, UK and New York.

      3 3 Telgen, J. (1981) Redundancy and linear programs, Mathematisch Centrum, Amsterdam.

      4 4 Karwan, M.H., Lotfi, V., Telgen, J., and Zionts, S. (1983) Redundancy in mathematical programming: a state‐of‐the‐art survey, Lecture notes in economics and mathematical systems, vol. 206, Springer‐Verlag, Berlin and New York.

      5 5 Brearley, A.L., Mitra, G., and Williams, H.P. (1975) Analysis of mathematical programming problems prior to applying the simplex algorithm. Mathematical Programming, 8 (1), 54–83, doi: 10.1007/BF01580428.

      6 6 Suard, R., Lofberg, J., Grieder, P., Kvasnica, M., and Morari, M. (2004) Efficient computation of controller partitions in multi‐parametric programming, in 2004 43rd IEEE Conference on Decision and Control (CDC), vol. 4, pp. 3643–3648, doi: 10.1109/CDC.2004.1429297.

      7 7 Jones,