A class of simplicial restart fixed point algorithms without an extra dimension

In an earlier paper we introduced an algorithm for approximating a fixed point of a mapping on the product space of unit simplices. Ideas of that paper are used to construct a class of triangulations ofR ⁿ. More precisely, for somek, 1 k n, and positive integersm ₁ , m_k with sumn, a triangulation ofR ⁿ is obtained by triangulating the cells which are formed by taking the product of given triangulations ofR ^mj, j = 1, ,k. The triangulation of each cell will be defined in relation to an arbitrarily chosen pointv inR ⁿ, being the starting point of the algorithm. Fork = n we obtain theK triangulation originally due to Todd. Each element of the class can be used to find a simplex which approximates a fixed point of a mapping onR ⁿ by generating a unique path of adjacent simplices of variable dimension starting with the pointv. We also give convergence conditions. It is indicated how in casek = n a connected set of fixed points can be generated. Moreover, we give some computational experience.     

Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems

Summary This paper deals with rational functions ø(z) approximating the exponential function exp(z) related to numerical procedures for solving initial value problems. Motivated by positivity and contractivity requirements imposed on these numerical procedures we study the greatest nonnegative numberR, denoted byR(ø), such that ø is absolutely monotonic on (–R, 0]. An algorithm for the computation ofR(ø) is presented. Application of this algorithm yields the valueR(ø) for the well-known Padé approximations to exp(z). For some specific values ofm, n andp we determine the maximum ofR(ø) when ø varies over the class of all rational functions ø with degree of the numerator m, degree of the denominator n and ø(z)=exp(z)+(z ^p+1 ) (forz0).     

A generalized conjugate gradient algorithm for minimization

Summary A generalized conjugate gradient algorithm which is invariant to a nonlinear scaling of a strictly convex quadratic function is described, which terminates after at mostn steps when applied to scaled quadratic functionsf: R _n R₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹ (R₁) an arbitrary strictly monotone functionh. The algorithm does not suppose the knowledge ofh orF but only off(x) and its gradientg(x).     

Homotopies for computation of fixed points on unbounded regions

Givenf: R ⁿ R ^n* with some conditions, our aim is to compute a fixed pointx f(x) off; hereR ⁿ isn-dimensional Euclidean space andR ^n* is the collection of nonempty subsets ofR ⁿ . A typical application of the algorithm can be motivated as follows: Beginning with the constant mapf ₀:R ⁿ {0} R ⁿ and its fixed pointx ₀ = 0, we deformf _t ast tof f and follow the pathx _t of fixed points off _t . Cluster points of thex _t 's ast are fixed points off. This research was supported in part by Army Research Office-Durham Contract DAHC-04-71-C-0041 and by National Science Foundation Grant GK-5695.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

On accelerating PL continuation algorithms by predictor—corrector methods

We consider path following methods designed to trace the zeroes of a continuous or differentiable mapF:R ⁿ⁺¹ R ⁿ . These methods are applicable e.g. in the numerical study of nonlinear eigenvalue and bifurcation problems. Traditionally a simplicial algorithm is based on a fixed triangulationT ofR ⁿ⁺¹ and a corresponding piecewise linear approximationF _T :R ⁿ⁺¹ R ⁿ .4 A fixed triangulation algorithm then traces the zeroes ofF _T via a complementary pivoting procedure. We present two kinds of hybrid algorithms that have the structure of a predictor—corrector method using simplicial methods to carry out the corrector steps. Numerical experience is reported showing the improvement in efficiency as compared to the fixed triangulation algorithm.     

Entire functions of exponential type,increasing slowly along the real hyperplane

Entire functionsf(z), zC ⁿ , of exponential type at most a and bounded on subsets E of the real hyperplane, are investigated. It is known that if E is relatively dense with respect to the Lebesgue measure or it is an -net inR ⁿ , then such f(z) are bounded on all ofR ⁿ (for e-nets in the case of sufficiently small ). It is shown that if E is close in a certain sense either to a relatively dense subset ofR ⁿ , or to an -net, then f(z) cannot increase fast alongR ⁿ . Similar estimates are established for integral metrics.Translated from Teoriya Funktsii, Funktsional'nyi Analiz i Ikh Prilozheniya, No. 50, pp. 74–76, 1988.     

Consistency of a linear system of inequalities

We show that a consistency check of a linear system of inequalitiesAxb reduces to check whetherQb0 for a certain matrixQ. It is a direct consequence of the Farkas-Minkowski theorem. Thus, when one has to check consistency for different values ofb, one need not run a numerical algorithm for eachb.On leave at the Electronics Research Laboratory of the University of California at Berkeley in a CNRS/NSF Exchange Program.     

A select and insert sorting algorithm

A general sorting algorithm, having the well knownO(n ²) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n ^1.5) and a worst case complexity ofO(n ²). However, making random choices (by some random number generator) is time consuming, and a simple quasi-random scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n ^1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.     

Infinite retrogression in the Eaves—Saigal algorithm

For certain functionsf fromR ⁿ toR ⁿ , the Eaves—Saigal algorithm computes a path inR ⁿ × (0, 1] which converges to a zero off. In this case, it is shown that even whenf is of classC and has a unique zero, the converging path may retrogress infinitely many times.Army Research Office, Durham, Contract No. DAAG-29-78-G-0026; National Science Foundation Grant No. MCS-77-05623.     

Separating convex sets in the plane

Given a setA inR ² and a collectionS of plane sets, we say that a lineL separatesA fromS ifA is contained in one of the closed half-planes defined byL, while every set inS is contained in the complementary closed half-plane.We prove that, for any collectionF ofn disjoint disks inR ², there is a lineL that separates a disk inF from a subcollection ofF with at least (n–7)/4 disks. We produce configurationsH _n andG _n , withn and 2n disks, respectively, such that no pair of disks inH _n can be simultaneously separated from any set with more than one disk ofH _n , and no disk inG _n can be separated from any subset ofG _n with more thann disks.We also present a setJ _m with 3m line segments inR ², such that no segment inJ _m can be separated from a subset ofJ _m with more thanm+1 elements. This disproves a conjecture by N. Alonet al. Finally we show that ifF is a set ofn disjoint line segments in the plane such that they can be extended to be disjoint semilines, then there is a lineL that separates one of the segments from at least n/3+1 elements ofF.     

Near-rings with no non-zero nilpotent two-sidedR-subsets

It has been proved that, ifR is a near-ring with no non-zero nilpotent two-sidedR-subsets and if the annihilator of any non-zero ideal is contained in some maximal annihilator, thenR is a subdirect sum of strictly prime near-rings. Moreover, ifR is a near-ring with no non-zero nilpotent two-sidedR-subsets and satisfying a.c.c. or d.c.c. on annihilating ideals of the form Ann (Q), whereQ is an ideal ofR, thenR is a finite subdirect sum of strictly prime near-rings. It is also proved that, ifR is a regular and right duo near-ring that satisfies a.c.c. (or d.c.c.) on annihilating ideals of the form Ann (Q), whereQ is an ideal ofR, thenR is a finite direct sum of near-ringsR _i (1 i n) where eachR _i is simple and strictly prime.     

Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

In this paper we analyze the average number of steps performed by the self-dual simplex algorithm for linear programming, under the probabilistic model of spherical symmetry. The model was proposed by Smale. Consider a problem ofn variables withm constraints. Smale established that for every number of constraintsm, there is a constantc(m) such that the number of pivot steps of the self-dual algorithm,(m, n), is less thanc(m)(lnn) ^m(m+1) . We improve upon this estimate by showing that(m, n) is bounded by a function ofm only. The symmetry of the function inm andn implies that(m, n) is in fact bounded by a function of the smaller ofm andn. Parts of this research were done while the author was visiting Stanford University, XEROX- PARC, Carnegie-Mellon University and Northwestern University and was supported in part by the National Science Foundation under Grants MCS-8300984, ECS-8218181 and ECS-8121741.     

Unique winning policies for linear differential pursuit games

We study optimal control problems which are the duals, in a specified sense, to a certain class of linear differential games. Directly verifiable conditions, in terms of the data of the game, for uniqueness of solutions of the dual problem and thus for uniqueness of winning policies for the differential game, are derived. As a byproduct, in the particular context of two-dimensional problems, a strong result concerning normality is obtained. As a second byproduct, several geometrical and topological properties of thestar difference are derived. This set operation is of paramount importance for the study of rich classes of differential and difference games extending far beyond that treated here.Notation co(P) convex hull of a setPR ⁿ - ext(P) set of extreme points ofP - [x ₁,x ₂] line segment joining the pointsx ₁,x ₂ R ⁿ - S(P, c) Supporting closed halfspace ofP with exterior normalc - H(P, c) supporting hyperplane ofP with exterior normalc - F(P, c) face of the polytopeP with exterior normalc - span(P) linear span ofP - lin(P) linear closure ofP = smallest linear manifold containingP - relbd(P) relative boundary ofP - int(P) interior ofP with respect to the topology ofR ⁿ - ri(P) relative interior ofP with respect to lin(P) - a, b inner product (inR ⁿ) ofa andb - U/W {x:x U R ⁿ andx W R ⁿ} - cl(P) closure ofP This work was done during the year 1972, when the author was a student of Prof. O. Hajek at Case Western Reserve University, Cleveland, Ohio. The author wishes to thank Dr. Hajek for his many comments, suggestions, and critique.     

On the number of iterations of Karmarkar's algorithm for linear programming

Karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a potential function by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple ofn, wheren is the number of inequality constraints. By considering a simple example that allowsn to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by Karmarkar's original algorithm can require aboutn/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

On the evaluation of multivariate polynomials and their derivatives

LetH be a polynomial inn>1 variables over the fields of real or complex numbers. An algorithm is presented here for the simultaneous evaluation ofH and its first and second (F-) derivativesH andH, or of any combination ofH,H,H. The evaluations ofH alone or ofH andH together are of the same order inn andd whered is the degree ofH, while the computation ofH,H, andH isd times this order. The process takes account of the sparsity pattern ofH by using a tree structure induced by the nonzero coefficients. It also allows for simultaneous operation with several polynomials with the same sparsity pattern. The data structure for the method is rather simple in nature and can be adapted easily to specific types of polynomials. Several possible implementations and their complexity are discussed.     

Persistency in quadratic 0–1 optimization

This paper is concerned with persistency properties which allow the evaluation of some variables at all maximizing points of a quadratic pseudo-Boolean function. Hammer, Hansen and Simeone (1984) have proposed to determine these variables using a procedure described by Balinski for computing a strongly complementary pair of optimal primal and dual solutions for arbitrary linear programs. We propose a linear time algorithm for determining these variables from a best roof off, i.e. from a lowest upper linear bound off.     

Numerical decomposition of a convex function

Given then×p orthogonal matrixA and the convex functionf:R ⁿR, we find two orthogonal matricesP andQ such thatf is almost constant on the convex hull of ± the columns ofP, f is sufficiently nonconstant on the column space ofQ, and the column spaces ofP andQ provide an orthogonal direct sum decomposition of the column space ofA. This provides a numerically stable algorithm for calculating the cone of directions of constancy, at a pointx, of a convex function. Applications to convex programming are discussed.This work was supported by the National Science and Engineering Research Council of Canada (Grant No. A3388 and Summer Grant).     

On a certain identity satisfied by a derivation and an arbitrary additive mapping

Summary LetR be a prime ring andd be a nonzero derivation ofR. If an additive mappingf ofR satisfiesd(x)f(x) = 0 for allx R, thenf vanishes on some nonzero left ideal ofR and on some nonzero right ideal ofR.     

A note on constructing a symmetric matrix with specified diagonal entries and eigenvalues

A finite step algorithm is given such that for any two vectorsa, R ⁿ witha majorized by , it computes a symmetric matrixH R ^{n x n} with the elements ofa and as its diagonal entries and eigenvalues, respectively.Supported in part by NSF grant CCR-9308399.Supported in part by China State Major Key Project for Basic Researches.