Groupe d’études et de recherche en analyse des décisions

Approximation schemes for distributionally robust optimization

Huifu Xu University of Southampton, Royaume-Uni

We consider a class of stochastic programming problems where the true probability distribution is unknown but it is possible to use some partial information such as empirical data, computer simulation and/or subjective judgement to construct an ambiguity set of distributions which contains the true probability distribution with specified confidence.

The optimal decision is consequently based on the worst probability distribution from the ambiguity set to mitigate the risk arising from ambiguity of the true distribution.

The approach is known as distributionally robust optimisation (DRO) which has received increasing attention over the past decade. Differing from the mainstream research on DRO which focuses on tractable reformulation of DRO as a convex semi-definite programming (SDP) problem, we concentrate on approximation schemes for DRO whereby the approximation may come from the process of constructing the ambiguity set or from computational need where reformulation of DRO as SDP is impossible and discretisation becomes only effective alternative. We look into various theoretical and computational issues including quantification of uncertainty, qualitative and quantitative stability analysis of the optimal value and optimisation solutions for one stage DRO problems and mathematical programs with distributionally robust chance constraints, and efficient numerical methods. In particular, we propose two discretization schemes for solving the DRO with one for the dualized DRO and the other directly through the ambiguity set of the DRO. In the absence of strong duality, the discretization scheme via Lagrange duality may provide an upper bound for the optimal value of the DRO whereas the direct discretization approach provides a lower bound. Two cutting plane schemes are consequently proposed: one for the discretized dualized DRO and the other for the minimax DRO with discretized ambiguity set. Convergence analysis is presented for the approximation schemes in terms of the optimal value, the optimal solutions and the stationary points under Wasserstein/Kantorovich metric. Comparative numerical results are reported for the resulting algorithms and a case study on capacity outsourcing problem is given to illustrate how robustness affect buyer and supplier's profit in semiconductor manufacturing markets.

Entrée gratuite.
Bienvenue à tous!