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

Lastly, it is important to highlight that the impact of degeneracy on mp‐LP problems goes beyond the derivation of more sophisticated solution strategies. In fact, the presence of primal and dual degeneracy can be directly linked to the optimality conditions required for the calculation of the parametric solution. In the following text, each optimality condition required for the basic sensitivity theorem is revisited with the consideration of the presence of degeneracy.

 Second‐order sufficient conditions (SOSC): This condition states that the second derivative of the Lagrange function with respect to the optimization variables has to be positive semi‐definite. For mp‐LP (and convex mp‐QP) problems, this condition is naturally satisfied.

 Linear Independence Constraint Qualification (LICQ): This condition states that the matrix in Eq. (2.4a) has to have rank , i.e. there cannot be linearly dependent constraints within the active set. Consider now the case of primal degeneracy, where the number of candidate constraints for the active set , i.e. more than constraints are active at the optimal solution. Clearly, the matrix cannot have full rank, since the maximum rank is as . As a result, the occurrence of primal degeneracy can be viewed as a LICQ violation at the optimal solution.

 Strict Complementary Slackness (SCS): This condition states that there cannot exist a constraint such that and . In particular, consider that the Lagrange multiplier can be viewed as a “cost” incurred in the objective function when moving along a given constraint. However, dual degeneracy inherently implies that there are multiple points along the same constraints that have the same optimal objective function and thus, this “cost” is equal to 0 (see Figure 2.4 b). Hence, the presence of dual degeneracy is directly linked to the violation of the SCS property, as dual degeneracy implies that there exists at least one constraint such that and .