{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,16]],"date-time":"2025-11-16T21:49:47Z","timestamp":1763329787276,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T00:00:00Z","timestamp":1580860800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T00:00:00Z","timestamp":1580860800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006463","name":"Bayerisches Staatsministerium f\u00fcr Wirtschaft und Medien, Energie und Technologie","doi-asserted-by":"publisher","award":["EnCN"],"award-info":[{"award-number":["EnCN"]}],"id":[{"id":"10.13039\/501100006463","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Manag Sci"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Robust model predictive control approaches and other applications lead to nonlinear optimization problems defined on (scenario) trees. We present structure-preserving Quasi-Newton update formulas as well as structured inertia correction techniques that allow to solve these problems by interior-point methods with specialized KKT solvers for tree-structured optimization problems. The same type of KKT solvers could be used in active-set based SQP methods. The viability of our approach is demonstrated by two robust control problems.<\/jats:p>","DOI":"10.1007\/s10287-020-00362-9","type":"journal-article","created":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T08:02:56Z","timestamp":1580889776000},"page":"409-436","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimization techniques for tree-structured nonlinear problems"],"prefix":"10.1007","volume":"17","author":[{"given":"Jens","family":"H\u00fcbner","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6208-5677","authenticated-orcid":false,"given":"Martin","family":"Schmidt","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6343-9809","authenticated-orcid":false,"given":"Marc C.","family":"Steinbach","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,5]]},"reference":[{"key":"362_CR1","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF01418331","volume":"41","author":"G Bader","year":"1983","unstructured":"Bader G, Deuflhard P (1983) A semi-implicit midpoint rule for stiff systems of ordinary differential equations. Numer Math 41:373\u2013398. https:\/\/doi.org\/10.1007\/BF01418331","journal-title":"Numer Math"},{"key":"362_CR2","unstructured":"Berger AJ, Mulvey JM, Rothberg E, Vanderbei RJ (1995) Solving multistage stochastic programs using tree dissection. Technical Report SOR-95-07. Princeton University, USA"},{"key":"362_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0237-4","volume-title":"Introduction to stochastic programming","author":"JR Birge","year":"2011","unstructured":"Birge JR, Louveaux F (2011) Introduction to stochastic programming. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-1-4614-0237-4"},{"issue":"2","key":"362_CR4","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1016\/S0377-2217(02)00301-6","volume":"143","author":"J Blomvall","year":"2002","unstructured":"Blomvall J, Lindberg PO (2002) A Riccati-based primal interior point solver for multistage stochastic programming. Eur J Oper Rese 143(2):452\u2013461. https:\/\/doi.org\/10.1016\/S0377-2217(02)00301-6","journal-title":"Eur J Oper Rese"},{"issue":"4","key":"362_CR5","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/S0167-8191(03)00015-2","volume":"29","author":"J Blomvall","year":"2003","unstructured":"Blomvall J (2003) A multistage stochastic programming algorithm suitable for parallel computing. Parallel Comput 29(4):431\u2013445. https:\/\/doi.org\/10.1016\/S0167-8191(03)00015-2","journal-title":"Parallel Comput"},{"key":"362_CR6","doi-asserted-by":"publisher","unstructured":"Bock HG, Plitt KJ (1985) A multiple shooting algorithm for direct solution of optimal control problems. In: Gertler J (ed) Proceedings of the 9th IFAC world congress, Budapest, Hungary, 1984, vol IX. Pergamon Press, Oxford, UK, pp 242\u2013247. https:\/\/doi.org\/10.1016\/S1474-6670(17)61205-9","DOI":"10.1016\/S1474-6670(17)61205-9"},{"issue":"1","key":"362_CR7","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/PL00011391","volume":"89","author":"RH Byrd","year":"2000","unstructured":"Byrd RH, Gilbert J-C, Nocedal J (2000) A trust region method based on interior point techniques for nonlinear programming. Math Program 89(1):149\u2013185. https:\/\/doi.org\/10.1007\/PL00011391","journal-title":"Math Program"},{"key":"362_CR8","doi-asserted-by":"publisher","unstructured":"Byrd RH, Nocedal J, Waltz RA (2006) KNITRO: an integrated package for nonlinear optimization. In: Large scale nonlinear optimization, 35\u201359, 2006. Springer, pp 35\u201359. https:\/\/doi.org\/10.1007\/0-387-30065-1_4","DOI":"10.1007\/0-387-30065-1_4"},{"issue":"2","key":"362_CR9","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1287\/ijoc.5.2.182","volume":"5","author":"TJ Carpenter","year":"1993","unstructured":"Carpenter TJ, Lustig IJ, Mulvey JM, Shanno DF (1993) Separable quadratic programming via a primal-dual interior point method and its use in a sequential procedure. ORSA J Comput 5(2):182\u2013191. https:\/\/doi.org\/10.1287\/ijoc.5.2.182","journal-title":"ORSA J Comput"},{"issue":"4","key":"362_CR10","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1287\/ijoc.7.4.474","volume":"7","author":"J Czyzyk","year":"1995","unstructured":"Czyzyk J, Fourer R, Mehrotra S (1995) A study of the augmented system and column-splitting approaches for solving two-stage stochastic linear programs by interior-point methods. ORSA J Comput 7(4):474\u2013490. https:\/\/doi.org\/10.1287\/ijoc.7.4.474","journal-title":"ORSA J Comput"},{"issue":"1","key":"362_CR11","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1137\/1019005","volume":"19","author":"JE Dennis","year":"1977","unstructured":"Dennis JE, Mor\u00e9 JJ (1977) Quasi-Newton methods, motivation and theory. SIAM Rev 19(1):46\u201389. https:\/\/doi.org\/10.1137\/1019005","journal-title":"SIAM Rev"},{"key":"362_CR12","doi-asserted-by":"publisher","unstructured":"Dennis JE, Schnabel RB (1996) Numerical methods for unconstrained optimization and nonlinear equations, vol 16. SIAM. https:\/\/doi.org\/10.1137\/1.9781611971200","DOI":"10.1137\/1.9781611971200"},{"issue":"1","key":"362_CR13","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1137\/0805010","volume":"5","author":"R Fletcher","year":"1995","unstructured":"Fletcher R (1995) An optimal positive definite update for sparse Hessian matrices. SIAM J Optim 5(1):192\u2013218. https:\/\/doi.org\/10.1137\/0805010","journal-title":"SIAM J Optim"},{"key":"362_CR14","doi-asserted-by":"publisher","DOI":"10.1002\/9781118723203","volume-title":"Practical methods of optimization","author":"R Fletcher","year":"2013","unstructured":"Fletcher R (2013) Practical methods of optimization. Wiley, New York. https:\/\/doi.org\/10.1002\/9781118723203"},{"issue":"3","key":"362_CR15","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1137\/0905041","volume":"5","author":"PE Gill","year":"1984","unstructured":"Gill PE, Murray W, Saunders MA, Wright MH (1984) Sparse matrix methods in optimization. SIAM J Sci Stat Comput 5(3):562\u2013589. https:\/\/doi.org\/10.1137\/0905041","journal-title":"SIAM J Sci Stat Comput"},{"issue":"4","key":"362_CR16","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1137\/S1052623499350013","volume":"12","author":"PE Gill","year":"2002","unstructured":"Gill PE, Murray W, Saunders MS (2002) SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM J Optim 12(4):979\u20131006. https:\/\/doi.org\/10.1137\/S1052623499350013","journal-title":"SIAM J Optim"},{"key":"362_CR17","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/11752578_62","volume-title":"Parallel processing and applied mathematics","author":"J Gondzio","year":"2006","unstructured":"Gondzio J, Grothey A (2006) Direct solution of linear systems of size 109 arising in optimization with interior point methods. In: Wyrzykowski R, Dongarra J, Meyer N, Wasniewski J (eds) Parallel processing and applied mathematics, vol 3911. Lecture notes in computer science. Springer, Berlin, pp 513\u2013525. https:\/\/doi.org\/10.1007\/11752578_62"},{"issue":"1","key":"362_CR18","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10479-006-0139-z","volume":"152","author":"J Gondzio","year":"2007","unstructured":"Gondzio J, Grothey A (2007) Parallel interior-point solver for structured quadratic programs: application to financial planning problems. Ann Oper Res 152(1):319\u2013339. https:\/\/doi.org\/10.1007\/s10479-006-0139-z","journal-title":"Ann Oper Res"},{"issue":"2","key":"362_CR19","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10287-008-0090-3","volume":"6","author":"J Gondzio","year":"2009","unstructured":"Gondzio J, Grothey A (2009) Exploiting structure in parallel implementation of interior point methods for optimization. Comput Manag Sci 6(2):135\u2013160. https:\/\/doi.org\/10.1007\/s10287-008-0090-3","journal-title":"Comput Manag Sci"},{"issue":"1","key":"362_CR20","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/BF01399316","volume":"39","author":"A Griewank","year":"1982","unstructured":"Griewank A, Toint PL (1982a) Partitioned variable metric updates for large structured optimization problems. Numer Math 39(1):119\u2013137. https:\/\/doi.org\/10.1007\/BF01399316","journal-title":"Numer Math"},{"key":"362_CR21","first-page":"301","volume-title":"Nonlinear optimization 1981","author":"A Griewank","year":"1982","unstructured":"Griewank A, Toint P (1982b) On the unconstrained optimization of partially separable functions. In: Powell M (ed) Nonlinear optimization 1981. Academic press, Cambridge, pp 301\u2013312"},{"key":"362_CR22","unstructured":"H\u00fcbner J (2016) Distributed algorithms for nonlinear tree-sparse problems. Ph.D. Thesis. Gottfried Wilhelm Leibniz Universit\u00e4t Hannover"},{"issue":"4","key":"362_CR23","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1287\/ijoc.2017.0748","volume":"29","author":"J H\u00fcbner","year":"2017","unstructured":"H\u00fcbner J, Steinbach MC, Schmidt M (2017) A distributed interior-point KKT solver for multistage stochastic optimization. INFORMS J Comput 29(4):612\u2013630. https:\/\/doi.org\/10.1287\/ijoc.2017.0748","journal-title":"INFORMS J Comput"},{"issue":"4","key":"362_CR24","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0804048","volume":"4","author":"ER Jessup","year":"1994","unstructured":"Jessup ER, Yang D, Zenios SA (1994) Parallel factorization of structured matrices arising in stochastic programming. SIAM J Optim 4(4):833\u2013846. https:\/\/doi.org\/10.1137\/0804048","journal-title":"SIAM J Optim"},{"key":"362_CR25","series-title":"Wiley-interscience series in systems and optimization","volume-title":"Stochastic programming","author":"P Kall","year":"1994","unstructured":"Kall P, Wallace SW (1994) Stochastic programming. Wiley-interscience series in systems and optimization. Wiley, New York"},{"issue":"1","key":"362_CR26","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.sysconle.2007.06.013","volume":"57","author":"M Lazar","year":"2008","unstructured":"Lazar M, De La Pe\u00f1a DM, Heemels W, Alamo T (2008) On input-tostate stability of min-max nonlinear model predictive control. Syst Control Lett 57(1):39\u201348. https:\/\/doi.org\/10.1016\/j.sysconle.2007.06.013","journal-title":"Syst Control Lett"},{"issue":"3","key":"362_CR27","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/BF01589116","volume":"45","author":"DC Liu","year":"1989","unstructured":"Liu DC, Nocedal J (1989) On the limited memory BFGS method for large scale optimization. Math Program 45(3):503\u2013528. https:\/\/doi.org\/10.1007\/BF01589116","journal-title":"Math Program"},{"issue":"4\u20135","key":"362_CR28","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1080\/10556788.2011.602976","volume":"27","author":"M Lubin","year":"2012","unstructured":"Lubin M, Petra CG, Anitescu M (2012) The parallel solution of dense saddle-point linear systems arising in stochastic programming. Optim Methods Softw 27(4\u20135):845\u2013864. https:\/\/doi.org\/10.1080\/10556788.2011.602976","journal-title":"Optim Methods Softw"},{"key":"362_CR29","doi-asserted-by":"crossref","unstructured":"Lucia A (1983) An explicit Quasi-Newton update for sparse optimization calculations. Math Comput 40(161):317\u2013322. http:\/\/www.jstor.org\/stable\/2007377","DOI":"10.1090\/S0025-5718-1983-0679448-4"},{"issue":"17","key":"362_CR30","doi-asserted-by":"publisher","first-page":"181","DOI":"10.3182\/20120823-5-NL-3013.00015","volume":"45","author":"S Lucia","year":"2012","unstructured":"Lucia S, Engell S (2012) Multi-stage and two-stage robust nonlinear model predictive control. Nonlinear Model Predict Control 45(17):181\u2013186. https:\/\/doi.org\/10.3182\/20120823-5-NL-3013.00015","journal-title":"Nonlinear Model Predict Control"},{"key":"362_CR31","doi-asserted-by":"publisher","unstructured":"Lucia S, Finkler T, Basak D, Engell S (2012) A new robust NMPC scheme and its application to a semi-batch reactor example. In: Proceedings of the international symposium on advanced control of chemical processes, pp 69\u201374. https:\/\/doi.org\/10.3182\/20120710-4-SG-2026.00035","DOI":"10.3182\/20120710-4-SG-2026.00035"},{"key":"362_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-40065-5","volume-title":"Numerical optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal J, Wright SJ (2006) Numerical optimization, 2nd edn. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-0-387-40065-5","edition":"2"},{"issue":"4","key":"362_CR33","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1093\/imanum\/1.4.403","volume":"1","author":"M Powell","year":"1981","unstructured":"Powell M, Toint PL (1981) The Shanno\u2013Toint procedure for updating sparse symmetric matrices. IMA J Numer Anal 1(4):403\u2013413. https:\/\/doi.org\/10.1093\/imanum\/1.4.403","journal-title":"IMA J Numer Anal"},{"key":"362_CR34","unstructured":"Rose D (2018) An elastic primal active-set method for structured QPs. Ph.D. Thesis. Leibniz Universit\u00e4t Hannover"},{"key":"362_CR35","unstructured":"Schmidt M (2013) A generic interior-point framework for nonsmooth and complementarity constrained nonlinear optimization. Ph.D. Thesis. Gottfried Wilhelm Leibniz Universit\u00e4t Hannover"},{"issue":"4","key":"362_CR36","doi-asserted-by":"publisher","first-page":"956","DOI":"10.1137\/S105262349528456X","volume":"8","author":"E Schweitzer","year":"1998","unstructured":"Schweitzer E (1998) An interior random vector algorithm for multistage stochastic linear programs. SIAM J Optim 8(4):956\u2013972. https:\/\/doi.org\/10.1137\/S105262349528456X","journal-title":"SIAM J Optim"},{"key":"362_CR37","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-1-4757-6594-6_16","volume-title":"Stochastic optimization: algorithms and applications","author":"MC Steinbach","year":"2001","unstructured":"Steinbach MC (2001) Hierarchical sparsity in multistage convex stochastic programs. In: Uryasev SP, Pardalos PM (eds) Stochastic optimization: algorithms and applications. Kluwer Academic Publishers, Dordrecht, pp 385\u2013410. https:\/\/doi.org\/10.1007\/978-1-4757-6594-6_16"},{"issue":"3","key":"362_CR38","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s001860200227","volume":"56","author":"MC Steinbach","year":"2002","unstructured":"Steinbach MC (2002) Tree-sparse convex programs. Math Methods Oper Res 56(3):347\u2013376. https:\/\/doi.org\/10.1007\/s001860200227","journal-title":"Math Methods Oper Res"},{"issue":"1","key":"362_CR39","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/BF01584238","volume":"21","author":"PL Toint","year":"1981","unstructured":"Toint PL (1981) A note about sparsity exploiting quasi-Newton updates. Math Program 21(1):172\u2013181. https:\/\/doi.org\/10.1007\/BF01584238","journal-title":"Math Program"},{"key":"362_CR40","unstructured":"Ungar LH (1990) A bioreactor benchmark for adaptive network-based process control. In: Miller WT III, Sutton RS, Werbos PJ (eds) Neural networks for control. MIT Press, Cambridge, pp 387\u2013402. http:\/\/dl.acm.org\/citation.cfm?id=104204.104221"},{"key":"362_CR41","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1023\/A:1008677427361","volume":"13","author":"RJ Vanderbei","year":"1997","unstructured":"Vanderbei RJ, Shanno DF (1997) An interior-point algorithm for nonconvex nonlinear programming. Comput Optim Appl 13:231\u2013252. https:\/\/doi.org\/10.1023\/A:1008677427361","journal-title":"Comput Optim Appl"},{"issue":"1","key":"362_CR42","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-004-0559-y","volume":"106","author":"A W\u00e4chter","year":"2006","unstructured":"W\u00e4chter A, Biegler LT (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math Program 106(1):25\u201357. https:\/\/doi.org\/10.1007\/s10107-004-0559-y","journal-title":"Math Program"}],"container-title":["Computational Management Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-020-00362-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10287-020-00362-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-020-00362-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,4]],"date-time":"2021-02-04T00:32:28Z","timestamp":1612398748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10287-020-00362-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,5]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["362"],"URL":"https:\/\/doi.org\/10.1007\/s10287-020-00362-9","relation":{},"ISSN":["1619-697X","1619-6988"],"issn-type":[{"type":"print","value":"1619-697X"},{"type":"electronic","value":"1619-6988"}],"subject":[],"published":{"date-parts":[[2020,2,5]]},"assertion":[{"value":"11 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}