where each vector , corresponds to a particular “scenario”.
The robust counterpart to a half-space constraint:
can be simply expressed as a set of affine inequalities:
Note that the scenario model actually enforces more than feasibility at the “scenario” points . In fact, for any that is in the convex hull of the set , the robust counterpart holds. Indeed, if the above holds, then for any set of nonnegative weights summing to one, we have
With a scenario uncertainty, the robust counterpart to the original LP:
with , , becomes
This is an LP, with a total of constraints, where is the number of elements in the finite set , and is the number of constraints in the original (nominal) LP.
The scenario model is attractive for its simplicity. However, the number of scenarios can result in too large a problem.
A robust half-space constraint with scenario uncertainty, with three scenarios. The constraint represents a polyhedron (dark blue).
where is a measure of the size of the uncertainty, and represents a ‘‘nominal’’ vector. This describes a ‘‘box’’ of half-diameter around the center .
Note that the robust counterpart to a half-space constraint
can be handled as a scenario model, with “scenarios” the vectors , where represents one of the vertices of the unit box (that is, vectors with 's as components). Indeed, enforcing the constraint implies that holds for every in the convex hull of the 's, which is precisely the box . This approach is not practical, as there are an exponential number of vertices, hence of constraints, to deal with.
The maximization problem has a simple form (proof):
A robust half-space constraint with box uncertainty, with different uncertainty levels. Such sets can be described by a finite (but exponential in the dimension) number of inequalities.
With a box uncertainty model, defined as , , the robust counterpart to the original LP:
is also an LP (in polyhedral form)
A robust LP with box uncertainty. The robust feasible set (darker blue) is inside the feasible set for the nominal LP (lighter blue); both feasible sets are polyhedral. The objective is to minimize , where the vector is shown. The nominal LP has many optimal points (red line), which means a solution might be very sensitive to data changes (such as if we change the direction of the objective slightly). Although in this case, the roubst LP has a unique solution (red dot), it is still an LP, so it might be sensitive to changes in the objective vector.
where is a matrix which describes the “shape” of the ellipsoid around its center, which is . If for some , then the above is a simple sphere of radius around ; we refer to this special case as the spherical uncertainty model.
Ellipsoidal uncertainty models are useful to “couple” uncertainties across different components of the coefficient vector . This is contrast with the previous ‘‘box’’ models, which allow uncertainties to take their largest values independently of each other.
A robust half-space constraint with spherical uncertainty, with different uncertainty levels.
With an ellipsoidal uncertainty model, defined as , , the robust counterpart to the original LP:
becomes an SOCP:
A robust LP with spherical uncertainty. The robust feasible set (darker blue) is inside the (polyhedral) feasible set for the nominal LP (lighter blue). The objective is to minimize , where the vector is shown. The nominal LP has many optimal points (red line), which means a solution might be very sensitive to data changes (such as if we change the direction of the objective slightly). In constrast, the solution to the robust LP is unique (red dot), irrespective of the choice of the objective. As a result, it not very sensitive to changes in the objective or other problem data.