trust-region methods

A Dense initialization for limited-memory quasi-Newton methods

  • Johannes Brust
  • Oleg Burdakov
  • Jennifer B. Erway
  • Roummel F. Marcia
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    We consider a family of dense initializations for limited-memory quasi-Newton methods. The proposed initialization exploits an eigendecomposition-based separation of the full space into two complementary subspaces, assigning a different initialization parameter to each subspace. This family of dense initializations is proposed in the context of a limited-memory Broyden- Fletcher-Goldfarb-Shanno (L-BFGS) trust-region method that makes use … Read more

    Globally Solving the Trust Region Subproblem Using Simple First-Order Methods

  • Amir Beck
  • Yakov Vaisbourd
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    We consider the trust region subproblem which is given by a minimization of a quadratic, not necessarily convex, function over the Euclidean ball. Based on the well-known second-order necessary and sufficient optimality conditions for this problem, we present two sufficient optimality conditions defined solely in terms of the primal variables. Each of these conditions corresponds … Read more

    New quasi-Newton method for solving systems of nonlinear equations

  • Ladislav Lukšan
  • Jan Vlček
    • Categories Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , , , , , ,

    In this report, we propose the new Broyden method for solving systems of nonlinear equations, which uses the first derivatives, but it is more efficient than the Newton method (measured by the computational time) for larger dense systems. The new method updates QR decompositions of nonsymmetric approximations of the Jacobian matrix, so it requires $O(n^2)$ … Read more

    A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

  • Elhoucine Bergou
  • Youssef Diouane
  • Serge Gratton
    • Categories Unconstrained Optimization Tags , , , , ,

    Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity amongst second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such scaled norm, the obtained method … Read more

    On the use of the energy norm in trust-region and adaptive cubic regularization subproblems

  • Elhoucine Bergou
  • Youssef Diouane
  • Serge Gratton
    • Categories Unconstrained Optimization Tags , , , , , , ,

    We consider solving unconstrained optimization problems by means of two popular globalization techniques: trust-region (TR) algorithms and adaptive regularized framework using cubics (ARC). Both techniques require the solution of a so-called “subproblem” in which a trial step is computed by solving an optimization problem involving an approximation of the objective function, called “the model”. The … Read more

    A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds

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

    In order to be provably convergent towards a second-order stationary point, optimization methods applied to nonconvex problems must necessarily exploit both first and second-order information. However, as revealed by recent complexity analyzes of some of these methods, the overall effort to reach second-order points is significantly larger when compared to the one of approaching first-order … Read more

    Complexity and global rates of trust-region methods based on probabilistic models

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
  • Z. Zhang
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , ,

    Trust-region algorithms have been proved to globally converge with probability one when the accuracy of the trust-region models is imposed with a certain probability conditioning on the iteration history. In this paper, we study their complexity, providing global rates and worst case complexity bounds on the number of iterations (with overwhelmingly high probability), for both … Read more

    trlib: A vector-free implementation of the GLTR method for iterative solution of the trust region problem

  • Christian Kirches
  • Andreas Potschka
  • Felix Lenders
    • Categories Optimization Software and Modeling Systems, Quadratic Programming Tags , , ,

    We describe trlib, a library that implements a Variant of Gould’s Generalized Lanczos method (Gould et al. in SIAM J. Opt. 9(2), 504–525, 1999) for solving the trust region problem. Our implementation has several distinct features that set it apart from preexisting ones. We implement both conjugate gradient (CG) and Lanczos iterations for assembly of … Read more

    A New First-order Algorithmic Framework for Optimization Problems with Orthogonality Constraints

  • Xiaojun Chen
  • Bin Gao
  • Xin Liu
  • Ya-xiang Yuan
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization Tags , , , , ,

    In this paper, we consider a class of optimization problems with orthogonality constraints, the feasible region of which is called the Stiefel manifold. Our new framework combines a function value reduction step with a correction step. Different from the existing approaches, the function value reduction step of our algorithmic framework searches along the standard Euclidean … Read more

    A Sequential Algorithm for Solving Nonlinear Optimization Problems with Chance Constraints

  • Frank E. Curtis
  • Victor M. Zavala
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , ,

    An algorithm is presented for solving nonlinear optimization problems with chance constraints, i.e., those in which a constraint involving an uncertain parameter must be satisfied with at least a minimum probability. In particular, the algorithm is designed to solve cardinality-constrained nonlinear optimization problems that arise in sample average approximations of chance-constrained problems, as well as … Read more