*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Semidefinite programming (SDP) is a generalization of linear programming.
SDP has numerous applications in various fields, such as statistics, structural design, electrical engineering and combinatorial optimization.
Interior-point methods (IPMs) are known as polynomial time methods for solving SDPs, and are favorable for small or medium-sized SDPs. It is well-known that weighted central paths play important role in the design and analysis of IPMs for SDPs. The first topic of this thesis is to study limiting behavior of weighted paths associated with the SDP map $X^{1/2}SX^{1/2}$ and provide applications to error bound analysis and superlinear convergence of a class of primal-dual IPMs.
Although SDPs are polynomially solvable, it is still very challenging to solve large-scale SDPs efficiently. The second topic of this thesis is to provide an approach for solving large-scale well-structured sparse SDPs via a saddle point mirror-prox algorithm with ${cal O}(epsilon^{-1})$ efficiency by exploiting sparsity structure and reformulating SDPs into smooth convex-concave saddle point problems.
The third topic of this thesis is to develop a long-step primal-dual infeasible path-following algorithm for convex quadratic programming
(CQP) whose search directions are computed by means of a preconditioned iterative linear solver. A uniform bound, depending only on the CQP data, on the number of iterations needed by a preconditioned iterative linear solver is established. A polynomial bound on the number of iterations of this method is also obtained.
The last topic of this thesis is to develop an efficient ``nearly exact''
type of method for solving large-scale ``low-rank'' trust region subproblems by completely avoiding the computations of Cholesky or partial Cholesky factorizations. We also provide a computational study on this method by applying it to solve some large-scale nonlinear programming problems.
