On the performance of affine policies for two-stage adaptive optimization: a geometric perspective
type: Item
instance of: scholarly article
title: On the performance of affine policies for two-stage adaptive optimization: a geometric perspective
zbMATH Open document ID: 1341.90094
author: Hoda Bidkhori
author: Dimitris Bertsimas
published in: Mathematical Programming. Series A. Series B
publication date: 2015-10-19T00:00:00Z
review text: The two-stage adaptive robust linear optimization problem \(\Pi_{\mathrm{Adopt}}(U)\), given by \(z_{\mathrm{Adopt}}(U)=\min c^Tx + \max_{b\in U}\min_{y(b)} d^Ty(b)\), subject to \(Ax+By(b) \geq b\) for all \(b\in U\) and \(x,y(b)\geq 0\) is considered, where \(A,B\) are matrices, \(c,d\) are vectors and \(U\subset \mathbb R^m_+\) is a convex, compact uncertainty set of possible values \(b\). Using affine policies \(y(b)=Pb+q\), the authors get a tractable problem with objective \(z_{\mathrm{Aff}}(U)\) and construct for the intractable problem \(\Pi_{\mathrm{Adopt}}(U)\) a priory bounds according to \(z_{\mathrm{Adopt}}(U)\leq z_{\mathrm{Aff}}(U)\leq (\lambda(1+\rho/s)/(\lambda+\rho/s)z_{\mathrm{Adopt}}(U)\). Here \(s={\mathrm{sym}}(U)\in [1/m,1]\) is an improved measure of symmetry taking into account the geometric structure of \(U\), \(\rho\) is a translation factor of \(U\) towards the origin inside of \(\mathbb R^m_+\) and \(\lambda\geq 1\) is the simplex dilation factor with respect to an inscribed and circumscribed simplex of \(U\). The parameters \(s,\rho,\lambda\) are determined for a couple of important examples of \(U\) showing the significant improvement of the new a priori bound in contrast to the robust bound in [\textit{D. Bertsimas} et al., Math. Oper. Res. 36, No. 1, 24--54 (2011; Zbl 1218.90142)]. In case of an inventory problem, the authors demonstrate that their new a priory bound is competitive to known a posteriori bounds. The main results are shown in detail.
reviewed by: Armin Hoffmann
Mathematics Subject Classification ID: 90C15
Mathematics Subject Classification ID: 90C47
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 6495762
zbMATH Keywords: robust linear optimization
zbMATH Keywords: adjustable linear optimization
zbMATH Keywords: affine policies
zbMATH Keywords: a priori bounds
zbMATH Keywords: symmetry factor
zbMATH Keywords: translation factor
zbMATH Keywords: simplex dilation factor
MaRDI profile type: Publication
full work available at URL: s10107-014-0818-5
OpenAlex ID: W2162210915
cites work: On the symmetry function of a convex set
cites work: Min-max control of constrained uncertain discrete-time linear systems
cites work: Extending scope of robust optimization: comprehensive robust counterparts of uncertain problems
cites work: Adjustable robust solutions of uncertain linear programs
cites work: Selected topics in robust convex optimization
cites work: Constrained Stochastic LQC: A Tractable Approach
cites work: Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization
cites work: On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems
cites work: On the power and limitations of affine policies in two-stage adaptive optimization
cites work: A Geometric Characterization of the Power of Finite Adaptability in Multistage Stochastic and Adaptive Optimization
cites work: Robust Combinatorial Optimization with Exponential Scenarios
cites work: Optimization over state feedback policies for robust control with constraints
cites work: An Efficient Method to Estimate the Suboptimality of Affine Controllers
cites work: Two-Stage Robust Network Design with Exponential Scenarios
cites work: Primal and dual linear decision rules in stochastic and robust optimization
cites work: Bounds for Lattice Polytopes Containing a Fixed Number of Interior Points in a Sublattice
cites work: The Optimal Recourse Problem in Discrete Time: $L^1 $-Multipliers for Inequality Constraints
cites work: Design of Affine Controllers via Convex Optimization
cites work: Distributionally Robust Control of Constrained Stochastic Systems
DOI: 10.1007/S10107-014-0818-5
Recommended article: A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides
Recommended article: A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization
Recommended article: A Primal–Dual Lifting Scheme for Two-Stage Robust Optimization
Recommended article: Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls
Recommended article: On the approximability of adjustable robust convex optimization under uncertainty
Recommended article: A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization
Recommended article: Saddle point approximation approaches for two-stage robust optimization problems
Recommended article: A Geometric Characterization of the Power of Finite Adaptability in Multistage Stochastic and Adaptive Optimization
Recommended article: On the power and limitations of affine policies in two-stage adaptive optimization
Recommended article: \(K\)-adaptability in two-stage mixed-integer robust optimization
description: scientific article; zbMATH DE number 6495762