Efstratios N. Pistikopoulos - Multi-parametric Optimization and Control

(2.7)

Based on Eq. (2.7), the following Lemmata result:

Every critical region is uniquely defined by its active set.

By inspection of Eq. (2.7), it is clear that the differences between any two critical regions are the values of , , and , respectively, which only depend on the active set . Thus, the set of active constraints uniquely defines the critical region , which completes the proof.

The maximum number of critical regions, , for problem 2.2is given by

(2.8)

Consider . Then an optimal solution of the resulting LP problem is guaranteed to lie in a vertex, thus featuring active constraints. However, as the equality constraints have to be fulfilled for all , the number of active inequality constraints is given by , where is the number of equality constraints. As the number of critical regions is uniquely defined by the active set, it is bound by above by all possible combinations of active sets, which is given by , which completes the proof.

The solution properties described in Chapter 2.1.1hold for any feasible point and thus the following theorem can be formulated:

Consider the mp‐LP problem ( 2.2). Then the set of feasible parameters is convex, the optimizer is continuous and piecewise affine, and the optimal objective function is continuous, convex, and piecewise affine.

The two key statements that need to be proven are the convexity of and . Consider two generic parameter values and let , and and be the corresponding optimal objective function values and optimizers. Additionally, let and define and . Then, since , , and are feasible and satisfy the constraints and . As these constraints are affine, they can be linearly combined to obtain , and therefore is feasible for the optimization problem ( 2.2). Since a feasible solution exists at , an optimal solution exists at and thus is convex.