We present a solution framework for general alternating current optimal power flow (AC OPF) problems that include discrete decisions. The latter occur, for instance, in the context of the curtailment of renewables or the switching of power generation units and transmission lines. Our approach delivers globally optimal solutions and is provably convergent. We model AC … Read more
We present a mathematical and computational framework for the problem of learning a dynamical system from noisy observations of a few trajectories and subject to side information. Side information is any knowledge we might have about the dynamical system we would like to learn besides trajectory data. It is typically inferred from domain-specific knowledge or … Read more
We utilize association schemes to analyze the quality of semidefinite programming (SDP) based convex relaxations of integral packing and covering polyhedra determined by matchings in hypergraphs. As a by-product of our approach, we obtain bounds on the clique and stability numbers of some regular graphs reminiscent of classical bounds by Delsarte and Hoffman. We determine … Read more
We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if … Read more
We develop a new interior-point method (IPM) for symmetric-cone optimization, a common generalization of linear, second-order-cone, and semidefinite programming. In contrast to classical IPMs, we update iterates with a geodesic of the cone instead of the kernel of the linear constraints. This approach yields a primal-dual-symmetric, scale-invariant, and line-search-free algorithm that uses just half the … Read more
Second-order necessary optimality conditions for nonlinear conic programming problems that depend on a single Lagrange multiplier are usually built under nondegeneracy and strict complementarity. In this paper we establish a condition of such type for two classes of nonlinear conic problems, namely semidefinite and second-order cone programming, assuming Robinson’s constraint qualification and a generalized form … Read more
We introduce the notion of consistent error bound functions which provides a unifying framework for error bounds for multiple convex sets. This framework goes beyond the classical Lipschitzian and Holderian error bounds and includes logarithmic and entropic error bound found in the exponential cone. It also includes the error bounds obtainable under the theory of … Read more
In 2011, Korovin and Voronkov (Proceedings of the 23rd International Conference on Automated Deduction, vol. 6803 of Lecture Notes in Computer Science, pp. 369-383) proposed a method based on bound propagation for solving systems of linear inequalities. In this paper, an alternate description of their algorithm which also incorporates an addition that returns a certificate … Read more
We propose a randomized method for solving linear programs with a large number of columns but a relatively small number of constraints. Since enumerating all the columns is usually unrealistic, such linear programs are commonly solved by column generation, which is often still computationally challenging due to the intractability of the subproblem in many applications. … Read more
A closed convex conic subset $\cS$ of the positive semidefinite (PSD) cone is rank-one generated (ROG) if all of its extreme rays are generated by rank-one matrices. The ROG property of $\cS$ is closely related to the exactness of SDP relaxations of nonconvex quadratically constrained quadratic programs (QCQPs) related to $\cS$. We consider the case … Read more