×

A potential-reduction variant of Renegar’s short-step path-following method for linear programming. (English) Zbl 0734.65050

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 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.
Reviewer: J.Guddat (Berlin)

MSC:

65K05 Numerical mathematical programming methods
90C05 Linear programming

Citations:

Zbl 0654.90050
Full Text: DOI

References:

[1] den Hertog, D.; Roos, C., A survey of Search Directions in Interior Point Methods for Linear Programming, (Report 89-65 (1989), Faculty of Mathematics and Informatics/Computer Science, Delft Univ. of Technology: Faculty of Mathematics and Informatics/Computer Science, Delft Univ. of Technology Delft, Holland) · Zbl 0739.90041
[2] Freund, R. M., Polynomial-Time Algorithms for Linear Programming Based only on Primal Scaling and Projected Gradients of a Potential Function (1988), Sloan School of Management, M.I.T.,: Sloan School of Management, M.I.T., Cambridge, Mass.,, Preprint
[3] Gonzaga, C. C., Large-Step Path-Following Methods for Linear Programming: Barrier Function Method, (Report ES-210/89 (1989), Dept. of Systems Engineering and Computer Sciences, COPPE—Federal University of Rio de Janeiro: Dept. of Systems Engineering and Computer Sciences, COPPE—Federal University of Rio de Janeiro Rio de Janeiro, Brasil) · Zbl 0754.90035
[4] Gonzaga, C. C., Large-Step Path-Following Methods for Linear Programming: Potential Reduction Method, (Report ES-211/89 (1989), Dept. of Systems Engineering and Computer Sciences, COPPE—Federal University of Rio de Janeiro: Dept. of Systems Engineering and Computer Sciences, COPPE—Federal University of Rio de Janeiro Rio de Janeiro, Brasil) · Zbl 0754.90036
[5] Jarre, F., The Method of Analytic Centers for Smooth Convex Programs (1989), Inst. für Angewandte Mathematik und Statistik, Univ. Würzburg: Inst. für Angewandte Mathematik und Statistik, Univ. Würzburg Würzburg, West Germany, Preprint 165 · Zbl 0684.90068
[6] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[7] Nesterov, Y. E.; Nemirovsky, A. S., Self-Concordant Functions and Polynomial Time Methods in Convex Programming (1989), Moscow
[8] Renegar, J., A polynomial-time algorithm, based on Newton’s method, for linear programming, Math. Programming, 40, 59-93 (1988) · Zbl 0654.90050
[9] Roos, C.; Vial, J.-Ph., Long Steps with the Logarithmic Penalty Barrier Function in Linear Programming, (Gabszevwicz, J.; Richard, J.-F.; Wolsey, L., Economic Decision-Making: Games, Economics and Optimization (1990), Elsevier Science Publisher B.V.), 433-441, (dedicated to Jacques H. Dréze) · Zbl 0709.90076
[10] Vaidya, P. M., An Algorithm for Linear Programming which Requires \(O(((m + n)n^2 + (m + n)^{1.5}n)L)\) Arithmetic Operations, Math. Programming, 47, 175-201 (1990) · Zbl 0708.90047
[11] Ye, Y., A Class of Potential Functions for Linear Programming (1988), Dept. of Management Sciences, Univ. of Iowa: Dept. of Management Sciences, Univ. of Iowa Iowa City
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.