Эротические рассказы

Multi-parametric Optimization and Control. Efstratios N. PistikopoulosЧитать онлайн книгу.

Multi-parametric Optimization and Control - Efstratios N. Pistikopoulos


Скачать книгу
rel="nofollow" href="#fb3_img_img_224c3da8-2c59-5f72-95f9-057af5b5cf46.png" alt="images"/> is a valid solution of the LP problem at images, the key challenge is to identify the effect of primal and dual degeneracy onto the solution of the mp‐LP problem.

      2.2.1 Primal Degeneracy

      2.2.2 Dual Degeneracy

      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 images differ, the presence of dual degeneracy might eliminate the continuous nature of the optimizer described in Theorem 2.1.

      Remark 2.4

      Dual degeneracy results from the non‐uniqueness of the optimal solution images. 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.

      2.2.3 Connections Between Degeneracy and Optimality Conditions

      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 .

      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


Скачать книгу
Яндекс.Метрика