First-Order Algorithms for Robust Optimization Problems via Convex-Concave Saddle-Point Lagrangian Reformulation
针对大规模鲁棒优化问题，提出一种确定性一阶算法，通过凸凹鞍点拉格朗日重构避免随机性和二分搜索，在一般情形下达到O(1/ε²)收敛率，在仿射约束下达到O(1/ε)收敛率，实验验证了数值优势。
Robust optimization (RO) is one of the key paradigms for solving optimization problems affected by uncertainty. Two principal approaches for RO, the robust counterpart method and the adversarial approach, potentially lead to excessively large optimization problems. For that reason, first-order approaches, based on online convex optimization, have been proposed as alternatives for the case of large-scale problems. However, existing first-order methods are either stochastic in nature or involve a binary search for the optimal value. We show that this problem can also be solved with deterministic first-order algorithms based on a saddle-point Lagrangian reformulation that avoids both of these issues. Our approach recovers the other approaches’ [Formula: see text] convergence rate in the general case and offers an improved [Formula: see text] rate for problems with constraints that are affine both in the decision and in the uncertainty. Experiment involving robust quadratic optimization demonstrates the numerical benefits of our approach. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: This work was supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant VI.Veni.191E.035] and the Israel Science Foundation [Grant 1460/19]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0200 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0200 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .