Efficient Algorithms for a Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management

References

• Agarwal A, Kakade SM, Lee JD, Mahajan G (2020) Optimality and approximation with policy gradient methods in Markov decision processes. Proc. Thirty Third Conf. Learn. Theory (PMLR, New York), 64–66.Google Scholar
• Agarwal A, Wainwright MJ, Bartlett PL, Ravikumar PK (2009) Information-theoretic lower bounds on the oracle complexity of convex optimization. Adv. Neural Inform. Processing Systems (NIPS 2009), vol. 22 (Curran Associates Inc., Red Hook, NY), 1–9.Google Scholar
• Agrawal S, Devanur NR (2014) Fast algorithms for online stochastic convex programming. Proc. Twenty-Sixth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1405–1424.Google Scholar
• Anderson J, Doyle JC, Low SH, Matni N (2019) System level synthesis. Annual Rev. Control 47:364–393.Crossref, Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2023) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• Barz C, Gartner D (2016) Air cargo network revenue management. Transportation Sci. 50(4):1206–1222.Link, Google Scholar
• Ben-Tal A, Teboulle M (1996) Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Programming 72(1):51–63.Crossref, Google Scholar
• Bhandari J, Russo D (2019) Global optimality guarantees for policy gradient methods. Preprint, submitted June 5, https://arxiv.org/abs/1906.01786.Google Scholar
• Bottou L, Curtis FE, Nocedal J (2018) Optimization methods for large-scale machine learning. SIAM Rev. 60(2):223–311.Crossref, Google Scholar
• Brumelle SL, McGill JI (1993) Airline seat allocation with multiple nested fare classes. Oper. Res. 41(1):127–137.Link, Google Scholar
• Chen X, Gao X (2019) Stochastic optimization with decisions truncated by positively dependent random variables. Oper. Res. 67(5):1321–1327.Link, Google Scholar
• Chen Y, Shi C (2023) Network revenue management with online inverse batch gradient descent method. Production Oper. Management 32(7):2123–2137.Crossref, Google Scholar
• Chen X, Gao X, Hu Z (2015) A new approach to two-location joint inventory and transshipment control via l♮-convexity. Oper. Res. Lett. 43(1):65–68.Crossref, Google Scholar
• Chen X, Gao X, Pang Z (2018) Preservation of structural properties in optimization with decisions truncated by random variables and its applications. Oper. Res. 66(2):340–357.Link, Google Scholar
• Chen B, Jiang J, Zhang J, Zhou Z (2022) Learning to order for inventory systems with lost sales and uncertain supplies. Preprint, submitted July 10, https://arxiv.org/abs/2207.04550.Google Scholar
• Ciarallo FW, Akella R, Morton TE (1994) A periodic review, production planning model with uncertain capacity and uncertain demand—Optimality of extended myopic policies. Management Sci. 40(3):320–332.Link, Google Scholar
• Dada M, Petruzzi NC, Schwarz LB (2007) A newsvendor’s procurement problem when suppliers are unreliable. Manufacturing Service Oper. Management 9(1):9–32.Link, Google Scholar
• Davis D, Drusvyatskiy D (2018) Stochastic subgradient method converges at the rate O(k−1/4) on weakly convex functions. Preprint, submitted February 8, https://arxiv.org/abs/1802.02988.Google Scholar
• Deng C, Xiong Y, Yang L, Yang Y, Wang G (2022) A smoothing SAA method for solving a nonconvex multisource supply chain stochastic optimization model. Math. Problems Engrg. 2022:1–7.Crossref, Google Scholar
• Drusvyatskiy D, Paquette C (2019) Efficiency of minimizing compositions of convex functions and smooth maps. Math. Programming 178(1):503–558.Crossref, Google Scholar
• Erdelyi A, Topaloglu H (2010) A dynamic programming decomposition method for making overbooking decisions over an airline network. INFORMS J. Comput. 22(3):443–456.Link, Google Scholar
• Fatkhullin I, He N, Hu Y (2023) Stochastic optimization under hidden convexity. Preprint, submitted December 30, https://arxiv.org/abs/2401.00108.Google Scholar
• Feng Q, Shanthikumar JG (2018) Supply and demand functions in inventory models. Oper. Res. 66(1):77–91.Link, Google Scholar
• Feng Q, Shanthikumar JG (2022) Applications of stochastic orders and stochastic functions in inventory and pricing problems. Production Oper. Management 31(4):1433–1453.Crossref, Google Scholar
• Feng B, Li Y, Shen ZJM (2015) Air cargo operations: Literature review and comparison with practices. Transportation Res. Part C Emerging Tech. 56:263–280.Crossref, Google Scholar
• Feng Q, Jia J, Shanthikumar JG (2019) Dynamic multisourcing with dependent supplies. Management Sci. 65(6):2770–2786.Link, Google Scholar
• Ghadimi S, Lan G (2013) Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim. 23(4):2341–2368.Crossref, Google Scholar
• Ghadimi S, Lan G, Zhang H (2016) Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Math. Programming 155(1):267–305.Crossref, Google Scholar
• Ghai U, Lu Z, Hazan E (2022) Non-convex online learning via algorithmic equivalence. 36th Conf. Neural Inform. Processing Systems (NeurIPS 2022), vol. 35 (Curran Associates Inc., Red Hook, NY), 22161–22172.Google Scholar
• Han Y, Zhou Z, Weissman T (2020) Optimal no-regret learning in repeated first-price auctions. Preprint, submitted March 22, https://arxiv.org/abs/2003.09795.Google Scholar
• Hong M, Wai HT, Wang Z, Yang Z (2020) A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. Preprint, submitted July 10, https://arxiv.org/abs/2007.05170.Google Scholar
• Hu Y, Chen X, He N (2021) On the bias-variance-cost tradeoff of stochastic optimization. Adv. Neural Inform. Processing Systems (NeurIPS 2021), vol. 34 (Curran Associates Inc., Red Hook, NY).Google Scholar
• Hu Y, Wang J, Xie Y, Krause A, Kuhn D (2024) Contextual stochastic bilevel optimization. Adv. Neural Inform. Processing Systems (NeurIPS 2023), vol. 36 (Curran Associates Inc., Red Hook, NY).Google Scholar
• Karaesmen I, Van Ryzin G (2004) Overbooking with substitutable inventory classes. Oper. Res. 52(1):83–104.Link, Google Scholar
• Karimi H, Nutini J, Schmidt M (2016) Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition. Joint Eur. Conf. Machine Learn. Knowledge Discovery Databases (Springer, Berlin), 795–811.Google Scholar
• Klein R, Koch S, Steinhardt C, Strauss AK (2020) A review of revenue management: Recent generalizations and advances in industry applications. Eur. J. Oper. Res. 284(2):397–412.Crossref, Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Kunnumkal S, Topaloglu H (2008) Using stochastic approximation methods to compute optimal base-stock levels in inventory control problems. Oper. Res. 56(3):646–664.Link, Google Scholar
• Li D, Pang Z (2017) Dynamic booking control for car rental revenue management: A decomposition approach. Eur. J. Oper. Res. 256(3):850–867.Crossref, Google Scholar
• Li X, Ye Y (2022) Online linear programming: Dual convergence, new algorithms, and regret bounds. Oper. Res. 70(5):2948–2966.Link, Google Scholar
• Miao S, Wang Y (2021) Network revenue management with nonparametric demand learning: T-regret and polynomial dimension dependency. Preprint, submitted October 25, http://dx.doi.org/10.2139/ssrn.3948140.Google Scholar
• Miao S, Wang Y (2024) Demand balancing in primal-dual optimization for blind network revenue management. Preprint, submitted April 6, https://arxiv.org/abs/2404.04467.Google Scholar
• Nemirovski A, Juditsky A, Lan G, Shapiro A (2009) Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4):1574–1609.Crossref, Google Scholar
• Previgliano F, Vulcano G (2021) Managing uncertain capacities for network revenue optimization. Manufacturing Service Oper. Management 24(2):1202–1219.Link, Google Scholar
• Sakos I, Vlatakis-Gkaragkounis EV, Mertikopoulos P, Piliouras G (2024) Exploiting hidden structures in non-convex games for convergence to Nash equilibrium. Adv. Neural Inform. Processing Systems (NeurIPS 2023), vol. 36 (Curran Associates Inc., Red Hook, NY), 66979–67006.Google Scholar
• Shaked M, Shanthikumar JG (2007) Stochastic Orders (Springer Science & Business Media, Berlin).Crossref, Google Scholar
• Singham DI, Lam H (2020) Sample average approximation for functional decisions under shape constraints. 2020 Winter Simulation Conf. (WSC) (IEEE, Piscataway, NJ), 2791–2799.Google Scholar
• Starr RM (1969) Quasi-equilibria in markets with non-convex preferences. Econometrica 37(1):25–38.Crossref, Google Scholar
• Sun J (2021) Provable nonconvex methods/algorithms. Accessed July 15, 2023, https://sunju.org/research/nonconvex/.Google Scholar
• Talluri K, Van Ryzin G (1998) An analysis of bid-price controls for network revenue management. Management Sci. 44(11):1577–1593.Link, Google Scholar
• Tang SY, Kouvelis P (2014) Pay-back-revenue-sharing contract in coordinating supply chains with random yield. Production Oper. Management 23(12):2089–2102.Crossref, Google Scholar
• Vapnik V (1999) The Nature of Statistical Learning Theory (Springer Science & Business Media, Berlin).Google Scholar
• Wang X (2016) Optimal allocation of limited and random network resources to discrete stochastic demands for standardized cargo transportation networks. Transportation Res. Part B Methodological 91:310–331.Crossref, Google Scholar
• Wang T, Meng Q, Wang S, Qu X (2021) A two-stage stochastic nonlinear integer-programming model for slot allocation of a liner container shipping service. Transportation Res. Part B Methodological 150:143–160.Crossref, Google Scholar
• Ying D, Guo MA, Ding Y, Lavaei J, Shen ZJ (2023) Policy-based primal-dual methods for convex constrained Markov decision processes. Proc. AAAI Conf. Artificial Intelligence 37(9):10963–10971.Crossref, Google Scholar
• Yuan H, Luo Q, Shi C (2021) Marrying stochastic gradient descent with bandits: Learning algorithms for inventory systems with fixed costs. Management Sci. 67(10):6089–6115.Link, Google Scholar
• Zhang J, Koppel A, Bedi AS, Szepesvari C, Wang M (2020) Variational policy gradient method for reinforcement learning with general utilities. Adv. Neural Inform. Processing Systems (NeurIPS 2020), vol. 33 (Curran Associates Inc., Red Hook, NY), 4572–4583.Google Scholar