optiml.opti.unconstrained.line_search.gradient_descent module

class optiml.opti.unconstrained.line_search.gradient_descent.SteepestGradientDescent(f, x=None, eps=1e-06, tol=1e-08, max_iter=1000, max_f_eval=1000, 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 the classical Steepest Descent algorithm for the minimization of the provided function f.

At each iteration the search direction is simply the negative gradient \(d = -\nabla f(x)\) and the step size is chosen by an Armijo-Wolfe (or Backtracking) line search. For quadratic functions the exact closed-form step size along the steepest descent direction is used instead.

Parameters:

  • f – the objective function.

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

  • 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.

  • 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).

  • 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. - v (real, scalar): if x == [] this is the best known lower bound on the unconstrained global optimum of f(); it can be -inf if either f() is not bounded below, or no such information is available. If x ~= [] then v = f(x); - g (real, [n x 1] real vector): this also depends on x. If x == [] this is the standard starting point from which the algorithm should start, otherwise it is the gradient of f() at x (or a subgradient if f() is not differentiable at x, which it should not be if you are applying the gradient method to it).

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()