More Like this

1. Optimal stopping with expectation constraints

   https://doi.org/10.1214/23-AAP1980  

   Bayraktar, Erhan; Yao, Song (February 2024, The Annals of Applied Probability)

   We analyze an optimal stopping problem with a series of inequality-type and equality-type expectation constraints in a general non-Markovian framework. We show that the optimal stopping problem with expectation constraints (OSEC) in an arbitrary probability setting is equivalent to the constrained problem in weak formulation (an optimization over joint laws of stopping rules with Brownian motion and state dynamics on an enlarged canonical space), and thus the OSEC value is independent of a specific probabilistic setup. Using a martingale-problem formulation, we make an equivalent characterization of the probability classes in weak formulation, which implies that the OSEC value function is upper semianalytic. Then we exploit a measurable selection argument to establish a dynamic programming principle in weak formulation for the OSEC value function, in which the conditional expected costs act as additional states for constraint levels at the intermediate horizon. 

   more » « less
2. A Framework for the Dynamic Programming Principle and Martingale-Generated Control Correspondences

   https://doi.org/10.1007/s00245-019-09589-8  

   Fayvisovich, Roman; Žitković, Gordan (June 2019, Applied Mathematics & Optimization)

   We construct an abstract framework in which the dynamic programming principle (DPP) can be readily proven. It encompasses a broad range of common stochastic control problems in the weak formulation, and deals with problems in the “martingale formulation” with particular ease. We give two illustrations; first, we establish the DPP for general controlled diffusions and show that their value functions are viscosity solutions of the associated Hamilton–Jacobi–Bellman equations under minimal conditions. After that, we show how to treat singular control on the example of the classical monotone-follower problem. 

   more » « less
3. An Overview of Uncertain Control Co-Design Formulations

   https://doi.org/10.1115/1.4062753  

   Azad, Saeed; Herber, Daniel R. (September 2023, Journal of Mechanical Design)

   This article explores various uncertain control co-design (UCCD) problem formulations. While previous work offers formulations that are method-dependent and limited to only a handful of uncertainties (often from one discipline), effective application of UCCD to real-world dynamic systems requires a thorough understanding of uncertainties and how their impact can be captured. Since the first step is defining the UCCD problem of interest, this article aims at addressing some of the limitations of the current literature by identifying possible sources of uncertainties in a general UCCD context and then formalizing ways in which their impact is captured through problem formulation alone (without having to immediately resort to specific solution strategies). We first develop and then discuss a generalized UCCD formulation that can capture uncertainty representations presented in this article. Issues such as the treatment of the objective function, the challenge of the analysis-type equality constraints, and various formulations for inequality constraints are discussed. Then, more specialized problem formulations such as stochastic in expectation, stochastic chance-constrained, probabilistic robust, worst-case robust, fuzzy expected value, and possibilistic chance-constrained UCCD formulations are presented. Key concepts from these formulations, along with insights from closely-related fields, such as robust and stochastic control theory, are discussed, and future research directions are identified. 

   more » « less
4. Optimal Secure Control with Linear Temporal Logic Constraints

   Niu, L; Clark, A (July 2019, IEEE transactions on automatic control)

   Prior work on automatic control synthesis for cyberphysical systems under logical constraints has primarily focused on environmental disturbances or modeling uncertainties, however, the impact of deliberate and malicious attacks has been less studied. In this paper, we consider a discrete-time dynamical system with a linear temporal logic (LTL) constraint in the presence of an adversary, which is modeled as a stochastic game. We assume that the adversary observes the control policy before choosing an attack strategy. We investigate two problems. In the first problem, we synthesize a robust control policy for the stochastic game that maximizes the probability of satisfying the LTL constraint. A value iteration based algorithm is proposed to compute the optimal control policy. In the second problem, we focus on a subclass of LTL constraints, which consist of an arbitrary LTL formula and an invariant constraint. We then investigate the problem of computing a control policy that minimizes the expected number of invariant constraint violations while maximizing the probability of satisfying the arbitrary LTL constraint. We characterize the optimality condition for the desired control policy. A policy iteration based algorithm is proposed to compute the control policy. We illustrate the proposed approaches using two numerical case studies. 

   more » « less
5. Probing to Minimize

   https://doi.org/10.4230/LIPIcs.ITCS.2022.120  

   Wang, Weina; Gupta, Anupam; Williams, Jalani K. (January 2022, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022))

   Braverman, Mark (Ed.)

   We develop approximation algorithms for set-selection problems with deterministic constraints, but random objective values, i.e., stochastic probing problems. When the goal is to maximize the objective, approximation algorithms for probing problems are well-studied. On the other hand, few techniques are known for minimizing the objective, especially in the adaptive setting, where information about the random objective is revealed during the set-selection process and allowed to influence it. For minimization problems in particular, incorporating adaptivity can have a considerable effect on performance. In this work, we seek approximation algorithms that compare well to the optimal adaptive policy. We develop new techniques for adaptive minimization, applying them to a few problems of interest. The core technique we develop here is an approximate reduction from an adaptive expectation minimization problem to a set of adaptive probability minimization problems which we call threshold problems. By providing near-optimal solutions to these threshold problems, we obtain bicriteria adaptive policies. We apply this method to obtain an adaptive approximation algorithm for the Min-Element problem, where the goal is to adaptively pick random variables to minimize the expected minimum value seen among them, subject to a knapsack constraint. This partially resolves an open problem raised in [Goel et al., 2010]. We further consider three extensions on the Min-Element problem, where our objective is the sum of the smallest k element-weights, or the weight of the min-weight basis of a given matroid, or where the constraint is not given by a knapsack but by a matroid constraint. For all three of the variations we explore, we develop adaptive approximation algorithms for their corresponding threshold problems, and prove their near-optimality via coupling arguments. 

   more » « less