Sublinear upper bounds for stochastic programs with recourse (Q1115346)

Consider the stochastic linear program with recourse: find \(x\in R^ n\), \(\chi \in R^ m\) such that \(Ax=b\), \(Tx-\chi =0\), \(x\geq 0\) and \(cx+E\psi (\chi,\xi)\) is minimized where \[ \psi (\chi,\xi)=\inf_{y\geq 0}\{qy| \quad Wy=\xi -\chi \}. \] Let \(e_ i\) be the i-th unit m- vector. Then solutions of linear programs \(\min_{y\geq 0}\{qy|\) \(Wy=e_ i\}\) give us an approximation of the initial problem by simple recourse vectors. In this paper, using other bases then \(\pm e_ i\), the sublinear (positively homogeneous and convex) approximations of \(\psi\) are presented (for example, let \(D=\{d_ 1\),..., \(d_ m\}\) be a linear basis such that pos[D, \(-D]=R^ m)\). Such linear transformations of random vectors can be used to obtain a variety of separable, sublinear bounding functions. These sublinear approximations are solved using their duals. Computational results are presented.