On the choice of parameters for power-series interior point algorithms in linear programming

In this paper we study higher-order interior point algorithms, especially power-series algorithms, for solving linear programming problems. Since higher-order differentials are not parameter-invariant, it is important to choose a suitable parameter for a power-series algorithm. We propose a parameter transformation to obtain a good choice of parameter, called ak-parameter, for general truncated powerseries approximations. We give a method to find ak-parameter. This method is applied to two powerseries interior point algorithms, which are built on a primal—dual algorithm and a dual algorithm, respectively. Computational results indicate that these higher-order power-series algorithms accelerate convergence compared to first-order algorithms by reducing the number of iterations. Also they demonstrate the efficiency of thek-parameter transformation to amend an unsuitable parameter in power-series algorithms.Work supported in part by the DFG Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung.     

Theoretical convergence of large-step primal—dual interior point algorithms for linear programming

This paper proposes two sets of rules, Rule G and Rule P, for controlling step lengths in a generic primal—dual interior point method for solving the linear programming problem in standard form and its dual. Theoretically, Rule G ensures the global convergence, while Rule P, which is a special case of Rule G, ensures the O(nL) iteration polynomial-time computational complexity. Both rules depend only on the lengths of the steps from the current iterates in the primal and dual spaces to the respective boundaries of the primal and dual feasible regions. They rely neither on neighborhoods of the central trajectory nor on potential function. These rules allow large steps without performing any line search. Rule G is especially flexible enough for implementation in practically efficient primal—dual interior point algorithms.Part of the research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contracts N00014-87-C-0820 and N00014-91-C-0026 is acknowledged.     

An interior point algorithm for semi-infinite linear programming

We consider the generalization of a variant of Karmarkar's algorithm to semi-infinite programming. The extension of interior point methods to infinite-dimensional linear programming is discussed and an algorithm is derived. An implementation of the algorithm for a class of semi-infinite linear programs is described and the results of a number of test problems are given. We pay particular attention to the problem of Chebyshev approximation. Some further results are given for an implementation of the algorithm applied to a discretization of the semi-infinite linear program, and a convergence proof is given in this case.     

A primal projective interior point method for linear programming

We present a new projective interior point method for linear programming with unknown optimal value. This algorithm requires only that an interior feasible point be provided. It generates a strictly decreasing sequence of objective values and within polynomial time, either determines an optimal solution, or proves that the problem is unbounded. We also analyze the asymptotic convergence rate of our method and discuss its relationship to other polynomial time projective interior point methods and the affine scaling method.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402 and ONR Contract N00014-87-K0214.     

Dual interior point methods for linear semidefinite programming problems

Dual interior point methods for solving linear semidefinite programming problems are proposed. These methods are an extension of dual barrier-projection methods for linear programs. It is shown that the proposed methods converge locally at a linear rate provided that the solutions to the primal and dual problems are nondegenerate.     

Projected Hessian algorithm with backtracking interior point technique for linear constrained optimization

In this paper, we propose a new trust-region-projected Hessian algorithm with nonmonotonic backtracking interior point technique for linear constrained optimization. By performing the QR decomposition of an affine scaling equality constraint matrix, the conducted subproblem in the algorithm is changed into the general trust-region subproblem defined by minimizing a quadratic function subject only to an ellipsoidal constraint. By using both the trust-region strategy and the line-search technique, each iteration switches to a backtracking interior point step generated by the trustregion subproblem. The global convergence and fast local convergence rates for the proposed algorithm are established under some reasonable assumptions. A nonmonotonic criterion is used to speed up the convergence in some ill-conditioned cases. Selected from Journal of Shanghai Normal University (Natural Science), 2003, 32(4): 7–13     

A unified view of interior point methods for linear programming

The paper shows how various interior point methods for linear programming may all be derived from logarithmic barrier methods. These methods include primal and dual projective methods, affine methods, and methods based on the method of centers. In particular, the paper demonstrates that Karmarkar's algorithm is equivalent to a classical logarithmic barrier method applied to a problem in standard form.Invited paper presented at the Workshop on Supercomputers in Optimization, Minneapolis, Minn., May 1988.The work of this author was supported by the Air Force Office of Scientific Research, Air Force Systems Command, USA, under Grants AFOSR-87-0215 and AFOSR-85-0271. The US Government is authorized to reproduce and distribute reprints for Governmental purposes not withstanding any copyright notation thereon.     

Degeneracy in interior point methods for linear programming: a survey

The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming.We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.Partially supported by a research fund of SHELL.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116.     

An active-set strategy in an interior point method for linear programming

We will present a potential reduction method for linear programming where only the constraints with relatively small dual slacks—termed active constraints—will be taken into account to form the ellipsoid constraint at each iteration of the process. The algorithm converges to the optimal feasible solution in O( L) iterations with the same polynomial bound as in the full constraints case, wheren is the number of variables andL is the data length. If a small portion of the constraints is active near the optimal solution, the computational cost to find the next direction of movement in one iteration may be considerably reduced by the proposed strategy.This research was partially done in June 1990 while the author was visiting the Department of Mathematics, University of Pisa.     

Interior point algorithms for linear programming with inequality constraints

Interior methods for linear programming were designed mainly for problems formulated with equality constraints and non-negative variables. The formulation with inequality constraints has shown to be very convenient for practical implementations, and the translation of methods designed for one formulation into the other is not trivial. This paper relates the geometric features of both representations, shows how to transport data and procedures between them and shows how cones and conical projections can be associated with inequality constraints.     

A primal interior point method for the linear semidefinite programming problem

The linear semidefinite programming problem is examined. A primal interior point method is proposed to solve this problem. It extends the barrier-projection method used for linear programs. The basic properties of the proposed method are discussed, and its local convergence is proved.     

A new efficient short-step projective interior point method for linear programming

In this paper, we are interested in the performance of Karmarkar’s projective algorithm for linear programming. We propose a new displacement step to accelerate and improve the convergence of this algorithm. This purpose is confirmed by numerical experimentations showing the efficiency and the robustness of the obtained algorithm over Schrijver’s one for small problem dimensions.     

Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

Computational results of an interior point algorithm for large scale linear programming

This paper gives computational results for an efficient implementation of a variant of dual projective algorithm for linear programming. The implementation uses the preconditioned conjugate gradient method for computing projections. Our computational experience reported in this paper indicates that this algorithm has potential as an alternative for solving very large LPs in which the direct methods fail due to memory and CPU time requirements. The conjugate gradient algorithm was able to find very accurate directions even when the system was ill-conditioned. The paper also discusses a new mathematical technique called the reciprocal estimates for estimating the primal variables. We have conducted extensive computational experiments on problems representative of large classes of applications of current interest. We have also chosen instances of the problems of future potential interest, which could not be solved in the past due to the weakness of the prior solution methods, but which represent a large class of new applications. The hypergraph model is such an example. Comparison of our implementation with MINOS 5.1 shows that our implementation is orders of magnitude faster than MINOS 5.1 for these problems.     

Dual interior point algorithms

For a linear programming problem stated in the canonical form we consider the dual problem and describe a class of interior point algorithms which generate monotonically improving approximations to its solution. We theoretically substantiate the optimization process in the admissible domain under the assumption that the dual problem is nondegenerate. In addition, we describe subsets of algorithms that lead to relative interior points of optimal solutions. These algorithms have linear and superlinear convergence rates. Moreover, we obtain a special subset of algorithms which generate iterative sequences of approximations to a solution of the direct problem, whose convergence rate exceeds that of the sequences of monotonically improving approximations to a solution of the dual problem.     

A limit field for orthogonal range searches in two-dimensional random point search trees

We consider the cost of general orthogonal range queries in random quadtrees. The cost of a given query is encoded into a (random) function of four variables which characterize the coordinates of two opposite corners of the query rectangle. We prove that, when suitably shifted and rescaled, the random cost function converges uniformly in probability towards a random field that is characterized as the unique solution to a distributional fixed-point equation. We also state similar results for 2-d trees. Our results imply for instance that the worst case query satisfies the same asymptotic estimates as a typical query, and thereby resolve an open question of Chanzy et al. (2001).     

A weighted least squaes study of robustness in interior point linear programming

This paper studies the robustness of interior point linear programming algorthims with respect to initial iterates that are too close to the boundary. Weighted least squares analysis is used in studying the near-boundary behavior of the affine scaling and Newton centering directions, which are often combined by interior point methods. This analysis leads to the develoment of a modified Newton centering direction exhibiting better near-boundary behavior than the two directions. Theoretical and computational results from the NETLIB test set are presented indicating that an approach which uses the modified newton direction is more robust than both the pure affine scaling approach and one which uses the Newton direction as the centering direction.     

A parallel interior point algorithm for linear programming on a network of transputers

Interior Point algorithms have become a very successful tool for solving large-scale linear programming problems. The Dual Affine algorithm is one of the Interior Point algorithms implemented in the computer program OB1. It is a good candidate for implementation on a parallel computer because it is very computing-intensive. A parallel Dual Affine algorithm is presented which is suitable for a parallel computer with a distributed memory. The algorithm obtains its speedup from parallel sparse linear algebra computations such as Cholesky factorisation, matrix multiplication, and triangular system solving, which form the bulk of the computing work. Efficient algorithms based on the grid distribution of matrices are presented for each of these computations. The algorithm is implemented in occam 2 on a square mesh of transputers. The resulting parallel program is connected to the sequentialFortran 77 program OB1, which performs the preprocessing and the postprocessing. Experimental results on a mesh of 400 transputers are given for a test set of seven realistic planning and scheduling problems from Shell and seven problems from the NETLIB LP collection; the results show a speedup of 88 for the largest problem.     

Neighborhood-following algorithms for linear programming

In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(n~(1/2)L)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.