Quasi-Newton and linear solve

[cvanaret]

Hi all,

I'm not sure where (or even whether) the implementation of quasi-Newton methods is documented somewhere. Here's my question:
The L-BFGS Hessian approximation is formed as $B_k = B_0 - U_k U_k^T + V_k V_k^T$, where $U_k$ and $V_k$ are tall-and-skinny matrices. Obviously, you don't want to form the explicit (dense) matrix, but rather you'd like to keep it as is - a low-rank update.

Now, how is the primal-dual perturbed KKT system solved? The KKT matrix looks something like:

$$ \begin{pmatrix} B_0 - U_k U_k^T + V_k V_k^T + \Sigma_k & \nabla c(x_k) \\ \nabla c(x_k)^T & -\delta_c I \end{pmatrix} $$

I see several options:

• form the normal equations by writing the Schur complement of the $(1, 1)$ block as a function of $U_k$ and $V_k$ (see here).
• use a null space approach and form the reduced Hessian explicitly.
• throw the linear system at an iterative solver for symmetric indefinite linear systems (e.g., MINRES).
• ...

Thanks,

Charlie
@leyffer

[frapac]

Dear Charlie,

Ipopt is using the Woodbury formula to solve the linear system when using the LBFGS algorithm. This is similar to what's implemented in Knitro. You can find the reference formula page 13 in this article:
https://link.springer.com/article/10.1007/s10107-004-0560-5

[leyffer]

Of course! You extend the BFGS vectors to include the multipliers (0's), and treat it as a low-tank update to the primal-dual linear system with a diagonal Hessian. I should have thought of that! Thanks for the quick response! Sven Sven Leyffer Senior Computational Mathematician and Deputy Director Mathematics and Computer Science Division Argonne National Laboratory

…

________________________________ From: François Pacaud ***@***.***> Sent: Friday, May 16, 2025 6:36 AM To: coin-or/Ipopt ***@***.***> Cc: Leyffer, Sven ***@***.***>; Mention ***@***.***> Subject: Re: [coin-or/Ipopt] Quasi-Newton and linear solve (Discussion #829) Dear Charlie, Ipopt is using the Woodbury formula to solve the linear system when using the LBFGS algorithm. This is similar to what's implemented in Knitro. You can find the reference formula page 13 in this article: https: //link. springer. com/article/10. 1007/s10107-004-0560-5 ZjQcmQRYFpfptBannerStart This Message Is From an External Sender This message came from outside your organization. ZjQcmQRYFpfptBannerEnd Dear Charlie, Ipopt is using the Woodbury formula to solve the linear system when using the LBFGS algorithm. This is similar to what's implemented in Knitro. You can find the reference formula page 13 in this article: https://link.springer.com/article/10.1007/s10107-004-0560-5<https://urldefense.us/v3/__https://link.springer.com/article/10.1007/s10107-004-0560-5__;!!G_uCfscf7eWS!ZBQ2wKub0VbFRF9MgFRDfvJpgX4Blfe5iGjXtqo6JdXuWDv6OOfoxKXPC1dIfz1h2QRtL1BbcOG43yldaPyd57ks0YQ$> — Reply to this email directly, view it on GitHub<https://urldefense.us/v3/__https://github.com/coin-or/Ipopt/discussions/829*discussioncomment-13169799__;Iw!!G_uCfscf7eWS!ZBQ2wKub0VbFRF9MgFRDfvJpgX4Blfe5iGjXtqo6JdXuWDv6OOfoxKXPC1dIfz1h2QRtL1BbcOG43yldaPydQFAur_I$>, or unsubscribe<https://urldefense.us/v3/__https://github.com/notifications/unsubscribe-auth/AB52TLNECR74YN2EHSJHWUT26XEVPAVCNFSM6AAAAAB5IE26EGVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTGMJWHE3TSOI__;!!G_uCfscf7eWS!ZBQ2wKub0VbFRF9MgFRDfvJpgX4Blfe5iGjXtqo6JdXuWDv6OOfoxKXPC1dIfz1h2QRtL1BbcOG43yldaPyddpkA4sM$>. You are receiving this because you were mentioned.Message ID: ***@***.***>

[cvanaret]

Thanks a lot François! I'll try to work out the math.
Talk to you soon,
Charlie