An official website of the United States government
In this work, we consider two-stage quadratic optimization problems under ellipsoidal uncertainty. In the first stage, one needs to decide upon the values of a subset of optimization variables (control variables). In the second stage, the uncertainty is revealed, and the rest of the optimization variables (state variables) are set up as a solution to a known system of possibly nonlinear equations. This type of problem occurs, for instance, in optimization for dynamical systems, such as electric power systems as well as gas and water networks. We propose a convergent iterative algorithm to build a sequence of approximately robustly feasible solutions with an improving objective value. At each iteration, the algorithm optimizes over a subset of the feasible set and uses affine approximations of the second-stage equations while preserving the nonlinearity of other constraints. We implement our approach and demonstrate its performance on Matpower instances of AC optimal power flow. Although this paper focuses on quadratic problems, the approach is suitable for more general setups.
more »
« less
This content will become publicly available on April 1, 2026
The Benefit of Uncertainty Coupling in Robust and Adaptive Robust Optimization
Despite the modeling power for problems under uncertainty, robust optimization (RO) and adaptive RO (ARO) can exhibit too conservative solutions in terms of objective value degradation compared with the nominal case. One of the main reasons behind this conservatism is that, in many practical applications, uncertain constraints are directly designed as constraint-wise without taking into account couplings over multiple constraints. In this paper, we define a coupled uncertainty set as the intersection between a constraint-wise uncertainty set and a coupling set. We study the benefit of coupling in alleviating conservatism in RO and ARO. We provide theoretical tight and computable upper and lower bounds on the objective value improvement of RO and ARO problems under coupled uncertainty over constraint-wise uncertainty. In addition, we relate the power of adaptability over static solutions with the coupling of uncertainty set. Computational results demonstrate the benefit of coupling in applications. Funding: I. Wang was supported by the NSF CAREER Award [ECCS 2239771] and Wallace Memorial Honorific Fellowship from Princeton University. B. Stellato was supported by the NSF CAREER Award [ECCS 2239771].
more »
« less
- Award ID(s):
- 2239771
- PAR ID:
- 10595308
- Publisher / Repository:
- INFORMS
- Date Published:
- Journal Name:
- INFORMS Journal on Optimization
- Volume:
- 7
- Issue:
- 2
- ISSN:
- 2575-1484
- Page Range / eLocation ID:
- 105 to 141
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We provide a processed JSON version of the 3234 page PDF document of Anthony Fauci's emails that were released in 2021 to provide a better understanding of the United States government response to the COVID-19 pandemic. The main JSON file contains a collection of 1289 email threads with 2761 emails among the threads, which includes 101 duplicate emails. For each email, we provide information about the sender, recipients, CC-list, subject, email body text, and email time stamp (when available). We also provide a number of derived datasets stored in individual JSON files: 5 different types of derived email networks, 1 email hypergraph, 1 temporal graph, and 3 tensors. Details for the data conversion process, the construction of the derived datasets, and subsequent analyses can all be found in an online technical report at https://arxiv.org/abs/2108.01239. Updated code for processing and analyzing the data can be found at https://github.com/nveldt/fauci-email.</p> Research additionally supported by ARO Award W911NF-19-1-0057, ARO MURI, and NSF CAREER Award IIS-2045555, as well as NSF awards CCF-1909528, IIS-2007481, and the Sloan Foundation.more » « less
-
Adjustable robust optimization (ARO) involves recourse decisions (i.e. reactive actions after the realization of the uncertainty, ‘wait-and-see’) as functions of the uncertainty, typically posed in a two-stage stochastic setting. Solving the general ARO problems is challenging, therefore ways to reduce the computational effort have been proposed, with the most popular being the affine decision rules, where ‘wait-and-see’ decisions are approximated as affine adjustments of the uncertainty. In this work we propose a novel method for the derivation of generalized affine decision rules for linear mixed-integer ARO problems through multi-parametric programming, that lead to the exact and global solution of the ARO problem. The problem is treated as a multi-level programming problem and it is then solved using a novel algorithm for the exact and global solution of multi-level mixed-integer linear programming problems. The main idea behind the proposed approach is to solve the lower optimization level of the ARO problem parametrically, by considering ‘here-and-now’ variables and uncertainties as parameters. This will result in a set of affine decision rules for the ‘wait-and-see’ variables as a function of ‘here-and-now’ variables and uncertainties for their entire feasible space. A set of illustrative numerical examples are provided to demonstrate the potential of the proposed novel approach.more » « less
-
A stochastic algorithm is proposed, analyzed, and tested experimentally for solving continuous optimization problems with nonlinear equality constraints. It is assumed that constraint function and derivative values can be computed but that only stochastic approximations are available for the objective function and its derivatives. The algorithm is of the sequential quadratic optimization variety. Distinguishing features of the algorithm are that it only employs stochastic objective gradient estimates that satisfy a relatively weak set of assumptions (while using neither objective function values nor estimates of them) and that it allows inexact subproblem solutions to be employed, the latter of which is particularly useful in large-scale settings when the matrices defining the subproblems are too large to form and/or factorize. Conditions are imposed on the inexact subproblem solutions that account for the fact that only stochastic objective gradient estimates are employed. Convergence results are established for the method. Numerical experiments show that the proposed method vastly outperforms a stochastic subgradient method and can outperform an alternative sequential quadratic programming algorithm that employs highly accurate subproblem solutions in every iteration. Funding: This material is based upon work supported by the National Science Foundation [Awards CCF-1740796 and CCF-2139735] and the Office of Naval Research [Award N00014-21-1-2532].more » « less
-
In this paper, we consider a personalized assortment planning problem under inventory constraints, where each arriving customer type is defined by a primary item of interest. As long as that item is in stock, the customer adds it to the shopping cart, at which point the retailer can recommend to the customer an assortment of add-ons to go along with the primary item. This problem is motivated by the new “recommendation at checkout” systems that have been deployed at many online retailers, and it also serves as a framework that unifies many existing problems in online algorithms (e.g., personalized assortment planning, single-leg booking, and online matching with stochastic rewards). In our problem, add-on recommendation opportunities are eluded when primary items go out of stock, which poses additional challenges for the development of an online policy. We overcome these challenges by introducing the notion of an inventory protection level in expectation and derive an algorithm with a 1/4-competitive ratio guarantee under adversarial arrivals. Funding: This work was supported by the Adobe Data Science Research Award and the Alibaba Innovation Research Award. L. Xin was partly supported by the National Science Foundation (NSF) [Award CMMI-1635160], X. Chen was supported by the NSF [CAREER Award IIS-1845444]. W. Ma and D. Simchi-Levi were supported by the Accenture and MIT Alliance in Business Analytics.more » « less
