Motivations and Standard Forms
The uncertainty problemData uncertaintyConsider the linear program in inequality form: ![]() In practice, the data of the linear program (contained in the vectors Example: Uncertainty in the drug production problem. Implementation errorsUncertainty can originate also from implementation errors. Often, the optimal variable In an antenna array design problem for example, the optimal antenna weights are in reality characteristics of certain physical devices and as such cannot be implemented exactly as they are computed via the optimization model. Or, in a manufacturing process, the planned production amounts are never exactly implemented due to, say, production plant failures. Implementation errors can result in catastrophic behavior, in the sense that when the optimal variable Example: Antenna array design with relative implementation error. Robust optimization approachMain ideaIn robust optimization, we assume that the data in the LP is not exactly known. We postulate that a model of uncertainty is known. In its simplest version, we assume that the Robust counterpartThe robust counterpart to the original LP above is defined as follows. ![]() The interpretation of the above problem is that it attempts to find a solution that is feasible, independent of the particular choice of the coefficient vectors The robust counterpart is always convex, independent of the shape of the sets of confidence For some classes of uncertainty sets Robust half-space constraintsThe feasible set of the robust counterpart is the intersection of single constraints called robust half-space constraints. Given a subset ![]() is called a robust half-space constraint. The condition is always convex, irrespective of the choice of the set To analyze a robust half-space constraint, the main idea is to formulate it in terms of an optimization problem, as ![]() For some choices of |