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.
2.1.2 Global Properties
The solution properties described in Chapter 2.1.1 hold for any feasible point and thus the following theorem can be formulated:
Theorem 2.1 (The Solution of mp‐LP Problems)
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.
Proof
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.
The optimal solution at will be less than or equal to the feasible solution, i.e. and thus:
(2.9a)
(2.9b)
i.e. , , . This proves the convexity of and . The piecewise affine nature of and is a direct result from the fact that the boundary between two regions belongs to both regions. Since the optimum is unique, the optimizer and thus the optimal objective function value must be continuous across the boundary.
In addition to the fundamental properties derived in Theorem 2.1, it is possible to infer more structural information about the connections between the critical regions:
Definition 2.1 (mp‐LP Graph)
Let each active set of an mp‐LP problem be a node in the set of solutions . Then the nodes and are connected if (i) there exists a such that and are both optimal active sets and (ii) it is possible to pass from to by one step of the dual simplex algorithm. The resulting graph is fully defined by the nodes as well as all connections , i.e. .
Theorem 2.2 (The Connected‐graph Theorem)
Consider the solution to an mp‐LP problem and
