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

den Hertog, D.; Roos, C.; Terlaky, T.

Linear Algebra Appl. 152, 43-68 (1991).

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

Keywords:

polynomial potential-reduction method; linear programming; large-step pathfollowing method; line search; Newton direction; iteration bound

Citations:

Zbl 0654.90050

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