Multi-parametric Optimization and Control. Efstratios N. Pistikopoulos

and . The first‐order Taylor expansion of the vector F around can be expressed as follows:

      (1.20)

Under the assumptions and the principles of the Basic Sensitivity Theorem, in a neighborhood of the first‐order KKT conditions hold and the value of F() around remains zero. For systems that consist of polynomial objective functions of up to second degree and linear constraints, with respect to the optimization variables and the uncertain parameters, the first‐order Taylor expansion is exact. Hence, the exact multi‐parametric solution can be obtained for the following multi‐parametric quadratic programming problem

      (1.21)

      where matrices , and , , and the scalars , correspond to the and inequality and equality constraints of the sets and , respectively. This problem serves as the basis that will be discussed in Part I, where its solution properties and solution strategies among other things are in focus. Part II then focusses on the application of such problems to optimal control, as the use of parameters enables the formulation of explicit model predictive control problems.

1.3 Polytopes

      Multi‐parametric programming is intimately related to the properties and operations applicable to polytopes. In the following, some basic definitions on polytopes are stated, which are used throughout the book.

      Definition 1.9

      A function , where is a polytope, is called piecewise affine if it is possible to partition into disjoint polytopes, called critical regions, and

      (1.22)

      Remark 1.2 The definition of piecewise quadratic is analogous.

Definition 1.10

      The set is called a ‐dimensional polytope if it satisfies

(1.23)

      where is finite.

A schematic representation of a polytope is given in Figure 1.1.

Figure 1.1 A schematic representation of a two‐dimensional polytope

.

In addition to Definition (1.10), the following well‐known characteristics of polytopes are considered:

       A polytope is called bounded if and only if there exists a finite and such for all .

       A polytope, which is closed and bounded, is called compact.

       Let be an ‐dimensional polytope. Then, a subset of a polytope is called a face of if it can be represented as(1.24) for some inequality , which holds for all . The faces of polytopes of dimension , 1, and 0 are referred to as facets, edges, and vertices, respectively.

       Two polytopes and are called disjoint if . Similarly, two polytopes and are called overlapping if . Lastly, two polytopes and are called adjacent or neighboring if is a ‐dimensional polytope.

       Let and be two adjacent polytopes. Then the facet‐to‐facet property is said to hold if is a facet of both and (see Figure 1.2 for an illustration).

       Let be an ‐dimensional polytope. Then, there exists a series of vertices such that(1.25)

       Eq. (1.23) is referred to the halfspace (or H) representation, while Eq. (1.25) denotes the vertex (or V) representation. The process of moving from the halfspace to the vertex representation is referred to as vertex enumeration.

       The Chebyshev center of a polytope is given as the largest Euclidean ball that lies in a polytope [2]. It can be determined by solving the following linear programming (LP) problem:(1.26) where the solution denotes the radius of the largest Euclidean ball. Based on the solution of problem (1.26), the following conclusions can be drawn:– Problem (1.26) is infeasible: The polytope is empty.– : The polytope is lower‐dimensional.– : The polytope is full‐dimensional.

Figure 1.2 A schematic representation of the differences between two polytopes and (a), which are adjacent and (b) where the facet‐to‐facet property holds. Clearly,