Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence

We extend the Mizuno-Todd-Ye predictor-corrector algorithm for solving monotone linear complementarity problems. We prove that the extended algorithm is globally Q-linearly convergent and solves problems with integer data of bitlengthL in at most iterations. We also prove that the duality gap converges to zero Q-superlinearly for problems having strictly complementary solutions. Our results generalize the results obtained by Ye, Tapia, and Zhang for linear programming.     

A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio

We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = (d ²), the expected total number of major Karmarkar's iterations is O(d ²(logn)L), compared to the best known deterministic bound of O( L). We also present several other results which follow from the general scheme.     

An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations

We present an algorithm for linear programming which requires O(((m+n)n ²+(m+n)^1.5 n)L) arithmetic operations wherem is the number of constraints, andn is the number of variables. Each operation is performed to a precision of O(L) bits.L is bounded by the number of bits in the input. The worst-case running time of the algorithm is better than that of Karmarkar's algorithm by a factor of .     

A quadratically convergentO((\kappa + 1)\sqrt n L)-iteration algorithm for theP *(κ)-matrix linear complementarity problem

An interior-point predictor-corrector algorithm for theP _*()-matrix linear complementarity problem is proposed. The algorithm is an extension of Mizuno—Todd—Ye's predictor—corrector algorithm for linear programming problem. The extended algorithm is quadratically convergent with iteration complexity . It is the first polynomially and quadratically convergent algorithm for a class of LCPs that are not necessarily monotone.     

A quadratically convergent O(\sqrt n L)-iteration algorithm for linear programming

Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.Supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.Supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Supported in part by NSF Grant DMS-9102761 and DOE Grant DE-FG05-91ER25100.     

A simplified homogeneous and self-dual linear programming algorithm and its implementation

We present a simplification and generalization of the recent homogeneous and self-dual linear programming (LP) algorithm. The algorithm does not use any Big-M initial point and achieves -iteration complexity, wheren andL are the number of variables and the length of data of the LP problem. It also detects LP infeasibility based on a provable criterion. Its preliminary implementation with a simple predictor and corrector technique results in an efficient computer code in practice. In contrast to other interior-point methods, our code solves NETLIB problems, feasible or infeasible, starting simply fromx=e (primal variables),y=0 (dual variables),z=e (dual slack variables), wheree is the vector of all ones. We describe our computational experience in solving these problems, and compare our results with OB1.60, a state-of-the-art implementation of interior-point algorithms.Research supported in part by NSF Grant DDM-9207347 and by an Iowa College of Business Administration Summer Grant.Part of this work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, USA, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

Linear Widths of the Besov Classes of Periodic Functions of Many Variables. I

We obtain order estimates for linear widths of the Besov classes of periodic functions of many variables in the space L _q for certain values of the parameters p and q.     

A particle method for first-order symmetric systems

Summary We present and study a conservative particle method of approximation of linear hyperbolic and parabolic systems. This method is based on an extensive use of cut-off functions. We prove its convergence inL ² at the order as soon as the cut-off function belongs toW ^m+1.1.Dedicated to Professor Joachim Nitsche on the occasion of his 60th birthday     

Linear Widths of the Besov Classes of Periodic Functions of Many Variables. II

We obtain order estimates for linear widths of the Besov classes of periodic functions of many variables in the space L _q for certain values of parameters p and q different from those considered in the first part of the work.     

A Predictor–Corrector Algorithm for QSDP Combining Dikin-Type and Newton Centering Steps

Recently, we have extended SDP by adding a quadratic term in the objective function and give a potential reduction algorithm using NT directions. This paper presents a predictor–corrector algorithm using both Dikin-type and Newton centering steps and studies properties of Dikin-type step. In this algorithm, when the condition K(XS) is less than a given number K ₀, we use Dikin-type step. Otherwise, Newton centering step is taken. In both cases, step-length is determined by line search. We show that at least a constant reduction in the potential function is guaranteed. Moreover the algorithm is proved to terminate in O log(1/)) steps. In the end of this paper, we discuss how to compute search direction (X,S) using the conjugate gradient method.     

AnO(nL) infeasible-interior-point algorithm for LCP with quadratic convergence

The Mizuno-Todd-Ye predictor-corrector algorithm for linear programming is extended for solving monotone linear complementarity problems from infeasible starting points. The proposed algorithm requires two matrix factorizations and at most three backsolves per iteration. Its computational complexity depends on the quality of the starting point. If the starting points are large enough, then the algorithm hasO(nL) iteration complexity. If a certain measure of feasibility at the starting point is small enough, then the algorithm has iteration complexity. At each iteration, both feasibility and optimality are reduced exactly at the same rate. The algorithm is quadratically convergent for problems having a strictly complementary solution, and therefore its asymptotic efficiency index is . A variant of the algorithm can be used to detect whether solutions with norm less than a given constant exist.This work was supported in part by the National Science Foundation under grant DMS-9305760.     

Estimates for Approximation Characteristics of the Besov Classes $$B_{p,\theta }^r $$ of Periodic Functions of Many Variables in the Space Lq. II

We obtain order estimates for the approximation of the classes of periodic functions of many variables in the space L _q by using operators of orthogonal projection and linear operators satisfying certain conditions.     

Optimal Recovery of Functions and Their Derivatives from Inaccurate Information about the Spectrum and Inequalities for Derivatives

We study problems of optimal recovery of functions and their derivatives in the L ₂ metric on the line from information about the Fourier transform of the function in question known approximately on a finite interval or on the entire line. Exact values of optimal recovery errors and closed-form expressions for optimal recovery methods are obtained. We also prove a sharp inequality for derivatives (closely related to these recovery problems), which estimates the th derivative of a function in the L ₂-norm on the line via the L ₂-norm of the th derivative and the -norm of the Fourier transform of the function.     

A modified layered-step interior-point algorithm for linear programming

The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient matrixA. The main drawback of the algorithm is the use of an unknown big constant in computing the search direction and to initiate the algorithm. We propose a modified layered-step interior-point algorithm which does not use the big constant in computing the search direction. The constant is required only for initialization when a well-centered feasible solution is not available, and it is not required if an upper bound on the norm of a primal—dual optimal solution is known in advance. The complexity of the simplified algorithm is the same as that of Vavasis and Ye. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research supported in part by ONR contract N00014-94-C-0007 and the Grant-in-Aid for Scientific Research (C) 08680478 and the Grant-in-Aid for Encouragement of Young Scientists (A) 08780227 of the Ministry of Science, Education and Culture of Japan. This research was partially done while S. Mizuno and T. Tsuchiya were visiting IBM Almaden Research Center in the summer of 1995.     

An O(n 3 L) primal—dual potential reduction algorithm for solving convex quadratic programs

In this paper we combine partial updating and an adaptation of Anstreicher's safeguarded linesearch of the primal—dual potential function with Kojima, Mizuno and Yoshise's potential reduction algorithm for the linear complementarity problem to obtain an O(n ³ L) algorithm for convex quadratic programming. Our modified algorithm is a long step method that requires at most O( L) steps.This research was supported in part by ONR Contract N-00014-87-K0214, NSF Grants DMS-85-12277 and DMS-91-06195.     

Fine tuning Nesterov’s steepest descent algorithm for differentiable convex programming

We modify the first order algorithm for convex programming described by Nesterov in his book (in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004). In his algorithms, Nesterov makes explicit use of a Lipschitz constant L for the function gradient, which is either assumed known (Nesterov in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004), or is estimated by an adaptive procedure (Nesterov 2007). We eliminate the use of L at the cost of an extra imprecise line search, and obtain an algorithm which keeps the optimal complexity properties and also inherit the global convergence properties of the steepest descent method for general continuously differentiable optimization. Besides this, we develop an adaptive procedure for estimating a strong convexity constant for the function. Numerical tests for a limited set of toy problems show an improvement in performance when compared with the original Nesterov’s algorithms.     

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.     

Near boundary behavior of primal—dual potential reduction algorithms for linear programming

This paper is concerned with selection of the-parameter in the primal—dual potential reduction algorithm for linear programming. Chosen from [n + , ), the level of determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant, must be set close ton + . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate that can be sometimes chosen in a wide range [n + , ) while still guaranteeing the currently best convergence rate of O( L) iterations. This finding is encouraging since in practice large values of have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.Research supported in part by NSF Grant DDM-8922636.     

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.We present a complete solution to this problem: For every bin size b1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.     

A Shifted-Barrier Primal-Dual Algorithm Model for Linearly Constrained Optimization Problems

In this paper we describe a Newton-type algorithm model for solving smooth constrained optimization problems with nonlinear objective function, general linear constraints and bounded variables. The algorithm model is based on the definition of a continuously differentiable exact merit function that follows an exact penalty approach for the box constraints and an exact augmented Lagrangian approach for the general linear constraints. Under very mild assumptions and without requiring the strict complementarity assumption, the algorithm model produces a sequence of pairs converging quadratically to a pair where satisfies the first order necessary conditions and is a KKT multipliers vector associated to the linear constraints. As regards the behaviour of the sequence x ^k alone, it is guaranteed that it converges at least superlinearly. At each iteration, the algorithm requires only the solution of a linear system that can be performed by means of conjugate gradient methods. Numerical experiments and comparison are reported.