A potential-reduction variant of Renegar's short-step path-following method for linear programming (Q811094): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q114852085, #quickstatements; #temporary_batch_1704714147019 |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:05, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A potential-reduction variant of Renegar's short-step path-following method for linear programming |
scientific article |
Statements
A potential-reduction variant of Renegar's short-step path-following method for linear programming (English)
0 references
1991
0 references
The authors propose a new polynomial potential-reduction method for linear programming. This method can be interpreted as a large-step pathfollowing method. A line search is performed along the Newton direction with respect to \textit{J. Renegar}'s strictly convex potential function [Math. Program, Ser. A 40, No.1, 59-93 (1988; Zbl 0654.90050)] if the iterate is far away from the central trajectory. In the other case the lower bound for the optimal value will be updated. Depending on this updating scheme, the iteration bound is proved to be O(\(\sqrt{n}L)\) or O(nL). The method differs from the previous potential- reduction method in the choice of the potential function and the search direction.
0 references
polynomial potential-reduction method
0 references
linear programming
0 references
large-step pathfollowing method
0 references
line search
0 references
Newton direction
0 references
iteration bound
0 references