# Source code for pymor.algorithms.line_search

# This file is part of the pyMOR project (http://www.pymor.org).

from pymor.core.defaults import defaults
from pymor.core.logger import getLogger

[docs]@defaults('alpha_init', 'tau', 'beta', 'maxiter')
def armijo(f, starting_point, direction, grad=None, initial_value=None,
alpha_init=1.0, tau=0.5, beta=0.0001, maxiter=10):
"""Armijo line search algorithm.

This method computes a step size such that the Armijo condition (see [NW06]_, p. 33)
is fulfilled.

Parameters
----------
f
Real-valued function that can be evaluated for its value.
starting_point
A |VectorArray| of length 1 containing the starting point of the line search.
direction
Descent direction along which the line search is performed.
Gradient of f in the point starting_point.
initial_value
Value of f in the point starting_point.
alpha_init
Initial step size that is gradually reduced.
tau
The fraction by which the step size is reduced in each iteration.
beta
Control parameter to adjust the required decrease of the function value of f.
maxiter
Use alpha_init as default if the iteration count reaches this value without
finding a point fulfilling the Armijo condition.

Returns
-------
alpha
Step size computed according to the Armijo condition.
"""
assert alpha_init > 0
assert 0 < tau < 1
assert maxiter > 0

# Start line search with step size of alpha_init
alpha = alpha_init

# Compute initial function value
if initial_value is None:
initial_value = f(starting_point)

iteration = 0
slope = 0.0

# Compute slope if gradient is provided

while True:
# Compute new function value
current_value = f(starting_point + alpha * direction)
# Check the Armijo condition
if current_value < initial_value + alpha * beta * slope:
break
# Check if maxiter is reached
if iteration >= maxiter:
# Use default value as step size
alpha = alpha_init
# Log warning
logger = getLogger('pymor.algorithms.line_search.armijo')
logger.warning(f'Reached maximum number of line search steps; using initial step size of {alpha_init} instead')
break
iteration += 1