A class of polynomial volumetric barrier decomposition algorithms for stochastic semidefinite programming

Ariyawansa, K.; Zhu, Yuntao

doi:10.1090/S0025-5718-2010-02449-4

A class of polynomial volumetric barrier decomposition algorithms for stochastic semidefinite programming
HTML articles powered by AMS MathViewer

by K. A. Ariyawansa and Yuntao Zhu;

Math. Comp. 80 (2011), 1639-1661

DOI: https://doi.org/10.1090/S0025-5718-2010-02449-4

Published electronically: December 16, 2010

PDF | Request permission

Abstract:

Ariyawansa and Zhu have recently proposed a new class of optimization problems termed stochastic semidefinite programs (SSDPs). SSDPs may be viewed as an extension of two-stage stochastic (linear) programs with recourse (SLPs). Zhao has derived a decomposition algorithm for SLPs based on a logarithmic barrier and proved its polynomial complexity. Mehrotra and Özevin have extended the work of Zhao to the case of SSDPs to derive a polynomial logarithmic barrier decomposition algorithm for SSDPs. An alternative to the logarithmic barrier is the volumetric barrier of Vaidya. There is no work based on the volumetric barrier analogous to that of Zhao for SLPs or to the work of Mehrotra and Özevin for SSDPs. The purpose of this paper is to derive a class of volumetric barrier decomposition algorithms for SSDPs, and to prove polynomial complexity of certain members of the class.

References

Farid Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim. 5 (1995), no. 1, 13–51. MR 1315703, DOI 10.1137/0805002
Kurt M. Anstreicher, On Vaidya’s volumetric cutting plane method for convex programming, Math. Oper. Res. 22 (1997), no. 1, 63–89. MR 1436574, DOI 10.1287/moor.22.1.63
Kurt M. Anstreicher, Volumetric path following algorithms for linear programming, Math. Programming 76 (1997), no. 1, Ser. B, 245–263. Interior point methods in theory and practice (Iowa City, IA, 1994). MR 1426406, DOI 10.1016/S0025-5610(96)00042-1
Kurt M. Anstreicher, The volumetric barrier for semidefinite programming, Math. Oper. Res. 25 (2000), no. 3, 365–380. MR 1855171, DOI 10.1287/moor.25.3.365.12212
K. A. Ariyawansa and Yuntao Zhu, Stochastic semidefinite programming: a new paradigm for stochastic optimization, 4OR 4 (2006), no. 3, 239–253. MR 2262090, DOI 10.1007/s10288-006-0016-2
K. A. Ariyawansa and Yuntao Zhu, A class of volumetric barrier decomposition algorithms for stochastic quadratic programming, Appl. Math. Comput. 186 (2007), no. 2, 1683–1693. MR 2319065, DOI 10.1016/j.amc.2006.08.171
John R. Birge and François Louveaux, Introduction to stochastic programming, Springer Series in Operations Research, Springer-Verlag, New York, 1997. MR 1460264
M. A. H. Dempster (ed.), Stochastic programming, Institute of Mathematics and its Applications Conference Series, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1980. MR 592594
R. J.-B. Wets (ed.), Numerical techniques for stochastic optimization, Springer Series in Computational Mathematics, vol. 10, Springer-Verlag, Berlin, 1988. MR 957304, DOI 10.1007/978-3-642-61370-8
A. J. Felt. A Computational Evaluation of Interior Point Cutting Plane Algorithms for Stochastic Programs. Ph.D. dissertation, Department of Pure and Applied Mathematics, Washington State University, Pullman, WA, 2000.
Anthony V. Fiacco and Garth P. McCormick, Nonlinear programming: Sequential unconstrained minimization techniques, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 243831
Alexander Graham, Kronecker products and matrix calculus: with applications, Ellis Horwood Series in Mathematics and its Applications, Ellis Horwood Ltd., Chichester; Halsted Press [John Wiley & Sons, Inc.], New York, 1981. MR 640865
Clovis C. Gonzaga, Path-following methods for linear programming, SIAM Rev. 34 (1992), no. 2, 167–224. MR 1166175, DOI 10.1137/1034048
Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
Roger A. Horn and Charles R. Johnson, Topics in matrix analysis, Cambridge University Press, Cambridge, 1991. MR 1091716, DOI 10.1017/CBO9780511840371
P. L. Jiang. Polynomial Cutting Plane Algorithms for Stochastic Programming and Related Problems. Ph.D. dissertation, Department of Pure and Applied Mathematics, Washington State University, Pullman, WA, 1997.
Peter Kall and Stein W. Wallace, Stochastic programming, Wiley-Interscience Series in Systems and Optimization, John Wiley & Sons, Ltd., Chichester, 1994. MR 1315300
Sanjay Mehrotra and M. Gökhan Özevin, Decomposition-based interior point methods for two-stage stochastic semidefinite programming, SIAM J. Optim. 18 (2007), no. 1, 206–222. MR 2299681, DOI 10.1137/050622067
Yurii Nesterov and Arkadii Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics, vol. 13, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR 1258086, DOI 10.1137/1.9781611970791
András Prékopa, Stochastic programming, Mathematics and its Applications, vol. 324, Kluwer Academic Publishers Group, Dordrecht, 1995. MR 1375234, DOI 10.1007/978-94-017-3087-7
Pravin M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Math. Programming 73 (1996), no. 3, Ser. A, 291–341. MR 1393123, DOI 10.1016/0025-5610(92)00021-S
R.J. Vanderbei and H.Y. Benson. On Formulating Semidefinite Programming Problems as Smooth Convex Nonlinear Optimization Problems. Working Paper, Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ, 2000.
Lieven Vandenberghe and Stephen Boyd, Semidefinite programming, SIAM Rev. 38 (1996), no. 1, 49–95. MR 1379041, DOI 10.1137/1038003
Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe (eds.), Handbook of semidefinite programming, International Series in Operations Research & Management Science, vol. 27, Kluwer Academic Publishers, Boston, MA, 2000. Theory, algorithms, and applications. MR 1778223, DOI 10.1007/978-1-4615-4381-7
M. J. Todd, Semidefinite optimization, Acta Numer. 10 (2001), 515–560. MR 2009698, DOI 10.1017/S0962492901000071
Gongyun Zhao, A log-barrier method with Benders decomposition for solving two-stage stochastic linear programs, Math. Program. 90 (2001), no. 3, Ser. A, 507–536. MR 1832221, DOI 10.1007/PL00011433