Krzysztof Postek

joint work with Shimrit Shtern

First-order methods for solving robust optimization problems

We show how robust optimization problems where each onstraints is convex in the decision variables and concave in the uncertain parameters, can be solved using a first-order saddle-point algorithm. Importantly, the computations of proximal operators involving the uncertain parameters ("pessimization") are parallelizable over the problem's constraints. The scheme has an O(1/T) convergence rate with known both optimality and feasibility guarantees.

Dick den Hertog

Solving hard non-robust optimization problems by Robust Optimization

We discuss several hard classes of optimization problems that contain no uncertainty, and that can be reformulated to (adaptive) robust optimization (RO) problems. We start with several geometrical problems that can be modeled as RO problems. Then, we show that disjoint bilinear and concave minimization problems with linear constraints can be efficiently solved by reformulating these problems as adaptive linear RO problems. This talk summarizes several (recent) papers and is joint work with many other researchers. We expect that more hard classes of problems can be treated in this way.

Shimrit Shtern

joint work with Bradley Sturt, Dimitris Bertsimas

Data-Driven Two-Stage Linear Optimization: Feasibility and Approximation Guarantees

In this talk, we focus on two-stage linear optimization problems wherein the information about uncertainty is given by historical data. We present a method that employs a simple robustification of the data combined with a multi-policy approximation in order to solve this problem, and prove is combines (i) strong out-of-sample finite-sample guarantees and (ii) asymptotic optimality. A key contribution of this work is the development of novel geometric insights, which we use to show our approximation is asymptotically optimal.