Optimization and Control (math.OC)

Abstract: Numerical methods for the optimal feedback control of high-dimensional dynamical systems typically suffer from the curse of dimensionality. In the current presentation, we devise a mesh-free data-based approximation method for the value function of optimal control problems, which partially mitigates the dimensionality problem. The method is based on a greedy Hermite kernel interpolation scheme and incorporates context-knowledge by its structure. Especially, the value function surrogate is elegantly enforced to be 0 in the target state, non-negative and constructed as a correction of a linearized model. The algorithm is proposed in a matrix-free way, which circumvents the large-matrix-problem for multivariate Hermite interpolation. For finite time horizons, both convergence of the surrogate to the value function as well as for the surrogate vs. the optimal controlled dynamical system are proven. Experiments support the effectiveness of the scheme, using among others a new academic model that has a scalable dimension and an explicitly given value function. It may also be useful for the community to validate other optimal control approaches.

Abstract: In this work, we design primal and dual bounding methods for multistage adjustable robust optimization (MSARO) problems by adapting two decision rules rooted in the stochastic programming literature. This approach approximates the primal and dual formulations of an MSARO problem with two-stage models. From the primal perspective, this is achieved by applying two-stage decision rules that restrict the functional forms of a certain subset of decision variables. We present sufficient conditions under which the well-known constraint-and-column generation algorithm can be used to solve the primal approximation with finite convergence guarantees. From the dual side, we introduce a distributionally robust dual problem for MSARO models using their nonanticipative Lagrangian dual and then apply linear decision rules on the Lagrangian multipliers. For this dual approximation, we present a monolithic bilinear program valid for continuous recourse problems, and a cutting-plane method for mixed-integer recourse problems. Our framework is general-purpose and does not require strong assumptions such as a stage-wise independent uncertainty set, and can consider integer recourse variables. Computational experiments on newsvendor, location-transportation, and capital budgeting problems show that our bounds yield considerably smaller optimality gaps compared to the existing methods.