The limiting behavior of weighted paths associated with the semidefinite program (SDP) map $X^{1/2}SX^{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 ${cal O}(epsilon^{-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.

Over the last 25 years, interior-point methods (IPMs) have emerged as a viable class of algorithms for solving various forms of conic optimization problems. Most IPMs use a modified Newton method to determine the search direction at each iteration. The system of equations corresponding to the modified Newton system can often be reduced to the so-called normal equation, a system of equations whose matrix ADA' is positive definite, yet often ill-conditioned. In this thesis, we first investigate the theoretical properties of the maximum weight basis (MWB) preconditioner, and show that when applied to a matrix of the form ADA', where D is positive definite and diagonal, the MWB preconditioner yields a preconditioned matrix whose condition number is uniformly bounded by a constant depending only on A. Next, we incorporate the results regarding the MWB preconditioner into infeasible, long-step, primal-dual, path-following algorithms for linear programming (LP) and convex quadratic programming (CQP). In both LP and CQP, we show that the number of iterative solver iterations of the algorithms can be uniformly bounded by n and a condition number of A, while the algorithmic iterations of the IPMs can be polynomially bounded by n and the logarithm of the desired accuracy. We also expand the scope of the LP and CQP algorithms to incorporate a family of preconditioners, of which MWB is a member, to determine an approximate solution to the normal equation. For the remainder of the thesis, we develop a new preconditioning strategy for solving systems of equations whose associated matrix is positive definite but ill-conditioned. Our so-called adaptive preconditioning strategy allows one to change the preconditioner during the course of the conjugate gradient (CG) algorithm by post-multiplying the current preconditioner by a simple matrix, consisting of the identity matrix plus a rank-one update. Our resulting algorithm, the Adaptive Preconditioned CG (APCG) algorithm, is shown to have polynomial convergence properties. Numerical tests are conducted to compare a variant of the APCG algorithm with the CG algorithm on various matrices.