Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming

We devise a scheme for solving an iterative sequence of linear programs (LPs) or second order cone programs (SOCPs) to approximate the optimal value of any semidefinite program (SDP) or sum of squares (SOS) program. The first LP and SOCP-based bounds in the sequence come from the recent work of Ahmadi and Majumdar on diagonally … Read more

High Throughput Computing for Massive Scenario Analysis and Optimization to Minimize Cascading Blackout Risk

We describe a simulation-based optimization method that allocates additional capacity to transmission lines in order to minimize the expected value of the load shed due to a cascading blackout. Estimation of the load-shed distribution is accomplished via the ORNL-PSerc-Alaska (OPA) simulation model, which solves a sequence of linear programs. Key to achieving an effective algorithm … Read more

On the Lovasz Theta Function and Some Variants

The Lovasz theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lovasz and the other to Groetschel et al. The former SDP is often thought to be preferable … Read more

New Formulation and Strong MISOCP Relaxations for AC Optimal Transmission Switching Problem

As the modern transmission control and relay technologies evolve, transmission line switching has become an important option in power system operators’ toolkits to reduce operational cost and improve system reliability. Most recent research has relied on the DC approximation of the power flow model in the optimal transmission switching problem. However, it is known that … Read more

Polynomial SDP Cuts for Optimal Power Flow

The use of convex relaxations has lately gained considerable interest in Power Systems. These relaxations play a major role in providing quality guarantees for non-convex optimization problems. For the Optimal Power Flow (OPF) prob- lem, the semidefinite programming (SDP) relaxation is known to produce tight lower bounds. Unfortunately, SDP solvers still suffer from a lack … Read more

Improved Damped Quasi-Newton Methods for Unconstrained Optimization

Recently, Al-Baali (2014) has extended the damped-technique in the modified BFGS method of Powell (1978) for Lagrange constrained optimization functions to the Broyden family of quasi-Newton methods for unconstrained optimization. Appropriate choices for the damped-parameter, which maintain the global and superlinear con- vergence property of these methods on convex functions and correct the Hessian approximations … Read more

On the convergence rate of grid search for polynomial optimization over the simplex

We consider the approximate minimization of a given polynomial on the standard simplex, obtained by taking the minimum value over all rational grid points with given denominator ${r} \in \mathbb{N}$. It was shown in [De Klerk, E., Laurent, M., Sun, Z.: An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric … Read more

Extended Formulations for Vertex Cover

The vertex cover polytopes of graphs do not admit polynomial-size extended formulations. This motivates the search for polyhedral analogues to approximation algorithms and fixed-parameter tractable (FPT) algorithms. While the polyhedral approximability of vertex cover has been studied, we know of no extended formulations parameterized by the size of the vertex cover. To this end, we … Read more

Stochastically Constrained Simulation Optimization On Integer-Ordered Spaces: The cgR-SPLINE Algorithm

We consider the problem of identifying the solution(s) to an optimization problem whose domain is a subset of the integer lattice, and whose objective and constraint functions can only be observed using a stochastic simulation. Such problems seem particularly prevalent (see www.simopt.org) within service systems having capacity or service-level constraints. We present cgR-SPLINE — a … Read more