Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: K. A. Ariyawansa and Yuntao Zhu
Journal: Math. Comp. 80 (2011), 1639-1661
MSC (2010): Primary 90C15, 90C51, 49M27
DOI: https://doi.org/10.1090/S0025-5718-2010-02449-4
Published electronically: December 16, 2010
MathSciNet review: 2785472
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim., 5:13-51, 1995. MR 1315703 (95k:90065)
  • 2. K. M. Anstreicher. On Vaidya's volumetric cutting plane method for convex programming. Mathematics of Operations Research, 22(1):63-89, 1997. MR 1436574 (98b:90103)
  • 3. K. M. Anstreicher. Volumetric path following algorithms for linear programming. Mathematical Programming, 76(1B):245-263, 1997. MR 1426406 (98a:90057)
  • 4. K. M. Anstreicher. The volumetric barrier for semidefinite programming. Mathematics of Operations Research, 25(3):365-380, 2000. MR 1855171 (2002f:90078)
  • 5. K. A. Ariyawansa and Y. Zhu. Stochastic Semidefinite Programming: A New Paradigm for Stochastic Optimization. 4OR--The Quarterly Journal of the Belgian, French and Italian OR Societies, 4(3):65-79, 2006. (An earlier version of this paper appeared as Technical Report 2004-10 of the Department of Mathematics, Washington State University, Pullman, WA 99164-3113, in October 2004.) MR 2262090 (2008e:90059)
  • 6. K. A. Ariyawansa and Y. Zhu. A class of volumetric barrier decomposition algorithms for stochastic quadratic programming. Applied Mathematics and Computation, 186(2):1683-1693, 2007. MR 2319065
  • 7. J. R. Birge and F. Louveaux. Introduction to Stochastic Programming. Springer, New York, NY, 1997. MR 1460264 (99b:90001)
  • 8. M. A. H. Dempster. Stochastic Programming. Academic Press, London, U.K., 1980. MR 592594 (81j:90094)
  • 9. Y. Ermoliev and R. J-B. Wets. Numerical Techniques for Stochastic Optimization. Springer-Verlag, Berlin, Germany, 1988. MR 957304 (90h:90131)
  • 10. 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.
  • 11. A. V. Fiacco and G. P. McCormick. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley, New York, NY, 1968. MR 0243831 (39:5152)
  • 12. A. Graham. Kronecker Products and Matrix Calculus: With Applications. Ellis Horwood, Chichester, U.K., 1981. MR 640865 (83g:15001)
  • 13. C. C. Gonzaga. Path following methods for linear programming. SIAM Review, 34:167-224, 1992. MR 1166175 (93j:90050)
  • 14. R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, U.K., 1985. MR 832183 (87e:15001)
  • 15. R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press, Cambridge, U.K., 1991. MR 1091716 (92e:15003)
  • 16. 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.
  • 17. P. Kall and S. Wallace. Stochastic Programming. Wiley, New York, NY, 1994. MR 1315300 (96h:90002)
  • 18. S. Mehrotra and M. G. Özevin. Decomposition-based interior point methods for two-stage stochastic semidefinite programming. SIAM J. of Optimization, 18(1):206-222, 2007. (An earlier draft of this paper appeared under the title ``Two-state stochastic semidefinite programming and decomposition based interior point methods: theory,'' IEMS Technical Report 2004-16, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, in December 2004.) MR 2299681 (2007m:90135)
  • 19. Yu. E. Nesterov and A. S. Nemirovskii. Interior Point Polynomial Algorithms in Convex Programming. SIAM Publications, Philadelphia, PA, 1994. MR 1258086 (94m:90005)
  • 20. A. Prékopa. Stochastic Programming. Kluwer Academic Publishers, Boston, MA, 1995. MR 1375234 (97f:90001)
  • 21. P. M. Vaidya. A new algorithm for minimizing convex functions over a convex set. Math. Program., Ser. A, 73:291-341, 1996. MR 1393123 (97e:90060)
  • 22. 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.
  • 23. L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Rev., 38:49-95, 1996. MR 1379041 (96m:90005)
  • 24. H. Wolkowicz, R. Saigal and L. Vandenberghe. Handbook of Semidefinite Programming--Theory, Algorithms, and Applications. Kluwer Academic Publishers, Norwell, MA, 2000. MR 1778223 (2001k:90001)
  • 25. M. J. Todd. Semidefinite Optimization. ACTA Numerica, 10:515-560, 2001. MR 2009698 (2004g:90004)
  • 26. G. Zhao. A log-barrier method with Benders decomposition for solving two-stage stochastic linear programs. Math. Program., Ser. A, 90:507-536, 2001. MR 1832221 (2002g:90067)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C15, 90C51, 49M27

Retrieve articles in all journals with MSC (2010): 90C15, 90C51, 49M27


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

DOI: https://doi.org/10.1090/S0025-5718-2010-02449-4
Keywords: Stochastic linear programming, semidefinite programming, stochastic semidefinite programming, volumetric-barrier, self-concordance, decomposition
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.
Article copyright: © Copyright 2010 American Mathematical Society

American Mathematical Society