Dissertation Information for Deep MedhiNAME:
DEGREE:
DISCIPLINE:
SCHOOL: ADVISORS: COMMITTEE MEMBERS: 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. |
MPACT Scores for Deep MedhiA = 0 Advisors and Advisees Graph |