Homogeneous Self-Dual Algorithms for Stochastic Semidefinite Programming

摘要

Ariyawansa and Zhu 3 have proposed a new class of optimization problems termed stochastic semidefinite programs (SSDPs) to handle data uncertainty in applications leading to (deterministic) semidefinite programs (DSDPs). For the case where the event space of the random variables in an SSDP is finite they have also derived a class of volumetric barrier decomposition algorithms, and proved polynomial complexity of the short-step and long-step members of the class 2. When the event space of the random variables in an SSDP is finite, the SSDP is equivalent to a large scale DSDP with special structure. Polynomial homogeneous self-dual algorithms are an important class of algorithms that have been introduced for solving (general) DSDPs. It is therefore possible to solve SSDPs by applying homogeneous self-dual algorithms to their DSDP equivalents. However, such algorithms, while polynomial, will still have high computational complexities in comparison to decomposition algorithms. In this paper, we show how the special structure in DSDP equivalents of SSDPs can be exploited to design homogeneous self-dual algorithms with computation.