Unconstrained Optimization

High-order Evaluation Complexity of a Stochastic Adaptive Regularization Algorithm for Nonconvex Optimization Using Inexact Function Evaluations and Randomly Perturbed Derivatives

  • Stefania Bellavia
  • Benedetta Morini
  • Philippe L. Toint
  • Gianmarco Gurioli
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    A stochastic adaptive regularization algorithm allowing random noise in derivatives and inexact function values is proposed for computing strong approximate minimizers of any order for inexpensively constrained smooth optimization problems. For an objective function with Lipschitz continuous p-th derivative in a convex neighbourhood of the feasible set and given an arbitrary optimality order q, it … Read more

    Using gradient directions to get global convergence of Newton-type methods

  • Daniela di Serafino
  • Gerardo Toraldo
  • Marco Viola
    • Categories Unconstrained Optimization

    The renewed interest in Steepest Descent (SD) methods following the work of Barzilai and Borwein [IMA Journal of Numerical Analysis, 8 (1988)] has driven us to consider a globalization strategy based on SD, which is applicable to any line-search method. In particular, we combine Newton-type directions with scaled SD steps to have suitable descent directions. … Read more

    Variance Reduction of Stochastic Gradients Without Full Gradient Evaluation

  • Florian Jarre
  • Felix Lieder
    • Categories Unconstrained Optimization Tags ,

    A standard concept for reducing the variance of stochastic gradient approximations is based on full gradient evaluations every now and then. In this paper an approach is considered that — while approximating a local minimizer of a sum of functions — also generates approximations of the gradient and the function values without relying on full … Read more

    Complexity iteration analysis for stongly convex multi-objective optimization using a Newton path-following procedure

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
    • Categories Unconstrained Optimization

    In this note we consider the iteration complexity of solving strongly convex multi objective optimization. We discuss the precise meaning of this problem, and indicate it is loosely defined, but the most natural notion is to find a set of Pareto optimal points across a grid of scalarized problems. We derive that in most cases, … Read more

    Expected complexity analysis of stochastic direct-search

  • Kwassi Joseph Dzahini
    • Categories Nonlinear Optimization, Stochastic Approaches, Unconstrained Optimization Tags , , , , ,

    This work presents the convergence rate analysis of stochastic variants of the broad class of direct-search methods of directional type. It introduces an algorithm designed to optimize differentiable objective functions $f$ whose values can only be computed through a stochastically noisy blackbox. The proposed stochastic directional direct-search (SDDS) algorithm accepts new iterates by imposing a … Read more

    Properties of the delayed weighted gradient method

  • Roberto Andreani
  • Marcos Raydan
    • Categories Unconstrained Optimization Tags , , , ,

    The delayed weighted gradient method, recently introduced in [13], is a low-cost gradient-type method that exhibits a surprisingly and perhaps unexpected fast convergence behavior that competes favorably with the well-known conjugate gradient method for the minimization of convex quadratic functions. In this work, we establish several orthogonality properties that add understanding to the practical behavior … Read more

    A Hybrid Gradient Method for Strictly Convex Quadratic Programming

  • Oscar S. Dalmau
  • Rafael Herrera
  • Harry Oviedo
    • Categories Convex Optimization, Nonlinear Optimization, Unconstrained Optimization Tags ,

    In this paper, a reliable hybrid algorithm for solving convex quadratic minimization problems is presented. At each iteration, two points are computed: first, an auxiliary point $\dot{x}_k$ is generated by performing a gradient step equipped with an optimal steplength, then, the next iterate $x_{k+1}$ is obtained through a weighted sum of $\dot{x}_k$ with the penultimate … Read more

    Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions

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

    We introduce the concept of strong high-order approximate minimizers for nonconvex optimization problems. These apply in both standard smooth and composite non-smooth settings, and additionally allow convex or inexpensive constraints. An adaptive regularization algorithm is then proposed to find such approximate minimizers. Under suitable Lipschitz continuity assumptions, whenever the feasible set is convex, it is … Read more

    Modeling Hessian-vector products in nonlinear optimization: New Hessian-free methods

  • L. Song
  • Luis Nunes Vicente
    • Categories Unconstrained Optimization Tags , , , ,

    In this paper, we suggest two ways of calculating interpolation models for unconstrained smooth nonlinear optimization when Hessian-vector products are available. The main idea is to interpolate the objective function using a quadratic on a set of points around the current one and concurrently using the curvature information from products of the Hessian times appropriate … Read more

    Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • ClĂ©ment W. Royer
  • Stephen Wright
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    Worst-case complexity guarantees for nonconvex optimization algorithms have been a topic of growing interest. Multiple frameworks that achieve the best known complexity bounds among a broad class of first- and second-order strategies have been proposed. These methods have often been designed primarily with complexity guarantees in mind and, as a result, represent a departure from … Read more