Abstract We present MUSE-BB, a branch-and-bound (B&B) based decomposition algorithm for the deterministic global solution of nonconvex two-stage stochastic programming problems. In contrast to three recent decomposition algorithms, which solve this type of problem in a projected form by nesting an inner B&B in an outer B&B on the first-stage variables, we branch on all variables within a single B&B tree. This results in a higher convergence order of the lower bounding scheme, avoids repeated consideration of subdomains, inherent to the nesting of B&B searches, and enables the use of cheaper subproblems. In particular, when branching on second-stage variables, we employ a multisection variant of strong-branching, in which we simultaneously consider one candidate variable from each scenario for branching. By our decomposable lower bounding scheme, the resulting subproblems are independent and can be solved in parallel. We then use strong-branching scores to filter less promising candidate variables and only generate child nodes corresponding to a multisection involving the remaining variables by combining the appropriate subproblem results. We prove finite $$\varepsilon _f$$ ε f -convergence, and demonstrate that the lower-bounding scheme of MUSE-BB has at least first-order convergence under the mild assumption of Lipschitz continuous functions and relaxations. MUSE-BB is implemented and made available open source, as an extension of our deterministic global solver for mixed-integer nonlinear programs, MAiNGO, with OpenMP-parallelization of the decomposable subroutines. Numerical results show that MUSE-BB requires less CPU time than solving the deterministic equivalent using the standard version of MAiNGO; moreover, the parallelized decomposition allows for further reduction in wall time.

Abstract Hammerstein–Wiener models constitute a significant class of block-structured dynamic models, as they approximate process nonlinearities on the basis of input–output data without requiring identification of a full nonlinear process model. Optimization problems with Hammerstein–Wiener models embedded are nonconvex, and thus local optimization methods may obtain suboptimal solutions. In this work, we develop a deterministic global optimization strategy that exploits the specific structure of Hammerstein–Wiener models to extend existing theory on global optimization of systems with linear dynamics. At first, we discuss alternative formulations of the dynamic optimization problem with Hammerstein–Wiener models embedded, demonstrating that careful selection of the optimization variables of the problem can offer significant numerical advantages to the solution approach. Then, we develop convex relaxations for the proposed optimization problem and discuss implementation aspects to obtain the global solution focusing on a control parametrization technique. Finally, we apply our optimization strategy to case studies comprising both offline and online dynamic optimization problems. The results confirm an improved computational performance of the proposed solution approach over alternative options not exploiting the linear dynamics for all considered examples. They also underline the tractability of deterministic global dynamic optimization when using few control intervals in online applications like nonlinear model predictive control.

Abstract The computation of lower bounds via the solution of convex lower bounding problems depicts current state-of-the-art in deterministic global optimization. Typically, the nonlinear convex relaxations are further underestimated through linearizations of the convex underestimators at one or several points resulting in a lower bounding linear optimization problem. The selection of linearization points substantially affects the tightness of the lower bounding linear problem. Established methods for the computation of such linearization points, e.g., the sandwich algorithm, are already available for the auxiliary variable method used in state-of-the-art deterministic global optimization solvers. In contrast, no such methods have been proposed for the (multivariate) McCormick relaxations. The difficulty of determining a good set of linearization points for the McCormick technique lies in the fact that no auxiliary variables are introduced and thus, the linearization points have to be determined in the space of original optimization variables. We propose algorithms for the computation of linearization points for convex relaxations constructed via the (multivariate) McCormick theorems. We discuss alternative approaches based on an adaptation of Kelley’s algorithm; computation of all vertices of an n -simplex; a combination of the two; and random selection. All algorithms provide substantial speed ups when compared to the single point strategy used in our previous works. Moreover, we provide first results on the hybridization of the auxiliary variable method with the McCormick technique benefiting from the presented linearization strategies resulting in additional computational advantages.