We introduce an extension of Dual Dynamic Programming (DDP) to solve convex nonlinear dynamic programming equations. We call Inexact DDP (IDDP) this extension which applies to situations where some or all primal and dual subproblems to be solved along the iterations of the method are solved with a bounded error. We show that any accumulation … Read more
We study the problem of repositioning autonomous vehicles in a shared mobility system in order to simultaneously minimize the unsatisfied demand and the total operating cost. We first present a mixed integer linear programming formulation for the deterministic version of the problem, and based on that we develop an extended formulation that is easier to … Read more
We explore the power of semidefinite programming (SDP) for finding additive epsilon-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equilibrium (NE) problem and provide a number of valid inequalities to improve the quality of the relaxation. If a rank-1 solution to this SDP is … Read more
The well-known Jahn-Graef-Younes algorithm, proposed by Jahn in 2006, generates all minimal elements of a finite set with respect to an ordering cone. It consists of two Graef-Younes procedures, namely the forward iteration, which eliminates a part of the non-minimal elements, followed by the backward iteration, which is applied to the reduced set generated by … Read more
Approximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) of intractable Markov decision processes (MDPs) arising in applications. VFAs from ALPs have desirable theoretical properties, define an operating policy, and provide a lower bound on the optimal policy cost, which can be used to assess the suboptimality of heuristic policies. However, … Read more
In this paper we extend naturally the scalarization proximal point method to solve multiobjective unconstrained minimization problems, proposed by Apolinario et al.(2016), from Euclidean spaces to Hadamard manifolds for locally Lipschitz and quasiconvex vector objective functions. Moreover, we present a convergence analysis, under some mild assumptions on the multiobjective function, for two inexact variants of … Read more
Consider settings such as stochastic optimization where a smooth objective function $f$ is unknown but can be estimated with an \emph{inexact oracle} such as quasi-Monte Carlo (QMC) or numerical quadrature. The inexact oracle is assumed to yield function estimates having error that decays with increasing oracle effort. For solving such problems, we present the Adaptive … Read more
We study the problem of choosing the best subset of p features in linear regression given n observations. This problem naturally contains two objective functions including minimizing the amount of bias and minimizing the number of predictors. The existing approaches transform the problem into a single-objective optimization problem either by combining the two objectives using … Read more
We consider convex optimization problems formulated using dynamic programming equations. Such problems can be solved using the Dual Dynamic Programming algorithm combined with the Level 1 cut selection strategy or the Territory algorithm to select the most relevant Benders cuts. We propose a limited memory variant of Level 1 and show the convergence of DDP … Read more
We study the computational complexity of the infinite-horizon discounted-reward Markov Decision Problem (MDP) with a finite state space $\cS$ and a finite action space $\cA$. We show that any randomized algorithm needs a running time at least $\Omega(\carS^2\carA)$ to compute an $\epsilon$-optimal policy with high probability. We consider two variants of the MDP where the … Read more