worst-case complexity

Quadratic Regularization Methods with Finite-Difference Gradient Approximations

  • Geovani Nunes Grapiglia
    • Categories Nonlinear Optimization Tags , , ,

    This paper presents two quadratic regularization methods with finite-difference gradient approximations for smooth unconstrained optimization problems. One method is based on forward finite-difference gradients, while the other is based on central finite-difference gradients. In both methods, the accuracy of the gradient approximations and the regularization parameter in the quadratic models are jointly adjusted using a … Read more

    Derivative-free separable quadratic modeling and cubic regularization for unconstrained optimization

  • Ana Luisa Custódio
  • R. Garmanjani
  • Marcos Raydan
    • Categories Unconstrained Optimization Tags , , , ,

    We present a derivative-free separable quadratic modeling and cubic regularization technique for solving smooth unconstrained minimization problems. The derivative-free approach is mainly concerned with building a quadratic model that could be generated by numerical interpolation or using a minimum Frobenious norm approach, when the number of points available does not allow to build a complete … 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

    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

    A Generalized Worst-Case Complexity Analysis for Non-Monotone Line Searches

  • Geovani Nunes Grapiglia
  • Ekkehard Sachs
    • Categories Nonlinear Optimization Tags , , ,

    We study the worst-case complexity of a non-monotone line search framework that covers a wide variety of known techniques published in the literature. In this framework, the non-monotonicity is controlled by a sequence of nonnegative parameters. We obtain complexity bounds to achieve approximate first-order optimality even when this sequence is not summable. ArticleDownload View PDF

    Tensor Methods for Finding Approximate Stationary Points of Convex Functions

  • Geovani Nunes Grapiglia
  • Yurii Nesterov
    • Categories Convex Optimization Tags , , , ,

    In this paper we consider the problem of finding \epsilon-approximate stationary points of convex functions that are p-times differentiable with \nu-Hölder continuous pth derivatives. We present tensor methods with and without acceleration. Specifically, we show that the non-accelerated schemes take at most O(\epsilon^{-1/(p+\nu-1)}) iterations to reduce the norm of the gradient of the objective below … Read more

    On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization

  • Geovani Nunes Grapiglia
  • Ya-xiang Yuan
    • Categories Nonlinear Optimization Tags , , ,

    In this paper we study the worst-case complexity of an inexact Augmented Lagrangian method for nonconvex constrained problems. Assuming that the penalty parameters are bounded, we prove a complexity bound of $\mathcal{O}(|\log(\epsilon)|)$ outer iterations for the referred algorithm to generate an $\epsilon$-approximate KKT point, for $\epsilon\in (0,1)$. When the penalty parameters are unbounded, we prove … Read more

    A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees

  • Michael J. O'Neill
  • Stephen Wright
    • Categories Bound-constrained Optimization Tags , , ,

    We describe an algorithm based on a logarithmic barrier function, Newton’s method, and linear conjugate gradients, that obtains an approximate minimizer of a smooth function over the nonnegative orthant. We develop a bound on the complexity of the approach, stated in terms of the required accuracy and the cost of a single gradient evaluation of … Read more

    A Subsampling Line-Search Method with Second-Order Results

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
  • Clément W. Royer
  • V. Kunc
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    In many contemporary optimization problems such as those arising in machine learning, it can be computationally challenging or even infeasible to evaluate an entire function or its derivatives. This motivates the use of stochastic algorithms that sample problem data, which can jeopardize the guarantees obtained through classical globalization techniques in optimization such as a trust … Read more

    Complexity of gradient descent for multiobjective optimization

  • Jörg Fliege
  • A. Ismael F. Vaz
  • Luis Nunes Vicente
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    A number of first-order methods have been proposed for smooth multiobjective optimization for which some form of convergence to first order criticality has been proved. Such convergence is global in the sense of being independent of the starting point. In this paper we analyze the rate of convergence of gradient descent for smooth unconstrained multiobjective … Read more