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

Event Details
  • Date/Time:
    • Tuesday June 21, 2005
      12:00 pm - 12:00 am
  • Location: Groseclose, room 226A
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher
404.385.3102
Summaries

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

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

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.

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
No keywords were submitted.
Status
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 8, 2010 - 7:38am
  • Last Updated: Oct 7, 2016 - 9:52pm