2.1. In (a), the partitioning of the convex, feasible parameter space
, as well as the piecewise affine nature of the optimal solution
and the convex and piecewise affine nature of the objective function
is shown. In (b), the Lagrange multipliers
as a function of
are shown.
2.1.1 Local Properties
Consider a fixed, nominal point , which transforms the mp‐LP problem (2.2) into an LP problem of type (2.1). The solution of this LP problem at yields the solution as well as the values of the Lagrange multipliers . Based on these, the indices of the active set are identified:
(2.3a)
(2.3b)
Remark 2.3
In the case where the set from Eq. (2.3) is not unique, the solution is said to be degenerate. The impact of degeneracy on the parametric solution is discussed in Chapter 2.2.
Together with the equality constraints, which have to be satisfied for any , the following active set matrices and vectors are defined:
(2.4a)
(2.4b)
(2.4c)
Note that has to have full rank in order to fulfill the LICQ condition described in Chapter 1. Since the objective function is linear and the constraints are affine, the change of the solution of problem (2.2) based on the basic sensitivity theorem is given by2:
(2.5a)
(2.5b)
(2.5c)
Based on Eq. (2.5), the following statements regarding the solution around can be made:
The optimization variables are affine functions of the parameter .
In the case of mp‐LP problems, the values of the Lagrange multipliers and do not change as a function of around a nominal point .
The square matrix is invertible since the SCS and LICQ conditions of Chapter 1 have to hold.
In order for Eq. (2.5) to remain the optimal solution around a nominal point , it needs to be feasible, i.e.(2.6a) (2.6b) Note that since the values of the Lagrange multipliers do not change as a function of , the optimality requirement from the Karush‐Kuhn‐Tucker conditions can be omitted from the construction of the feasible region.
Thus, the optimal solution of problem (2.2) around is given by Eq. (2.5) and is valid in the compact polytope described by Eq. (2.6), which is referred to as critical region:
(2.7)
Based on Eq. (2.7), the following Lemmata result:
Lemma 2.1
Every critical region is uniquely defined by its active set.
Proof
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.
Lemma 2.2
The maximum number of critical regions, , for problem 2.2 is given by
(2.8)
Proof
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 ,
