Solving linear systems involved in constrained optimization
type: Item
instance of: scholarly article
title: Solving linear systems involved in constrained optimization
zbMATH Open document ID: 0837.65062
DOI: 10.1016/0024-3795(94)00007-Z
author: Yixun Shi
published in: Linear Algebra and its Applications
publication date: 1996-05-21T00:00:00Z
review text: The interior point methods for large scale linear, quadratic and convex programming need \((n+ m)\times (n+ m)\) systems of linear equations to be solved in each iteration. The author proposes an inexpensive iterative method for solving those systems which guarantees exact solutions to the last \(m\) equations. Current implementations solve the systems by considering an equivalent system in each iteration and reducing the task to solving an \((m\times m)\) system which has to be solved exactly and therefore the iterative methods are avoided. The typical approach uses the Cholesky factorization in every iteration step which makes the computation costly and sometimes impractical. The new algorithm, proposed in this paper, uses only one Cholesky factorization at the initial step of the interior point algorithm. The description of the method and its convergence analysis are presented. Some implementation issues and the possibility to combine the proposed method with another iterative method such as the conjugate gradient method in order to have the advantages of both are discussed. Some preliminary numerical experiments, where the objective functions are widely used functions in economics, physics and engineering are shortly reported in the last section.
reviewed by: Krassimir Georgiev
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C06
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 90C25
zbMATH DE Number: 815902
zbMATH Keywords: interior point methods
zbMATH Keywords: large scale linear, quadratic and convex programming
zbMATH Keywords: iterative method
zbMATH Keywords: Cholesky factorization
zbMATH Keywords: algorithm
zbMATH Keywords: convergence
zbMATH Keywords: conjugate gradient method
zbMATH Keywords: numerical experiments
MaRDI profile type: Publication
cites work: Q3996272
cites work: On some efficient interior point methods for nonlinear convex programming
cites work: Solution of $P_0 $-Matrix Linear Complementarity Problems Using a potential Reduction Algorithm
cites work: Efficent line search algorithm for unconstrained optimization
cites work: The Mehrotra Predictor-Corrector Interior-Point Method As a Perturbed Composite Newton Method
cites work: A Centered Projective Algorithm for Linear Programming
cites work: Q4302066
cites work: On the finite convergence of interior-point algorithms for linear programming
cites work: A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
cites work: Containing and shrinking ellipsoids in the path-following algorithm
description: scientific article; zbMATH DE number 815902