On the implementation of a log-barrier progressive hedging method for multistage stochastic programs.

*(English)*Zbl 1189.65127Summary: A progressive hedging method incorporated with self-concordant barrier for solving multistage stochastic programs is proposed recently by G. Zhao [Math. Program. 102, No. 1, 1–24 (2005)]. The method relaxes the nonanticipativity constraints by the Lagrangian dual approach and smoothes the Lagrangian dual function by self-concordant barrier functions. The convergence and polynomial-time complexity of the method have been established. Although the analysis is done on stochastic convex programming, the method can be applied to the nonconvex situation.

We discuss some details on the implementation of this method including when to terminate the solution of unconstrained subproblems with special structure and how to perform a line search procedure for a new dual estimate effectively. In particular, the method is used to solve some multistage stochastic nonlinear test problems. The collection of test problems also contains two practical examples from the literature. We report the results of our preliminary numerical experiments. As a comparison, we also solve all test problems by the well-known progressive hedging method.

We discuss some details on the implementation of this method including when to terminate the solution of unconstrained subproblems with special structure and how to perform a line search procedure for a new dual estimate effectively. In particular, the method is used to solve some multistage stochastic nonlinear test problems. The collection of test problems also contains two practical examples from the literature. We report the results of our preliminary numerical experiments. As a comparison, we also solve all test problems by the well-known progressive hedging method.

##### Keywords:

progressive hedging method; multistage stochastic programs; Lagrangian dual; log-barrier method; numerical experiments; polynomial-time complexity##### Software:

MSLiP
PDF
BibTeX
XML
Cite

\textit{X. Liu} et al., J. Comput. Appl. Math. 234, No. 2, 579--592 (2010; Zbl 1189.65127)

Full Text:
DOI

##### References:

[1] | Birge, J.R.; Louveaux, F., Introduction to stochastic programming, (1997), Springer-Verlag · Zbl 0892.90142 |

[2] | Kall, P.; Wallace, S.W., Stochastic programming, (1994), John Wiley & Sons NY · Zbl 0812.90122 |

[3] | Berkelaar, A.; Dert, C.; Oldenkamp, B.; Zhang, S., A primal-dual decomposition-based interior point approach to two-stage stochastic linear programming, Oper. res., 50, 904-915, (2002) · Zbl 1163.90679 |

[4] | J.R. Birge, Current trends in stochastic programming computation and applications, Technical Report 95-15, Department of Industrial and Operations Engineering, University of Michigan, 1995 |

[5] | Gassmann, H.I., Mslip: A computer code for the multistage stochastic linear programming problem, Math. program., 47, 407-423, (1990) · Zbl 0701.90070 |

[6] | Mayer, J., Stochastic linear programming algorithms: A comparison based on a model management system, (1998), Gordon and Breach Science Publishers · Zbl 0966.90056 |

[7] | Ruszczyński, A., Some advances in decomposition methods for stochastic linear programming, Stochastic programming, state of the art, 1998 (Vancouver, BC), Ann. oper. res., 85, 153-172, (1999) · Zbl 0919.90119 |

[8] | Sun, J.; Liu, X., Scenario formulation of stochastic linear programs and the homogeneous self-dual interior point method, INFORMS J. comput., 18, 444-454, (2006) · Zbl 1241.90096 |

[9] | Zhao, G., Interior-point methods with decomposition for solving large-scale linear programs, J. optim. theory appl., 102, 169-192, (1999) · Zbl 0974.90028 |

[10] | Zhao, G., A log-barrier method with benders decomposition for solving two-stage stochastic programs, Math. program., 90, 507-536, (2001) · Zbl 1023.90045 |

[11] | Rockafellar, R.T.; Wets, R.J.-B., Scenarios and policy aggregation in optimization under uncertainty, Math. oper. res., 16, 119-147, (1991) · Zbl 0729.90067 |

[12] | Berland, N.J.; Haugen, K.K., Mixing stochastic dynamic programming and scenario aggregation, Stochastic programming, algorithms and models (lillehammer, 1994), Ann. oper. res., 64, 1-19, (1996) · Zbl 0854.90104 |

[13] | Mulvey, J.M.; Vladimirou, H., Applying the progressive hedging algorithm to stochastic generalized networks, Ann. oper. res., 31, 399-424, (1991) · Zbl 0734.90033 |

[14] | Helgason, T.; Wallace, S.W., Approximate scenario solutions in the progressive hedging algorithm, Ann. oper. res., 31, 425-444, (1991) · Zbl 0739.90047 |

[15] | Chun, B.J.; Robinson, S.M., Scenario analysis via bundle decomposition, Ann. oper. res., 56, 39-63, (1995) · Zbl 0838.90088 |

[16] | Ruszczyński, A., Parallel decomposition of multistage stochastic programming problems, Math. program., 58, 201-228, (1993) · Zbl 0777.90036 |

[17] | Ruszczyński, A., On convergence of an augmented Lagrangian decomposition method for sparse convex optimization, Math. oper. res., 20, 634-656, (1995) · Zbl 0845.90098 |

[18] | Liu, X.; Fukushima, M., Parallelizable preprocessing method for multistage stochastic programming problems, J. optim. theory appl., 131, 327-346, (2006) · Zbl 1139.90019 |

[19] | Liu, X.; Zhao, G., A decomposition method based on SQP for a class of multistage stochastic nonlinear programs, SIAM J. optim., 14, 200-222, (2003) · Zbl 1043.90058 |

[20] | Zhao, G., A Lagrangian dual method with self-concordant barrier for multi-stage stochastic convex nonlinear programming, Math. program., 102, 1-24, (2005) · Zbl 1058.90043 |

[21] | Birge, J.R.; Dempster, M.A.H.; Gassmann, H.I.; Gunn, E.A.; King, A.J.; Wallace, S.W., A standard input format for multistage stochastic linear programs, COAL newsl., 17, 1-19, (1987) |

[22] | Peters, R.J.; Boskma, K.; Kuper, H.A.E., Stochastic programming in production planning: A case with non-simple recourse, Statist. neerlandica, 31, 113-126, (1977) · Zbl 0362.90048 |

[23] | King, A.J., Stochastic programming problems: examples from the literature, (), 543-567 · Zbl 0661.90069 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.