Local convergence for alternating and averaged nonconvex projections

The idea of a finite collection of closed sets having “strongly regular intersection” at a given point is crucial in variational analysis. We show that this central theoretical tool also has striking algorithmic consequences. Specifically, we consider the case of two sets, one of which we assume to be suitably “regular” (special cases being convex … Read more

The Speed of Shor’s R-Algorithm

Shor’s r-algorithm is an iterative method for unconstrained optimization, designed for minimizing nonsmooth functions, for which its reported success has been considerable. Although some limited convergence results are known, nothing seems to be known about the algorithm’s rate of convergence, even in the smooth case. We study how the method behaves on convex quadratics, proving … Read more

Alternating projections on manifolds

We prove that if two smooth manifolds intersect transversally, then the method of alternating projections converges locally at a linear rate. We bound the speed of convergence in terms of the angle between the manifolds, which in turn we relate to the modulus of metric regularity for the intersection problem, a natural measure of conditioning. … Read more

Analysis of a Belgian Chocolate Stabilization Problem

We give a detailed numerical and theoretical analysis of a stabilization problem posed by V. Blondel in 1994. Our approach illustrates the effectiveness of a new gradient sampling algorithm for finding local optimizers of nonsmooth, nonconvex optimization problems arising in control, as well as the power of nonsmooth analysis for understanding variational problems involving polynomial … Read more

Perturbations and metric regularity

A point x is an approximate solution of a generalized equation [b lies in F(x)] if the distance from the point b to the set F(x) is small. Metric regularity of the set-valued mapping F means that, locally, a constant multiple of this distance bounds the distance from x to an exact solution. The smallest … Read more

Variational Analysis of Functions of the Roots of Polynomials

The Gauss-Lucas Theorem on the roots of polynomials nicely simplifies calculating the subderivative and regular subdifferential of the abscissa mapping on polynomials (the maximum of the real parts of the roots). This paper extends this approach to more general functions of the roots. By combining the Gauss-Lucas methodology with an analysis of the splitting behavior … Read more

A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization

Let $f$ be a continuous function on $\Rl^n$, and suppose $f$ is continuously differentiable on an open dense subset. Such functions arise in many applications, and very often minimizers are points at which $f$ is not differentiable. Of particular interest is the case where $f$ is not convex, and perhaps not even locally Lipschitz, but … Read more

The structured distance to ill-posedness for conic systems

An important measure of conditioning of a conic linear system is the size of the smallest structured perturbation making the system ill-posed. We show that this measure is unchanged if we restrict to perturbations of low rank. We thereby derive a broad generalization of the classical Eckart-Young result characterizing the distance to ill-posedness for a … Read more

The mathematics of eigenvalue optimization

Optimization problems involving the eigenvalues of symmetric and nonsymmetric matrices present a fascinating mathematical challenge. Such problems arise often in theory and practice, particularly in engineering design, and are amenable to a rich blend of classical mathematical techniques and contemporary optimization theory. This essay presents a personal choice of some central mathematical ideas, outlined for … Read more

The Lax conjecture is true

In 1958 Lax conjectured that hyperbolic polynomials in three variables are determinants of linear combinations of three symmetric matrices. This conjecture is equivalent to a recent observation of Helton and Vinnikov. Citation Department of Mathematics, Simon Fraser University, Canada Article Download View The Lax conjecture is true