Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds

Xiaocheng Li () and Yinyu Ye ()
Additional contact information
Xiaocheng Li: Imperial College Business School, Imperial College London, London SW7 2AZ, United Kingdom
Yinyu Ye: Department of Management Science and Engineering, Stanford University, Stanford, California 94305

Operations Research, 2022, vol. 70, issue 5, 2948-2966

Abstract: We study an online linear programming (OLP) problem under a random input model in which the columns of the constraint matrix along with the corresponding coefficients in the objective function are independently and identically drawn from an unknown distribution and revealed sequentially over time. Virtually all existing online algorithms were based on learning the dual optimal solutions/prices of the linear programs (LPs), and their analyses were focused on the aggregate objective value and solving the packing LP, where all coefficients in the constraint matrix and objective are nonnegative. However, two major open questions were as follows. (i) Does the set of LP optimal dual prices learned in the existing algorithms converge to those of the “offline” LP? (ii) Could the results be extended to general LP problems where the coefficients can be either positive or negative? We resolve these two questions by establishing convergence results for the dual prices under moderate regularity conditions for general LP problems. Specifically, we identify an equivalent form of the dual problem that relates the dual LP with a sample average approximation to a stochastic program. Furthermore, we propose a new type of OLP algorithm, action-history-dependent learning algorithm, which improves the previous algorithm performances by taking into account the past input data and the past decisions/actions. We derive an O ( log n log log n ) regret bound (under a locally strong convexity and smoothness condition) for the proposed algorithm, against the O ( n ) bound for typical dual-price learning algorithms, where n is the number of decision variables. Numerical experiments demonstrate the effectiveness of the proposed algorithm and the action-history-dependent design.

Keywords: Optimization; online linear programming; stochastic programming; sequential decision making; stochastic dynamic programming (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2164 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:5:p:2948-2966

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().