Optimization techniques for tree-structured nonlinear problems. (English) Zbl 07304217
Summary: 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.
MSC:
| 90Bxx | Operations research and management science |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
| 90C06 | Large-scale problems in mathematical programming |
| 90C15 | Stochastic programming |
| 90C30 | Nonlinear programming |
| 90C51 | Interior-point methods |
Keywords:
nonlinear stochastic optimization; interior-point methods; structured quasi-Newton updates; structured inertia correction; robust model predictive controlReferences:
| [1] | Bader, G.; Deuflhard, P., A semi-implicit midpoint rule for stiff systems of ordinary differential equations, Numer Math, 41, 373-398 (1983) · Zbl 0522.65050 · doi:10.1007/BF01418331 |
| [2] | Berger AJ, Mulvey JM, Rothberg E, Vanderbei RJ (1995) Solving multistage stochastic programs using tree dissection. Technical Report SOR-95-07. Princeton University, USA |
| [3] | Birge, JR; Louveaux, F., Introduction to stochastic programming (2011), Berlin: Springer, Berlin · Zbl 1223.90001 |
| [4] | Blomvall, J.; Lindberg, PO, A Riccati-based primal interior point solver for multistage stochastic programming, Eur J Oper Rese, 143, 2, 452-461 (2002) · Zbl 1058.90074 · doi:10.1016/S0377-2217(02)00301-6 |
| [5] | Blomvall, J., A multistage stochastic programming algorithm suitable for parallel computing, Parallel Comput, 29, 4, 431-445 (2003) · doi:10.1016/S0167-8191(03)00015-2 |
| [6] | 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-247. 10.1016/S1474-6670(17)61205-9 |
| [7] | Byrd, RH; Gilbert, J-C; Nocedal, J., A trust region method based on interior point techniques for nonlinear programming, Math Program, 89, 1, 149-185 (2000) · Zbl 1033.90152 · doi:10.1007/PL00011391 |
| [8] | Byrd RH, Nocedal J, Waltz RA (2006) KNITRO: an integrated package for nonlinear optimization. In: Large scale nonlinear optimization, 35-59, 2006. Springer, pp 35-59. 10.1007/0-387-30065-1_4 · Zbl 1108.90004 |
| [9] | Carpenter, TJ; Lustig, IJ; Mulvey, JM; Shanno, DF, Separable quadratic programming via a primal-dual interior point method and its use in a sequential procedure, ORSA J Comput, 5, 2, 182-191 (1993) · Zbl 0777.90038 · doi:10.1287/ijoc.5.2.182 |
| [10] | Czyzyk, J.; Fourer, R.; Mehrotra, S., 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-490 (1995) · Zbl 0843.90084 · doi:10.1287/ijoc.7.4.474 |
| [11] | Dennis, JE; Moré, JJ, Quasi-Newton methods, motivation and theory, SIAM Rev, 19, 1, 46-89 (1977) · Zbl 0356.65041 · doi:10.1137/1019005 |
| [12] | Dennis JE, Schnabel RB (1996) Numerical methods for unconstrained optimization and nonlinear equations, vol 16. SIAM. 10.1137/1.9781611971200 · Zbl 0847.65038 |
| [13] | Fletcher, R., An optimal positive definite update for sparse Hessian matrices, SIAM J Optim, 5, 1, 192-218 (1995) · Zbl 0824.65038 · doi:10.1137/0805010 |
| [14] | Fletcher, R., Practical methods of optimization (2013), New York: Wiley, New York · Zbl 0905.65002 |
| [15] | Gill, PE; Murray, W.; Saunders, MA; Wright, MH, Sparse matrix methods in optimization, SIAM J Sci Stat Comput, 5, 3, 562-589 (1984) · Zbl 0559.65042 · doi:10.1137/0905041 |
| [16] | Gill, PE; Murray, W.; Saunders, MS, SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM J Optim, 12, 4, 979-1006 (2002) · Zbl 1027.90111 · doi:10.1137/S1052623499350013 |
| [17] | Gondzio, J.; Grothey, A.; Wyrzykowski, R.; Dongarra, J.; Meyer, N.; Wasniewski, J., Direct solution of linear systems of size 109 arising in optimization with interior point methods, Parallel processing and applied mathematics, 513-525 (2006), Berlin: Springer, Berlin · Zbl 1182.65050 |
| [18] | Gondzio, J.; Grothey, A., Parallel interior-point solver for structured quadratic programs: application to financial planning problems, Ann Oper Res, 152, 1, 319-339 (2007) · Zbl 1144.90510 · doi:10.1007/s10479-006-0139-z |
| [19] | Gondzio, J.; Grothey, A., Exploiting structure in parallel implementation of interior point methods for optimization, Comput Manag Sci, 6, 2, 135-160 (2009) · Zbl 1170.90518 · doi:10.1007/s10287-008-0090-3 |
| [20] | Griewank, A.; Toint, PL, Partitioned variable metric updates for large structured optimization problems, Numer Math, 39, 1, 119-137 (1982) · Zbl 0482.65035 · doi:10.1007/BF01399316 |
| [21] | Griewank, A.; Toint, P.; Powell, M., On the unconstrained optimization of partially separable functions, Nonlinear optimization 1981, 301-312 (1982), Cambridge: Academic press, Cambridge · Zbl 0563.90085 |
| [22] | Hübner J (2016) Distributed algorithms for nonlinear tree-sparse problems. Ph.D. Thesis. Gottfried Wilhelm Leibniz Universität Hannover |
| [23] | Hübner, J.; Steinbach, MC; Schmidt, M., A distributed interior-point KKT solver for multistage stochastic optimization, INFORMS J Comput, 29, 4, 612-630 (2017) · Zbl 1528.90281 · doi:10.1287/ijoc.2017.0748 |
| [24] | Jessup, ER; Yang, D.; Zenios, SA, Parallel factorization of structured matrices arising in stochastic programming, SIAM J Optim, 4, 4, 833-846 (1994) · Zbl 0813.65063 · doi:10.1137/0804048 |
| [25] | Kall, P.; Wallace, SW, Stochastic programming (1994), New York: Wiley, New York · Zbl 0812.90122 |
| [26] | Lazar, M.; De La Peña, DM; Heemels, W.; Alamo, T., On input-tostate stability of min-max nonlinear model predictive control, Syst Control Lett, 57, 1, 39-48 (2008) · Zbl 1129.93433 · doi:10.1016/j.sysconle.2007.06.013 |
| [27] | Liu, DC; Nocedal, J., On the limited memory BFGS method for large scale optimization, Math Program, 45, 3, 503-528 (1989) · Zbl 0696.90048 · doi:10.1007/BF01589116 |
| [28] | Lubin, M.; Petra, CG; Anitescu, M., The parallel solution of dense saddle-point linear systems arising in stochastic programming, Optim Methods Softw, 27, 4-5, 845-864 (2012) · Zbl 1254.90140 · doi:10.1080/10556788.2011.602976 |
| [29] | Lucia A (1983) An explicit Quasi-Newton update for sparse optimization calculations. Math Comput 40(161):317-322. http://www.jstor.org/stable/2007377 · Zbl 0516.65045 |
| [30] | Lucia, S.; Engell, S., Multi-stage and two-stage robust nonlinear model predictive control, Nonlinear Model Predict Control, 45, 17, 181-186 (2012) · doi:10.3182/20120823-5-NL-3013.00015 |
| [31] | 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-74. 10.3182/20120710-4-SG-2026.00035 |
| [32] | Nocedal, J.; Wright, SJ, Numerical optimization (2006), Berlin: Springer, Berlin · Zbl 1104.65059 |
| [33] | Powell, M.; Toint, PL, The Shanno-Toint procedure for updating sparse symmetric matrices, IMA J Numer Anal, 1, 4, 403-413 (1981) · Zbl 0482.65034 · doi:10.1093/imanum/1.4.403 |
| [34] | Rose D (2018) An elastic primal active-set method for structured QPs. Ph.D. Thesis. Leibniz Universität Hannover |
| [35] | Schmidt M (2013) A generic interior-point framework for nonsmooth and complementarity constrained nonlinear optimization. Ph.D. Thesis. Gottfried Wilhelm Leibniz Universität Hannover |
| [36] | Schweitzer, E., An interior random vector algorithm for multistage stochastic linear programs, SIAM J Optim, 8, 4, 956-972 (1998) · Zbl 0912.90227 · doi:10.1137/S105262349528456X |
| [37] | Steinbach, MC; Uryasev, SP; Pardalos, PM, Hierarchical sparsity in multistage convex stochastic programs, Stochastic optimization: algorithms and applications, 385-410 (2001), Dordrecht: Kluwer Academic Publishers, Dordrecht |
| [38] | Steinbach, MC, Tree-sparse convex programs, Math Methods Oper Res, 56, 3, 347-376 (2002) · Zbl 1064.90033 · doi:10.1007/s001860200227 |
| [39] | Toint, PL, A note about sparsity exploiting quasi-Newton updates, Math Program, 21, 1, 172-181 (1981) · Zbl 0463.90081 · doi:10.1007/BF01584238 |
| [40] | 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-402. http://dl.acm.org/citation.cfm?id=104204.104221 |
| [41] | Vanderbei, RJ; Shanno, DF, An interior-point algorithm for nonconvex nonlinear programming, Comput Optim Appl, 13, 231-252 (1997) · Zbl 1040.90564 · doi:10.1023/A:1008677427361 |
| [42] | Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math Program, 106, 1, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
