optiml.opti.unconstrained.line_search package

Submodules

• optiml.opti.unconstrained.line_search.conjugate_gradient module
  • ConjugateGradient
    • ConjugateGradient.minimize()
    • ConjugateGradient.callback()
    • ConjugateGradient.check_lagrangian_dual_conditions()
    • ConjugateGradient.check_lagrangian_dual_optimality()
    • ConjugateGradient.is_augmented_lagrangian_dual()
    • ConjugateGradient.is_lagrangian_dual()
    • ConjugateGradient.is_verbose()
• optiml.opti.unconstrained.line_search.gradient_descent module
  • SteepestGradientDescent
    • SteepestGradientDescent.minimize()
    • SteepestGradientDescent.callback()
    • SteepestGradientDescent.check_lagrangian_dual_conditions()
    • SteepestGradientDescent.check_lagrangian_dual_optimality()
    • SteepestGradientDescent.is_augmented_lagrangian_dual()
    • SteepestGradientDescent.is_lagrangian_dual()
    • SteepestGradientDescent.is_verbose()
• optiml.opti.unconstrained.line_search.line_search module
  • LineSearch
    • LineSearch.search()
  • BacktrackingLineSearch
    • BacktrackingLineSearch.search()
  • ArmijoWolfeLineSearch
    • ArmijoWolfeLineSearch.search()
• optiml.opti.unconstrained.line_search.newton module
  • Newton
    • Newton.minimize()
    • Newton.callback()
    • Newton.check_lagrangian_dual_conditions()
    • Newton.check_lagrangian_dual_optimality()
    • Newton.is_augmented_lagrangian_dual()
    • Newton.is_lagrangian_dual()
    • Newton.is_verbose()
• optiml.opti.unconstrained.line_search.quasi_newton module
  • BFGS
    • BFGS.minimize()
    • BFGS.callback()
    • BFGS.check_lagrangian_dual_conditions()
    • BFGS.check_lagrangian_dual_optimality()
    • BFGS.is_augmented_lagrangian_dual()
    • BFGS.is_lagrangian_dual()
    • BFGS.is_verbose()
  • LBFGS
    • LBFGS.minimize()
    • LBFGS.callback()
    • LBFGS.check_lagrangian_dual_conditions()
    • LBFGS.check_lagrangian_dual_optimality()
    • LBFGS.is_augmented_lagrangian_dual()
    • LBFGS.is_lagrangian_dual()
    • LBFGS.is_verbose()

Module contents

class optiml.opti.unconstrained.line_search.LineSearchOptimizer(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)

Bases: Optimizer, ABC

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.

callback(args=())

check_lagrangian_dual_conditions()

check_lagrangian_dual_optimality()

is_augmented_lagrangian_dual()

is_lagrangian_dual()

is_verbose()

minimize()

class optiml.opti.unconstrained.line_search.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)

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

callback(args=())

check_lagrangian_dual_conditions()

check_lagrangian_dual_optimality()

is_augmented_lagrangian_dual()

is_lagrangian_dual()

is_verbose()

class optiml.opti.unconstrained.line_search.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)

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

callback(args=())

check_lagrangian_dual_conditions()

check_lagrangian_dual_optimality()

is_augmented_lagrangian_dual()

is_lagrangian_dual()

is_verbose()

class optiml.opti.unconstrained.line_search.Newton(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, delta=1e-06, tau=0.9, sfgrd=0.01, m_inf=-inf, min_a=1e-12, callback=None, callback_args=(), random_state=None, verbose=False)

Bases: LineSearchOptimizer

Apply a classical Newton’s method for the minimization of the provided function f.

At each iteration the search direction is computed as the solution of the Newton system \(H d = -g\), where \(H\) is the Hessian of f. To guarantee that d is a descent direction even when \(H\) is not positive definite, the Hessian is modified by shifting its spectrum so that its smallest eigenvalue is at least \(\delta\), and the resulting direction is then accepted by an Armijo-Wolfe (or Backtracking) line search.

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

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

• delta – (real scalar, optional, default value 1e-6): minimum positive value for the eigenvalues of the modified Hessian used to compute the Newton direction.

• 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-12): 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()

callback(args=())

check_lagrangian_dual_conditions()

check_lagrangian_dual_optimality()

is_augmented_lagrangian_dual()

is_lagrangian_dual()

is_verbose()

class optiml.opti.unconstrained.line_search.BFGS(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, delta=1, tau=0.9, sfgrd=0.01, m_inf=-inf, min_a=1e-16, callback=None, callback_args=(), random_state=None, verbose=False)

Bases: LineSearchOptimizer

Apply a Quasi-Newton approach, in particular using the celebrated Broyden-Fletcher-Goldfarb-Shanno (BFGS) formula, for the minimization of the provided function f.

Unlike Newton’s method, the (inverse of the) Hessian is not computed but iteratively approximated by a dense [n x n] matrix H, updated at each iteration with the rank-two BFGS formula from the latest step \(s^{i} = x^{i+1} - x^{i}\) and the latest gradient variation \(y^{i} = \nabla f(x^{i+1}) - \nabla f(x^{i})\), so that the search direction \(d = -H \nabla f(x)\) requires no linear system solve; the step size is then chosen by an Armijo-Wolfe (or Backtracking) line search.

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

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

• delta – (real scalar, optional, default value 1): the initial approximation of the inverse of the Hessian is taken as delta * I if delta > 0; otherwise, the initial Hessian is approximated by finite differences with - delta as the step, and inverted just the once.

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

callback(args=())

check_lagrangian_dual_conditions()

check_lagrangian_dual_optimality()

is_augmented_lagrangian_dual()

is_lagrangian_dual()

is_verbose()

class optiml.opti.unconstrained.line_search.LBFGS(f, x=None, m=20, eps=1e-06, tol=1e-08, max_iter=1000, max_f_eval=1000, m1=0.01, m2=0.9, a_start=1, delta=1, tau=0.9, sfgrd=0.01, m_inf=-inf, min_a=1e-16, callback=None, callback_args=(), random_state=None, verbose=False)

Bases: BFGS

Apply a Limited-memory Quasi-Newton approach, in particular the Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) formula, for the minimization of the provided function f.

Unlike the full BFGS, which explicitly stores and updates the [n x n] dense approximation of the inverse of the Hessian (hence requiring \(O(n^2)\) memory and \(O(n^2)\) operations per iteration), L-BFGS never forms that matrix: it only keeps the m most recent curvature pairs

\[s^{i} = x^{i+1} - x^{i} \qquad y^{i} = \nabla f(x^{i+1}) - \nabla f(x^{i})\]

dropping the oldest pair as soon as a new one is computed, and recovers the search direction \(d = -H \nabla f(x)\) implicitly through the celebrated two-loop recursion (Nocedal, 1980) [1], which costs just \(O(m n)\) memory and operations per iteration. This makes the method suited for large scale problems where storing a dense [n x n] matrix would be prohibitive, at the price of using a low-rank approximation of the inverse of the Hessian built only from the last m steps.

At each iteration the recursion is restarted from a fresh initial approximation of the inverse of the Hessian \(H^{0} = \gamma I\); rather than using the fixed delta of the full BFGS, \(\gamma\) is dynamically set to the scaling factor (Liu & Nocedal, 1989) [2] \(\gamma = (s^{i-1} y^{i-1}) / (y^{i-1} y^{i-1})\), which calibrates the trial step to the size of the latest curvature, greatly improving the quality of the search direction. As long as no curvature pair has been collected yet, i.e., at the very first iteration, the (scaled) steepest descent direction \(d = -\delta \nabla f(x)\) is used.

References

[1]

Nocedal, J. (1980). Updating Quasi-Newton Matrices with Limited Storage. Mathematics of Computation, 35(151), 773-782.

[2]

Liu, D. C., & Nocedal, J. (1989). On the Limited Memory BFGS Method for Large Scale Optimization. Mathematical Programming, 45, 503-528.

Parameters:

• f – the objective function.

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

• m – (integer scalar, optional, default value 20): the number of most recent curvature pairs \(\{s^{i}, y^{i}\}\) kept in memory to implicitly represent the approximation of the inverse of the Hessian. Larger values yield a more accurate approximation (closer to the full BFGS) at the price of more memory and computation per iteration. Has to be >= 1.

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

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

• delta – (real scalar, optional, default value 1): scaling of the steepest descent direction \(d = -\delta \nabla f(x)\) used at the very first iteration, before any curvature pair is available. Has to be > 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()

callback(args=())

check_lagrangian_dual_conditions()

check_lagrangian_dual_optimality()

is_augmented_lagrangian_dual()

is_lagrangian_dual()

is_verbose()