A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides

2016/09/23 by Guanglin Xu, Samuel Burer, Xu, Guanglin +1 · 2 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Risk and Portfolio Optimization

paper · pdf · doi:10.48550/arxiv.1609.07402

openalex publication_date 2016/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which in turn leads to a class of tractable, semidefinite-based approximations that are at least as strong as the affine policy. We investigate several examples from the literature demonstrating that our tractable approximations significantly improve the affine policy. In particular, our approach solves exactly in polynomial time a class of instances of increasing size for which the affine policy admits an arbitrarily large gap.

Cited by

• Extended Trust-Region Problems with One or Two Balls: Exact Copositive and Lagrangian Relaxations
• The discrete moment problem with nonconvex shape constraints

Related

• Improved Decision Rule Approximations for Multi-Stage Robust Optimization via Copositive Programming
• A Tractable Approach for designing Piecewise Affine Policies in\n Two-stage Adjustable Robust Optimization
• Robust Quadratic Programming with Mixed-Integer Uncertainty
• On the Optimality of Affine Policies for Budgeted Uncertainty Sets
• Robust two-stage combinatorial optimization problems under convex\n uncertainty