Unconstrained Optimization

Limited-memory Common-directions Method for Large-scale Optimization: Convergence, Parallelization, and Distributed Optimization

  • Ching-pei Lee
  • Po-Wei Wang
  • Chih-Jen Lin
    • Categories Parallel Algorithms, Unconstrained Optimization Tags , , ,

    In this paper, we present a limited-memory common-directions method for smooth optimization that interpolates between first- and second- order methods. At each iteration, a subspace of a limited dimension size is constructed using first-order information from previous iterations, and an ef- ficient Newton method is deployed to find an approximate minimizer within this subspace. With … Read more

    Globally convergent Newton-type methods for multiobjective optimization

  • Max L. N. Gonçalves
  • Leandro Fonseca Prudente
  • F. S. Lima
    • Categories Multi-Criteria Optimization, Unconstrained Optimization Tags , , ,

    We propose two Newton-type methods for solving (possibly) nonconvex unconstrained multiobjective optimization problems. The first is directly inspired by the Newton method designed to solve convex problems, whereas  the second uses  second-order information of the objective functions with ingredients of the steepest descent method.  One of the key points of our approaches  is to impose … Read more

    A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer

  • Frank E. Curtis
  • Daniel P. Robinson
  • Yutong Dai
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , , ,

    We consider the problem of minimizing an objective function that is the sum of a convex function and a group sparsity-inducing regularizer. Problems that integrate such regularizers arise in modern machine learning applications, often for the purpose of obtaining models that are easier to interpret and that have higher predictive accuracy. We present a new … Read more

    A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees

  • Michael J. O'Neill
  • Stephen Wright
    • Categories Unconstrained Optimization Tags , ,

    We describe a line-search algorithm which achieves the best-known worst-case complexity results for problems with a certain “strict saddle” property that has been observed to hold in low-rank matrix optimization problems. Our algorithm is adaptive, in the sense that it makes use of backtracking line searches and does not require prior knowledge of the parameters … Read more

    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