## Invited Session Tue.3.MA 042

#### Tuesday, 15:15 - 16:45 h, Room: MA 042

**Cluster 20: Robust optimization** [...]

### Theory of robust optimization

**Chair: Dick Den Hertog**

**Tuesday, 15:15 - 15:40 h, Room: MA 042, Talk 1**

**Dick Den Hertog**

Deriving robust counterparts of nonlinear uncertain inequalities

**Coauthors: Aharon Ben-Tal, Jean-Philippe Vial**

**Abstract:**

We provide a structured way to construct the robust counterpart for a nonlinear uncertain inequality that is concave in the uncertain parameters. We use convex analysis (support functions, conjugate functions, Fenchel duality) in order to convert the robust counterpart into an explicit and computationally tractable set of constraints. It turns out that to do so one has to calculate the support function of the uncertainty set and the concave conjugate of the nonlinear constraint function. Surprisingly, these two computations are completely independent. This approach has several advantages. First, it provides an easy, structured, way to construct the robust counterpart both for linear and nonlinear inequalities. Second, it shows that for new classes of uncertainty regions and for new classes of nonlinear optimization problems tractable counterparts can be derived. Third, it paves the way to a new, more flexible, Globalized Robust Counterpart approach.

**Tuesday, 15:45 - 16:10 h, Room: MA 042, Talk 2**

**Bram L. Gorissen**

Tractable robust counterparts of linear conic optimization problems via their duals

**Coauthors: Aharon Ben Tal, Hans Blanc, Dick Den Hertog**

**Abstract:**

We propose a new way to derive the tractable robust counterpart of a linear conic optimization problem.

For the dual of a robust optimization problem, it is known that the uncertain parameters of the primal problem become optimization variables in the dual problem ("primal worst is dual best''). We give a convex reformulation of the dual problem of a robust linear conic program. When this problem is bounded and satisfies the Slater condition, strong duality holds. We show how to construct the primal optimal solution from the dual optimal solution. Our result allows many new uncertainty regions to be considered that were previously intractable, e.g., the set of steady state probability vectors of a Markov chain with uncertain transition probabilities, or the set of vectors whose Bregman or phi-divergence distance to a given vector is restricted. Our result also makes it easy to construct the robust counterpart for intersections of uncertainty regions. The description of the uncertainty region is in the constraints of the dual optimization problem, so using intersections of uncertainty regions is as simple as adding constraints for all uncertainty regions involved.

**Tuesday, 16:15 - 16:40 h, Room: MA 042, Talk 3**

**Ulrich Pferschy**

On the robust knapsack problem

**Coauthor: Michele Monaci**

**Abstract:**

We consider an uncertain variant of the knapsack problem that arises when the exact weight of each item is not exactly known in advance but belongs to a given interval, and the number of items whose weight differs from the nominal value but attains an arbitrary value in this interval is bounded by a constant. We analyze the worsening of the optimal solution value with respect to the classical knapsack problem, and exactly determine its worst-case performance depending on uncertainty for all parameter configurations. In addition, we perform the same analysis for the fractional version of the problem and provide an efficient, nontrivial algorithm for its solution. Finally, we derive the worst-case performance ratio of the fractional problem and of a variant of the greedy algorithm for the robust knapsack problem.