Algorithm design and analysis for large-scale semidefinite programming and nonlinear programming |
Posted on:2006-07-03 | Degree:Ph.D | Type:Dissertation |
University:Georgia Institute of Technology | Candidate:Lu, Zhaosong | Full Text:PDF |
GTID:1450390005995348 | Subject:Operations Research |
Abstract/Summary: | |
The limiting behavior of weighted paths associated with the semidefinite program (SDP) map X1/2SX 1/2 was studied and some applications to error bound analysis and superlinear convergence of a class of primal-dual interior-point methods were provided. A new approach for solving large-scale well-structured sparse SDPs via a saddle point mirror-prox algorithm with Oe-1 efficiency was developed based on exploiting sparsity structure and reformulating SDPs into smooth convex-concave saddle point problems. An iterative solver-based long-step primal-dual infeasible path-following algorithm for convex quadratic programming (CQP) was developed. The search directions of this algorithm were computed by means of a preconditioned iterative linear solver. A uniform bound, depending only on the CQP data, on the number of iterations performed by a preconditioned iterative linear solver was established. A polynomial bound on the number of iterations of this algorithm was also obtained. One efficient "nearly exact" type of method for solving large-scale "low-rank" trust region subproblems was proposed by completely avoiding the computations of Cholesky or partial Cholesky factorizations. A computational study of this method was also provided by applying it to solve some large-scale nonlinear programming problems. |
Keywords/Search Tags: | Large-scale, Programming, Algorithm |
|
Related items |