A parallel two-stage interior point decomposition algorithm

Event Details
  • Date/Time:
    • Tuesday November 18, 2008
      2:00 pm - 3:00 pm
  • Location: Executive classroom 228, main bldg.
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    $0.00
  • Extras:
Contact
Anita Race
H. Milton Stewart School of Industrial and Systems Engineering
Contact Anita Race
Summaries

Summary Sentence: A parallel two-stage interior point decomposition algorithm

Full Summary: A parallel two-stage interior point decomposition algorithm for large scale structured semidefinite programs

TITLE: A parallel two-stage interior point decomposition algorithm for large scale structured semidefinite programs

SPEAKER: Dr. Kartik Sivaramakrishnan (Researh Div., Axioma,Inc.)

ABSTRACT:

Semidefinite programming (SDP) is referred to as "linear programming for the 21st century" and has a variety of applications in science and engineering. Primal-dual interior point algorithms are currently the most popular techniques for solving large scale SDPs. However, these algorithms are fairly limited in the size of SDPs that they can solve in practice.

We present a two stage decomposition algorithm to solve large scale structured semidefinite programs (SDPs). In the first stage, we exploit the sparsity and/or the symmetry in an underlying SDP in order to process it into an equivalent problem having a "block-angular" structure. We will illustrate the procedure with simple examples in the talk. In the 2nd stage, we solve the resulting "block-angular" SDP in an iterative fashion between a master problem and "decomposed" and "distributed" subproblems in a parallel computing environment. We will give the details of our decomposition algorithm and also highlight some of our enhancements that improve the convergence of the algorithm. We will also report our computational experiences with the algorithm on the distributed "Henry2" cluster at NC State University. Finally, we compare our algorithm with the OpenMP version of CSDP that is available via the COIN-OR interface.

Additional Information

In Campus Calendar
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
Decomposition algorithm
Status
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Oct 12, 2009 - 4:37pm
  • Last Updated: Oct 7, 2016 - 9:47pm