Homogeneous Self-Dual Algorithms for Stochastic Semidefinite Programming
Abstract
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 [11] 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
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 23, 2011
- Accession Number
- ADA544763
Entities
People
- K. A. Ariyawansa
- Shengping Jin
- Yuntao Zhu
Organizations
- Washington State University