superlinear convergence

Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems with application to linear matrix inequalities

  • Chee-Khian Sim
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    In the literature, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual and the NT direction, to solve semi-definite programs (SDPs) can be shown by (i) assuming that the given SDP is nondegenerate and modifying these algorithms [10], or (ii) considering special classes of SDPs, such … Read more

    A successive centralized circumcentered-reflection method for the convex feasibility problem

  • Yunier Bello-Cruz
  • Roger Behling
  • A. N. Iusem
  • Luiz-Rafael Santos
  • Di Liu
    • Categories Convex Optimization Tags , , ,

    In this paper, we present a successive centralization process for the circumcentered-reflection scheme with several control sequences for solving the convex feasibility problem in Euclidean space. Assuming that a standard error bound holds, we prove the linear convergence of the method with the most violated constraint control sequence. Moreover, under additional smoothness assumptions on the … Read more

    A globally trust-region LP-Newton method for nonsmooth functions under the Hölder metric subregularity

  • Leticia Becher
  • Damián Fernández
  • Alberto Ramos
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    We describe and analyse a globally convergent algorithm to find a possible nonisolated zero of a piecewise smooth mapping over a polyhedral set, such formulation includes Karush-Kuhn-Tucker (KKT) systems, variational inequalities problems, and generalized Nash equilibrium problems. Our algorithm is based on a modification of the fast locally convergent Linear Programming (LP)-Newton method with a … Read more

    Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods

  • M. Marques Alves
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , ,

    For solving strongly convex optimization problems, we propose and study the global convergence of variants of the A-HPE and large-step A-HPE algorithms of Monteiro and Svaiter. We prove \emph{linear} and the \emph{superlinear} $\mathcal{O}\left(k^{\,-k\left(\frac{p-1}{p+1}\right)}\right)$ global rates for the proposed variants of the A-HPE and large-step A-HPE methods, respectively. The parameter $p\geq 2$ appears in the (high-order) … Read more

    Accelerating Inexact Successive Quadratic Approximation for Regularized Optimization Through Manifold Identification

  • Ching-pei Lee
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    For regularized optimization that minimizes the sum of a smooth term and a regularizer that promotes structured solutions, inexact proximal-Newton-type methods, or successive quadratic approximation (SQA) methods, are widely used for their superlinear convergence in terms of iterations. However, unlike the counter parts in smooth optimization, they suffer from lengthy running time in solving regularized … Read more

    Limited-Memory BFGS with Displacement Aggregation

  • Albert S. Berahas
  • Frank E. Curtis
  • Baoyu Zhou
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    A displacement aggregation strategy is proposed for the curvature pairs stored in a limited-memory BFGS (a.k.a. L-BFGS) method such that the resulting (inverse) Hessian approximations are equal to those that would be derived from a full-memory BFGS method. This means that, if a sufficiently large number of pairs are stored, then an optimization algorithm employing … Read more

    Subsampled Inexact Newton methods for minimizing large sums of convex functions

  • Stefania Bellavia
  • Nataša Krejić
  • Nataša Krklec Jerinkić
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , ,

    This paper deals with the minimization of large sum of convex functions by Inexact Newton (IN) methods employing subsampled Hessian approximations. The Conjugate Gradient method is used to compute the inexact Newton step and global convergence is enforced by a nonmonotone line search procedure. The aim is to obtain methods with affordable costs and fast … Read more

    Multipoint secant and interpolation methods with nonmonotone line search for solving systems of nonlinear equations

  • Oleg Burdakov
  • Ahmad Kamandi
    • Categories Nonlinear Optimization Tags , , , , ,

    Multipoint secant and interpolation methods are effective tools for solving systems of nonlinear equations. They use quasi-Newton updates for approximating the Jacobian matrix. Owing to their ability to more completely utilize the information about the Jacobian matrix gathered at the previous iterations, these methods are especially efficient in the case of expensive functions. They are … Read more

    Superlinearly convergent smoothing Newton continuation algorithms for variational inequalities over definable sets

  • Chek Beng Chua
  • Le Thi Khanh Hien
    • Categories Complementarity and Variational Inequalities Tags , , ,

    In this paper, we use the concept of barrier-based smoothing approximations introduced by Chua and Li to extend various smoothing Newton continuation algorithms to variational inequalities over general closed convex sets X. We prove that when the underlying barrier has a gradient map that is definable in some o-minimal structure, the iterates generated converge superlinearly … Read more

    A Sequential Quadratic Optimization Algorithm with Rapid Infeasibility Detection

  • James V. Burke
  • Frank E. Curtis
  • Hao Wang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    We present a sequential quadratic optimization (SQO) algorithm for nonlinear constrained optimization. The method attains all of the strong global and fast local convergence guarantees of classical SQO methods, but has the important additional feature that fast local convergence is guaranteed when the algorithm is employed to solve infeasible instances. A two-phase strategy, carefully constructed … Read more