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


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


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


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.


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.