The volumetric barrier for convex quadratic constraints (Q1885279)

The self-concordance parameter of barrier functions for a convex set \({\mathcal Q}\) plays a key role in the complexity of certain algorithms for optimization problems over \({\mathcal Q}\). In this paper the author study the self-concordance parameter of barrier functions for the convex set \({\mathcal Q} =\{x \in \mathbb{R}^{n}\mid x^{T}Q_ix - a_i^{T}x +c_i \leq 0, i=1,\ldots,k \}\), where each \(Q_i\) is a \(n\times n\) positive semidefinite matrix (\(Q_i\succeq 0\)). The set \({\mathcal Q}\) can be equivalently represented as a semidefinite (SDP) constraint of the form \({\mathcal S}=\{x \in \mathbb{R}^{n}\mid \sum_{i=1}^{n}A_ix_i - C_i \succeq 0\}\), where \(A_i\) and \(C_i\) are \(m\times m\) symmetric matrices. In this representation of \({\mathcal Q}\) the matrices \(A_i\) and \(C_i\) have a particular structure and the size \(m\) satisfies \(m=\sum_{i=1}^{k}(1+r_i)\), where \(r_i\) is the rank of \(Q_i\). In a previous paper the author proved that the volumetric and combined volumetric-logarithmic barriers are \(O(\sqrt{m}n)\) and \(O(\sqrt{mn})\) self-concordant barriers respectively for general semidefinite constraints of the form \({\mathcal S}\). In this paper it is demonstrated that these self-concordance parameters can be improved to \(O(\sqrt{k}n)\) and \(O(\sqrt{kn})\) respectively, when the matrices \(A_i\) and \(C_i\) have the particular structure found in the SDP representation of \({\mathcal Q}\). The results are actually given for a class of SDP problems slightly more general than those corresponding to the SDP representation of \({\mathcal Q}\).