On the cost of approximating all roots of a complex polynomial

This work examines the computational complexity of a homotopy algorithm in approximating all roots of a complex polynomialf. It is shown that, probabilistically, monotonic convergence to each of the roots occurs after a determined number of steps. Moreover, in all subsequent steps, each rootz is approximated by a complex numberx, where ifx ₀ =x, x _j =x _j–1 –f(x _j–1)/f(x _j–1),j = 1, 2,, then |x _j –z| < (1/|x ₀ –z|)|x _j–1–z|².     

Foreword

Foundations of Computational Mathematics -     

A Simple Nearly Optimal Restart Scheme For Speeding Up First-Order Methods

Foundations of Computational Mathematics - We present a simple scheme for restarting first-order methods for convex optimization problems. Restarts are made based only on achieving specified...     

Unified complexity analysis for Newton LP methods

We show that a theorem of Smale can be used to unify the polynomial-time bound proofs of several of the recent interior algorithms for linear programming and convex quadratic programming.This research is supported by NSF grants.     

Foreword

Steve Smale set the agenda for FoCM in his call for the 1995 conference in Park City, Utah. No stranger he to ambitious agendas and extraordinary accomplishments. He is one of the dominant figures in the mathematics of the second half of the twentieth century. Smale’s theory of immersions, the generalized Poincare conjecture, and H-cobordism theorems with their far-reaching consequences are the bedrock of differential topology. His horseshoe is the hallmark of chaos, and his hyperbolic dynamics the rejuvenation of the geometric theory of dynamical systems. He is one of the pioneers in the introduction of infinite-dimensional manifolds for the study of nonlinear problems in the calculus of variations and partial differential equations. The list goes on: the systematic use of differential techniques in microeconomics, electrical circuit theory, chaos in predator–prey equations and, finally, for the twentieth century, the foundations of computational mathematics and complexity theory, and now, in the twenty-first century, the theory of learning. It has been our privilege to be among his collaborators and students in the broadest sense of the word. With these issues (Volume 5 Number 4 and Volume 6 Number 1, as well as an earlier article appearing in Volume 5 Number 2, are dedicated to Steve Smale’s 75th Birthday) we celebrate Steve’s 75th birthday and continuing vitality. He sets the bar high. We do our best.     

Computing approximate solutions for convex conic systems of constraints

We propose a way to reformulate a conic system of constraints as an optimization problem. When an appropriate interior-point method (ipm) is applied to the reformulation, the ipm iterates yield backward-approximate solutions, that is, solutions for nearby conic systems. In addition, once the number of ipm iterations passes a certain threshold, the ipm iterates yield forward-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of distance to ill-posedness of the original conic system.?The condition numbers of the linear equations encountered when applying an ipm influence the computational cost at each iteration. We show that for the reformulation, the condition numbers of the linear equations are uniformly bounded both when computing reasonably-accurate backward-approximate solutions to arbitrary conic systems and when computing forward-approximate solutions to well-conditioned conic systems. Received: July 11, 1997 / Accepted: August 18, 1999?Published online March 15, 2000     

Linear programming,complexity theory and elementary functional analysis

We propose analyzing interior-point methods using notions of problem-instance size which are direct generalizations of the condition number of a matrix. The notions pertain to linear programming quite generally; the underlying vector spaces are not required to be finite-dimensional and, more importantly, the cones defining nonnegativity are not required to be polyhedral. Thus, for example, the notions are appropriate in the context of semi-definite programming. We prove various theorems to demonstrate how the notions can be used in analyzing interior-point methods. These theorems assume little more than that the interiors of the cones (defining nonnegativity) are the domains of self-concordant barrier functions.Research supported by NSF Grant #CCR-9103285 and IBM. This paper was conceived in part while the author was sponsored by the visiting scientist program at the IBM T.J. Watson Research Center.     

Some perturbation theory for linear programming

Mathematical Programming -     

Rudiments of an average case complexity theory for piecewise-linear path following algorithms

We examine the efficiency of PL path following algorithms in followingF _T ^-1 (0), whereF _T is the PL approximation, induced by the simplicial triangulationT, to a mapf: ^{n n-1}. In particular, we consider the problem of determining an upper bound on the expected number of pivots made per unit length off ^–1(0) that is approximated. We show that if the sizes of the simplices ofT are sufficiently small, where sufficiently small is an explicitly given quantity dependent on measurements of how nicef is, then the average directional density ofT, as introduced by Todd, really does give a good approximation to the expected number of pivots made, confirming what researchers have believed on intuitive grounds for a decade. Because what constitutes sufficiently small is a precisely given quantity, i.e., non-asymptotic, we are able to provide some rigorous justification for the claim that the expected number of pivots grows only polynomially inn, the number of variables.Several other issues are also examined.Research supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship. This research was performed while the author was a member of the Mathematical Sciences Research Institute, Berkeley, California.     

On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials

LetS be a triangulation of andf(z) = z ^d +a _d–1 z ^d–1++a ₀, a complex polynomial. LetF be the piecewise linear approximation off determined byS. For certainS, we establish an upper bound on the complexity of an algorithm which finds zeros ofF. This bound is a polynomial in terms ofn, max{a _i } _i , and measures of the sizes of simplices inS.