Читать книгу Multi-parametric Optimization and Control - Efstratios N. Pistikopoulos - Страница 65

Consider the line segment joining and , i.e.

(2.10)

Based on Theorem 2.1, , as is convex. Setting in the mp‐LP problem (2.2) converts the original mp‐LP problem into a parametric linear programming (p‐LP) problem. The solution of this p‐LP problem is given by a series of line segments that are connected as the union constitutes the feasible parameter space and is convex based on Theorem 2.1. Based on Eq. (2.6), the limits of each line segment result from the violation of a currently inactive constraint for the parametric solution of that line segment, as all the active constraints are satisfied by definition. Thus, in order to move beyond these limits, the violated constraint needs to be considered as an active constraint, i.e. a step of the dual simplex algorithm needs to be performed. This results in a new active set, and by extension in a sequence of active sets that correspond to the path in the mp‐LP graph .

In order to visualize the concept described in Theorem 2.2, Figure 2.3 shows a schematic representation of a connected graph for an mp‐LP problem.

Figure 2.3 A schematic representation of the connected‐graph theorem, (a) from a geometrical viewpoint, i.e. considering the a geometric interpretation of the feasible parameter space , and (b) from an active set viewpoint, where the dual pivot can be identified in the transition between the active sets associated with the critical regions. Note that although and have the point in common, i.e. “ and are both optimal active sets” (Definition 2.1), it is not possible to pass from to in a single step of the dual simplex algorithm. Thus, and are not connected.

The proof of Theorem 2.2 is based on the statement that only a single currently inactive constraint limits the solution of the p‐LP problem resulting from the substitution of the parametrized line segment joining and . However, in the case of degeneracy or identical constraints, this may not necessarily be the case. While the case of identical constraints can be handled directly, the issue of degeneracy has to be considered in more detail and is discussed in Chapter 2.2.