First-Order Algorithms for Robust Optimization Problems via Convex-Concave Saddle-Point Lagrangian Reformulation

References

• Alacaoglu A, Malitsky Y, Cevher V (2021) Forward-reflected-backward method with variance reduction. Comput. Optim. Appl. 80(2):321–346.Crossref, Google Scholar
• Andersson JAE, Gillis J, Horn G, Rawlings JB, Diehl M (2019) CasADi: A software framework for nonlinear optimization and optimal control. Math. Programming Comput. 11(1):1–36.Crossref, Google Scholar
• Auslender A, Teboulle M (2009) Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities. Math. Programming 120(1):27–48.Crossref, Google Scholar
• Bauschke HH, Combettes PL (2011) Convex Analysis and Monotone Operator Theory in Hilbert Spaces (Springer, Berlin).Crossref, Google Scholar
• Ben-Tal A, den Hertog D, Vial JP (2015a) Deriving robust counterparts of nonlinear uncertain inequalities. Math. Programming 149(1):265–299.Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Ben-Tal A, Hazan E, Koren T, Mannor S (2015b) Oracle-based robust optimization via online learning. Oper. Res. 63(3):628–638.Link, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bienstock D (2007) Histogram models for robust portfolio optimization. J. Comput. Finance 11(1):1.Crossref, Google Scholar
• Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40(1):120–145.Crossref, Google Scholar
• Combettes PL, Müller CL (2018) Perspective functions: Proximal calculus and applications in high-dimensional statistics. J. Math. Anal. Appl. 457(2):1283–1306.Crossref, Google Scholar
• Gabrel V, Murat C, Thiele A (2014) Recent advances in robust optimization: An overview. Eur. J. Oper. Res. 235(3):471–483.Crossref, Google Scholar
• Gidel G, Jebara T, Lacoste-Julien S (2017) Frank-Wolfe algorithms for saddle point problems. Artificial Intelligence and Statistics (PMLR, New York), 362–371.Google Scholar
• Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optim. 2(3–4):157–325.Google Scholar
• Ho-Nguyen N, Kilinç-Karzan F (2018) Online first-order framework for robust convex optimization. Oper. Res. 66(6):1670–1692.Link, Google Scholar
• Ho-Nguyen N, Kilinç-Karzan F (2019) Exploiting problem structure in optimization under uncertainty via online convex optimization. Math. Programming 177(1):113–147.Crossref, Google Scholar
• Jeyakumar V, Li G (2014) Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization. Math. Programming 147(1–2):171–206.Crossref, Google Scholar
• Juditsky A, Nemirovski A (2011) First order methods for nonsmooth convex large-scale optimization, II: Utilizing problems structure. Sra SSN, Wright SJ, eds. Optimization for Machine Learning (MIT Press, Cambridge, MA), 149–181.Crossref, Google Scholar
• Korpelevich G (1976) Extragradient method for finding saddle points and other problems. Экон. и мат. методы 12(4):747–756.Google Scholar
• Malitsky Y, Tam MK (2020) A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM J. Optim. 30(2):1451–1472.Crossref, Google Scholar
• Mutapcic A, Boyd S (2009) Cutting-set methods for robust convex optimization with pessimizing oracles. Optim. Methods Software 24(3):381–406.Crossref, Google Scholar
• Nedić A, Ozdaglar A (2009) Subgradient methods for saddle-point problems. J. Optim. Theory Appl. 142(1):205–228.Crossref, Google Scholar
• Nemirovski A (1994) Information based complexity of convex programming. Accessed September 4, 2024, https://www2.isye.gatech.edu/∼nemirovs/Lec_EMCO.pdf.Google Scholar
• Nemirovski A (2004) Prox-method with rate of convergence o (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1):229–251.Crossref, Google Scholar
• Nesterov Y (2007) Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Programming 109(2):319–344.Crossref, Google Scholar
• Optimization G (2020) Gurobi optimizer reference manual. Accessed September 4, 2024, http://www.gurobi.com.Google Scholar
• Ouyang Y, Xu Y (2021) Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Programming 185(1):1–35.Crossref, Google Scholar
• Postek K, Shtern S (2024) First-order algorithms for robust optimization problems via convex-concave saddle-point Lagrangian reformulation. http://dx.doi.org/10.1287/ijoc.2022.0200, http://github.com/INFORMSJoC/2022.0200.Google Scholar
• Tseng P (1991) Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control Optim. 29(1):119–138.Crossref, Google Scholar
• Wächter A, Biegler LT (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Programming 106(1):25–57.Crossref, Google Scholar
• Zhang J, Hong M, Zhang S (2022) On lower iteration complexity bounds for the convex concave saddle point problems. Math. Programming 194(1–2):901–935.Crossref, Google Scholar