optiml.opti.unconstrained.line_search.conjugate_gradient module

class optiml.opti.unconstrained.line_search.conjugate_gradient.ConjugateGradient(f, x=None, wf='fr', eps=1e-06, tol=1e-08, max_iter=1000, max_f_eval=1000, r_start=0, m1=0.01, m2=0.9, a_start=1, tau=0.9, sfgrd=0.01, m_inf=-inf, min_a=1e-16, callback=None, callback_args=(), random_state=None, verbose=False)[source]

Bases: LineSearchOptimizer

Apply a Nonlinear Conjugate Gradient algorithm for the minimization of the provided function f.

At each iteration the search direction is a combination of the current (negative) gradient and the previous search direction, \(d = -g + \beta \, d_{prev}\), where the scalar \(\beta\) is computed according to one of the classical Nonlinear Conjugate Gradient formulae (Fletcher-Reeves, Polak-Ribiere, Hestenes-Stiefel or Dai-Yuan); the step size is then chosen by an Armijo-Wolfe (or Backtracking) line search. For quadratic functions the exact conjugacy condition and the closed-form step size are used instead.

Parameters:

  • f – the objective function.

  • x – ([n x 1] real column vector): the point where to start the algorithm from.

  • wf – (string, optional, default value ‘fr’): which of the Nonlinear Conjugate Gradient formulae to use to compute beta. Possible values are: ‘fr’ (Fletcher-Reeves), ‘pr’ (Polak-Ribiere), ‘hs’ (Hestenes-Stiefel) and ‘dy’ (Dai-Yuan).

  • eps – (real scalar, optional, default value 1e-6): the accuracy in the stopping criterion: the algorithm is stopped when the norm of the gradient is less than or equal to eps. If a negative value is provided, this is used in a relative stopping criterion: the algorithm is stopped when the norm of the gradient is less than or equal to (- eps) * || norm of the first gradient ||.

  • max_f_eval – (integer scalar, optional, default value 1000): the maximum number of function evaluations (hence, iterations will be not more than max_f_eval because at each iteration at least a function evaluation is performed, possibly more due to the line search).

  • r_start – (integer scalar, optional, default value 0): if > 0, restarts (setting beta = 0) are performed every n * r_start iterations.

  • m1 – (real scalar, optional, default value 0.01): first parameter of the Armijo-Wolfe-type line search (sufficient decrease). Has to be in (0,1).

  • m2 – (real scalar, optional, default value 0.9): typically the second parameter of the Armijo-Wolfe-type line search (strong curvature condition). It should to be in (0,1); if not, it is taken to mean that the simpler Backtracking line search should be used instead.

  • a_start – (real scalar, optional, default value 1): starting value of alpha in the line search (> 0).

  • tau – (real scalar, optional, default value 0.9): scaling parameter for the line search. In the Armijo-Wolfe line search it is used in the first phase: if the derivative is not positive, then the step is divided by tau (which is < 1, hence it is increased). In the Backtracking line search, each time the step is multiplied by tau (hence it is decreased).

  • sfgrd – (real scalar, optional, default value 0.01): safeguard parameter for the line search. To avoid numerical problems that can occur with the quadratic interpolation if the derivative at one endpoint is too large w.r.t. The one at the other (which leads to choosing a point extremely near to the other endpoint), a safeguarded version of interpolation is used whereby the new point is chosen in the interval [as * (1 + sfgrd), am * (1 - sfgrd)], being [as, am] the current interval, whatever quadratic interpolation says. If you experience problems with the line search taking too many iterations to converge at “nasty” points, try to increase this.

  • m_inf – (real scalar, optional, default value -inf): if the algorithm determines a value for f() <= m_inf this is taken as an indication that the problem is unbounded below and computation is stopped (a “finite -inf”).

  • min_a – (real scalar, optional, default value 1e-16): if the algorithm determines a step size value <= min_a, this is taken as an indication that something has gone wrong (the gradient is not a direction of descent, so maybe the function is not differentiable) and computation is stopped. It is legal to take min_a = 0, thereby in fact skipping this test.

  • verbose – (boolean, optional, default value False): print details about each iteration if True, nothing otherwise.

Return x:

([n x 1] real column vector): the best solution found so far.

Return status:

(string): the status of the algorithm at termination, one of: optimal (x is a(n approximately) optimal solution), unbounded (f() was driven below m_inf, i.e., the problem looks unbounded below), stopped (the maximum number of iterations or evaluations was reached) or error (a numerical error occurred, e.g., the step size fell below min_a).

minimize()[source]
callback(args=())
check_lagrangian_dual_conditions()
check_lagrangian_dual_optimality()
is_augmented_lagrangian_dual()
is_lagrangian_dual()
is_verbose()