linear convergence

A Linearly Convergent Linear-Time First-Order Algorithm for Support Vector Classification with a Core Set Result

  • Piyush Kumar
  • E. Alper Yildirim
    • Categories Convex Optimization Tags , , , , ,

    We present a simple, first-order approximation algorithm for the support vector classification problem. Given a pair of linearly separable data sets and $\epsilon \in (0,1)$, the proposed algorithm computes a separating hyperplane whose margin is within a factor of $(1-\epsilon)$ of that of the maximum-margin separating hyperplane. We discuss how our algorithm can be extended … Read more

    Local convergence for alternating and averaged nonconvex projections

  • Adrian Lewis
  • Jérôme Malick
  • Russell Luke
    • Categories Constrained Nonlinear Optimization, Control Applications, Nonsmooth Optimization Tags , , , , , , , ,

    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

  • James V. Burke
  • Adrian Lewis
  • Michael L. Overton
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    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

    An Augmented Primal-Dual Method for Linear Conic Programs

  • Florian Jarre
  • Franz Rendl
    • Categories Convex Optimization Tags , ,

    We propose a new iterative approach for solving linear programs over convex cones. Assuming that Slaters condition is satisfied, the conic problem is transformed to the minimization of a convex differentiable function. This “agumented primal-dual function” or “apd-function” is restricted to an affine set in the primal-dual space. The evaluation of the function and its … Read more

    Linear convergence of a modified Frank-Wolfe algorithm for computing minimum volume ellipsoids

  • Selin Damla Ahipasaoglu
  • Peng Sun
  • Michael J. Todd
    • Categories Convex Optimization Tags , , ,

    We show the linear convergence of a simple first-order algorithm for the minimum-volume enclosing ellipsoid problem and its dual, the D-optimal design problem of statistics. Computational tests confirm the attractive features of this method. Citation Optimization Methods and Software 23 (2008), 5–19. Article Download View Linear convergence of a modified Frank-Wolfe algorithm for computing minimum … Read more

    Alternating projections on manifolds

  • Adrian Lewis
  • Jérôme Malick
    • Categories Constrained Nonlinear Optimization Tags , , , , , ,

    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

    NOTE ON PAN’S SECOND-ORDER QUASI-NEWTON UPDATES

  • Pan Pingqi
  • Lei-Hong Zhang
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , ,

    This note, attempts to further Pan’s second-order quasi-Newton methods(\cite{panqn}). To complement the numerical implementation, the linear convergence of a rank-one second-order update and the least change property are presented. Citation 1,Department of Mathematics, Southeast University, Nanjing, 210096, P.R.China.