Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Davidon–Fletcher–Powell formula
open-in-new
<h2 id="compact-representation">Compact representation</h2> <p>By unwinding the matrix recurrence for B k {\displaystyle B_{k}} , the DFP formula can be expressed as a <a href="/facts/Compact_quasi-Newton_representation/N8ChSQmf">compact matrix representation</a>. Specifically, defining </p><p> S k = [ s 0 s 1 … s k − 1 ] , {\displaystyle S_{k}={\begin{bmatrix}s_{0}&s_{1}&\ldots &s_{k-1}\end{bmatrix}},} Y k = [ y 0 y 1 … y k − 1 ] , {\displaystyle Y_{k}={\begin{bmatrix}y_{0}&y_{1}&\ldots &y_{k-1}\end{bmatrix}},} </p><p>and upper triangular and diagonal matrices </p><p> ( R k ) i j := ( R k SY ) i j = s i − 1 T y j − 1 , ( R k YS ) i j = y i − 1 T s j − 1 , ( D k ) i i := ( D k SY ) i i = s i − 1 T y i − 1 for 1 ≤ i ≤ j ≤ k {\displaystyle {\big (}R_{k}{\big )}_{ij}:={\big (}R_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad {\big (}R_{k}^{\text{YS}}{\big )}_{ij}=y_{i-1}^{T}s_{j-1},\quad (D_{k})_{ii}:={\big (}D_{k}^{\text{SY}}{\big )}_{ii}=s_{i-1}^{T}y_{i-1}\quad \quad {\text{ for }}1\leq i\leq j\leq k} </p><p>the DFP matrix has the equivalent formula </p><p> B k = B 0 + J k N k − 1 J k T , {\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},} </p><p> J k = [ Y k Y k − B 0 S k ] {\displaystyle J_{k}={\begin{bmatrix}Y_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}}} </p><p> N k = [ 0 k × k R k YS ( R k YS ) T R k + R k T − ( D k + S k T B 0 S k ) ] {\displaystyle N_{k}={\begin{bmatrix}0_{k\times k}&R_{k}^{\text{YS}}\\{\big (}R_{k}^{\text{YS}}{\big )}^{T}&R_{k}+R_{k}^{T}-(D_{k}+S_{k}^{T}B_{0}S_{k})\end{bmatrix}}} </p><p>The inverse compact representation can be found by applying the <a href="/facts/Woodbury_matrix_identity/bcmjY73W">Sherman-Morrison-Woodbury inverse</a> to B k {\displaystyle B_{k}} . The compact representation is particularly useful for limited-memory and constrained problems.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Newton%2527s_method/VlRhI2FL">Newton's method</a></li> <li><a href="/facts/Newton%2527s_method_in_optimization/H46TN721">Newton's method in optimization</a></li> <li><a href="/facts/Quasi-Newton_method/1YX1vMRa">Quasi-Newton method</a></li> <li><a href="/facts/Broyden%25E2%2580%2593Fletcher%25E2%2580%2593Goldfarb%25E2%2580%2593Shanno_algorithm/aA6KXo6h">Broyden–Fletcher–Goldfarb–Shanno (BFGS) method</a></li> <li><a href="/facts/Limited-memory_BFGS/spe3MAb3">Limited-memory BFGS method</a></li> <li><a href="/facts/Symmetric_rank-one/ygdw0YXf">Symmetric rank-one formula</a></li> <li><a href="/facts/Nelder%25E2%2580%2593Mead_method/6aXswEax">Nelder–Mead method</a></li> <li><a href="/facts/Compact_quasi-Newton_representation/N8ChSQmf">Compact quasi-Newton representation</a></li></ul> <h2 id="further-reading">Further reading</h2> <ul><li>Davidon, W. C. (1959). <a href="https://digital.library.unt.edu/ark:/67531/metadc1021816/">"Variable Metric Method for Minimization"</a>. <i>AEC Research and Development Report ANL-5990</i>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2172%2F4252678">10.2172/4252678</a>. <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/2027%2Fmdp.39015078508226">2027/mdp.39015078508226</a>.</li> <li>Fletcher, Roger (1987). <a href="https://archive.org/details/practicalmethods0000flet"><i>Practical methods of optimization</i></a> (2nd ed.). New York: John Wiley & Sons. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-471-91547-8.</li> <li>Kowalik, J.; Osborne, M. R. (1968). <a href="https://archive.org/details/methodsforuncons0000kowa/page/45"><i>Methods for Unconstrained Optimization Problems</i></a>. New York: Elsevier. pp. <a href="https://archive.org/details/methodsforuncons0000kowa/page/45">45–48</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-00041-0.</li> <li>Nocedal, Jorge; Wright, Stephen J. (1999). <i>Numerical Optimization</i>. Springer-Verlag. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-98793-2.</li> <li>Walsh, G. R. (1975). <i>Methods of Optimization</i>. London: John Wiley & Sons. pp. 110–120. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-471-91922-5.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Avriel, Mordecai (1976). Nonlinear Programming: Analysis and Methods. Prentice-Hall. pp. 352–353. ISBN 0-13-623603-0. <a href="0-13-623603-0" target="_blank">0-13-623603-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Brust, J. J. (2024). "Useful Compact Representations for Data-Fitting". arXiv:2403.12206 [math.OC]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> </ol>