New self-concordant barrier for the hypercube

E. A.Papa Quiroz, P. R. Oliveira

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

We introduce a new barrier function to build new interior-point algorithms to solve optimization problems with bounded variables. First, we show that this function is a (3/2)n-self-concordant barrier for the unitary hypercube [0,1] n , assuring thus the polynomial property of related algorithms. Second, using the Hessian metric of that barrier, we present new explicit algorithms from the point of view of Riemannian geometry applications. Third, we prove that the central path defined by the new barrier to solve a certain class of linearly constrained convex problems maintains most of the properties of the central path defined by the usual logarithmic barrier. We present also a primal long-step path-following algorithm with similar complexity to the classical barrier. Finally, we introduce a new proximal-point Bregman type algorithm to solve linear problems in [0,1] n and prove its convergence. © 2007 Springer Science+Business Media, LLC.
Original languageAmerican English
Pages (from-to)475-490
Number of pages16
JournalJournal of Optimization Theory and Applications
DOIs
StatePublished - 1 Dec 2007
Externally publishedYes

Fingerprint Dive into the research topics of 'New self-concordant barrier for the hypercube'. Together they form a unique fingerprint.

  • Cite this