A Perturbed q-Tsallis Self-Concordant Barrier for Spectrally Robust Semidefinite Programming

Abstract

We introduce and analyse a perturbed $q$-Tsallis barrier for semidefinite programming (SDP), defined as a spectral perturbation of the classical log-det barrier on the cone of positive definite matrices. The barrier introduces eigenvalue-adaptive stiffening through a Tsallis-type matrix-power term controlled by parameters $q>1$ and $\eta \ge 0$. Our main theoretical contribution is a sharp characterisation of the differential self-concordance regime of the barrier. We prove that the barrier is differentially self-concordant on the interior of the positive semidefinite cone for all $\eta \ge 0$ if and only if $q\in (1,2]$, establishing the exact threshold at $q=2$. For $q>2$, uniform self-concordance fails globally, although local sufficient conditions remain valid on compact spectral domains. On compact feasible sets, the effective local barrier parameter remains $O(n)$, preserving the same asymptotic iteration complexity class as the classical log-det barrier. We further establish a spectral robustness result showing that the sensitivity of the central path to perturbations is selectively damped in small-eigenvalue directions according to the scaling $\kappa (X^{\ast }{)}^{-(q-1)}$, where $\kappa (X^{\ast })$ denotes the spectral condition number. This yields improved robustness relative to the classical log-det barrier for ill-conditioned SDP solutions. Finally, we develop a Mehrotra-type primal--dual predictor--corrector interior-point method equipped with a Lanczos-based Krylov kernel for evaluating matrix powers efficiently. Numerical experiments validate the theoretical predictions and demonstrate improved robustness together with significant computational acceleration.