Название: Multi-parametric Optimization and Control
Автор: Efstratios N. Pistikopoulos
Издательство: John Wiley & Sons Limited
Жанр: Математика
isbn: 9781119265191
isbn:
(2.9a)
(2.9b)
i.e. ,
,
. This proves the convexity of
and
. The piecewise affine nature of
and
is a direct result from the fact that the boundary between two regions belongs to both regions. Since the optimum is unique, the optimizer and thus the optimal objective function value must be continuous across the boundary.
In addition to the fundamental properties derived in Theorem 2.1, it is possible to infer more structural information about the connections between the critical regions:
Let each active set of an mp‐LP problem be a node in the set of solutions
. Then the nodes
and
are connected if (i) there exists a
such that
and
are both optimal active sets and (ii) it is possible to pass from
to
by one step of the dual simplex algorithm. The resulting graph
is fully defined by the nodes
as well as all connections
, i.e.
.
Theorem 2.2 (The Connected‐graph Theorem)
Consider the solution to an mp‐LP problem and let ,
be two arbitrary feasible parameters and
be given such that
. Then there exists a path
in the mp‐LP graph
such that
.
Proof
Consider the line segment joining and
, i.e.
(2.10)
Based on Theorem 2.1, , as
is convex. Setting
in the mp‐LP problem (2.2) converts the original mp‐LP problem into a parametric linear programming (p‐LP) problem. The solution of this p‐LP problem is given by a series of line segments that are connected as the union constitutes the feasible parameter space
and is convex based on Theorem 2.1. Based on Eq. (2.6), the limits of each line segment result from the violation of a currently inactive constraint for the parametric solution of that line segment, as all the active constraints are satisfied by definition. Thus, in order to move beyond these limits, the violated constraint needs to be considered as an active constraint, i.e. a step of the dual simplex algorithm needs to be performed. This results in a new active set, and by extension in a sequence of active sets that correspond to the path
in the mp‐LP graph
.
In order to visualize the concept described in Theorem 2.2, Figure 2.3 shows a schematic representation of a connected graph for an mp‐LP problem.
Figure 2.3 A 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. “
СКАЧАТЬ