A polynomial Newton method for linear programming (Q1094330): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Set OpenAlex properties.
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Khachiyan's linear programming algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex / rank
 
Normal rank
Property / cites work
 
Property / cites work: A new polynomial-time algorithm for linear programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: An extension of Karmarkar's algorithm for linear programming using dual variables / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3236239 / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/bf01840456 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1980845317 / rank
 
Normal rank

Latest revision as of 10:31, 30 July 2024

scientific article
Language Label Description Also known as
English
A polynomial Newton method for linear programming
scientific article

    Statements

    A polynomial Newton method for linear programming (English)
    0 references
    0 references
    0 references
    0 references
    1986
    0 references
    A method for solving systems of affine equations on the nonnegative orthant is proposed. The problem is reduced to the (equivalent) nonlinear programming problem with the cost function in the form of a sum of logarithms. A Newton-like method, based on the second-order approximation of a log-function, is proposed for solving the latter problem. The basic steps of the method are the projection of the vector on the null space of the equation and the one-dimensional search. The procedure computes an exact solution in at most \(0(n^ 3m^ 2L)\) operations (here L is the size of the problem).
    0 references
    0 references
    polynomial complexity
    0 references
    systems of affine equations
    0 references
    Newton-like method
    0 references
    second-order approximation
    0 references

    Identifiers