Armijo

The Armijo condition, also known as the Armijo rule or Armijo-Goldstein condition, is a line search method used in optimization algorithms, particularly in gradient-based methods, to determine a step size that ensures sufficient decrease in the objective function. It is a type of inexact line search, meaning that it does not require finding the exact minimum along the search direction, but rather aims to find a step size that satisfies certain conditions for function decrease.

The Armijo condition states that a step size α (alpha) is acceptable if the following inequality holds:

f(x + αp) ≤ f(x) + cα∇f(x)^Tp

Where:

• f(x) is the objective function to be minimized.
• x is the current point in the optimization process.
• p is the search direction (typically a descent direction, such as the negative gradient).
• α is the step size being tested.
• ∇f(x) is the gradient of the objective function at point x.
• c is a constant between 0 and 1 (0 < c < 1). A common value for c is 0.1.

The Armijo condition essentially checks if the reduction in the objective function achieved by taking a step of size α in the direction p is large enough compared to a linear prediction of the function decrease based on the gradient. The term cα∇f(x)^Tp represents this linear prediction.

The choice of the parameter c influences the stringency of the condition. A smaller value of c allows for larger step sizes, potentially leading to faster convergence but also a risk of overshooting the minimum. A larger value of c enforces a stricter decrease requirement, potentially leading to smaller step sizes and slower convergence but with a greater guarantee of sufficient decrease in the objective function.

The Armijo condition is often used in conjunction with backtracking line search. Backtracking line search starts with an initial guess for α (typically α = 1) and iteratively reduces α (e.g., by a factor of 0.5) until the Armijo condition is satisfied. This process ensures that a suitable step size is found that guarantees a sufficient decrease in the objective function at each iteration of the optimization algorithm.