The lifted Newton method and its application in optimization
We present a new “lifting” approach for the solution of nonlinear optimization problems (NLPs) that have objective and constraint functions with intermediate variables. Introducing these as additional degrees of freedom into the original problem, combined with adding suitable new constraints to ensu...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
2010
|
| In: |
SIAM journal on optimization
Year: 2010, Jahrgang: 20, Heft: 3, Pages: 1655-1684 |
| ISSN: | 1095-7189 |
| DOI: | 10.1137/080724885 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1137/080724885 Verlag, lizenzpflichtig, Volltext: https://epubs.siam.org/doi/10.1137/080724885 
|
| Verfasserangaben: | Jan Albersmeyer and Moritz Diehl |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1822662494 | ||
| 003 | DE-627 | ||
| 005 | 20230710163918.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 221116s2010 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1137/080724885 |2 doi | |
| 035 | |a (DE-627)1822662494 | ||
| 035 | |a (DE-599)KXP1822662494 | ||
| 035 | |a (OCoLC)1389822445 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Albersmeyer, Jan |e VerfasserIn |0 (DE-588)144033429 |0 (DE-627)65682154X |0 (DE-576)340448830 |4 aut | |
| 245 | 1 | 4 | |a The lifted Newton method and its application in optimization |c Jan Albersmeyer and Moritz Diehl |
| 264 | 1 | |c 2010 | |
| 300 | |a 30 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 16.11.2022 | ||
| 520 | |a We present a new “lifting” approach for the solution of nonlinear optimization problems (NLPs) that have objective and constraint functions with intermediate variables. Introducing these as additional degrees of freedom into the original problem, combined with adding suitable new constraints to ensure equivalence of the problems, we propose to solve this augmented system instead of the original system by a Newton-type method. This often offers advantages in terms of convergence rates and region of attraction. The main contribution of this article is an efficient algorithmic trick to generate the quantities needed for a Newton-type method on the augmented (“lifted”) system with (a) almost no additional computational cost per iteration compared to a nonlifted Newton method, and (b) with negligible programming burden. We derive lifted schemes for Newton's method, as well as for constrained Gauss-Newton and adjoint based sequential quadratic programming (SQP) methods, and show equivalence of the new efficiently lifted approaches with “full-space” lifted Newton iterations. We establish conditions on the intermediate functions that imply faster local quadratic convergence for lifted versus nonlifted Newton iterations, a phenomenon often observed in practice but not yet explained theoretically. Finally, we compare numerically the behavior of the lifted approach with the nonlifted approach on several test problems, including a large scale example with 27 million intermediate variables. The algorithms and examples are available as open-source code in the C++ package LiftOpt. | ||
| 650 | 4 | |a 65K05 | |
| 650 | 4 | |a 90C06 | |
| 650 | 4 | |a 90C30 | |
| 650 | 4 | |a 90C55 | |
| 650 | 4 | |a 90C90 | |
| 650 | 4 | |a constrained optimization | |
| 650 | 4 | |a Newton-type methods | |
| 650 | 4 | |a nonlinear optimization | |
| 650 | 4 | |a shooting methods | |
| 650 | 4 | |a SQP methods | |
| 700 | 1 | |a Diehl, Moritz |d 1971- |e VerfasserIn |0 (DE-588)1045085804 |0 (DE-627)773794379 |0 (DE-576)180684965 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |a Society for Industrial and Applied Mathematics |t SIAM journal on optimization |d Philadelphia, Pa. : SIAM, 1991 |g 20(2010), 3, Seite 1655-1684 |h Online-Ressource |w (DE-627)266885497 |w (DE-600)1468414-7 |w (DE-576)078590000 |x 1095-7189 |7 nnas |
| 773 | 1 | 8 | |g volume:20 |g year:2010 |g number:3 |g pages:1655-1684 |g extent:30 |a The lifted Newton method and its application in optimization |
| 856 | 4 | 0 | |u https://doi.org/10.1137/080724885 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://epubs.siam.org/doi/10.1137/080724885 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20221116 | ||
| 993 | |a Article | ||
| 994 | |a 2010 | ||
| 998 | |g 144033429 |a Albersmeyer, Jan |m 144033429:Albersmeyer, Jan |d 110000 |e 110000PA144033429 |k 0/110000/ |p 1 |x j | ||
| 999 | |a KXP-PPN1822662494 |e 4212372878 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"note":["Gesehen am 16.11.2022"],"type":{"bibl":"article-journal","media":"Online-Ressource"},"language":["eng"],"recId":"1822662494","person":[{"given":"Jan","family":"Albersmeyer","role":"aut","display":"Albersmeyer, Jan","roleDisplay":"VerfasserIn"},{"roleDisplay":"VerfasserIn","display":"Diehl, Moritz","role":"aut","family":"Diehl","given":"Moritz"}],"title":[{"title_sort":"lifted Newton method and its application in optimization","title":"The lifted Newton method and its application in optimization"}],"physDesc":[{"extent":"30 S."}],"relHost":[{"name":{"displayForm":["Society for Industrial and Applied Mathematics"]},"id":{"eki":["266885497"],"zdb":["1468414-7"],"issn":["1095-7189"]},"origin":[{"publisherPlace":"Philadelphia, Pa.","dateIssuedKey":"1991","publisher":"SIAM","dateIssuedDisp":"1991-"}],"physDesc":[{"extent":"Online-Ressource"}],"title":[{"title":"SIAM journal on optimization","title_sort":"SIAM journal on optimization"}],"language":["eng"],"corporate":[{"roleDisplay":"VerfasserIn","display":"Society for Industrial and Applied Mathematics","role":"aut"}],"recId":"266885497","disp":"Society for Industrial and Applied MathematicsSIAM journal on optimization","note":["Gesehen am 02.07.2021"],"type":{"media":"Online-Ressource","bibl":"periodical"},"titleAlt":[{"title":"Journal on optimization"}],"part":{"extent":"30","text":"20(2010), 3, Seite 1655-1684","volume":"20","issue":"3","pages":"1655-1684","year":"2010"},"pubHistory":["1.1991 -"]}],"name":{"displayForm":["Jan Albersmeyer and Moritz Diehl"]},"origin":[{"dateIssuedDisp":"2010","dateIssuedKey":"2010"}],"id":{"doi":["10.1137/080724885"],"eki":["1822662494"]}} | ||
| SRT | |a ALBERSMEYELIFTEDNEWT2010 | ||