aitter's Terlaky:T [5 articles]

Abstract

In this paper we discuss the polynomiality of Mehrotra-type predictor-corrector algorithms. We consider a variant of the original prototype of the algorithm that has been widely used in several IPM based optimization packages, for which no complexity result is known to date. By an example we show that in this variant the usual Mehrotra-type adaptive choice of the parameter $μ$ might force the algorithm to take many small steps to keep the iterates in a certain neighborhood of the central path, ...

Abstract

We propose a new class of primal-dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large update method for LO based on the new search direction has a polynomial complexity O n 4 4+ log n " iterations where 2 [0; 2] is a parameter used in the system dening the search direction. If = 0, our results reproduce the well known complexity of the standard primal dual Newton method for LO. At each iteration, our algorithm needs only to solve... ...

Abstract

Many issues that are crucial for an efficient implementation of an interior point algorithm are addressed in this paper. To start with, a prototype primal--dual algorithm is presented. Next, many tricks that make it so efficient in practice are discussed in detail. Those include: the preprocessing techniques, the initialization approaches, the methods of computing search directions (and lying behind them linear algebra techniques), centering strategies and methods of stepsize selection. Several ... ...

Abstract

In the past 10 years the interior point methods (IPM) for linear programming have gained extraordinary interest as an alternative to the sparse simplex based methods. This has initiated a fruitful competition between the two types of algorithms which has lead to very efficient implementations on both sides. The significant difference between interior point and simplex based methods is reflected not only in the theoretical background but also in the practical implementation. In this paper we... ...