Jerome W. O'Neal

An Iterative Solver-Based Long-Step Infeasible Primal-Dual Path-Following Algorithm for Convex QP Based on a Class of Preconditioners

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Jerome W. O'Neal
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors’ previous paper \cite{ONE04}, we propose a new linear system, which we refer to as the \emph{hybrid augmented normal equation} (HANE), to … Read more

    A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning

  • Renato D.C. Monteiro
  • Arkadi Nemirovski
  • Jerome W. O'Neal
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , , ,

    The conjugate gradient (CG) algorithm is well-known to have excellent theoretical properties for solving linear systems of equations $Ax = b$ where the $n\times n$ matrix $A$ is symmetric positive definite. However, for extremely ill-conditioned matrices the CG algorithm performs poorly in practice. In this paper, we discuss an adaptive preconditioning procedure which improves the … Read more

    An Iterative Solver-Based Infeasible Primal-Dual Path-Following Algorithm for Convex QP

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Jerome W. O'Neal
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    In this paper we develop an interior-point primal-dual long-step path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of an iterative (linear system) solver. We propose a new linear system, which we refer to as the \emph{augmented normal equation} (ANE), to determine the primal-dual search directions. Since the condition number … Read more

    Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers

  • Renato D.C. Monteiro
  • Jerome W. O'Neal
    • Categories Linear Programming, Network Optimization Tags , , , , , , ,

    In this paper, we consider a modified version of a well-known long-step primal-dual infeasible IP algorithm for solving the linear program $\min\{c^T x : Ax=b, \, x \ge 0\}$, $A \in \Re^{m \times n}$, where the search directions are computed by means of an iterative linear solver applied to a preconditioned normal system of equations. … Read more

    Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
  • Jerome W. O'Neal
    • Categories Linear Programming, Network Optimization Tags , , , , , , ,

    Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more