An extension of Chubanov’s algorithm to symmetric cones

Abstract

In this work we present an extension of Chubanov’s algorithm to the case of homogeneous feasibility problems over a symmetric cone ${\mathcal {K}}$. As in Chubanov’s method for linear feasibility problems, the algorithm consists of a basic procedure and a step where the solutions are confined to the intersection of a half-space and ${\mathcal {K}}$. Following an earlier work by Kitahara and Tsuchiya on second order cone feasibility problems, progress is measured through the volumes of those intersections: when they become sufficiently small, we know it is time to stop. We never have to explicitly compute the volumes, it is only necessary to keep track of the reductions between iterations. We show this is enough to obtain concrete upper bounds to the minimum eigenvalues of a scaled version of the original feasibility problem. Another distinguishing feature of our approach is the usage of a spectral norm that takes into account the way that ${\mathcal {K}}$ is decomposed as simple cones. In several key cases, including semidefinite programming and second order cone programming, these norms make it possible to obtain better complexity bounds for the basic procedure when compared to a recent approach by Peña and Soheili. Finally, in the appendix, we present a translation of the algorithm to the homogeneous feasibility problem in semidefinite programming.

A The case of semidefinite programming

For ease of reference, we “translate” here Algorithms 1 and 2 for the case of semidefinite programming, see Algorithms 3 and 4. In this case, we have $\ell = 1, r = n$, ${\mathcal {K}}= {\mathcal {S}^{n}_+}$ and ${\mathcal {E}}$ is the space of $n\times n$ symmetric matrices ${\mathcal {S}}^n$. We recall that if $y \in {\mathcal {S}^{n}_+}$, then $\left\| y\right\| _1 = \langle {e} , y \rangle = {\mathrm {tr}}\,y$, so the stopping criteria in Algorithm 1 becomes $\left\| z\right\| \le \frac{1}{2n}{\mathrm {tr}}\,y$. We will use $I_n$ to denote the $n\times n$ identity matrix. We will write $y \succeq 0$, if y is positive semidefinite and $y \succ 0$, if y is positive definite.

Furthermore, for $w \in {\mathcal {S}^{n}_+}$, the quadratic map $Q_{w}$ is the function that takes $x \in {\mathcal {S}}^n$ to wxw. We do not need, in fact, to explicitly construct the operator $Q_{w}$. In particular, if ${\mathcal {A}}x = 0$ is represented as the set of solutions of m linear equalities ${\mathrm {tr}}\,(a_1x) = 0, \ldots , {\mathrm {tr}}\,(a_mx) = 0$, the first assignment in Line 11 of Algorithm 4 is the same as substituting every $a_i$ by $n(w^{-1/2}a_iw^{-1/2})$. Finally, as remarked at the end of Sect. 4, the condition $z \ne 0$ in Algorithm 3 can be substituted by $y^i - z \not \succeq 0$.