Convergence of a Positive-Definite Scaled Symmetric Rank One Method

Abstract

Kami membincang kadar penumpuan bagi suatu kaedah terskala pangkat satu yang simetri (SSR1) dan tentu-positif. Kaedah tersebut dibangunkan oleh Malik et al. (2002). Secara umum, suatu prosidur mula-semula diterbitkan dan digunakan bersama dengan kaedah pangkat satu yang simetri (SR1). Prosidur mula-semula ini membekalkan suatu penggantian untuk $H_k$ yang tidak tentu-positif dengan suatu gandaan positif bagi matriks identiti. Walau bagaimanapun, jika kita memilih hampiran awal bagi songsangan Hessian sebagai matriks identiti. jujukan langkah yang dihasilkan oleh SSR1 tidak semestinya mempunyai sifat ``kemerdekaan linear seragam'' yang diandaikan dalam beberapa analisis penumpuan yang terkini bagi SR1. Justeru itu, kami kemukakan suatu analisis baru yang menunjukkan kaedah SSR1 dengan gelintaran garis menumpu pada $n+1$ langkah $q$-superlinear tanpa andaian lelaran merdeka linear. Analisis tersebut hanya mengandaikan bahawa hampiran Hessian adalah tentu-positif dan terbatas secara asimptot, yang merupakan syarat sebenar yang dipaparkan oleh SSR1. Ujikaji berangka menunjukkan bahawa SSR1 setanding dengan kaedah BFGS dan mudah diimplementasikan. Katakunci: Kaedah SSR1; kaedah BFGS; kadar penumpuan $q$-superlinear. We discuss the convergence rate of a positive-definite scaled symmetric rank one (SSR1) method. This method is developed by Malik et al. (2002). In general, a restart procedure is derived and used together with the symmetric rank one (SR1) method. The restart procedure provides a replacement for the non-positive definite $H_k$ with a positive multiple of the identity matrix. However if we choose the initial approximation for the inverse Hessian as an identity matrix, the sequences of steps produced by the SSR1 do not usually seem to have the ``uniform linear independence'' property that is assumed in some recent convergence analysis for SR1. Therefore, we present a new analysis that shows that the SSR1 method with a line search is $n+1$ step $q$-superlinearly convergent without the assumption of linearly independent iterates. This analysis only assumes that the Hessian approximations are positive-definite and bounded asymptotically, which are the actual conditions given by SSR1. Numerical experiments indicate that the SSR1 method is very competitive with the BFGS method and is easily implemented. Keywords: SSR1 method; BFGS method; $q$-superlinear rate of convergence.