Armijo Line Search Parameters

Question

I am trying to compare many unconstrained optimization algorithms like gradient method, Newton method with line search, Polak-Ribiere algorithm, Broyden-Fletcher-Goldfarb-Shanno algorithm, so on so forth. For these methods, I use Armijo line search method to determine how much to go towards a descent direction at each step.

As commonly known, the Armijo condition requires some parameter selection (namely the distance to go $\alpha$, the coefficient that will multiply $\alpha$ at each step which is $\sigma$, and some $\gamma \in (0, 1/2)).$ I am not familiar with a way of choosing the best set of parameters. I could imagine they would differ from problem to problem, but what is the most common way to decide these parameters?

Answer 1

You are correct that the optimal choice of parameters for the Armijo line search can vary depending on the problem and the optimization algorithm being used. In practice, there are several common strategies for choosing these parameters:

Fixed values: One approach is to use fixed values for the parameters $\alpha$, $\sigma$, and $\gamma$. For example, $\alpha$ could be set to a small value such as 0.01, $\sigma$ could be set to 0.5 or 0.9, and $\gamma$ could be set to 0.1 or 0.5. These values are often used as a starting point and can be adjusted manually based on the performance of the algorithm on the specific problem.

Backtracking line search: Another approach is to use a backtracking line search to automatically adjust the parameters at each iteration. In this approach, the initial value of $\alpha$ is set to a large value, and then decreased until the Armijo condition is satisfied. The parameter $\sigma$ is typically set to a small value such as 0.1 or 0.01, and the parameter $\gamma$ is usually set to a small value such as 0.1 or 0.01. Backtracking line search can be computationally expensive, but it can lead to better convergence properties and can adapt to the specific problem.

Adaptive strategies: A third approach is to use adaptive strategies to adjust the parameters dynamically during the optimization process. For example, the parameters could be adjusted based on the progress of the optimization, the magnitude of the gradient, or some other criterion. Adaptive strategies can be more complex to implement, but they can lead to better convergence properties and can adapt to the specific problem.

Overall, the choice of parameter selection strategy depends on the specific problem and the optimization algorithm being used. Fixed values can be a good starting point, but may need to be adjusted manually. Backtracking line search can be more computationally expensive, but can lead to better convergence properties. Adaptive strategies can be more complex to implement, but can adapt to the specific problem and lead to better convergence properties.