We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) and find ones that speed up the convex-concave procedure … Read more
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
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
Let K be a closed convex cone with dual K^* in a finite-dimensional real inner-product space V. The complementarity set of K is C(K) = { (x, s) in K × K^* | = 0 }. We say that a linear transformation L : V -> V is Lyapunov-like on K if = 0 for all (x, … Read more
Exploiting sparsity in Semidefinite Programs (SDP) is critical to solving large-scale problems. The chordal completion based maximal clique decomposition is the preferred approach for exploiting sparsity in SDPs. In this paper, we show that the maximal clique-based SDP decomposition is primal degenerate when the SDP has a low rank solution. We also derive conditions under … Read more
Recently, Pena and Soheili presented a deterministic rescaling perceptron algorithm and proved that it solves a feasible perceptron problem in $O(m^2n^2\log(\rho^{-1}))$ perceptron update steps, where $\rho$ is the radius of the largest inscribed ball. The original stochastic rescaling perceptron algorithm of Dunagan and Vempala is based on systematic increase of $\rho$, while the proof of … Read more
The primal-dual Dikin-type affine scaling method was originally proposed for linear optimization and then extended to semidefinite optimization. Here, the method is generalized to symmetric conic optimization using the notion of Euclidean Jordan algebras. The method starts with an interior feasible but not necessarily centered primal-dual solution, and it features both centering and reducing the … Read more
The objective of this work is to study weak infeasibility in second order cone programming. For this purpose, we consider a relaxation sequence of feasibility problems that mostly preserve the feasibility status of the original problem. This is used to show that for a given weakly infeasible problem at most m directions are needed to … Read more
We propose a framework for sensitivity analysis of linear programs (LPs) in minimiza- tion form, allowing for simultaneous perturbations in the objective coefficients and right-hand sides, where the perturbations are modeled in a compact, convex uncertainty set. This framework unifies and extends multiple approaches for LP sensitivity analysis in the literature and has close ties … Read more
Many uncertainty sets encountered in control systems analysis and design can be expressed in terms of semialgebraic sets, that is as the intersection of sets described by means of polynomial inequalities. Important examples are for instance the solution set of linear matrix inequalities or the Schur/Hurwitz stability domains. These sets often have very complicated shapes … Read more