Efstratios N. Pistikopoulos - Multi-parametric Optimization and Control

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

Figure 2.3A 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.2is 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.

The properties described in the previous section are based on the assumption that the active set of the LP problem solved at is unique. This uniqueness can only be guaranteed if the solution of the LP problem is non‐degenerate. In general, degeneracy refers to the situation where the LP problem under consideration has a specific structure, which does not allow for the unique identification of the active set . 3Commonly, the two types of degeneracy encountered are primal and dual degeneracy (see Figure 2.4):

Primal degeneracy: In this case, the vertex of the optimal solution of the LP is overdefined, i.e. there exist multiple sets such that(2.11) where, based on Eq. (2.3a): (2.12)

Dual degeneracy: If there exists more than one point, which attains the optimal objective function value, then the optimal solution is not unique. Thus, there exist multiple sets with such that(2.13) where . Note that as shown in Figure 2.4, the solution of the problem does not necessarily have to be a vertex, and thus, Eq. (2.12) does not have to hold.

Figure 2.4Primal and dual degeneracy in linear programming. In (a), primal degeneracy occurs since there are three constraints that are active at the solution, while in (b) dual degeneracy occurs since there is more than one point , which features the optimal objective function value.

While any solution is a valid solution of the LP problem at , the key challenge is to identify the effect of primal and dual degeneracy onto the solution of the mp‐LP problem.

Primal degeneracy is caused by the presence of weakly redundant constraints, i.e. constraints that are redundant yet intersect with the feasible parameter space (see Chapter 1.3). In particular, the space where the weakly redundant constraints hold as equality is lower‐dimensional with respect to the overall feasible parameter space. Thus, it is clear that if any weakly redundant constraint is chosen as an element of the active set, then the resulting critical region will be lower‐dimensional. 4As a consequence, from all possible combinations of active sets at a given solution, only one active set exists, which results in a full‐dimensional critical region, which does not feature any weakly redundant constraints. In the case of Figure 2.4, . Note that the presence of a lower‐dimensional critical region can be detected by calculating the radius of the Chebyshev ball (see Chapter 1.3).

In general, the effect of primal degeneracy onto the solution of mp‐LP problems is manageable, since it can be detected by solving a single LP problem for each candidate active set combination. However, dual degeneracy is much more challenging as the different active sets may result in full‐dimensional, but overlapping, critical regions. In particular since the optimal solutions differ, the presence of dual degeneracy might eliminate the continuous nature of the optimizer described in Theorem 2.1.

Dual degeneracy results from the non‐uniqueness of the optimal solution . This in turn can only occur, since LP problems are not strictly convex, and thus the minimizer is not guaranteed to be unique. Thus, dual degeneracy is not encountered for strictly convex problems such as strictly convex multi‐parametric quadratic programming (mp‐QP) problems.