Optimization Online


Revisiting Approximate Linear Programming Using a Saddle Point Based Reformulation and Root Finding Solution Approach

Qihang Lin(qihang-lin***at***uiowa.edu)
Selvaprabu Nadarajah(selvan***at***uic.edu)
Negar Soheili(nazad***at***uic.edu)

Abstract: Approximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) for high dimensional Markov decision processes (MDPs) arising in business 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, solving ALPs near optimally remains challenging, for instance, in applications where the MDP includes cost functions or transition dynamics that are nonlinear or when rich basis functions are required to obtain a good VFA. We address this tension between ALP theory and solvability by (i) proposing a saddle point based reformulation of an ALP that endogenizes a state-action density function as a dual decision variable to avoid non-convexities, and (ii) developing a solution approach, ALP-Secant, that combines root finding and saddle point methods to solve this reformulation. We establish that ALP-Secant returns a near optimal ALP solution and a lower bound on the optimal policy cost with high probability in a finite number of iterations. We numerically compare ALP-Secant with the commonly used constraint sampling approach to solve ALP and a look-ahead heuristic on inventory control and energy storage applications, where using row generation is not a viable option. We find that ALP-Secant is more effective than constraint sampling for solving ALPs and delivers high quality policies and lower bounds, with its policies outperforming those from the other two heuristics. Our ALP reformulation and solution approach broaden the applicability of approximate linear programming.

Keywords: approximate linear programming, approximate dynamic programming, Markov decision processes, first order methods, energy storage, inventory control

Category 1: Other Topics (Dynamic Programming )

Category 2: Stochastic Programming

Category 3: Infinite Dimensional Optimization (Semi-infinite Programming )

Citation: University of Illinois at Chicago and University of Iowa working paper, June 2011

Download: [PDF]

Entry Submitted: 06/11/2017
Entry Accepted: 06/12/2017
Entry Last Modified: 06/11/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society