Distributionally robust views on queues and related stochastic models

This dissertation explores distribution-free methods for stochastic models. Traditional approaches operate on the premise of complete knowledge about the probability distributions of the underlying random variables that govern these models. In contrast, this work adopts a distribution-free perspective, assuming only partial knowledge of these distributions, often limited to generalized moment information. Distributionally robust analysis seeks to determine the worst-case model performance. It involves optimization over a set of probability distributions that comply with this partial information, a task tantamount to solving a semiinfinite linear program. To address such an optimization problem, a solution approach based on the concept of weak duality is used. Through the proposed weak-duality argument, distribution-free bounds are derived for a wide range of stochastic models. Further, these bounds are applied to various distributionally robust stochastic programs and used to analyze extremal queueing models—central themes in applied probability and mathematical optimization.

-

In dit proefschrift behandelen we verdelingsvrije methoden voor stochastische modellen. De traditionele benadering voor deze modellen gaat vaak uit van volledige informatie met betrekking tot de kansverdelingen van de betreffende stochasten. In dit proefschrift wordt echter een verdelingsvrije benadering gehanteerd door slechts gedeeltelijke kennis over deze verdelingen
te veronderstellen, vaak beperkt tot informatie betreffende de momenten van de toevalsvariabelen. Verdelingsvrije analyse zoekt dan naar de slechtst mogelijke modelprestaties door te optimaliseren over een verzameling van kansverdelingen die voldoen aan deze gedeeltelijke informatie. Dit vereist vervolgens het oplossen van semi-oneindige optimaliseringsproblemen
met behulp van dualiteitstheorie. We streven ernaar in dit proefschrift een verband te leggen tussen het onderzoek naar gegeneraliseerde
momentproblemen, kansverdelingsvrije stochastische optimaliseringsproblemen en worst-case wachtrijmodellen, drie veel voorkomende onderzoeksrichtingen in de literatuur over toegepaste kansrekening en optimalisatie. We gebruiken methoden uit de literatuur over gegeneraliseerde momentproblemen om nieuwe verdelingsvrije begrenzingen af te leiden, die vervolgens gebruikt kunnen worden voor het oplossen van stochastische optimaliseringsproblemen en het uitvoeren van worst-case analyse op wachtrijmodellen. Een van de belangrijkste
bijdragen die dit proefschrift benadrukt, is het gebruik van semi-oneindige lineaire optimaliseringsproblemen en dualiteitstechnieken om scherpe (oftewel, optiale) grenzen vast te stellen voor de verdelingsvrije analyse en optimalisatie van stochastische modellen. Dit proefschrift belicht verder specifieke combinaties van doelfuncties en gedeeltelijke informatie die worst-case
kansverdelingen opleveren welke, in zekere zin, ongevoelig zijn voor de precieze stochastische modeldynamiek van het probleem, wat de analyse aanzienlijk vereenvoudigt. Dit proefschrift behandelt bovenstaande bijdragen aan de hand van diverse toepassingen, die zijn verdeeld over de verschillende hoofdstukken. In hoofdstuk 2 onderzoeken we het worstcase wachtrijprobleem en richten we ons op de slechtst mogelijke prestaties van de GI/G/1 wachtrij onder gemiddelde- en dispersiebeperkingen voor de tussenaankomst- en servicetijdverdelingen.
We gebruiken de gemiddelde absolute afwijking van het gemiddelde als de dispersiemaat in plaats van de, meer gangbare, variantie. Onze belangrijkste observatie is dat de verwachte wachttijd kan worden uitgedrukt als een componentgewijze convexe functie van toevalsvariabelen, wat ons in staat stelt om bekende begrenzingen te gebruiken voor de analyse van de GI/G/1 wachtrij. Deze benadering maakt gebruik van de ongevoeligheidseigenschap van de worst-case kansverdeling, en levert scherpe boven- en ondergrenzen op voor de momenten Distributionally robust views on stochastic models van de wachttijd, die, zelfs onder de onafhankelijkheidsaanname (welke verdelingsvrije analyse
normaal gesproken aanzienlijk lastiger maakt), valide zijn. In hoofdstuk 3 beschouwen we een M/M/𝑠 wachtrij me variantie en bereik. We stellen scherpe grenzen vast voor de verwachte wachttijd door een worst-case verdeling vast te stellen die ondersteund wordt op twee punten. De wiskundige bewijzen in dit hoofdstuk maken gebruik van de convexe afgeleide van de verwachte wachttijd
als functie van de aankomstintensiteit. Deze grenzen kunnen worden toegepast op de rationele wachtrijtheorie, waarbij klanten beslissen of ze wel of niet in de wachtrij gaan staan gebaseerd op het verwachte nut hiervan en de beperkte kennis over de totale marktomvang. In hoofdstuk 4 introduceren we nieuwe grenzen voor de staartkans van toevalsvariabelen met een bekend bereik, gemiddelde en gemiddelde absolute afwijking. Deze grenzen zijn opnieuw het resultaat van het oplossen van semi-oneindige lineaire optimaliseringsproblemen met behulp van zwakke dualiteit. In hoofdstuk 5 behandelen we begrenzingen voor conditionele verwachtingen die gebaseerd zijn op momentinformatie en waargenomen stochastische gebeurtenissen.
We herformuleren dit probleem als een semi-oneindig lineair 0ptimaliseringsprobleem, wat ons in staat stelt om scherpe grenzen af te leiden voor conditionele verwachtingen met behulp van de dualiteitstheorie voor gegeneraliseerde momentproblemen. In hoofdstuk 6 kijken we naar het multi-item newsvendor probleem met een beperkt budget, waarbij we de eerder
vervaardigde grenzen benutten om het optimaliseringsprobleem te vereenvoudigen. Door dit probleem te reduceren tot een stochastisch optimaliseringsprobleem met een zeer eenvoudige structuur, kunnen we een effici¨ent algoritme formuleren om optimale bestelhoeveelheden te vinden. In hoofdstuk 7 bespreken we het optimaal plannen van afspraken met behulp van
verdelingsvrije analysetechnieken. Het doel is om de kosten onder de slechtst mogelijke omstandigheden te minimaliseren. We pakken de uitdagingen aan die voortkomen uit de aanname van onafhankelijkheid met behulp van verdelingsvrije methoden die vergelijkbaar zijn met die uit hoofdstuk 2 voor de GI/G/1 wachtrij. In hoofdstuk 8 sluiten we het proefschrift af door klassen van functies en informatie te verkennen die de ongevoeligheidseigenschap opleveren.
Tevens beschrijven we mogelijke toekomstige onderzoeksrichtingen voor de ontwikkeling van een breder theoretisch raamwerk voor de verdelingsvrije analyse van stochastische modellen met onafhankelijke toevalsvariabelen.