Note sur la convergence de méthodes de directions conjuguées

Note sur la convergence de méthodes de directions conjuguées

1969 | E. POLAK, G. RIBIERE
E. Polak and G. Ribiere present a general convergence theorem for a class of algorithms with direction of movement, which is used to construct a convergent conjugate direction algorithm for the unconstrained minimization of real functions in R^n. This algorithm is derived from the Fletcher-Reeves method through a simple modification. They also show that the convergence of the variable step Newton method and the steepest descent method can be obtained using this theorem. The paper introduces a general algorithm for minimizing a continuous function f(x) in R^n. It starts from an arbitrary point x₀ and generates successive points x_{i+1} such that f(x_{i+1}) < f(x_i). A point is considered "desirable" if f(a(x)) ≥ f(x). The authors prove that any convergent subsequence of the algorithm's sequence has a limit at a "desirable" point. The paper then presents a theorem showing that any convergent subsequence of the sequence defined by a certain algorithm type has a limit at a stationary point. The proof involves showing that the algorithm's directions are normalized and that the function's derivative is continuous. The paper applies this theorem to quasi-Newton methods, showing that the condition number of the Hessian matrix must be bounded for the algorithm to converge. It also discusses the conjugate gradient method, showing that the algorithm of Daniel satisfies the convergence conditions. A modification of the Fletcher-Reeves method is proposed, which uses a simpler formula for the parameter γ_i, leading to a convergent algorithm. Numerical tests compare the Fletcher-Reeves method and the modified method. The modified method shows good convergence performance, even when the sequence of conjugate directions is broken. The paper concludes that using a general convergence result, such as Lemma 2.2, allows the demonstration of the convergence of many known algorithms and the modification of heuristic algorithms to obtain convergent methods.E. Polak and G. Ribiere present a general convergence theorem for a class of algorithms with direction of movement, which is used to construct a convergent conjugate direction algorithm for the unconstrained minimization of real functions in R^n. This algorithm is derived from the Fletcher-Reeves method through a simple modification. They also show that the convergence of the variable step Newton method and the steepest descent method can be obtained using this theorem. The paper introduces a general algorithm for minimizing a continuous function f(x) in R^n. It starts from an arbitrary point x₀ and generates successive points x_{i+1} such that f(x_{i+1}) < f(x_i). A point is considered "desirable" if f(a(x)) ≥ f(x). The authors prove that any convergent subsequence of the algorithm's sequence has a limit at a "desirable" point. The paper then presents a theorem showing that any convergent subsequence of the sequence defined by a certain algorithm type has a limit at a stationary point. The proof involves showing that the algorithm's directions are normalized and that the function's derivative is continuous. The paper applies this theorem to quasi-Newton methods, showing that the condition number of the Hessian matrix must be bounded for the algorithm to converge. It also discusses the conjugate gradient method, showing that the algorithm of Daniel satisfies the convergence conditions. A modification of the Fletcher-Reeves method is proposed, which uses a simpler formula for the parameter γ_i, leading to a convergent algorithm. Numerical tests compare the Fletcher-Reeves method and the modified method. The modified method shows good convergence performance, even when the sequence of conjugate directions is broken. The paper concludes that using a general convergence result, such as Lemma 2.2, allows the demonstration of the convergence of many known algorithms and the modification of heuristic algorithms to obtain convergent methods.
Reach us at info@study.space