Invited Session Fri.1.MA 004

Friday, 10:30 - 12:00 h, Room: MA 004

Cluster 20: Robust optimization [...]

A robust optimization approach to stochastic analysis


Chair: Nataly Youssef and Chaithanya Bandi



Friday, 10:30 - 10:55 h, Room: MA 004, Talk 1

Chaithanya Bandi
Optimal design for multi-item auctions: A robust optimization approach

Coauthor: Dimitris Bertsimas


We revisit the auction design problem for multi-item auctions with budget constrained buyers by introducing a robust optimization approach to model (a) concepts
such as incentive compatibility and individual rationality that are naturally expressed in the
language of robust optimization and (b) the auctioneer's beliefs on the buyers' valuations of
the items. Rather than using probability distributions (the classical probabilistic approach)
or an adversarial model to model valuations, we introduce an uncertainty set based model for
these valuations. We construct these uncertainty sets to incorporate historical information
available to the auctioneer in a way that is consistent with limit theorems of probability theory
or knowledge of the probability distribution. In this setting, we formulate the auction design
problem as a robust optimization problem and provide a characterization of the optimal
solution as an auction with reservation prices, thus extending the work of Myerson (1981)
from single item without budget constraints, to multiple items with budgets, potentially
correlated valuations and uncertain budgets.



Friday, 11:00 - 11:25 h, Room: MA 004, Talk 2

Nataly Youssef
Robust queueing theory

Coauthors: Chaithanya Bandi, Dimitris Bertsimas


We propose an approach for studying queueing systems by employing robust optimization as opposed to stochastic analysis. While traditional queueing theory relies on Kolmogorov's axioms and models arrivals and services as renewal processes, we use the limiting laws of probability as the axioms of our methodology and model the queueing primitives by uncertainty sets. We begin by analyzing the performance of single-class multi-server queues and obtain closed form expressions for the waiting times with heavy-tailed arrival and service processes; expressions that are not available under traditional queueing theory. We develop an exact calculus for analyzing a network of queues based on the following key principle: (a) the departure, (b) the superposition, and (c) the thinning of arrival processes have the same uncertainty set representation as the original arrival processes. We also derive closed form expressions for the transient behavior of single class queues and feed-forward networks. We show that our approach (a) yields accurate results in comparison to simulations for large scale queueing networks, and (b) is to a large extent insensitive to network size and traffic intensity.



Friday, 11:30 - 11:55 h, Room: MA 004, Talk 3

Dimitris Bertsimas
Network information theory via robust optimization

Coauthor: Chaitanya Bandi


We present a robust optimization framework to
solve the central problem of network information theory
of characterizing the capacity region and constructing matching optimal
codes for multi-user channels with interference. We first formulate the single user Gaussian channel as a semidefinite optimization problem with rank one constraints and recover the known capacity region (Shannon-1948) and
construct a matching optimal code. We then
characterize the capacity regions of the multi-user Gaussian interference
channel, the multicast and the multi-access Gaussian channels and
construct matching optimal codes by solving semidefinite optimization
problems with rank one constraints. We report numerical results that
show that our proposed approach is numerically tractable for code-book
sizes of up to 100,000 codewords. We further examine how the probability
description of noise affects the nature of the corresponding optimization
problem and show that for the case of exponential channels the optimization problem becomes a binary, mixed linear optimization problem that can be solved by commercial solvers.


  Online lending company provides a wide range of ways to get money by means of Tennessee Payday Loans. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.