Self-concordant function
In optimization, a self-concordant function is a function formula_1 for which or, equivalently, a function formula_1 that, wherever formula_4, satisfies and which satisfies formula_6 elsewhere. More generally, a multivariate function formula_7 is self-concordant if or, equivalently, if its restriction to any arbitrary line is self-concordant. History. As mentioned in the "Bibliography Comments" of their 1994 book, self-concordant functions were introduced in 1988 by Yurii Nesterov and further developed with Arkadi Nemirovski. As explained in their basic observation was that the Newton method is affine invariant, in the sense that if for a function  formula_9 we have Newton steps formula_10 then for a function formula_11 where formula_12 is a non-degenerate linear transformation, starting from formula_13 we have the Newton steps formula_14 which can be shown recursively However the standard analysis of the Newton method supposes that the Hessian of formula_16 is Lipschitz continuous, that is formula_17 for some constant formula_18. If we suppose that formula_16 is 3 times continuously differentiable, then this is equivalent to where formula_22 . Then the left hand side of the above inequality is invariant under the affine transformation formula_23, however the right hand side is not. The authors note  that the right hand side can be made also invariant if we replace the Euclidean metric by the scalar product defined by the Hessian of formula_16 defined as formula_25 for formula_26. They then arrive at the definition of a self concordant function as Properties. Linear combination. If formula_28 and formula_29 are self-concordant with constants formula_30 and formula_31 and formula_32, then formula_33 is self-concordant with constant formula_34. Affine transformation. If formula_16 is self-concordant with constant formula_18 and formula_37 is an affine transformation of formula_38, then formula_39 is also self-concordant with parameter formula_18. Convex conjugate. If formula_16 is  self-concordant, then its convex conjugate formula_42 is also self-concordant. Non-singular Hessian. If formula_16 is self-concordant and the domain of formula_16 contains no straight line (infinite in both directions), then formula_45 is non-singular. Conversely, if for some formula_46 in the domain of formula_16 and formula_48 we have formula_49, then formula_50 for all formula_51 for which formula_52 is in the domain of formula_16 and then formula_54 is linear and cannot have a maximum so all of formula_55 is in the domain of formula_16. We note also that formula_16 cannot have a minimum inside its domain . Applications. Among other things, self-concordant functions are useful in the analysis of Newton's method. Self-concordant "barrier functions" are used to develop the barrier functions used in interior point methods for convex and nonlinear optimization. The usual analysis of the Newton method would not work for barrier functions as their second derivative cannot be Lipschitz continuous, otherwise they would be bounded on any compact subset of formula_38. Self-concordant barrier functions Minimizing a self-concordant function. A self-concordant function may be minimized with a modified Newton method where we have a bound on the number of  steps required for convergence. We suppose here that formula_16 is a "standard" self-concordant function, that is it is self-concordant with parameter formula_60. We define the "Newton decrement" formula_61 of formula_16 at formula_46 as the size of the Newton step formula_64 in the local norm defined by the Hessian of formula_16 at formula_46 Then for formula_46 in the domain of formula_16, if formula_70 then it is possible to prove that the Newton iterate will be also in the domain of formula_16. This is because, based on the self-concordance of formula_16, it is possible to give some finite bounds  on the value of formula_74. We further have Then if we have then it is also guaranteed that formula_77, so that we can continue to use the Newton method until convergence. Note that for formula_78 for some formula_79 we have quadratic convergence of formula_80 to 0 as formula_81. This then gives quadratic convergence of formula_82 to formula_83 and of formula_46 to formula_85, where formula_86, by the following theorem. If formula_70 then with the following definitions If we start the Newton method from some formula_93 with formula_94 then we have to start by using a "damped Newton method" defined by For  this it can be shown that formula_96 with formula_97 as defined previously. Note that formula_98 is an increasing function for formula_99 so that formula_100 for any formula_101, so the value of formula_16 is guaranteed to decrease by a certain amount in each iteration, which also proves that formula_103 is in the domain of formula_16. Examples. Self-concordant functions. Functions that are not self-concordant