Multi-parametric Optimization and Control. Efstratios N. Pistikopoulos

Equality Set Projection: A new algorithm for the projection of polytopes in halfspace representation. Technical Report CUED/F‐INFENG/TR.463. Cambridge University, Cambridge, UK.

      8 8 Kouramas, K.I., Panos, C., Faísca, N.P., and Pistikopoulos, E.N. (2013) An algorithm for robust explicit/multi‐parametric model predictive control. Automatica, 49 (2), 381–389, doi: 10.1016/j.automatica.2012.11.035. URL http://www.sciencedirect.com/science/article/pii/S0005109812005717.

      9 9 Schrijver, A. (1998) Theory of linear and integer programming, Wiley‐interscience series in discrete mathematics and optimization, Wiley, Chichester and New York.

      10 10 Bemporad, A. and Morari, M. (1999) Control of systems integrating logic, dynamics, and constraints. Automatica, 35 (3), 407–427, doi: 10.1016/S0005‐1098(98)00178‐2. URL http://www.sciencedirect.com/science/article/pii/S0005109898001782.

      11 11 Williams, H.P. (2013) Model building in mathematical programming, Wiley, Hoboken, NJ, 5th edn.

Notes

      1 1 A function is called pseudo‐convex if for all feasible where we have .

      2 2 A function is called quasi‐convex if for all feasible and we have . Note that a quasi‐concave function is a function whose negative is quasi‐convex.

2 Multi‐parametric Linear Programming

Consider the following linear programming (LP) problem:

(2.1)

where , , , , , is a compact polytope and is assumed to have full rank.1 This problem formulation requires the deterministic knowledge of all elements of problem (2.1). However, in many applications values such as prices, demand, and risk might change over time and have great impact on the solution. In order to take this into account, the uncertainty can be considered explicitly by formulating a multi‐parametric linear programming (mp‐LP) problem:

(2.2)

where , , , and is a compact polytope. The difference between problems (2.1) and (2.2) is the presence of the bounded uncertain parameters in the constraints. As a result, the solution , the Lagrange multipliers and , and the optimal objective function of problem (2.2) are obtained as a function of , i.e. , , , and , respectively. A schematic representation of the difference between problem (2.1) and (2.2) is shown in Figure 2.1.

Figure 2.2 shows some of the properties of the solution of the mpLP problem 2.2.

      Remark 2.1

      Note that it is possible to add a scalar to the objective function of an LP problem without influencing the optimal solution. Similarly, it is possible to add an arbitrary scaling function to an mp‐LP problem without influencing the optimal solution.

Figure 2.1 The difference between the solution of an LP and an mp‐LP problem (black dot and line, respectively), where the mp‐LP problem is obtained by treating as a parameter. In (a), the solution is a single point in one of the vertices of the feasible space, while in (b) the solution is a function of the parameter .

2.1 Solution Properties

      Remark 2.2

Due to the similarities between mp‐LP and multi‐parametric quadratic programming (mp-QP) problems, the different solution strategies available are discussed in detail in Chapter 4.

Figure 2.2 A schematic representation of the solution of the mp‐LP problem from Figure