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 standard form variant,and safeguarded linesearch,for the modified Karmarkar algorithm

In his original analysis of the projective algorithm for linear programming, Karmarkar proposed a modified method which improved the worst-case arithmetic complexity of the original algorithm by a factor of . Karmarkar's analysis of the improvement is based on a primal-dual formulation, and requires that small steps be taken on each iteration. However, in practice the original algorithm can be easily applied to standard form problems, and is considerably improved by performing a linesearch on each iteration, generally leading to much larger steps. We show here that by incorporating a simple safeguard, a linesearch may be performed in the modified algorithm while retaining the complexity improvement over the original algorithm. We then show that the modified algorithm, with safeguarded linesearch, can be applied directly to a standard form linear program with unknown optimal objective value. The resulting algorithm enjoys a complexity advantage over standard form variants of the original algorithm.     

On the convergence of the method of analytic centers when applied to convex quadratic programs

This work examines the method of analytic centers of Sonnevend when applied to solve generalized convex quadratic programs — where also the constraints are given by convex quadratic functions. We establish the existence of a two-sided ellipsoidal approximation for the set of feasible points around its center and show, that a simple (zero order) algorithm starting from an initial center of the feasible set generates a sequence of strictly feasible points whose objective function values converge to the optimal value. Concerning the speed of convergence it is shown that an upper bound for the gap in between the objective function value and the optimal value is reduced by a factor of with iterations wherem is the number of inequality constraints. Here, each iteration involves the computation of one Newton step. The bound of Newton iterations to guarantee an error reduction by a factor of in the objective function is as good as the one currently given forlinear programs. However, the algorithm considered here is of theoretical interest only, full efficiency of the method can only be obtained when accelerating it by some (higher order) extrapolation scheme, see e.g. the work of Jarre, Sonnevend and Stoer.This work was supported by the Deutsche Forschungsgemeinschaft, Schwerpunktprogramm für anwendungsbezogene Optimierung und Steuerung.     

Comparative analysis of affine scaling algorithms based on simplifying assumptions

We analyze several affine potential reduction algorithms for linear programming based on simplifying assumptions. We show that, under a strong probabilistic assumption regarding the distribution of the data in an iteration, the decrease in the primal potential function will be with high probability, compared to the guaranteed(1). ( 2n is a parameter in the potential function andn is the number of variables.) Under the same assumption, we further show that the objective reduction rate of Dikin's affine scaling algorithm is with high probability, compared to no guaranteed convergence rate.Research supported in part by NSF Grant DDM-8922636.     

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 .     

Interior path following primal-dual algorithms. part II: Convex quadratic programming

We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of O(n ³ L).     

An interior point method, based on rank-1 updates, for linear programming

We propose a polynomial time primal—dual potential reduction algorithm for linear programming. The algorithm generates sequencesd ^k andv ^k rather than a primal—dual interior point (x ^k ,s ^k ), where and fori = 1, 2,,n. Only one element ofd ^k is changed in each iteration, so that the work per iteration is bounded by O(mn) using rank-1 updating techniques. The usual primal—dual iteratesx ^k ands ^k are not needed explicitly in the algorithm, whereasd ^k andv ^k are iterated so that the interior primal—dual solutions can always be recovered by aforementioned relations between (x ^k, s^k) and (d ^k, v^k) with improving primal—dual potential function values. Moreover, no approximation ofd ^k is needed in the computation of projection directions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

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.     

On the convergence rate of imperfect minimization algorithms in Broyden'sβ-class

This paper presents a local convergence analysis of Broyden's class of rank-2 algorithms for solving unconstrained minimization problems, ,h C¹(R ⁿ ), assuming that the step-size ai in each iterationx _i+1 =x _i - _i H _i h(x _i ) is determined by approximate line searches only. Many of these methods including the ones most often used in practice, converge locally at least with R-order, .     

Corrector–predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path

Two corrector–predictor interior point algorithms are proposed for solving monotone linear complementarity problems. The algorithms produce a sequence of iterates in the neighborhood of the central path. The first algorithm uses line search schemes requiring the solution of higher order polynomial equations in one variable, while the line search procedures of the second algorithm can be implemented in arithmetic operations, where n is the dimension of the problems, is a constant, and m is the maximum order of the predictor and the corrector. If then both algorithms have iteration complexity. They are superlinearly convergent even for degenerate problems.      

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.     

Interior path following primal-dual algorithms. part I: Linear programming

We describe a primal-dual interior point algorithm for linear programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea.     

Proximity control in bundle methods for convex nondifferentiable minimization

Proximal bundle methods for minimizing a convex functionf generate a sequence {x ^k } by takingx ^k+1 to be the minimizer of , where is a sufficiently accurate polyhedral approximation tof andu ^k > 0. The usual choice ofu ^k = 1 may yield very slow convergence. A technique is given for choosing {u ^k } adaptively that eliminates sensitivity to objective scaling. Some encouraging numerical experience is reported.This research was supported by Project CPBP.02.15.     

Complexity analysis of a linear complementarity algorithm based on a Lyapunov function

We consider a path following algorithm for solving linear complementarity problems with positive semi-definite matrices. This algorithm can start from any interior solution and attain a linear rate of convergence. Moreover, if the starting solution is appropriately chosen, this algorithm achieves a complexity of O( L}) iterations, wherem is the number of variables andL is the size of the problem encoding in binary. We present a simple complexity analysis for this algorithm, which is based on a new Lyapunov function for measuring the nearness to optimality. This Lyapunov function has itself interesting properties that can be used in a line search to accelerate convergence. We also develop an inexact line search procedure in which the line search stepsize is obtainable in a closed form. Finally, we extended this algorithm to handle directly variables which are unconstrained in sign and whose corresponding matrix is positive definite. The rate of convergence of this extended algorithm is shown to be independent of the number of such variables.This research is partially supported by the U.S. Army Research Office, contract DAAL03-86-K-0171 (Center for Intelligent Control Systems), and by the National Science Foundation, grant NSF-ECS-8519058.     

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.     

Win probabilities and simple majorities in probabilistic voting situations

This paper considers an election between candidatesA andB in which (1) voters may be uncertain about which candidate they will vote for, and (2) the winner is to be determined by a lottery betweenA andB that is based on their vote totals. This lottery is required to treat voters equally, to treat candidates equally, and to respond nonnegatively to increased support for a candidate. The set _n of all such lottery rules based on a total ofn voters is the convex hull of aboutn/2 basic lottery rules which include the simple majority rule. For odd values ofn 3 let , and for even values ofn 4 let . With the average of then voters probabilities of voting forA, it is shown that within _n the simple majority rule maximizes candidateA's overall win probability whenever , and that(n) is the smallest number for which this is true. Similarly, the simple majority rule maximizesB's overall win probability whenever (the average of the voters probabilities of voting forB) is as large as(n). This research was supported by the National Science Foundation, Grant SOC 75-00941.     

On Plane Maximal Curves

The number N of rational points on an algebraic curve of genus g over a finite field satisfies the Hasse–Weil bound . A curve that attains this bound is called maximal. With and , it is known that maximalcurves have . Maximal curves with have been characterized up to isomorphism. A natural genus to be studied is and for this genus there are two non-isomorphic maximal curves known when . Here, a maximal curve with genus g ₂ and a non-singular plane model is characterized as a Fermat curve of degree .     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

Intersections of Convex Bodies

Let be nonempty convex bodies in . Let be vectors in , let , and let . Then is a convex set, and the family of sets is concave. Let . Then for the mean cross-sectional measures W_v (\Phi (\rho )), , the functions are concave on D. (Note that % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbnrfifHhDYfgasaacH8srps0lbbf9q8WrFfeuY-Hhbbf9v8qqaq% Fr0xc9pk0xbba9q8WqFfea0-yr0RYxir-Jbba9q8aq0-yq-He9q8qq% Q8frFve9Fve9Ff0dmeaabaqaciGacaGaaeqabaWaaeaaeaaakeaaca% WGxbWaaSbaaSqaaiaaicdaaeqaaOGaaiikaiabfA6agjaacIcacqaH% bpGCcaGGPaGaaiykaiabg2da9iaabAfacaqGVbGaaeiBamaaBaaale% aatCvAUfKttLearyqr1ngBPrgaiuGacqWFRbWAaeqaaOGaeuOPdyKa% aiikaiabeg8aYjaacMcaaaa!4EE7!\[W_0 (\Phi (\rho )) = {\text{Vol}}_k\Phi (\rho )\] is the k-volume.) Bibliography: 2 titles.     

Superfluous matrices in linear complementarity

Superfluous matrices were introduced by Howe (1983) in linear complementarity. In general, producing examples of this class is tedious (a few examples can be found in Chapter 6 of Cottle, Pang and Stone (1992)). To overcome this problem, we define a new class of matrices and establish that in superfluous matrices of any ordern 4 can easily be constructed. For every integerk, an example of a superfluous matrix of degreek is exhibited in the end.