A general convergence theorem for the gradient method is proved under certain conditions. The paper shows that both the usual steepest descent and modified steepest descent algorithms converge under these conditions. The modified steepest descent algorithm allows for variable stepsize.
The paper defines four conditions (I-IV) for the function f. Condition IV implies Conditions I and II, and if S(x₀) is bounded, Condition IV is equivalent to Conditions I and II. The convergence theorem states that if 0 < δ ≤ 1/4K, then for any x in S(x₀), the set S*(x, δ) is nonempty and any sequence {x_k} such that x_{k+1} ∈ S*(x_k, δ) converges to the point x* which minimizes f.
Corollary 1 shows that the steepest descent algorithm converges to x*. Corollary 2 shows that the modified steepest descent algorithm also converges to x*. The modified algorithm allows for variable stepsize and does not require knowledge of the Lipschitz constant K.
The paper compares its results with previous work by Curry and Goldstein. While the convergence theorem uses more restrictive conditions than Curry's but less restrictive than Goldstein's, the algorithms considered here are easier to apply than Curry's algorithm, which requires minimizing a function of one variable at each step. Goldstein's method requires f to be twice continuously differentiable on S(x₀) and that S(x₀) be bounded, as well as knowledge of the norm of the Hessian matrix of f on S(x₀).
The author thanks the referee for his comments and suggestions.A general convergence theorem for the gradient method is proved under certain conditions. The paper shows that both the usual steepest descent and modified steepest descent algorithms converge under these conditions. The modified steepest descent algorithm allows for variable stepsize.
The paper defines four conditions (I-IV) for the function f. Condition IV implies Conditions I and II, and if S(x₀) is bounded, Condition IV is equivalent to Conditions I and II. The convergence theorem states that if 0 < δ ≤ 1/4K, then for any x in S(x₀), the set S*(x, δ) is nonempty and any sequence {x_k} such that x_{k+1} ∈ S*(x_k, δ) converges to the point x* which minimizes f.
Corollary 1 shows that the steepest descent algorithm converges to x*. Corollary 2 shows that the modified steepest descent algorithm also converges to x*. The modified algorithm allows for variable stepsize and does not require knowledge of the Lipschitz constant K.
The paper compares its results with previous work by Curry and Goldstein. While the convergence theorem uses more restrictive conditions than Curry's but less restrictive than Goldstein's, the algorithms considered here are easier to apply than Curry's algorithm, which requires minimizing a function of one variable at each step. Goldstein's method requires f to be twice continuously differentiable on S(x₀) and that S(x₀) be bounded, as well as knowledge of the norm of the Hessian matrix of f on S(x₀).
The author thanks the referee for his comments and suggestions.