A polynomial Newton method for linear programming (Q1094330): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| 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 | |||
Revision as of 12:12, 18 June 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
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
polynomial complexity
0 references
systems of affine equations
0 references
Newton-like method
0 references
second-order approximation
0 references
0 references
