Browsing by Author "Steihaug, Trond"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Application of a Class of Preconditioners to Large Scale Linear Programming Problems
    (Springer, 1999) Baryamureeba, Venansius; Steihaug, Trond; Zhang, Yin
    In most interior point methods for linear programming, a sequence of weighted linear least squares problems are solved, where the only changes from one iteration to the next are the weights and the right hand side. The weighted least squares problems are usually solved as weighted normal equations by the direct method of Cholesky factorization. In this paper, we consider solving the weighted normal equations by a preconditioned conjugate gradient method at every other iteration. We use a class of preconditioners based on a low rank correction to a Cholesky factorization obtained from the previous iteration. Numerical results show that when properly implemented, the approach of combining direct and iterative methods is promising
  • Thumbnail Image
    Item
    On the Convergence of an Inexact Primal-Dual Interior Point Method for Linear Programming
    (Springer, 2005) Baryamureeba, Venansius; Steihaug, Trond
    The inexact primal-dual interior point method which is discussed in this paper chooses a new iterate along an approximation to the Newton direction. The method is the Kojima, Megiddo, andMizuno globally convergent infeasible interior point algorithm. The inexact variation is shown to have the same convergence properties accepting a residue in both the primal and dual Newton step equation also for feasible iterates.
  • Thumbnail Image
    Item
    Properties of a class of preconditioners for weighted least squares problems
    (University of Berg, 1999) Baryamureeba, Venansius; Steihaug, Trond; Zhan, Yin
    A sequence of weighted linear least squares problems arises from interior-point methods for linear programming where the changes from one problem to the next are the weights and the right hand side One approach for solving such a weighted linear least squares problem is to apply a preconditioned conjugate gradient method to the normal equations where the preconditioner is based on a low rank correction to the Cholesky factorization of a previous coefficient matrix In this paper, we establish theoretical results for such preconditioners that provide guidelines for the construction of preconditioners of this kind We also present preliminary numerical experiments to validate our theoretical results and to demonstrate the effectiveness of this approach
  • Thumbnail Image
    Item
    A Review of Termination Rules of an Inexact Primal-Dual Interior Point Method for Linear Programming Problems
    (Investigación Operacional, 2018) Baryamureeba, Venansius; Steihaug, Trond; El Ghami, Mohamed
    In this paper we apply the Inexact Newton theory on the perturbed KKT-conditions that are derived from the Karush-Kuhn-Tucker optimality conditions for the standard linear optimization problem. We discuss different formulations and accuracy requirements for the linear systems and show global convergence properties of the method.