Export to Refworks Export to EndNote Email
Report an Issue

Stable computation of search directions for near-degenerate linear programming problems [electronic resource].

Published:
Arlington, Va. : National Science Foundation (U.S.), 1997.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
Physical Description:
24 pages : digital, PDF file
Additional Creators:
Sandia National Laboratories, National Science Foundation (U.S.), and United States. Department of Energy. Office of Scientific and Technical Information
Access Online

Availability

I Want It

Finding items...

Restrictions on Access:
Free-to-read Unrestricted online access
Summary:
In this paper, we examine stability issues that arise when computing search directions (δx, δy, δ s) for a primal-dual path-following interior point method for linear programming. The dual step δy can be obtained by solving a weighted least-squares problem for which the weight matrix becomes extremely il conditioned near the boundary of the feasible region. Hough and Vavisis proposed using a type of complete orthogonal decomposition (the COD algorithm) to solve such a problem and presented stability results. The work presented here addresses the stable computation of the primal step δx and the change in the dual slacks δs. These directions can be obtained in a straight-forward manner, but near-degeneracy in the linear programming instance introduces ill-conditioning which can cause numerical problems in this approach. Therefore, we propose a new method of computing δx and δs. More specifically, this paper describes and orthogonal projection algorithm that extends the COD method. Unlike other algorithms, this method is stable for interior point methods without assuming nondegeneracy in the linear programming instance. Thus, it is more general than other algorithms on near-degenerate problems.
Report Numbers:
E 1.99:sand--97-8243
sand--97-8243
Subject(s):
Other Subject(s):
Note:
Published through SciTech Connect.
03/01/1997.
"sand--97-8243"
"DE97052188"
": ONR Grant N0014-96-1-0050"
"NSF Grant DMS-9505155"
Hough, P.D.
Funding Information:
AC04-94AL85000
View MARC record | catkey: 14350798