Optimal stopping problems, commonly encountered in financial mathematics, involve determining the most opportune time to execute an action (e.g., exercising an option) to maximize expected returns. We introduce the dual problem associated to an optimal stopping problem by way of a perturbation function. We give an intuitive interpretation of the dual problem as well as the role it plays in practice.

This presentation considers chance-constrained stochastic problems (CCSPs) with finite support. We present an iterative algorithm that solves a reduced size chance-constrained model. This reduced model is obtained by partitioning the scenario set and, when solved to optimality, yields a bound on the optimal objective value of the original CCSP. Moreover, the algorithm ensures finite termination at an optimal solution of the original CCSP. At the heart of the algorithm lie two fundamental operations: refinement and merging. Refinement involves splitting a subset of the partition, while merging combines two subsets. These operations are executed to enhance the bound obtained in each step of the algorithm while minimally increasing the size of the reduced model to be solved. Under mild conditions, we prove that, for specific refinement and merge operations, the bound obtained after solving each reduced model strictly improves throughout the iterative process. Furthermore, the algorithm structure allows for the seamless integration of various computational enhancements, significantly reducing the computational time required to solve the reduced chance-constrained problems. Based on theoretical arguments we also provide strategies to initialize the partition considered in the algorithm. The efficiency of the algorithm is assessed through numerical experiments. We study the impact of every component of the algorithm and compare its performance against state-of-the-art methods on chance constrained multidimensional knapsack problems.

This work investigates the Assortment Optimization Problem under the Multinomial Logit choice model in scenarios where the firm does not know the attractiveness factors associated with each product. In our model, the firm relies on exogenous data consisting of the assortments offered by other firms and random variables defining a set of conversion rates, which are multiplicative factors indicating how the products' attractiveness adopted in the external assortments differ from the respective values for the firm. The notion of optimality is nuanced in this model, so we focus on identifying consistent assortments in the sense that the assortment decisions made by the firm should not conflict with exogenous data. We investigate the structural properties and different solution techniques for the problem based on assumptions about the conversion rates. We show that the expectation-based deterministic formulation of the problem can be solved efficiently. We also study some probabilistic-constrained formulations where such problems can be recast as second-order cone programs assuming the conversion rates are normally distributed. Our results show that the model does not require unrealistically large amounts of exogenous data to deliver accurate results, thus providing evidence that our framework can be adopted in practice.

We show that risk-constrained functional optimization problems with general integrable nonconvex instantaneous reward/constraint functions exhibit strong duality, regardless of nonconvexity. We consider risk constraints featuring convex and positively homogeneous risk measures admitting dual representations with bounded risk envelopes, generalizing expectations. Popular risk measures supported within our setting include the conditional value-at-risk (CVaR), the mean-absolute deviation (MAD, including the non-monotone case), certain distributionally robust representations and more generally all real-valued coherent risk measures on the space L1. We highlight the usefulness of our results by further discussing various generalizations of our base model, extensions for risk measures supported on Lp for p>1, implications in the context of mean-risk tradeoff models, as well as more specific applications in wireless systems resource allocation, and supervised constrained learning. Our core proof technique appears to be new and relies on risk conjugate duality in tandem with J. J. Uhl's weak extension of A. A. Lyapunov's convexity theorem for vector measures taking values in general infinite-dimensional Banach spaces.

For more information, please have a look at our full and detailed preprint available on arXiv through the link: https://arxiv.org/pdf/2206.11948.pdf