Search

In this paper we present a scaling-invariant, interior-point, predictor-corrector type algorithm for linear programming (LP) whose iteration-complexity is polynomially bounded by the dimension and the logarithm of a certain condition number of the LP constraint matrix. At the predictor stage, the algorithm either takes the step along the standard affine scaling (AS) direction or a new trust-region type direction, whose construction depends on a scaling-invariant bipartition of the variables determined by the AS direction. This contrasts with the layered least squares direction introduced in S. Vavasis and Y. Ye [Math. Program., 74 (1996), pp. 79-120], whose construction depends on multiple-layered partitions of the variables that are not scaling-invariant. Moreover, it is shown that the overall arithmetic complexity of the algorithm (weakly) depends on the right-hand side and the cost of the LP in view of the work involved in the computation of the trust region steps. [ABSTRACT FROM AUTHOR]

In this paper we present a new iteration-complexity bound for the Mizuno--Todd--Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program min {cTχ: Aχ = b, &chi ≥ 0 } with decision variable ..., we show that the MTY P-C algorithm, started from a well-centered interior-feasible solution with duality gap nμ0 finds an interior-feasible solution with duality gap less than nn in O (T(μ0/η)+n3.5 log (Χ*A)) iterations, where T(t ) =min {n² log (log t), log t} for all t>0 and Χ*A is a scaling invariant condition number associated with the matrix A. More specifically,Χ*A is the infimum of all the conditions numbers XAD, where D varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an O (n3.5 LA + min {n² log L, L}) iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where LA and L are the input sizes of the matrix A and the data (A,b,c ), respectively. This contrasts well with the classical iteration-complexity bound for the MTY P-C algorithm, which depends linearly on L instead of log L. [ABSTRACT FROM AUTHOR]

A new class of infeasible interior point methods for solving sufficient linear complementarity problems (LCPs) requiring one matrix factorization and m backsolves at each iteration is proposed and analyzed. The algorithms from this class use a large (N−∞ ) neighborhood of an infeasible central path associated with the complementarity problem and an initial positive, but not necessarily feasible, starting point. The Q-order of convergence of the complementarity gap, the residual, and the iteration sequence is m+ 1 for problems that admit a strict complementarity solution and (m+1)/2 for general sufficient LCPs. The methods do not depend on the handicap κ of the sufficient LCP. If the starting point is feasible (or “almost” feasible), the proposed algorithms have O((1 + κ)(1 +log m√1 + κ )√n L) iteration complexity, while if the starting point is “large enough,” the iteration complexity is O((1 + κ)2+1/m(1 + log m√1 +κ )n L). [ABSTRACT FROM AUTHOR]

A first order affine scaling method and two mth order affine scaling methods for solving monotone linear complementarity problems (LCPs) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has O(nL²(log nL²) (log log nL²)) iteration complexity. If the LCP admits a strict complementary solution, then both the duality gap and the iteration sequence converge superlinearly with Q-order two. If m = Ω(log(√nL)), then both higher order methods have O(√n)L iteration complexity. The Q-order of convergence of one of the methods is (m + 1) for problems that admit a strict complementarity solution, while the Q-order of convergence of the other method is (m + 1)/2 for general monotone LCPs. [ABSTRACT FROM AUTHOR]

Consider solving a linear program in standard form where the constraint matrix A is m x n, with n ≫ m ≫ 1. Such problems arise, for example, as the result of finely discretizing a semi-infinite program. The cost per iteration of typical primal-dual interior-point methods on such problems is O(m²n). We propose to reduce that cost by replacing the normal equation matrix, AD²AT, where D is a diagonal matrix, with a "reduced" version (of same dimension), AQDQ²AQT, where Q is an index set including the indices of M most nearly active (or most violated) dual constraints at the current iterate, with M ≥ m a prescribed integer. This can result in a speedup of close to n/¦Q¦ at each iteration. Promising numerical results are reported for constraint-reduced versions of a dual-feasible affine-scaling algorithm and of Mehrotra's predictor-corrector method [S. Mehrotra, SIAM J. Optim., 2 (1992), pp. 575-601]. In particular, while it could be expected that neglecting a large portion of the constraints, especially at early iterations, may result in a significant deterioration of the search direction, it appears that the total number of iterations typically remains essentially constant as the size of the reduced constraint set is decreased down to some threshold. In some cases this threshold is a small fraction of the total set. In the case of the affine-scaling algorithm, global convergence and local quadratic convergence are proved. [ABSTRACT FROM AUTHOR]