The Volumetric Barrier for Convex Quadratic Constraints

Kurt M. Anstreicher

Let ${\cal Q}=\{x | s_i(x)\ge 0, i=1,\ldots,k\}$, where $s_i(x)=a_i^T x-x^T Q_i x-c_i$, and $Q_i$ is an $n\times n$ positive semidefinite matrix. We prove that the volumetric and combined volumetric-logarithmic barriers for ${\cal Q}$ are $O(\sqrt{k}n)$ and $O(\sqrt{kn})$ self-concordant, respectively. Our analysis uses the semidefinite programming (SDP) representation for the convex quadratic constraints defining ${\cal Q}$, and our earlier results on the volumetric barrier for SDP. The self-concordancy results actually hold for a class of SDP problems more general than those corresponding to the SDP representation of ${\cal Q}$.

Dept. of Management Sciences, University of Iowa, Iowa City, October 1998.

Contact: kurt-anstreicher@uiowa.edu

[PS] [IP PAGE] [SEARCH AGAIN]