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 Free Access

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?)


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