Login

Publications  •  Project Statistics

Glossary  •  Schools  •  Disciplines
People Search: 
   
Title/Abstract Search: 

Dissertation Information for Deep Medhi

NAME:
- Deep Medhi
- (Alias) Deepankar Medhi

DEGREE:
- Ph.D.

DISCIPLINE:
- Computer Science

SCHOOL:
- University of Wisconsin, Madison (USA) (1987)

ADVISORS:
- None

COMMITTEE MEMBERS:
- None

MPACT Status: Incomplete - Not_Inspected

Title: DECOMPOSITION OF STRUCTURED LARGE-SCALE OPTIMIZATION PROBLEMS AND PARALLEL OPTIMIZATION

Abstract: In this dissertation, we present serial and parallel algorithms to solve efficiently the problem: inf $\{\sum\sbsp{i=1}{N} f\sb{i}(x\sb{i})\mid$ $\sum\sbsp{i=1}{N} A\sb{i}x\sb{i}$ = $a\}.$ Here, a $\in$ ${\rm I\!R}\sp{m},$ and for i = 1, dots, N, $A\sb{i}$ $\in$ ${\rm I\!R}\sp{m\times n\sb{i}},$ $x\sb{i}$ $\in$ ${\rm I\!R}\sp{n\sb{i}},$ and, $f\sb{i}$'s are closed proper convex functions (not necessarily differentiable) taking values in the extended real line $(-\infty, \infty\rbrack.$ For example, block-angular linear programming problems and linear multi-commodity network optimization problems can be cast into the above form. In our approach, we take the Rockafellar dual of the problem to arrive at an unconstrained nonsmooth maximization problem. The difficulty arises from the nonsmoothness of the dual objective. Traditional subgradient methods are not good enough as they do not have implementable stopping criterion and are reported to have slow convergence. One also may not obtain a primal solution at the end. Instead, we apply a modified bundle algorithm, which has an implementable stopping criterion, and more importantly, one can recover an approximate primal solution. We also obtain some theoretical a posteriori error information on the approximate solution. We have implemented this algorithm on randomly generated block-angular linear programming problems of size up to 4,000 equality constraints and 10,000 variables. Our implementation ran up to seventy times faster than MINOS version 5.0, and did substantially better than an advanced implementation of the Dantzig-Wolfe decomposition method. Thus we think that for this type of problem, our algorithm is very promising.

A nice feature of the dual problem is that is breaks up the original problem into smaller independent subproblems. Exploiting this fact, we present parallel algorithms implemented on the CRYSTAL multicomputer. We considered two groups of test problems for these algorithms, one in which the subproblems required approximately equal amounts of time to solve, and another in which the solution times varied. In the first group, we obtained 70%-80% efficiency with up to eleven processors. In the second group, we obtained 60% or more efficiency with relatively small problems and with up to five processors.

MPACT Scores for Deep Medhi

A = 0
C = 1
A+C = 1
T = 0
G = 0
W = 0
TD = 0
TA = 0
calculated 2009-05-24 20:34:31

Advisors and Advisees Graph