Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials via the definition of convexity, its first order characterization, and its second order characterization are equivalent. These three equivalent algebraic conditions, henceforth referred to as sos-convexity, can be checked by semidefinite programming … Read more
We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of … Read more
We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of … Read more
This paper presents an algorithm and its implementation in the software package NCSOStools for finding sums of hermitian squares and commutators decompositions for polynomials in noncommuting variables. The algorithm is based on noncommutative analogs of the classical Gram matrix method and the Newton polytope method, which allows us to use semidefinite programming. Throughout the paper … Read more
We propose a method to reduce the sizes of SDP relaxation problems for a given polynomial optimization problem (POP). This method is an extension of the elimination method for a sparse SOS polynomial in [Kojima et al., Mathematical Programming] and exploits sparsity of polynomials involved in a given POP. In addition, we show that this … Read more
The crossing number of a graph is the minimal number of edge crossings achievable in a drawing of the graph in the plane. The crossing numbers of complete and complete bipartite graphs are long standing open questions. In a 2-page drawing of a graph, all vertices are drawn on a circle, and no edge may … Read more
We propose an algorithm that computes the epsilon-correlated equilibria with global-optimal (i.e., maximum) expected social welfare for single stage polynomial games. We first derive an infinite-dimensional formulation of epsilon-correlated equilibria using Kantorovich polynomials and re-express it as a polynomial positivity constraint. In addition, we exploit polynomial sparsity to achieve a leaner problem formulation involving Sum-Of-Squares … Read more
In this paper, we study iteration complexities of Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithms in SDP and symmetric cone programs by way of curvature integrals. The curvature integral is defined along the central path, reflecting the geometric structure of the central path. The idea to exploit the curvature of the central path for the analysis of iteration … Read more
This paper is a continuation of the paper Kakihara, Ohara and Tsuchiya by the authors where they demonstrated that the number of iterations of Mizuno-Todd-Ye predictor-corrector primal-dual interior-point methods for SDP and more generally symmetric cone programs is (asymptotically) expressed with an integral over the central trajectory called “curvature integral.” It was shown that the … Read more
We analyze the properties of an interior point cutting plane algorithm that is based on a semi-infinite linear formulation of the dual semidefinite program. The cutting plane algorithm approximately solves a linear relaxation of the dual semidefinite program in every iteration and relies on a separation oracle that returns linear cutting planes. We show that … Read more