## 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 PDF
- Math. Comp.
**80**(2011), 1639-1661 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**0243831** - 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

## Additional Information

**K. A. Ariyawansa**- Affiliation: Department of Mathematics, Washington State University, Pullman, Washington 99164-3113
- Email: ari@wsu.edu
**Yuntao Zhu**- Affiliation: Division of Mathematical and Natural Sciences, Arizona State University, Phoenix, AZ 85069-7100
- Email: Yuntao.Zhu@asu.edu
- Received by editor(s): July 27, 2009
- Received by editor(s) in revised form: May 14, 2010
- Published electronically: December 16, 2010
- Additional Notes: The work of the first author was supported in part by the U.S. Army Research Office under Grant DAAD 19-00-1-0465 and under Award W911NF-08-1-0530.

The work of the second author was supported in part by the ASU West MGIA Grant 2007. - © Copyright 2010 American Mathematical Society
- Journal: Math. Comp.
**80**(2011), 1639-1661 - MSC (2010): Primary 90C15, 90C51, 49M27
- DOI: https://doi.org/10.1090/S0025-5718-2010-02449-4
- MathSciNet review: 2785472