Content deleted Content added
m Robot - Moving category Optimization to Mathematical optimization per CFD at Wikipedia:Categories for discussion/Log/2008 August 14. |
minimax |
||
Line 11:
where f is a function that measures the cost of the policy, P is a penalty function, and w > 0 (a parameter to trade off the cost of infeasibility). One example of f is the expected value: <math>\ f(x, y) = cx + \sum_s{d(s)y(s)p(s)}</math>, where p(s) = probability of scenario s. In a worst-case model, <math>\ f(x,y) = \max_s{d(s)y(s)}</math>. The '''penalty function''' is defined to be zero if (x, y) is feasible (for all scenarios) -- i.e., P(0)=0. In addition, P satisfies a form of monotonicity: worse violations incur greater penalty. This often has the form <math>\ P(z) = U(z^+) + V(-z^-)</math> -- i.e., the "up" and "down" penalties, where U and V are strictly increasing functions.
The above makes robust optimization similar (at least in the model) to a [[goal program]]. Recently, the robust optimization community defines it differently – it optimizes for the worst-case scenario, as in [[minimax]]. Let the uncertain MP be given by
:<math>\min f(x; s): x \in X(s),</math>
Line 18:
:<math>\min_x {\max_{s \in S} f(x; s)}\, x \in X(t)\, \forall t \in S,</math>
The policy (x) is required to be feasible no matter what parameter value (scenario) occurs; hence, it is required to be in the intersection of all possible X(s). The inner maximization yields the worst possible objective value among all scenarios. There are variations, such as "adjustability" (i.e., recourse).
== References==
| |||