gradient projection methods

Spectral properties of Barzilai-Borwein rules in solving singly linearly constrained optimization problems subject to lower and upper bounds

  • Serena Crisci
  • Federica Porta
  • Luca Zanni
  • Valeria Ruggiero
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    In 1988, Barzilai and Borwein published a pioneering paper which opened the way to inexpensively accelerate first-order methods. More in detail, in the framework of unconstrained optimization, Barzilai and Borwein developed two strategies to select the steplength in gradient descent methods with the aim of encoding some second-order information of the problem without computing and/or … Read more

    Steplength selection in gradient projection methods for box-constrained quadratic programs

  • Serena Crisci
  • Luca Zanni
  • Valeria Ruggiero
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags , , ,

    The role of the steplength selection strategies in gradient methods has been widely investigated in the last decades. Starting from the work of Barzilai and Borwein (1988), many efficient steplength rules have been designed, that contributed to make the gradient approaches an effective tool for the large-scale optimization problems arising in important real-world applications. Most … Read more

    A Non-monotonic Method for Large-scale Nonnegative Least Squares

  • Inderjit S. Dhillon
  • Dongmin Kim
  • Suvrit Sra
    • Categories Basic Sciences Applications, Bound-constrained Optimization, Nonlinear Systems and Least-Squares Tags , , , , , ,

    We present a new algorithm for nonnegative least-squares (NNLS). Our algorithm extends the unconstrained quadratic optimization algorithm of Barzilai and Borwein (BB) (J. Barzilai and J. M. Borwein; Two-Point Step Size Gradient Methods. IMA J. Numerical Analysis; 1988.) to handle nonnegativity constraints. Our extension diff ers in several basic aspects from other constrained BB variants. The … Read more

    An Implementable Proximal Point Algorithmic Framework for Nuclear Norm Minimization

  • Yong-Jin Liu
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact … Read more

    Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs

  • Michael P. Friedlander
  • Sven Leyffer
    • Categories Quadratic Programming Tags , , , , ,

    We present a two-phase algorithm for solving large-scale quadratic programs (QPs). In the first phase, gradient-projection iterations approximately minimize an augmented Lagrangian function and provide an estimate of the optimal active set. In the second phase, an equality-constrained QP defined by the current inactive variables is approximately minimized in order to generate a second-order search … Read more

    Gradient Projection Methods for Quadratic Programs and Applications in Training Support Vector Machines

  • Thomas Serafini
  • Luca Zanni
  • Gaetano Zanghirati
    • Categories Data-Mining, Quadratic Programming Tags , , , ,

    Gradient projection methods based on the Barzilai-Borwein spectral steplength choices are considered for quadratic programming problems with simple constraints. Well known nonmonotone spectral projected gradient methods and variable projection methods are discussed. For both approaches the behavior of different combinations of the two spectral steplengths is investigated. A nw adaptive stplength alternating rule is proposed, … Read more