A sampling-and-discarding approach to chance-constrained optimization: feasibility and Optimality

DOI10.1007/s10957-010-9754-6zbMath1211.90146OpenAlexW2066778083MaRDI QIDQ535064

Simone Garatti, Marco C. Campi

Publication date: 11 May 2011

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10957-010-9754-6

zbMATH Keywords

stochastic optimizationconvex optimizationrandomized methodschance-constrained optimizationsample-based optimization

Mathematics Subject Classification ID

Convex programming (90C25) Stochastic programming (90C15)

Related Items

Robust Control for Dynamical Systems with Non-Gaussian Noise via Formal Abstractions ⋮ Scenario-Based Verification of Uncertain MDPs ⋮ Chance-constrained problems and rare events: an importance sampling approach ⋮ Decomposition algorithms for two-stage chance-constrained programs ⋮ Scenario Min-Max Optimization and the Risk of Empirical Costs ⋮ Probabilistic optimization via approximate \(p\)-efficient points and bundle methods ⋮ A stochastic primal-dual method for a class of nonconvex constrained optimization ⋮ FAST—Fast Algorithm for the Scenario Technique ⋮ General Feasibility Bounds for Sample Average Approximation via Vapnik--Chervonenkis Dimension ⋮ Chance-Constrained Binary Packing Problems ⋮ Stochastic MPC with offline uncertainty sampling ⋮ Derivatives of probability functions: unions of polyhedra and elliptical distributions ⋮ A polyhedral study on chance constrained program with random right-hand side ⋮ Probability maximization via Minkowski functionals: convex representations and tractable resolution ⋮ Virtual reference feedback tuning for linear discrete-time systems with robust stability guarantees based on set membership ⋮ A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support ⋮ Risk-return trade-off with the scenario approach in practice: a case study in portfolio selection ⋮ An Inner-Outer Approximation Approach to Chance Constrained Optimization ⋮ Conditional scenario-based model predictive control ⋮ Chance-constrained optimization under limited distributional information: a review of reformulations based on sampling and distributional robustness ⋮ Probabilistic feasibility guarantees for convex scenario programs with an arbitrary number of discarded constraints ⋮ Learning stability guarantees for constrained switching linear systems from noisy observations ⋮ A distributionally robust optimization approach for two-stage facility location problems ⋮ Approximate methods for solving chance-constrained linear programs in probability measure space ⋮ On the sample size of random convex programs with structured dependence on the uncertainty ⋮ On Conditional Risk Assessments in Scenario Optimization ⋮ A limited-memory BFGS-based differential evolution algorithm for optimal control of nonlinear systems with mixed control variables and probability constraints ⋮ Stochastic self-triggered MPC for linear constrained systems under additive uncertainty and chance constraints ⋮ Consistency of the Scenario Approach ⋮ Optimal control of nonlinear systems with integer‐valued control inputs and stochastic constraints ⋮ Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints ⋮ Random sampling with removal ⋮ A polyhedral study of the static probabilistic lot-sizing problem ⋮ A constraint sampling approach for multi-stage robust optimization ⋮ Stochastic model predictive control with adaptive constraint tightening for non-conservative chance constraints satisfaction ⋮ Model reduction of switched affine systems ⋮ Robust control of uncertain systems: classical results and recent developments ⋮ Performance assessment and design of abstracted models for stochastic hybrid systems through a randomized approach ⋮ Sampling-Based Verification of CTMCs with Uncertain Rates ⋮ Calibration of a radiation quality model for sparse and uncertain data ⋮ Trading performance for state constraint feasibility in stochastic constrained control: a randomized approach ⋮ A polynomial approximation-based approach for chance-constrained optimization ⋮ Wait-and-judge scenario optimization ⋮ Automated driving: the role of forecasts and uncertainty -- a control perspective ⋮ Expected shortfall: heuristics and certificates ⋮ The decision rule approach to optimization under uncertainty: methodology and applications ⋮ Learning noisy functions via interval models ⋮ Research on probabilistic methods for control system design ⋮ Bi-objective autonomous vehicle repositioning problem with travel time uncertainty ⋮ On the quantification of aleatory and epistemic uncertainty using sliced-normal distributions ⋮ IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation ⋮ Optimal disturbance compensation for constrained linear systems operating in stationary conditions: a scenario-based approach ⋮ On a class of interval predictor models with universal reliability ⋮ Analytic approximation and differentiability of joint chance constraints ⋮ Approximate convex hull based scenario truncation for chance constrained trajectory optimization ⋮ General properties of two-stage stochastic programming problems with probabilistic criteria ⋮ Varying confidence levels for CVaR risk measures and minimax limits ⋮ Branch-and-cut approaches for chance-constrained formulations of reliable network design problems ⋮ Random variables with moment-matching staircase density functions ⋮ A randomized relaxation method to ensure feasibility in stochastic control of linear systems subject to state and input constraints ⋮ Frequentist history matching with interval predictor models ⋮ Partial sample average approximation method for chance constrained problems ⋮ A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs ⋮ Generalized Differentiation of Probability Functions Acting on an Infinite System of Constraints ⋮ A theory of the risk for empirical CVaR with application to portfolio selection ⋮ Chance-constrained sets approximation: a probabilistic scaling approach ⋮ Data-driven tuning for chance constrained optimization: analysis and extensions ⋮ Distributionally robust chance-constrained programs with right-hand side uncertainty under Wasserstein ambiguity ⋮ The scenario approach for stochastic model predictive control with bounds on closed-loop constraint violations ⋮ Randomized methods for design of uncertain systems: sample complexity and sequential algorithms ⋮ Advances and applications of chance-constrained approaches to systems optimisation under uncertainty ⋮ Generalized differentiation of probability functions: parameter dependent sets given by intersections of convex sets and complements of convex sets ⋮ A linear programming approach for linear programs with probabilistic constraints ⋮ Risk and complexity in scenario optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dual methods for probabilistic optimization problems.
• An integer programming approach for linear programs with probabilistic constraints
• Convexity of chance constraints with independent random variables
• Relaxations for probabilistically constrained programs with discrete random variables
• Worst-case properties of the uniform distribution and randomized algorithms for robustness analysis
• Probabilistic robustness analysis: Explicit bounds for the minimum number of samples
• Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra
• Probabilistic design of LPV control systems.
• Metric regularity and quantitative stability in stochastic programs with probabilistic constraints.
• Robust solutions of linear programming problems contaminated with uncertain data
• Randomized algorithms for analysis and control of uncertain systems. With a foreword by M. Vidyasagar
• Uncertain convex programs: randomized solutions and confidence levels
• Robust optimization-methodology and applications
• On convex probabilistic programming with discrete distributions.
• Randomized algorithms for quadratic stability of quantized sampled-data systems
• Hölder and Lipschitz stability of solution sets in programs with probabilistic constraints
• A stochastic approach to stability in stochastic programming
• On geometric optimization with few violated constraints
• Ambiguous chance constrained problems and robust optimization
• Randomized algorithms for probabilistic robustness with real and complex structured uncertainty
• Statistical Learning Theory: A Pack-based Strategy for Uncertain Feasibility and Optimization Problems
• Sharp Bounds on Probabilities Using Linear Programming
• The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
• A Sample Approximation Approach for Optimization with Probabilistic Constraints
• The Price of Robustness
• Lectures on Stochastic Programming
• Monte Carlo sampling approach to stochastic programming
• A branch and bound method for stochastic integer problems under probabilistic constraints
• Randomized Strategies for Probabilistic Solutions of Uncertain Feasibility and Optimization Problems
• Contributions to the theory of stochastic programming
• Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution
• The Scenario Approach to Robust Control Design
• Chance Constrained Programming with Joint Constraints
• Convex Approximations of Chance Constrained Programs
• On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
• Concavity and efficient points of discrete distributions in probabilistic programming.
• Probabilistic robust design with linear quadratic regulators