Thesis Defense :: Algorithm Design and Analysis for Large-Scale Semidefinite Programming and Nonlinear Programming

Primary tabs

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.


  • Workflow Status: Published
  • Created By: Barbara Christopher
  • Created: 10/08/2010
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016


No keywords were submitted.

Target Audience