RANDOMIZED PROGRAM

Randomized program - A randomized policy is a distribution over the policy set, X, that describes a policy as a random variable. This is not restricted to stochastic programs . The randomized form is called a randomized program, and it is the following semi-infinite program in response space :

where W = (w: X-->[0, 1]:w(x) > 0 for finitely many x in X, and Sum_x(w(x))=1). In this form, the randomized program is an ordinary linear program if X is finite. More generally, the definition of W renders the summations well defined. One could interpret w as a randomized policy: use x with probability w(x). A pure strategy is when w(x*)=1 for some x* (so w(x)=0 for x not= x*); otherwise, w is called a mixed strategy. One key fact is that the solutions to the original mathematical program (in standard form ) correspond to pure strategies in this randomized form. Further, a key to the Lagrangian Strong Duality Theorem is that every mixed strategy is dominated by a pure strategy. Moreover, this underlies the Generalized Lagrange Multiplier method , and there is no loss in optimality to restrict mixed strategies to satisfy the Haar condition: |(x: w(x) > 0) | <= m+1.