Robust quadratic programming with mixed-integer uncertainty
From MaRDI portal
Publication:3386756
DOI10.1287/IJOC.2019.0901zbMATH Open1474.90312arXiv1706.01949OpenAlexW2973191611MaRDI QIDQ3386756FDOQ3386756
Authors: Areesh Mittal, Can Gokalp, Grani A. Hanasusanto 
Publication date: 7 January 2021
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Abstract: We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S-lemma method --- which is valid only in the case of continuous uncertainty --- is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems.
Full work available at URL: https://arxiv.org/abs/1706.01949
Recommendations
- Robust convex quadratically constrained programs
- Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
- SDP reformulation for robust optimization problems based on nonconvex QP duality
- Robust solutions of uncertain complex-valued quadratically constrained programs
- Exact SDP reformulations of adjustable robust linear programs with box uncertainties under separable quadratic decision rules via SOS representations of non-negativity
Quadratic programming (90C20) Convex programming (90C25) Semidefinite programming (90C22) Robustness in mathematical programming (90C17)
Cites Work
- Support-vector networks
- Title not available (Why is that?)
- Robustness and regularization of support vector machines
- Theory and applications of robust optimization
- Robust optimization
- Robust Solutions to Least-Squares Problems with Uncertain Data
- Title not available (Why is that?)
- Infinitely constrained optimization problems
- On the copositive representation of binary and continuous nonconvex quadratic programs
- The sample average approximation method for stochastic discrete optimization
- Approximation of the stability number of a graph via copositive programming
- Robust convex optimization
- Distributionally robust optimization and its tractable approximations
- A Robust Optimization Perspective on Stochastic Programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- Rangen: A random network generator for activity-on-the-node networks
- Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
- Lectures on stochastic programming. Modeling and theory.
- Adjustable robust solutions of uncertain linear programs
- Generalized decision rule approximations for stochastic programming via liftings
- Scheduling arrivals to a stochastic service delivery system using copositive cones
- Distributionally robust mixed integer linear programs: persistency models with applications
- Mixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation
- Robust convex quadratically constrained programs
- Tractable approximations to robust conic optimization problems
- Copositive programming
- New results on the cp-rank and related properties of co(mpletely) positive matrices
- Convexity in SemiAlgebraic Geometry and Polynomial Optimization
- Generalized Linear-Quadratic Problems of Deterministic and Stochastic Optimal Control in Discrete Time
- On reduced semidefinite programs for second order moment bounds with applications
- Robust resource allocations in temporal networks
- A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides
- Perturbation Theory for the Least Squares Problem with Linear Equality Constraints
- Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls
- A fresh CP look at mixed-binary QPs: new formulations and relaxations
- Distributionally robust project crashing with partial or no correlation information
Cited In (15)
- Extending the Scope of Robust Quadratic Optimization
- A robustification approach in unconstrained quadratic optimization
- Interplay of non-convex quadratically constrained problems with adjustable robust optimization
- Title not available (Why is that?)
- Maximizing perturbation radii for robust convex quadratically constrained quadratic programs
- A note on \(\Sigma_2^p\)-completeness of a robust binary linear program with binary uncertainty set
- Interval quadratic programming for day-ahead dispatch of uncertain predicted demand
- Finding minimum volume circumscribing ellipsoids using generalized copositive programming
- On second-order conic programming duals for robust convex quadratic optimization problems
- Two-stage robust mixed integer programming problem with objective uncertainty
- Robust convex quadratically constrained programs
- Exact SDP reformulations for adjustable robust quadratic optimization with affine decision rules
- Optimization under uncertainty and risk: quadratic and copositive approaches
- Uncertainty Preferences in Robust Mixed-Integer Linear Optimization with Endogenous Uncertainty
- A Lagrangian dual method for two-stage robust optimization with binary uncertainties
Uses Software
This page was built for publication: Robust quadratic programming with mixed-integer uncertainty
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386756)
