A large number of practical algorithms for Optimal Control Problems (OCP) relies on a so-called condensing procedure to exploit the given structure in the quadratic programming (QP) subproblems. While the established structure-exploiting condensing algorithm is of cubic complexity in the horizon length, in this technical note we propose a novel algorithm that is only of … Read more
We define a regularized variant of the Dual Dynamic Programming algorithm called REDDP (REgularized Dual Dynamic Programming) to solve nonlinear dynamic programming equations. We extend the algorithm to solve nonlinear stochastic dynamic programming equations. The corresponding algorithm, called SDDP-REG, can be seen as an extension of a regularization of the Stochastic Dual Dynamic Programming (SDDP) … Read more
In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give the first-ever polynomial time (in the size of data) algorithm to train a ReLU DNN with one hidden layer to {\em global optimality}. This follows from our complete characterization of the ReLU DNN … Read more
We consider a two player finite strategic zero-sum game where each player has stochastic linear constraints. We formulate the stochastic constraints of each player as chance constraints. We show the existence of a saddle point equilibrium if the row vectors of the random matrices, defining the stochastic constraints of each player, are elliptically symmetric distributed … Read more
Business analytics is becoming more and more important nowadays. Up to now predictive analytics appears to be much more applied in practice than prescriptive analytics. We argue that although optimization is used to obtain predictive models, and predictive tools are used to forecast parameters in optimization models, still the deep relation between the predictive and … Read more
We study the online estimation of the optimal policy of a Markov decision process (MDP). We propose a class of Stochastic Primal-Dual (SPD) methods which exploit the inherent minimax duality of Bellman equations. The SPD methods update a few coordinates of the value and policy estimates as a new state transition is observed. These methods … Read more
We are interested in the existence of Pareto solutions to the vector optimization problem $$\text{\rm Min}_{\,\mathbb{R}^m_+} \{f(x) \,|\, x\in \mathbb{R}^n\},$$ where $f\colon\mathbb{R}^n\to \mathbb{R}^m$ is a polynomial map. By using the {\em tangency variety} of $f$ we first construct a semi-algebraic set of dimension at most $m – 1$ containing the set of Pareto values of … Read more
We study the continuous newsvendor problem (i.e. a newsvendor problem concerning goods of a non-discrete nature, such as fresh fruit juice) and a class of stochastic dynamic programs with several application areas, such as inventory control of a continuous good, economics, and supply chain management. The class is characterized by continuous state and action spaces, … Read more
We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can dynamically choose the next item based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more
We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the … Read more