We derive a new upper bound on the minimum rank of matrices belonging to an affine slice of the positive semidefinite cone, when the affine slice is defined according to a system of sparse linear matrix equations. It is shown that a feasible matrix whose rank is no greater than said bound can be computed in polynomial time. The bound depends on both the number of linear matrix equations and their underlying sparsity pattern. For certain problem families, this bound is shown to improve upon well known bounds in the literature. Several examples are provided to illustrate the efficacy of this bound.

10aRM14-0021 aLouca, Raphael1 aBose, Subhonmesh1 aBitar, Eilyan uhttps://certs.lbl.gov/publications/bound-minimum-rank-solutions-sparse01327nas a2200145 4500008003900000245007700039210006900116260003800185300001600223520081700239653001301056100001901069700001801088856007501106 2016 d00aA hierarchy of polyhedral approximations of robust semidefinite programs0 ahierarchy of polyhedral approximations of robust semidefinite pr aLas Vegas, NV, USAbIEEEc12/2016 a7056 - 70623 aRobust semidefinite programs are NP-hard in general. In contrast, robust linear programs admit equivalent reformulations as finite-dimensional convex programs provided that the problem data are parameterized affinely in the uncertain parameters; and that the underlying uncertainty set is described by an affine slice of a proper cone. In this paper, we propose a hierarchy of inner and outer polyhedral approximations to the positive semidefinite (PSD) cone that are exact in the limit. We apply these polyhedral approximations to the PSD cone to obtain a computationally tractable hierarchy of inner and outer approximations to the robust semidefinite program, which are similarly exact in the limit. We investigate the strengths and limitations of the proposed approach with a detailed numerical study.

10aRM14-0021 aLouca, Raphael1 aBitar, Eilyan uhttps://certs.lbl.gov/publications/hierarchy-polyhedral-approximations01210nas a2200145 4500008003900000245005800039210005800097260003800155300001600193520073300209653001300942100001900955700001800974856007200992 2016 d00aStochastic AC optimal power flow with affine recourse0 aStochastic AC optimal power flow with affine recourse aLas Vegas, NV, USAbIEEEc12/2016 a2431 - 24363 aWith the increasing penetration of intermittent renewable energy sources into the electric power grid, there is an emerging need to develop stochastic optimization methods to enable the reliable and efficient operation of power systems having a large fraction of their power supplied form uncertain resources. In this paper, we formulate the stochastic AC optimal power flow (OPF) problem as a two-stage stochastic program with robust constraints. This problem amounts to an infinite-dimensional nonconvex optimization problem. We develop a finite-dimensional inner approximation as a semidefinite program. Its solution yields an affine recourse policy that is guaranteed to be feasible for the stochastic AC OPF problem.

10aRM14-0021 aLouca, Raphael1 aBitar, Eilyan uhttps://certs.lbl.gov/publications/stochastic-ac-optimal-power-flow01353nas a2200145 4500008003900000245008800039210006900127260003600196300001600232520083400248653001301082100001901095700001801114856007501132 2015 d00aAcyclic semidefinite approximations of quadratically constrained quadratic programs0 aAcyclic semidefinite approximations of quadratically constrained aChicago, IL, USAbIEEEc07/2015 a5925 - 59303 aQuadratically constrained quadratic programs (QCQPs) belong to a class of nonconvex optimization problems that are NP-hard in general. Recent results have shown that QCQPs having acyclic graph structure can be solved in polynomial time, provided that their constraints satisfy a certain technical condition. In this paper, we consider complex QCQPs with arbitrary graph structure and investigate the extent to which it is possible to apply structured perturbations on the problem data to yield acyclic QCQPs having optimal solutions satisfying certain approximation guarantees. Specifically, we provide sufficient conditions under which the perturbed QCQP can be solved in polynomial time to yield a feasible solution to the original QCQP and derive an explicit bound on the performance of said solution in the worst case.

10aRM14-0021 aLouca, Raphael1 aBitar, Eilyan uhttps://certs.lbl.gov/publications/acyclic-semidefinite-approximations