The volumetric barrier for convex quadratic constraints
type: Item
instance of: scholarly article
title: The volumetric barrier for convex quadratic constraints
zbMATH Open document ID: 1070.90084
author: Kurt M. Anstreicher
published in: Mathematical Programming. Series A. Series B
publication date: 2004-10-28T00:00:00Z
review text: 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}\).
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 90C20
zbMATH DE Number: 2111488
zbMATH Keywords: self-concordance
zbMATH Keywords: volumetric barrier
zbMATH Keywords: semidefinite programming
zbMATH Keywords: convex quadratic constraints
reviewed by: Walter Gómez Bofill
MaRDI profile type: Publication
Recommended article: The volumetric barrier for semidefinite programming.
Recommended article: Volumetric barrier decomposition algorithms for stochastic quadratic second-order cone programming
Recommended article: A class of volumetric barrier decomposition algorithms for stochastic quadratic programming
Recommended article: Ellipsoidal approximations of convex sets based on the volumetric barrier
Recommended article: Quasiconvex functions incorporating volumetric constraints are rank-one convex
Recommended article: On a volume-constrained variational problem
Recommended article: A lower bound on the barrier parameter of barriers for convex cones
Recommended article: Optimality conditions and a barrier method in optimization with convex geometric constraint
Recommended article: Q5091983
Recommended article: The Convex Hull of a Quadratic Constraint over a Polytope
description: scientific article; zbMATH DE number 2111488