Self concordance

From Glossary

Jump to: navigation, search

Properties of a function that yield nice performance of Newton's method used for line search when optimizing a barrier function. Specifically, let B be a barrier function for LaTeX: \textstyle \mbox{S} = \{x \in \mbox{X}: g(x) \le 0\} with strict interior LaTeX: \textstyle \mbox{S}^0. Let x be in S and let d be a direction vector in LaTeX: \textstyle \mathbb{R}^n such that the line segment LaTeX: \textstyle [x-td, x+td] is in S for LaTeX: \textstyle t \mbox{ in } [0, t^*], where LaTeX: \textstyle t^* > 0. Then, define LaTeX: \textstyle \mbox{F}:[0,t^*] \to \mathbb{R} by:

LaTeX: 
\mbox{F}(t) = \mbox{B}(x + td)

(while noting that F depends on x and d). The function F is self-concordant if it is convex in C3 and satisfies the following for all x and d:

LaTeX: 
| \mbox{F}'''(0) | \le 2 \mbox{F}''(0)^\frac{3}{2}


One calls F k-self-concordant in an open convex domain if

LaTeX: 
| \mbox{F}'''(0) | \le 2 k \mbox{F}''(0)^{\frac{3}{2}}


The logarithmic barrier function, associated with linear programming, is self-concordant with LaTeX: k = 1. This further extends naturally to functions in LaTeX: \textstyle \mathbb{R}^n.


Views
Personal tools