2018/01/20 by Aharon Ben‐Tal, Ben-Tal, Aharon, Omar El Housni +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #Reservoir Engineering and Simulation Methods
paper · pdf · doi:10.48550/arxiv.1801.06751
openalex publication_date 2018/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of designing piecewise affine policies for two-stage\nadjustable robust linear optimization problems under right-hand side\nuncertainty. It is well known that a piecewise affine policy is optimal\nalthough the number of pieces can be exponentially large. A significant\nchallenge in designing a practical piecewise affine policy is constructing good\npieces of the uncertainty set. Here we address this challenge by introducing a\nnew framework in which the uncertainty set is "approximated" by a "dominating"\nsimplex. The corresponding policy is then based on a mapping from the\nuncertainty set to the simplex. Although our piecewise affine policy has\nexponentially many pieces, it can be computed efficiently by solving a compact\nlinear program given the dominating simplex. Furthermore, we can find the\ndominating simplex in a closed form if the uncertainty set satisfies some\nsymmetries and can be computed using a MIP in general. The performance of our\npolicy is significantly better than the affine policy for many important\nuncertainty sets, such as ellipsoids and norm-balls, both theoretically and\nnumerically. For instance, for hypersphere uncertainty set, our piecewise\naffine policy can be computed by an LP and gives a O(m1/4)-approximation\nwhereas the affine policy requires us to solve a second order cone program and\nhas a worst-case performance bound of O(\√ m).\n