2019 Dupačová-Prékopa Student Paper Prize Awards
First Prize
Philip Thompson (Instituto de Matemática Pura e Aplicada (IMPA), Rio de Janeiro)
Variance-Based Extragradient Methods with Line Search for Stochastic Variational Inequalities, SIAM Journal on Optimization, 29(1):175-206, 2019.
Advisors: Alfredo N. Iusem and Alejandro Jofre
Citation: The paper proposes the first provably convergent stochastic approximation method with variance reduction, either for stochastic variational inequalities or stochastic optimization, which is robust with respect to an unknown Lipschitz constant. This widens the applicability and improves the desired efficient acceleration of the existing variance reduction methods, all of which still assume knowledge of a Lipschitz constant. This paper breaks with the prevailing approach in stochastic optimization and obtains an optimal stochastic gradient descent algorithm with line search. This allows the authors to make only local assumptions. The paper is technically deep and includes advances in concentration inequalities as well as optimization theory. The paper has exceptional reach and is expected to significantly influence a large number of communities. Philip was the leading developer and author as confirmed with his co-authors.
Runner-up
Xie Weijun (School of Industrial & Systems Engineering, Georgia Institute of Technology)
On Deterministic Reformulations of Distributionally Robust Joint Chance Constrained Optimization Problems, SIAM Journal on Optimization, 28(2):1151-1182, 2018.
Advisor: Shabbir Ahmed
Citation: he paper studies tractable reformulations of a very general class of distributionally robust joint chance constrained optimization problems (DRCCP) where the joint chance constraint is required to hold for all probability distributions of the stochastic parameters from a convex moment ambiguity set. In recent years there has been a flurry of activity in deriving convex reformulations of distributionally robust chance constraints in a variety of different settings. This paper unifies several existing proof techniques for reformulating DRCCP, and provides substantial extensions by considering joint chance constraints. Xie was the leading developer and author as confirmed with his author.
Prize Committee: Nilay Noyan (chair), Alejandro Jofre, and Johannes Royset
2016 COSP Student Paper Prize Awards
First Prize
Algo Carè (University of Brescia)
Scenario Min-Max Optimization and the Risk of Empirical Costs, SIAM Journal on Optimization, 25(4):2061-2080, 2015.
Advisors: S. Garatti and M. C. Campi
Abstract: Many decision problems can be formulated as the problem of minimising a convex cost function that also depends on an uncertain variable. In this talk, we take a data-based worst-case approach to deal with uncertainty, and we minimise the maximum of the cost functions corresponding to some previously observed instances of the uncertain variable. We call these instances scenarios, and the solution to this optimisation problem is the scenario solution. The empirical costs are defined as the cost values that the scenario solution incurs for the various scenarios that have been used in optimisation. The risk of an empirical cost is defined as the probability that the empirical cost will be exceeded “tomorrow”, i.e., when a new instance of the uncertain variable will be experienced. In this work it is proven that the vector of the risks of the empirical costs has an ordered Dirichlet distribution independently of the distribution of the uncertainty. By virtue of this result, one can construct a probability box for the distribution of tomorrow’s cost, without making any assumption on the specific distribution of the uncertainty and without resorting to new observations.
Runner-up (in alphabetical order)
Tsvetan Asamov (Rutgers University)
Time-consistent approximations of risk-averse multistage stochastic optimization problems, Mathematical Programming, 153(2):459–493, 2015.
Advisor: Andrzej Ruszczyński
Abstract: In this paper we study the concept of time consistency as it relates to multi-stage risk-averse stochastic optimization problems on finite scenario trees. We use dynamic time-consistent formulations to approximate problems having a single coherent risk measure applied to the aggregated costs over all time periods. The dual representation of coherent risk measures is used to create a time-consistent cutting plane algorithm. Additionally, we also develop methods for the construction of universal time-consistent upper bounds. The performance of the proposed techniques is tested using monthly return data for the components of the Dow Jones Industrial Average. Our numerical results indicate that the resulting dynamic formulations yield close approximations to the original problem.
Runner-up (in alphabetical order)
Ward Romeijnders (University of Groningen)
A Convex Approximation for Two-Stage Mixed-Integer Recourse Models with a Uniform Error Bound, SIAM Journal on Optimization, 26(1):426–447, 2016.
Advisors: M.H. van der Vlerk and W.K. Klein Haneveld
Abstract: We develop a convex approximation for two-stage mixed-integer recourse models and we derive an error bound for this approximation that depends on the total variations of the probability density functions of the random variables in the model. We show that the error bound converges to zero if all these total variations converge to zero. Our convex approximation is a generalization of the one in Romeijnders et al. ("Total variation bounds on the expectation of periodic functions with applications to recourse approximations", Mathematical Programming, (2014), DOI: 10.1007/s10107-014-0829-2.) restricted to totally unimodular integer recourse models. For this special case it has the best worst-case error bound possible. As main building blocks in the derivation of the error bound we generalize the asymptotic periodicity results of Gomory ("Some polyhedra related to combinatorial problems", Linear Algebra and Its Applications, 2 (1969), pp. 451–558.) for pure integer programs to the mixed-integer case, and we use new total variation error bounds on the expectation of periodic functions.
Prize Committee: Nilay Noyan (chair), Andy Philpott, and Suvrajeet Sen
2013 COSP Student Paper Prize Awards
In 2013, the prize committee decided to award two first prizes, one for theory and the other for modeling
First Prize - Theory
Ruiwei Jiang (University of Florida)
Data Driven Chance-Constrained Stochastic Program
Advisor: Yongpei Guan
First Prize - Modeling
Ali Koç (University of Texas at Austin)
Prioritization via stochastic optimization
Advisor: David Morton
Prize Committee: Georg Pflug (chair), Suvrajeet Sen, and Güzin Bayraksan
2010 COSP Student Paper Prize Awards
First Prize
Uma Ravat (University of Illinois at Urbana-Champaign)
On the characterization of solution sets of smooth and nonsmooth stochastic Nash games
Advisor: Uday V. Shanbhag
Citation: The inaugural COSP Student Paper Prize has been awarded to Uma Ravat for the paper entitled 'On the Characterization of Solution Sets of Smooth and Nonsmooth Stochastic Nash Games'. Uma Ravat is currently a Ph.D. candidate in the Mathematics Department at the University of Illinois at Urbana-Champaign, working in the research group of Uday Shanbhag.
The paper studies game theoretic stochastic programs, in particular, a class of continuous strategy Nash games with uncertain data where the players solve expected value problems. A comprehensive analysis of the structural properties of these games is presented by providing conditions under which the corresponding sample point problems exhibit similar structural properties in an almost sure sense or with some positive measure. Several cases such as smooth and nonsmooth Nash games and games with coupled stochastic constraints are examined. The concepts are illustrated through important examples such as risk-neutral and risk-averse Nash-Cournot games and with expected value constraints.
The concept of Nash equilibrium was introduced by Nash in early 1950s and the stochastic programming models were introduces in mid-to-late fifties by Dantzig, 1955, Beale 1955, and Charnes and Cooper, 1959. While the two areas have had a steady stream of contributions, the avenues at the intersection of the two have been less explored. The paper makes a fundamental contribution in this avenue. Mathematically the paper is very mature, elegantly combining techniques from different areas. The exposition is clear and the theory is substantiated with important special cases. The paper opens up a new realm of applications in computational game theory.
Second Prize
Christian Kuechler (Humboldt University of Berlin)
On stability of multistage stochastic programs
Advisor: Werner Römisch
Citation: This citation goes to Christian Kuchler for his paper "On stability of multistage stochastic programs". The paper was written while the author was a doctoral student at Humboldt-University Berlin in the research group of Werner R\"omisch. It has been published in Volume 19, 2008, of SIAM Journal on Optimization.
In research on multistage linear stochastic programs a lasting discrepancy can be observed. On one hand, there is an abundance of algorithmic work, mainly for models with discrete probability distributions. On the other, fairly little is known on structure, and, more so, on stability of models in general settings. This is somewhat unsatisfactory since, quite often, models with discrete distributions arise from approximations of general models. Then it would be good to have some safeguards that solutions to approximate problems stay close to the solutions of the original one.
Kuchler's paper contributes to milden this discrepancy. The main result identifies sufficient conditions for the Lipschitz continuity of optimal values if the underlying stochastic data processes are subjected to perturbations. Some of the preparatory results, on Lipschitz continuity of recourse functions and calmness of optimal solutions, are substantial on their own.
The paper shows a remarkable analytical mastership. Profound knowledge of optimization and probability theory meets technical maturity in handling non-trivial estimates and recursions. Finding the "right" concepts is another strength of the paper. This concerns assumptions, which are strong enough for the desired conclusions but stay sufficiently general to include relevant problem classes.
The paper is very well written. Despite the inevitable technical complexity of the topic the reader is never left alone. Coming investigations are skillfully motivated. Indispensability of assumptions and their role in related research are carefully discussed. With competence, concepts and results of the paper are put into perspective with the existing literature.Prize Committee: Alan King (chair), Ruediger Schultz, and Güzin Bayraksan