top of page

New Algorithms Added!

Non-Monotone Line Search Techniques

All these codes are implementation of Line Search Techniques suitable for different kind of problems.

Nonmonotone Sequential Quadratic Programming for general constraints​.

This code implements a non-monotone trust region algorithm for nonlinear optimization subject to general constraints.
The objective function is iteratively approximated by a quadratic surface; the estimate is updated by using a quadratic programming algorithm.
To solve the quadratic programming problem is used an experimental quadratic programming algorithm developed from me, however analogous results can be optained using matlab "quadprog".
The non-monotone technique is described in (1.). The algorithm uses an internal function to  estimate the gradient of the objective function.

  1. "A non-monotone trust region algorithm for nonlinear optimization subject to general constraints", Hongchao Zhang.

Nonmonotone Technique for the Barzilai-Borwein Gradient Method.​

This function implements a Non-Monotone Globalization Technique for the Barzilai-Borwein Gradient Method.

In particular the algorithm combine nonmonotone watch dog technique with nonmonotone line search rules, the authors of the algorithm prove in [1] global convergence for this scheme.

This algorithm, while having a low computational cost, is comparable in large dimendional problems with more sofisticated reduced memory quasi-Newton methods. I tested this algorithm with problems having up to 10000 variables!

 

The algorithm is described in:

  1. "Non-Monotone Globalization Techniques for the Barzilai-Borwein Gradient Method", L. Grippo, M. Sciandrone, Univ. of Rome "La Sapienza", Rome. 

Nonmonotone Truncated Newton Method

This code implements an unconstrained optimization algorithm based on a non-monotone truncated Newton Method. 
At each iteration a truncated newton method, based on the conjugate gradient algorithm, is used to find the search direction; the step size along the search direction is  computed using a nonmonotone generalization of the Armijo's line search method. This algorithm is a detailed implementation of the work presented in 1.:

 

  1. "A Truncated Newton Method with Nonmonotone Line Search for Unconstrained Optimization", L. Grippo, F. Lampariello, AND S. Lucidi.

 

Nonmonotone projected gradient algorithm.​

This function implements a non-monotone projected projected gradient algorithm for non-linear optimization subject to box constraints. The algorithm is composed of two main steps:

  1. take a step proportional to the negative of the gradient at the current point; the step-length choice is based on Barzilai-Borwein formula.

  2. the point on the gradient direction is projected on the feasible set and a second step is done along the projected gradient direction; this step is computed using a non-monotone generalization of the Armijo's line search method.

The algorithm is described in:

  • "A Non-Monotone Optimization Algorithm for IIR Filter Design", M. Antonelli, A. Rizzi, Univ. of Rome "La Sapienza", Rome.

Nonmonotone projected gradient for quadratic programming with box constraints

This code implements a non-monotone gradient projection methods for minimizing quadratic functions on convex sets. The algorithm solves the following problem:

  • Convex quadratic programming (QP) problem with box constraints.

The considered special case of quadratic programming is of primary importance in training Support Vector Machine (SVM) a special class of Machine Learning. 

This algorithm consists in an adaptation of the one proposed in (1.) to the special case of quadratic objective function.

  1. "A Non-Monotone Optimization Algorithm for IIR Filter Design", M. Antonelli, A. Rizzi, Univ. of Rome "La Sapienza", Rome.

Nonmonotone Truncated Newton for large Scale Least Square Problems

This code implements a Gauss-Newton method for the solution of large-scale nonlinear least-squares problems. First the search direction is estimated as approximate solutionof a Gauss-Newton type equation. The specific truncated Gauss-Newton algorithm is described in [1].

The step size along the search direction is  computed by using a nonmonotone generalization of the Armijo's line search method as described in [2].

  1. "Newton Method for Large-Scale Nonlinear Least-Squares Problems", G. Fasano, F. Lampariello, M. Sciandrone.

  2. "A Truncated Newton Method with Nonmonotone Line Search for Unconstrained Optimization", L. Grippo, F. Lampariello, AND S. Lucidi.

bottom of page