Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens

A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this paper, we first revisit basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we … Read more

The Generalized Trust Region Subproblem: solution complexity and convex hull results

We consider the Generalized Trust Region Subproblem (GTRS) of minimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. A lifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this … Read more

Risk Guarantees for End-to-End Prediction and Optimization Processes

Prediction models are often employed in estimating parameters of optimization models. Despite the fact that in an \emph{end-to-end} view, the real goal is to achieve good optimization performance, the prediction performance is measured on its own. While it is usually believed that good prediction performance in estimating the parameters will result in good subsequent optimization … Read more

Dynamic Data-Driven Estimation of Non-Parametric Choice Models

We study non-parametric estimation of choice models, which was introduced to alleviate unreasonable assumptions in traditional parametric models, and are prevalent in several application areas. Existing literature focuses only on the static observational setting where all of the observations are given upfront, and lacks algorithms that provide explicit convergence rate guarantees or an a priori … Read more

On Intersection of Two Mixing Sets with Applications to Joint Chance-Constrained Programs

We study the polyhedral structure of a generalization of a mixing set described by the intersection of two mixing sets with two shared continuous variables, where one continuous variable has a positive coefficient in one mixing set, and a negative coefficient in the other. Our developments are motivated from a key substructure of linear joint … Read more

Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization

In this paper, we consider two paradigms that are developed to account for uncertainty in optimization models: robust optimization (RO) and joint estimation-optimization (JEO). We examine recent developments on efficient and scalable iterative first-order methods for these problems, and show that these iterative methods can be viewed through the lens of online convex optimization (OCO). … Read more

Online First-Order Framework for Robust Convex Optimization

Robust optimization (RO) has emerged as one of the leading paradigms to efficiently model parameter uncertainty. The recent connections between RO and problems in statistics and machine learning domains demand for solving RO problems in ever more larger scale. However, the traditional approaches for solving RO formulations based on building and solving robust counterparts or … Read more

Low-Complexity Relaxations and Convex Hulls of Disjunctions on the Positive Semidefinite Cone and General Regular Cones

In this paper we analyze general two-term disjunctions on a regular cone $\K$ and derive a general form for a family of convex inequalities which are valid for the resulting nonconvex sets. Under mild technical assumptions, these inequalities collectively describe the closed convex hulls of these disjunctions, and if additional conditions are satisfied, a single … Read more

A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants

We study the trust region subproblem (TRS) of minimizing a nonconvex quadratic function over the unit ball with additional conic constraints. Despite having a nonconvex objective, it is known that the TRS and a number of its variants are polynomial-time solvable. In this paper, we follow a second-order cone based approach to derive an exact … Read more

On Sublinear Inequalities for Mixed Integer Conic Programs

This paper studies $K$-sublinear inequalities, a class of inequalities with strong relations to K-minimal inequalities for disjunctive conic sets. We establish a stronger result on the sufficiency of $K$-sublinear inequalities. That is, we show that when $K$ is the nonnegative orthant or the second-order cone, $K$-sublinear inequalities together with the original conic constraint are always … Read more