On the approximability of adjustable robust convex optimization under uncertainty (Q2392812): Difference between revisions

The adjustable robust version of the (intractable) two stage convex programming optimization problem under uncertain constraints with an uncertain variable \(u\) in a compact convex set \(U\) according to \(z_{AR}^{\text{const}}(U):=\max_{x\in X} f_1(x)+\min_{u\in U} \max_{y(u)\in Y} f_2(y(u))\) subject to the constraints \(g_i(x,y(u),u)\leq c_i\) for all \(u\in U\) and all \(i\in I\) is approximated by the computable static-robust problem \(z_{Rob}^{\text{const}}(U):=\max_{x\in X, y\in Y} f_1(x)+f_2(y)\) subject to the constraints \(g_i(x,y,u)\leq c_i\) for all \(u\in U\) and all \(i\in I\). Using mainly convexity (for \(X,Y\), \(g\) in \(x,y\)) / concavity (for \(f_1\) in \(x\), \(f_2\) in \(y\), \(g_i\) in \(u\)) assumptions and coordinate wise increasing of \(u\) the estimation \(z_{Rob}^{\text{const}}(U)\leq z_{AR}^{\text{const}}(U)\leq (1+\rho/s)z_{Rob}^{\text{const}}(U)\) is shown (Th. 1). Here \(\rho\) denotes the Minkowski value of symmetry of \(U\) and \(s\) denotes the translation factor of \(U\subset I\!\!R_+^m\) w.r.t. the order cone \(I\!\!R_+^m\) and the point of symmetry of \(U\). The result holds also for the multi stage variant where \(\rho\) is the maximum over all values of symmetry and \(s\) is the minimum over all translation factors (Th. 5). In the case of the two stage problem with uncertain objective \(f_2(y(u),u)\) (above notations without const.) they prove the relations \(z_{Rob}(U)\leq z_{AR}(U)\leq (1+\rho/s)^2 z_{Rob}(U)\) under the additional assumption that \(f_2\) is decreasing in \(u\) and satisfies some growth condition in \(u\). The proves for the two stage case are given in detail. It seems to be the first approximations in such a generality.