Unconstrained Optimization

A second-order globally convergent direct-search method and its worst-case complexity

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Direct-search algorithms form one of the main classes of algorithms for smooth unconstrained derivative-free optimization, due to their simplicity and their well-established convergence results. They proceed by iteratively looking for improvement along some vectors or directions. In the presence of smoothness, first-order global convergence comes from the ability of the vectors to approximate the steepest … Read more

    Global convergence rate analysis of unconstrained optimization methods based on probabilistic models

  • Coralia Cartis
  • Katya Scheinberg
    • Categories Unconstrained Optimization Tags , , ,

    We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain probability. We show that in terms of the order of the accuracy, the evaluation complexity of such a method is the same as its counterparts that use deterministic accurate models; … Read more

    Stochastic Optimization using a Trust-Region Method and Random Models

  • Ruobing Chen
  • Matt Menickelly
  • Katya Scheinberg
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , ,

    In this paper, we propose and analyze a trust-region model-based algorithm for solving unconstrained stochastic optimization problems. Our framework utilizes random models of an objective function $f(x)$, obtained from stochastic observations of the function or its gradient. Our method also utilizes estimates of function values to gauge progress that is being made. The convergence analysis … Read more

    A Nonmonotone Approach without Differentiability Test for Gradient Sampling Methods

  • Elias Salomão Helou
  • Sandra Augusta Santos
  • Lucas E. A. Simões
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    Recently, optimization problems involving nonsmooth and locally Lipschitz functions have been subject of investigation, and an innovative method known as Gradient Sampling has gained attention. Although the method has shown good results for important real problems, some drawbacks still remain unexplored. This study suggests modifications to the gradient sampling class of methods in order to … Read more

    On the equivalence of the method of conjugate gradients and quasi-Newton methods on quadratic problems

  • Anders Forsgren
  • Tove Odland
    • Categories Quadratic Programming, Unconstrained Optimization Tags , ,

    In this paper we state necessary and sufficient conditions for equivalence of the method of conjugate gradients and quasi-Newton methods on a quadratic problem. We show that the set of quasi-Newton schemes that generate parallel search directions to those of the method of conjugate gradients is strictly larger than the one-parameter Broyden family. In addition, … Read more

    Trust-region methods without using derivatives: Worst case complexity and the non-smooth case

  • R. Garmanjani
  • Luis Nunes Vicente
  • Diogo Júdice
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , ,

    Trust-region methods are a broad class of methods for continuous optimization that found application in a variety of problems and contexts. In particular, they have been studied and applied for problems without using derivatives. The analysis of trust-region derivative-free methods has focused on global convergence, and they have been proved to generate a sequence of … Read more

    Object-Parallel Infrastructure for Implementing First-Order Methods, with an Example Application to LASSO

  • Jonathan Eckstein
  • Gyorgy Matyasfalvi
    • Categories Bound-constrained Optimization, Parallel Algorithms, Unconstrained Optimization Tags , ,

    We describe the design of a C++ vector-manipulation substrate that allows first-order optimization algorithms to be expressed in a concise and readable manner, yet still achieve high performance in parallel computing environments. We use standard object-oriented techniques of encapsulation and operator overloading, combined with a novel “symbolic temporaries” delayed-evaluation system that greatly reduces the overhead … Read more

    A Preconditioner for a Primal-Dual Newton Conjugate Gradients Method for Compressed Sensing Problems

  • Ioannis Dassios
  • Kimon Fountoulakis
  • Jacek Gondzio
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , ,

    In this paper we are concerned with the solution of Compressed Sensing (CS) problems where the signals to be recovered are sparse in coherent and redundant dictionaries. We extend a primal-dual Newton Conjugate Gradients (pdNCG) method for CS problems. We provide an inexpensive and provably effective preconditioning technique for linear systems using pdNCG. Numerical results … Read more

    Global convergence of the Heavy-ball method for convex optimization

  • Hamid Reza Feyzmahdavian
  • Euhanna Ghadimi
  • Mikael Johansson
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , ,

    This paper establishes global convergence and provides global bounds of the convergence rate of the Heavy-ball method for convex optimization problems. When the objective function has Lipschitz-continuous gradient, we show that the Cesa ́ro average of the iterates converges to the optimum at a rate of $O(1/k)$ where k is the number of iterations. When … Read more