A Geometrical Analysis of a Class of Nonconvex Conic Programs for Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems

We present a geometrical analysis on the completely positive programming reformulation of quadratic optimization problems and its extension to polynomial optimization problems with a class of geometrically defined nonconvex conic programs and their covexification. The class of nonconvex conic programs is described with a linear objective function in a linear space $V$, and the constraint … Read more

Distributionally Robust Optimization with Confidence Bands for Probability Density Functions

Distributionally robust optimization (DRO) has been introduced for solving stochastic programs where the distribution of the random parameters is unknown and must be estimated by samples from that distribution. A key element of DRO is the construction of the ambiguity set, which is a set of distributions that covers the true distribution with a high … Read more

Intersection disjunctions for reverse convex sets

We present a framework to obtain valid inequalities for optimization problems constrained by a reverse convex set, which is defined as the set of points in a polyhedron that lie outside a given open convex set. We are particularly interested in cases where the closure of the convex set is either non-polyhedral, or is defined … Read more

Local minimizers of semi-algebraic functions

Consider a semi-algebraic function $f\colon\mathbb{R}^n \to {\mathbb{R}},$ which is continuous around a point $\bar{x} \in \mathbb{R}^n.$ Using the so–called {\em tangency variety} of $f$ at $\bar{x},$ we first provide necessary and sufficient conditions for $\bar{x}$ to be a local minimizer of $f,$ and then in the case where $\bar{x}$ is an isolated local minimizer of … Read more

Composite optimization for robust blind deconvolution

The blind deconvolution problem seeks to recover a pair of vectors from a set of rank one bilinear measurements. We consider a natural nonsmooth formulation of the problem and show that under standard statistical assumptions, its moduli of weak convexity, sharpness, and Lipschitz continuity are all dimension independent. This phenomenon persists even when up to … Read more

Constrained Assortment Optimization under the Paired Combinatorial Logit Model

We study the assortment optimization problem when customer choices are governed by the paired combinatorial logit model. We study unconstrained, capacitated and knapsack constrained versions of this problem, which are all known to be NP-hard. We design efficient algorithms that compute approximately optimal solutions, using a novel relation to the maximum directed cut problem and … Read more

A Tutorial on Formulating and Using QUBO Models

The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become … Read more

Interdiction of a Mixed-Integer Linear System

A system-interdiction problem can be modeled as a bilevel program in which the upper level models interdiction decisions and the lower level models system operation. This paper studies MILSIP, a mixed-integer linear system interdiction problem, which assumes binary interdiction decisions and models system operations through a mixed-integer linear program. To solve large-scale instances of MILSIP, … Read more

Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization

In this paper we propose a splitting scheme which hybridizes generalized conditional gradient with a proximal step which we call CGALP algorithm, for minimizing the sum of three proper convex and lower-semicontinuous functions in real Hilbert spaces. The minimization is subject to an affine constraint, that allows in particular to deal with composite problems (sum … Read more

Pricing in Multi-Interval Real-Time Markets

This paper examines multi-interval real-time markets in the context of US independent system operators (ISOs). We show that current ISO implementations that settle only the upcoming interval of the multi-interval solution can create incentive problems. Fundamentally, this is the result of each successive optimization problem treating historical losses as sunk costs. To solve the incentive … Read more