In this paper we extend the algorithm and several results published in the celebrated 1959 paper of Cheney and Goldstein about the best approximation pair (BAP) problem in two separate directions. One is the consideration of more than two sets. The other is the ability to handle each set as an intersections of a finite … Read more
We study the convergence rate of the moment-SOS (sum-of-squares) hierarchy for polynomial optimization problems (POPs) on a bounded subset of the real line described by arbitrary polynomial inequalities. We prove that, for every fixed univariate POP, the relaxation error is bounded by $O(1/r^2)$, where $r$ is the relaxation order. In particular, boundary degeneracies in the … Read more
We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in the size of the instance and in 1/epsilon, provided that the number of integer variables and the number of negative eigenvalues of the Hessian of the objective … Read more
We study tight conic relaxations for a quadratically constrained quadratic programming (QCQP) formulation of rank-one doubly nonnegative (DNN) matrix completion. Motivated by sparse QCQPs whose lifted matrix variables include elements not directly specified by the objective or constraints, we interpret tightness as a rank-one completion property for the unspecified elements. For sparsity patterns whose blocks … Read more
In this paper, we develop a direction adaptation evolution strategy (DAES)—a new MAES-type method—for noisy derivative-free optimization, designed to reconcile the population-based search mechanisms of evolution strategies with rigorous complexity analysis. Unlike standard MAES schemes, DAES fixes the adaptation matrix to the identity and replaces matrix adaptation with a structured direction-generation mechanism based on symmetric … Read more
The global demand for grid-scale energy storage continues to increase. Carnot batteries (CBs) are not geographically constrained and consist of mature components. Furthermore, charging power, discharging power, and storage capacity can be sized independently and tailored to the intended use case. Designing an optimal CB also requires considering the resulting operational behavior. While design and … Read more
The Interval Branch and Bound (IBB) method is a widely used approach for solving nonlinear programming problems, especially when a rigorous solution is required. It uses Interval Arithmetic to handle rounding errors. Although numerous variants of the IBB method have been proposed in the literature, relatively few implementations incorporate Karush-Kuhn-Tucker or Fritz-John (FJ) optimality conditions … Read more
We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity … Read more
We are interested in exactness, strong conic duality and dual attainability in copositive relaxations of quadratic optimization problems (QPs) of a special form, in which any (feasible) QP can be recast. By using our results, the celebrated Frank-Wolfe theorem on the attainability of any bounded QP even over unbounded polyhedra, regardless of whether the objective … Read more
Electricity storage is used for intertemporal price arbitrage and for ancillary services that balance unforeseen supply and demand fluctuations via frequency regulation. We present an optimization model that computes bids for both arbitrage and frequency regulation and ensures that storage operators can honor their market commitments at all times for all fluctuation signals in an … Read more