EFFICIENT ALGORITHMS FOR DISTRIBUTIONALLY ROBUST STOCHASTIC OPTIMIZATION WITH DISCRETE SCENARIO SUPPORT

Article Computer Science, Software Engineering

Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems

Yuyuan Ouyang et al.

Summary: This paper explores the lower complexity bounds of first-order methods on large-scale convex-concave bilinear saddle-point problems (SPP). The study shows that first-order methods on affinely constrained problems generally cannot be accelerated to a higher convergence rate than O(1/t) for convex problems, and O(1/t²) is the best possible convergence rate for strongly convex problems. The lower complexity bounds match with established upper complexity bounds in the literature, indicating the optimality of existing first-order methods.

MATHEMATICAL PROGRAMMING (2021)

Add to Collection

Article Operations Research & Management Science

Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems

Yannan Chen et al.

Summary: In this paper, a novel algorithmic framework is proposed for solving two-stage minimax distributionally robust optimization problems, utilizing nonanticipativity constraints, Lagrange decomposition, and the PDHG method. The framework is independent of the specific structure of the ambiguity set and extends to continuously distributed random variables through a discretization scheme. Preliminary numerical tests show promising performance of the proposed decomposition algorithm with parallel computing capabilities.

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS (2021)

Add to Collection

Article Computer Science, Software Engineering