Selfconcordant

Selfconcordant is a term used in optimization theory to describe a specific property of objective functions. A function is said to be selfconcordant if its third derivative is bounded by a function of its second derivative. More formally, for a univariate function $f(x)$, it is selfconcordant if there exists a constant $M \ge 0$ such that for all $x$ in its domain, $|f'''(x)| \le M |f''(x)|$. This definition is often extended to include a parameter, such that $|f'''(x)| \le M|f''(x)|^{3/2}$ or other variations.

This property is particularly important in the context of interior-point methods, a class of algorithms used to solve optimization problems. Selfconcordant functions allow for the theoretical analysis of these methods, guaranteeing convergence under certain conditions. The selfconcordance property essentially measures how much a function deviates from being quadratic. Quadratic functions are trivially selfconcordant.

The concept was introduced and developed by Yurii Nesterov and Arkadi Nemirovski in their work on interior-point methods and barrier functions. Functions that are selfconcordant often arise naturally as barrier functions in convex optimization problems. Examples of selfconcordant functions include the logarithmic barrier function for linear programming and certain types of entropy functions. The benefit of using selfconcordant barrier functions is that they simplify the analysis of the convergence rates of interior-point algorithms, often leading to polynomial-time complexity guarantees.