 # Self concordance

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.$