Robust two-stage stochastic linear programs with moment constraints

Abstract

We consider the two-stage stochastic linear programming model, in which the recourse function is a worst case expected value over a set of probabilistic distributions. These distributions share the same first- and second-order moments. By using duality of semi-infinite programming and assuming knowledge on extreme points of the dual polyhedron of the constraints, we show that a deterministic equivalence of the two-stage problem is a second-order cone optimization problem. Numerical examples are presented to show non-conservativeness and computational advantage of this approach.

Keywords:

• second-order cone optimization
• stochastic programming

AMS Subject Classifications:

• 90B50
• 90C15

Notes

This paper is dedicated to Professor Minyi Yue of Chinese Academy of Science in celebration of his 90th birthday.

1 The conditions ensuring such strong duality can be found in Anderson and Nash [6].

2 This is a slightly different version of Example 7.3 in the book of Bertsimas and Freund [7].

3 Our model extends the uncertainty set from the one in Ang et al. [3] toHence, the dual form has one extra non-negativity constraint,compared with that in Ang et al. [3]. When we conduct the numerical experiment following the formulation in Ang et al. [3], we add this non-negativity constraint to their original SOCP formulation. Therefore, different numerical result is obtained here (not but ) with exact same formulation method taken.

Research is partially supported by The Provost’s Chair Grant at National University of Singapore, the National Basic Research Program of China [grant number 2010CB732501]; the National Natural Science Foundation of China [grant number 11171018].