Computing bounds via duality for singular stochastic control problems

A variety of problems such as control of queues in heavy traffic, portfolio optimization, sequential investment, etc., can be modeled as singular stochastic control problems. In these problems, control can effect instantaneous displacement in the state. The objective is to pick a control process to minimize the expected infinite horizon discounted sum of holding and control costs. Such singular stochastic control problems are not tractable except in very special cases. Therefore, we lower our aspiration from minimizing the cost functional to numerically constructing lower bounds on it. By constructing lower bounds we achieve two objectives. Firstly, one can compare a lower bound with expected discounted cost for a proposed policy as a means of bounding the performance loss when following that policy. Secondly, lower bounds will be constructed here by a method that has the following property: there is associated with each such bound an admissible control policy of a certain structured type, and in numerical examples analyzed thus far, the performance of that associated policy is nearly optimal when the bound is tight.;We provide a theoretical framework for constructing a sequence of increasing lower bounds. We do this by constructing feasible solutions to the dual of the stochastic control problem. A crucial step in constructing these dual feasible solutions is establishing a connection between the Hamilton-Jacobi-Bellman equation and solutions to Poisson's equation over sublevel sets of the holding cost function. The dual feasible solutions constructed this way can be thought of as being solutions of a related but different control problem, whose control costs are endogenously chosen. The proposed procedure is efficient in that at each step it is only necessary to compute certain integrals; it is not necessary to solve the HJB equation except at the last step when the user terminates the procedure. We demonstrate the numerical efficacy of the procedure on test examples drawn from economics and queuing theory applications.