The Sufficient Decrease Condition

The Armijo condition or sufficient decrease condition states:

\[ f(R_{x_k}(\alpha_k{}p_k)) \leq f(x_k) + c_1g_{x_k}(\alpha_k{}p_k, \mathrm{grad}^g_{x_k}f), \]

for some constant $c_1\in(0, 1)$ (see SimpleSolvers.DEFAULT_WOLFE_c₁).

The sufficient decrease condition can also be written as

\[ \frac{f(R_{x_k}(\alpha_k{}p_k)) - f(x_k)}{\alpha_k} \leq g_{x_k}(c_1p_k, \mathrm{grad}^g_{x_k}f).\]

As we assume that $f(R_{x_k}(\alpha_k{}p_k)) \leq f(x_k)$ and $g_{x_k}(c_1p_k, \mathrm{grad}^g_{x_k}f) < 0$, we can rewrite this as:

\[ |\frac{f(R_{x_k}(\alpha_k{}p_k)) - f(x_k)}{\alpha_k}| \geq |g_{x_k}(c_1p_k, \mathrm{grad}^g_{x_k}f)|,\]

making clear why this is called the sufficient decrease condition. The parameter $c_1$ is typically chosen very small, around $10^{-4}$. This is implemented as SufficientDecreaseCondition.

Example

We include an example:

x = [3., 1.3]
y = similar(x)
f(y, x, params) = y .= 10 .* x .^ 3 ./ 6 .- x .^ 2 ./ 2
_params = NullParameters()
f(y, x, _params)
s = NewtonSolver(x, y; F = f)
c₁ = 1e-4
state = NonlinearSolverState(x)
update!(state, x, y)
direction!(s, x, _params, 0)
ls_obj = linesearch_problem(s)
params = (x = state.x, parameters = _params)
sdc = SufficientDecreaseCondition(c₁, ls_obj.F(0., params), ls_obj.D(0., params), alpha -> ls_obj.F(alpha, params))

# check different values
α₁, α₂, α₃, α₄, α₅ = .09, .4, 0.7, 1., 1.3
(sdc(α₁), sdc(α₂), sdc(α₃), sdc(α₄), sdc(α₅))

(true, true, true, true, true)

We further illustrate this: