A CLASS OF POLYNOMIAL VOLUMETRIC BARRIER DECOMPOSITION ALGORITHMS FOR STOCHASTIC SEMIDEFINITE PROGRAMMING

作者：Ariyawansa K A^*; Zhu Yuntao

来源：Mathematics of Computation, 2011, 80(275): 1639-1661.

DOI：10.1090/S0025-5718-2010-02449-4

• Stochastic linear programming
• semidefinite programming
• stochastic semidefinite programming
• volumetric-barrier
• self-concordance
• decomposition

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 Ozevin 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 Ozevin 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.

• 出版日期2011-7