Unconstrained Optimization

Quadratic regularization with cubic descent for unconstrained optimization

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Unconstrained Optimization Tags , , , ,

    Cubic-regularization and trust-region methods with worst case first-order complexity $O(\varepsilon^{-3/2})$ and worst-case second-order complexity $O(\varepsilon^{-3})$ have been developed in the last few years. In this paper it is proved that the same complexities are achieved by means of a quadratic regularization method with a cubic sufficient-descent condition instead of the more usual predicted-reduction based descent. … Read more

    R-Linear Convergence of Limited Memory Steepest Descent

  • Frank E. Curtis
  • Wei Guo
    • Categories Nonlinear Optimization, Unconstrained Optimization

    The limited memory steepest descent method (LMSD) proposed by Fletcher is an extension of the Barzilai-Borwein “two-point step size” strategy for steepest descent methods for solving unconstrained optimization problems. It is known that the Barzilai-Borwein strategy yields a method with an R-linear rate of convergence when it is employed to minimize a strongly convex quadratic. … Read more

    Block BFGS Methods

  • Wenbo Gao
  • Donald Goldfarb
    • Categories Unconstrained Optimization Tags , , ,

    We introduce a quasi-Newton method with block updates called Block BFGS. We show that this method, performed with inexact Armijo-Wolfe line searches, converges globally and superlinearly under the same convexity assumptions as BFGS. We also show that Block BFGS is globally convergent to a stationary point when applied to non-convex functions with bounded Hessian, and … Read more

    Regularized nonlinear acceleration

  • Francis Bach
  • Alexandre d'Aspremont
  • Damien Scieur
    • Categories Convex Optimization, Unconstrained Optimization Tags

    We describe a convergence acceleration technique for generic optimization problems. Our scheme computes estimates of the optimum from a nonlinear average of the iterates produced by any optimization method. The weights in this average are computed via a simple linear system, whose solution can be updated online. This acceleration scheme runs in parallel to the … Read more

    Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    High-order optimality conditions for convexly-constrained nonlinear optimization problems are analyzed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order $\epsilon$-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that, if derivatives of the objective function up to order $q \geq 1$ … Read more

    Step lengths in BFGS method for monotone gradients

  • Yunda Dong
    • Categories Convex Optimization, Unconstrained Optimization

    In this paper, we consider how to directly apply the BFGS method to finding a zero point of any given monotone gradient and thus suggest new conditions to locate the corresponding step lengths. The suggested conditions involve curvature condition and merely use gradients’ computations. Furthermore, they can guarantee convergence without any other restrictions. Finally, preliminary … Read more

    ALGORITHM XXX: SC-SR1: MATLAB SOFTWARE FOR SOLVING SHAPE-CHANGING L-SR1 TRUST-REGION SUBPROBLEMS

  • Johannes Brust
  • Oleg Burdakov
  • Jennifer B. Erway
  • Roummel F. Marcia
  • Ya-xiang Yuan
    • Categories Unconstrained Optimization Tags , , , , ,

    We present a MATLAB implementation of the shape-changing sym- metric rank-one (SC-SR1) method that solves trust-region subproblems when a limited-memory symmetric rank-one (L-SR1) matrix is used in place of the true Hessian matrix. The method takes advantage of two shape-changing norms [4, 3] to decompose the trust-region subproblem into two separate problems. Using one of … Read more

    A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation

  • Émilie Chouzenoux
  • Jean-Christophe Pesquet
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , , , , , , , ,

    Stochastic approximation techniques play an important role in solving many problems encountered in machine learning or adaptive signal processing. In these contexts, the statistics of the data are often unknown a priori or their direct computation is too intensive, and they have thus to be estimated online from the observed signals. For batch optimization of … Read more

    Backward Step Control for Global Newton-type Methods

  • Andreas Potschka
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , ,

    We present and analyze a new damping approach called backward step control for the globalization of the convergence of Newton-type methods for the numerical solution of nonlinear root-finding problems. We provide and discuss reasonable assumptions that imply convergence of backward step control on the basis of generalized Newton paths in conjunction with a backward analysis … Read more