Optimization techniques for tree-structured nonlinear problems
- PDF / 1,130,081 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 219 Views
Optimization techniques for tree-structured nonlinear problems Jens Hübner1 · Martin Schmidt2
· Marc C. Steinbach3
Received: 11 June 2019 / Accepted: 8 January 2020 © The Author(s) 2020
Abstract 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. Keywords Nonlinear stochastic optimization · Interior-point methods · Structured Quasi-Newton updates · Structured inertia correction · Robust model predictive control Mathematics Subject Classification 90-08 · 90C06 · 90C15 · 90C30 · 90C51
1 Introduction This paper addresses nonlinear optimization problems (NLPs) with an underlying tree topology. The prototypical example are multistage stochastic optimization problems. These are computationally expensive because they involve some random process
B
Martin Schmidt [email protected] Jens Hübner [email protected] Marc C. Steinbach [email protected]
1
HaCon Ingenieurgesellschaft mbH, Lister Str. 15, 30163 Hannover, Germany
2
Department of Mathematics, Trier University, Universitätsring 15, 54296 Trier, Germany
3
Institute of Applied Mathematics, Leibniz Universität Hannover, Welfengarten 1, 30167 Hannover, Germany
123
J. Hübner et al.
whose discretization yields a scenario tree that grows exponentially with the length of the planning horizon. Primal and dual decomposition methods are specially tailored to linear and mildly nonlinear convex multistage stochastic optimization problems. Moreover, they extend well to the mixed-integer case. See Birge and Louveaux (2011), Kall and Wallace (1994) for an overview of algorithmic approaches and of stochastic optimization in general. To tackle highly nonlinear convex and nonconvex NLPs, we consider interior-point and SQP methods. Interior-point methods (IPMs) are also efficient on linear or quadratic problems, while SQP methods extend well to mixedinteger problems. In both cases the key to efficiency is the algebraic structure of the arising KKT systems rather than the stochastic structure. Therefore, we allow arbitrary trees instead of only scenario trees. All methods mentioned above are amenable to parallelization due to the rich structure of the underlying tree. In Steinbach (2002) and the references therein, the third author has developed suitable formulations and a sequential interior-point approach for convex tree-structured NLPs with polyhedral constraints, although with parallelization and with the fully nonlinear and nonconvex case in mind. Other early interior-point approaches for stochastic optimization include Berger et al. (1995), Carpenter et al. (1993), Czyzyk et al.
Data Loading...
