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

In linear programming (LP), the term “basic solution” is a result of the use of the simplex algorithm and identifies the solution as a vertex of the feasible space, which is uniquely defined by the indices of the constraints that form the vertex. However, with the emergence of interior‐point methods, as well as in the face of degeneracy, it cannot be guaranteed that the solution obtained from an LP solver is a basic solution leading to a full‐dimensional critical region. As the classical definition of the critical region is directly tied to the active set (i.e. the indices of the constraints that form the vertex), alternative definitions of critical regions have been considered.

The main theme is thereby to identify an appropriate invariancy set over the parametric space. The three sets typically considered are the following [5]:

 Optimal basis invariancy [6]: This invariancy refers to the classical definition of the critical region as a set of active constraints that form a basic solution. The main issue with this approach occurs in the case of degeneracy (see section 2.2), which might lead to lower‐dimensional or overlapping regions.

 Support set invariancy [7–9]: Given the LP problem formulation(2.14) the support set is defined as . The concept of support set invariancy describes the region of the parameter space for which the same support set remains optimal. It can be shown that this eliminates the issue of degeneracy, as the support set is independent of the active constraints.

 Optimal partition invariancy [8, 10–12]: The optimal partition is given by the cone, which is spanned from the solution found in the directions of the inactive constraints.