Search for: All records

We study the problem of finding the Löwner–John ellipsoid (i.e., an ellipsoid with minimum volume that contains a given convex set). We reformulate the problem as a generalized copositive program and use that reformulation to derive tractable semidefinite programming approximations for instances where the set is defined by affine and quadratic inequalities. We prove that, when the underlying set is a polytope, our method never provides an ellipsoid of higher volume than the one obtained by scaling the maximum volume-inscribed ellipsoid. We empirically demonstrate that our proposed method generates high-quality solutions and can be solved much faster than solving the problem to optimality. Furthermore, we outperform the existing approximation schemes in terms of solution time and quality. We present applications of our method to obtain piecewise linear decision rule approximations for dynamic distributionally robust problems with random recourse and to generate ellipsoidal approximations for the set of reachable states in a linear dynamical system when the set of allowed controls is a polytope. 

We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S-lemma method—which is valid only in the case of continuous uncertainty—is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems. 

In this paper, we consider the problem of operating a battery storage unit in a home with a rooftop solar photovoltaic (PV) system so as to minimize expected long-run electricity costs under uncertain electricity usage, PV generation, and electricity prices. Solving this dynamic program using standard techniques is computationally burdensome, and is often complicated by the difficulty of estimating conditional distributions from sparse data. To overcome these challenges, we implement a data-driven dynamic programming (DDP) algorithm that uses historical data observations to generate empirical conditional distributions and approximate the cost-to-go function. Then, we formulate two robust data-driven dynamic programming (RDDP) algorithms that consider the worst-case expected cost over a set of conditional distributions centered at the empirical distribution, and within a given Chi-square or Wasserstein distance, respectively. We test our algorithms using data from homes with rooftop PV in Austin, Texas. Numerical results reveal that DDP and RDDP outperform common existing methods with acceptable computational effort. Finally, we show that implementation of these superior operational algorithms significantly raises the break-even battery cost under which a homeowner is incentivized to invest in a residential battery rather than participate in a feed-in tariff or net energy metering program.