We present a theorem of Sard type for semi-algebraic set-valued mappings whose graphs have dimension no larger than that of their range space: the inverse of such a mapping admits a single-valued analytic localization around any pair in the graph, fo
r a generic value parameter. This simple result yields a transparent and unified treatment of generic properties of semi-algebraic optimization problems: typical semi-algebraic problems have finitely many critical points, around each of which they admit a unique active manifold (analogue of an active set in nonlinear optimization); moreover, such critical points satisfy strict complementarity and second-order sufficient conditions for optimality are indeed necessary.
We consider minimization of functions that are compositions of convex or prox-regular functions (possibly extended-valued) with smooth vector functions. A wide variety of important optimization problems fall into this framework. We describe an algori
thmic framework based on a subproblem constructed from a linearized approximation to the objective and a regularization term. Properties of local solutions of this subproblem underlie both a global convergence result and an identification property of the active manifold containing the solution of the original problem. Preliminary computational results on both convex and nonconvex examples are promising.
We consider the method of alternating projections for finding a point in the intersection of two closed sets, possibly nonconvex. Assuming only the standard transversality condition (or a weaker version thereof), we prove local linear convergence. Wh
en the two sets are semi-algebraic and bounded, but not necessarily transversal, we nonetheless prove subsequence convergence.
We prove that quasiconvex functions always admit descent trajectories bypassing all non-minimizing critical points.
Steepest descent is central in variational mathematics. We present a new transparent existence proof for curves of near-maximal slope --- an influential notion of steepest descent in a nonsmooth setting. We moreover show that for semi-algebraic funct
ions --- prototypical nonpathological functions in nonsmooth optimization --- such curves are precisely the solutions of subgradient dynamical systems.
We consider linear optimization over a fixed compact convex feasible region that is semi-algebraic (or, more generally, tame). Generically, we prove that the optimal solution is unique and lies on a unique manifold, around which the feasible region i
s partly smooth, ensuring finite identification of the manifold by many optimization algorithms. Furthermore, second-order optimality conditions hold, guaranteeing smooth behavior of the optimal solution under small perturbations to the objective.
We study randomized variants of two classical algorithms: coordinate descent for systems of linear equations and iterated projections for systems of linear inequalities. Expanding on a recent randomized iterated projection algorithm of Strohmer and V
ershynin for systems of linear equations, we show that, under appropriate probability distributions, the linear rates of convergence (in expectation) can be bounded in terms of natural linear-algebraic condition numbers for the problems. We relate these condition measures to distances to ill-posedness, and discuss generalizations to convex systems under metric regularity assumptions.
