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

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.

However, in order to generate continuous optimizers as well as non‐overlapping critical regions, three different approaches have been developed:

 Reformulation to an mp‐QP problem [1]: The key idea is to reformulate the mp‐LP problem (2.2) into an mp‐QP problem (3.2), which yields the same solution at the considered point. Since mp‐QP problems do not encounter dual degeneracy due to the inherently unique nature of their optimizers, the continuity of the optimizer can be guaranteed.

 Graph/Cluster evaluation [2,3]: In [2], it was shown that the solution to an mp‐LP problem is given by a connected graph, where the nodes are the different active sets and the connections are given by the application of a single step of the dual simplex algorithm. In addition, [3] considers the dual of the mp‐LP problem as a parametrized vertex problem and identifies clusters of connected vertices equivalent to the connections in [2]. When dual degeneracy occurs, multiple disconnected graphs/clusters can occur, only some of which may represent the continuous solution of the mp‐LP problem across the entire feasible parameter space [3].

 Lexicographic perturbation [4]: The problem of dual‐degeneracy only arises because of the specific numerical structure of the objective function and the constraints. In order to overcome the degeneracy, the right‐hand side of the constraints as well as the objective function are symbolically perturbed in order to obtain a single, continuous optimizer for the solution of the mp‐LP problem. Note that the problem is not actually perturbed, but only the result of a proposed perturbation is analyzed enabling the formulation of a continuous optimizer.