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
The forest-harvesting and road-construction planning problem basically consists of managing land designated for timber production and divided into harvest cells. For each time period in the given time horizon one must decide which cells to cut and what access roads to build in order to maximize expected net profit under a risk manageable scheme to … Read more
Radiation therapy is considered to be one of important treatment protocols for cancers. Radiation therapy employs several beams of ionizing radiation to kill cancer tumors, but such irradiation also causes damage to normal tissues. Therefore, a treatment plan should satisfy dose-volume constraints (DVCs). Intensity-modulated radiotherapy treatment (IMRT) enables to control the beam intensities and gives … Read more
We propose simple polynomial-time algorithms for two linear conic feasibility problems. For a matrix $A\in \R^{m\times n}$, the {\em kernel problem} requires a positive vector in the kernel of $A$, and the {\em image problem} requires a positive vector in the image of $A^\T$. Both algorithms iterate between simple first order steps and rescaling steps. … Read more
Adaptive cubic regularization methods have emerged as a credible alternative to linesearch and trust-region for smooth nonconvex optimization, with optimal complexity amongst second-order methods. Here we consider a general/new class of adaptive regularization methods, that use first- or higher-order local Taylor models of the objective regularized by a(ny) power of the step size and applied … Read more
In this paper, we discuss how to design the graph topology to reduce the communication complexity of certain algorithms for decentralized optimization. Our goal is to minimize the total communication needed to achieve a prescribed accuracy. We discover that the so-called expander graphs are near-optimal choices. We propose three approaches to construct expander graphs for … Read more
Multi-stage robust optimization problems, where the decision maker can dynamically react to consecutively observed realizations of the uncertain problem parameters, pose formidable theoretical and computational challenges. As a result, the existing solution approaches for this problem class typically determine subopti- mal solutions under restrictive assumptions. In this paper, we propose a robust dual dynamic programming … Read more
We describe the fundamentals of algorithms for minimizing a smooth nonlinear function, and extensions of these methods to the sum of a smooth function and a convex nonsmooth function. Such objective functions are ubiquitous in data analysis applications, as we illustrate using several examples. We discuss methods that make use of gradient (first-order) information about … Read more
We introduce a new continuous location-allocation problem where the facilities have both a xed opening cost and a coverage distance limitation. The problem might have wide applications especially in the spatial planning of water and/or energy access networks where the coverage distance might be associated with the physical loss constraints. We formulate a mixed integer … Read more