Feb 2, 3:30pm, Wean 8220

Richard Peng, CMU

Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

Richard Peng, CMU

Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming

Abstract:

Semidefinite programs are generalizations of linear programs that play a
key role in many optimization problems. The special case where all matrices
in the constraints and objective are positive semidefinite can also be
viewed as a generalization of positive linear programs. Recently, Jain and
Yao gave an algorithm that produces an (1+eps) approximation in
((log n)/eps)^13
iterations for this case, bringing the problem to NC.

We present a simpler NC parallel algorithm that requires O(((log n)/eps)^4 log(1/eps)) iterations. Moreover, if the positive SDP is provided in a factorized form, the total work of our algorithm is nearly linear.

This is ongoing work with Kanat Tangwongsan.