Optimization Online


First-order algorithms for robust optimization problems via convex-concave saddle-point Lagrangian reformulation

Krzysztof Postek (k.s.postek***at***tudelft.nl)
Shimrit Shtern (shimrits***at***technion.ac.il)

Abstract: 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 (Ben-Tal et al. (2015), Kilinc-Karzan and Ho-Nguyen (2018)) as alternatives for the case of large-scale problems. However, these methods are either stochastic in nature or involve a binary search for the optimal value. We propose deterministic first-order algorithms based on a saddle-point Lagrangian reformulation that avoids both of these issues. Our approach recovers the other approaches' O(1/epsilon^2) convergence rate in the general case, and offers an improved O(1/epsilon) rate for problems with constraints which are affine both in the decision and in the uncertainty. Experiment involving robust quadratic optimization demonstrates the numerical benefits of our approach.

Keywords: robust optimization; first-order methods; saddle point

Category 1: Robust Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [Postscript][PDF]

Entry Submitted: 01/07/2021
Entry Accepted: 01/07/2021
Entry Last Modified: 01/08/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society