Self-concordant function

A '''self-concordant function''' is a function satisfying a certain [[differential inequality]], which makes it particularly easy for [[Optimization problem|optimization]] using [[Newton's method]]<ref name=":0">{{Cite web |last=Nemirovsky and Ben-Tal |date=2023 |title=Optimization III: Convex Optimization |url=http://www2.isye.gatech.edu/~nemirovs/OPTIIILN2023Spring.pdf}}</ref>{{Rp|location=Sub.6.2.4.2}} A '''self-concordant barrier''' is a particular self-concordant function, that is also a [[barrier function]] for a particular convex set. Self-concordant barriers are important ingredients in [[interior point method]]s for optimization.

== Self-concordant functions ==

=== Multivariate self-concordant function === Here is the general definition of a self-concordant function.<ref name=":1">{{Cite web |last=Arkadi Nemirovsky |date=2004 |title=Interior point polynomial time methods in convex programming |url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=8c3cb6395a35cb504019f87f447d65cb6cf1cdf0}}</ref>{{Rp|location=Def.2.0.1}}

Let ''C'' be a convex nonempty [[open set]] in R''ⁿ''. Let ''f'' be a function that is three-times continuously differentiable defined on ''C''. We say that '''f is self-concordant on ''C''''' if it satisfies the following properties:

1. ''Barrier property'': on any sequence of points in ''C'' that converges to a boundary point of ''C'', ''f'' converges to ∞.

2. ''Differential inequality'': for every point '''x''' in ''C'', and any direction '''h''' in R^''n'', let ''g''_h be the function ''f'' restricted to the direction '''h''', that is: ''g''_h(''t'') = ''f''('''x'''+t*'''h'''). Then the one-dimensional function ''g''_h should satisfy the following differential inequality: <blockquote><math>|g_h'''(x)| \leq 2 g_h''(x)^{3/2}</math>. </blockquote>Equivalently:<ref>{{cite book |last1=Boyd |first1=Stephen P. |url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf |title=Convex Optimization |last2=Vandenberghe |first2=Lieven |publisher=Cambridge University Press |year=2004 |isbn=978-0-521-83378-3 |access-date=October 15, 2011}}</ref><blockquote><math>\left. \frac{d}{d\alpha} \nabla^2 f(x + \alpha y) \right|_{\alpha = 0} \preceq 2 \sqrt{y^T \nabla^2 f(x)\,y} \, \nabla^2 f(x)</math></blockquote>

=== Univariate self-concordant function === A [[function (mathematics)|function]] <math>f:\mathbb{R} \rightarrow \mathbb{R}</math> is self-concordant on <math>\mathbb{R}</math> if:

: <math>|f'''(x)| \leq 2 f''(x)^{3/2}</math>

Equivalently: if wherever <math>f''(x) > 0</math> it satisfies:

: <math>\left| \frac{d}{dx} \frac{1}{\sqrt{f''(x)}} \right| \leq 1</math>

and satisfies <math>f'''(x) = 0</math> elsewhere.

=== Examples ===

* Linear and convex quadratic functions are self-concordant, since their third derivative is zero. * Any function <math>f(x) = -\log(-g(x))-\log x</math> where <math>g(x)</math> is defined and convex for all <math>x > 0</math> and verifies <math>| g'''(x) | \leq 3g''(x)/x</math>, is self concordant on its domain which is <math>\{ x \mid x > 0, g(x) < 0 \}</math>. Some examples are **<math>g(x) = -x^p</math> for <math>0 < p \leq 1</math> ** <math>g(x) = -\log x</math> ** <math>g(x) = x^p</math> for <math>-1 \leq p \leq 0</math> ** <math>g(x) = (ax+b)^2 / x</math> ** for any function <math>g</math> satisfying the conditions, the function <math>g(x) + a x^2 + bx + c</math> with <math>a \geq 0</math> also satisfies the conditions.

Some functions that are not self-concordant:

* <math>f(x) = e^x</math> * <math>f(x) = \frac{1}{x^p}, x >0, p >0</math> * <math>f(x) = |x^p|, p > 2</math>

== Self-concordant barriers{{Anchor|barrier}} == Here is the general definition of a self-concordant barrier (SCB).<ref name=":1" />{{Rp|location=Def.3.1.1}}

Let ''C'' be a convex closed set in R''ⁿ'' with a non-empty interior. Let ''f'' be a function from interior(''C'') to R. Let ''M''>0 be a real parameter. We say that '''''f'' is a ''M''-self-concordant barrier for ''C''''' if it satisfies the following:

1. ''f'' is a self-concordant function on interior(''C'').

2. For every point '''x''' in interior(''C''), and any direction '''h''' in R^''n'', let ''g''_h be the function ''f'' restricted to the direction '''h''', that is: ''g''_h(''t'') = ''f''('''x'''+t*'''h'''). Then the one-dimensional function ''g''_h should satisfy the following differential inequality:<blockquote><math>|g_h'(x)| \leq M^{1/2}\cdot g_h''(x)^{1/2}</math>. </blockquote>

=== Constructing SCBs === Due to the importance of SCBs in interior-point methods, it is important to know how to construct SCBs for various domains.

In theory, it can be proved that ''every'' closed convex domain in Rⁿ has a self-concordant barrier with parameter O(''n''). But this “universal barrier” is given by some multivariate integrals, and it is too complicated for actual computations. Hence, the main goal is to construct SCBs that are efficiently computable.<ref name=":02">{{Cite web |last=Nemirovsky and Ben-Tal |date=2023 |title=Optimization III: Convex Optimization |url=http://www2.isye.gatech.edu/~nemirovs/OPTIIILN2023Spring.pdf}}</ref>{{Rp|location=Sec.9.2.3.3}}

SCBs can be constructed from some ''basic SCBs'', that are combined to produce SCBs for more complex domains, using several ''combination rules''.

=== Basic SCBs === Every constant is a self-concordant barrier for all R''ⁿ'', with parameter M=0. It is the only self-concordant barrier for the entire space, and the only self-concordant barrier with ''M'' < 1.<ref name=":1" />{{Rp|location=Example 3.1.1}} [Note that linear and quadratic functions are self-concordant functions, but they are ''not'' self concordant barriers].

For the positive half-line <math>\mathbb R_+</math>(<math>x > 0</math>), <math>f(x) = -\ln x</math> is a self-concordant barrier with parameter <math>M = 1</math>. This can be proved directly from the definition.

=== Substitution rule === Let ''G'' be a closed convex domain in ''Rⁿ'', and ''g'' an ''M''-SCB for ''G''. Let ''x'' = ''Ay''+''b'' be an affine mapping from R^k to Rⁿ with its image intersecting the interior of ''G''. Let ''H'' be the inverse image of ''G'' under the mapping: ''H'' = {''y'' in R^''k'' | ''Ay+b'' in ''G''}. Let ''h'' be the composite function ''h''(''y'') := g(''Ay''+''b''). Then, ''h'' is an ''M''-SCB for ''H''.<ref name=":1" />{{Rp|location=Prop.3.1.1}}

For example, take ''n''=1, ''G'' the positive half-line, and <math>g(x) = -\ln x</math>. For any ''k'', let ''a'' be a ''k''-element vector and ''b'' a scalar. Let ''H'' = {''y'' in R^k | ''a''^T''y+b'' ≥ 0} = a ''k''-dimensional half-space. By the substitution rule, <math>h(y) = -\ln (a^T y+b)</math> is a 1-SCB for ''H''. A more common format is ''H'' = {''x'' in R^''k'' | ''a^Tx'' ≤ b}, for which the SCB is <math>h(y) = -\ln (b - a^T y)</math>.

The substitution rule can be extended from affine mappings to a certain class of "appropriate" mappings,<ref name=":1" />{{Rp|location=Thm.9.1.1}} and to quadratic mappings.<ref name=":1" />{{Rp|location=Sub.9.3}}

=== Cartesian product rule === For all ''i'' in 1,...,''m'', let ''G_i'' be a closed convex domains in ''Rⁿⁱ'', and let ''g_i'' be an ''M''_i-SCB for ''G_i''. Let ''G'' be the [[cartesian product]] of all ''G_i''. Let ''g(x''₁'',...,x_m)'' := sum''_i g_i''(''x_i''). Then, ''g'' is a SCB for ''G'', with parameter sum''_i M_i''.<ref name=":1" />{{Rp|location=Prop.3.1.1}}

For example, take all ''G_i'' to be the positive half-line, so that ''G'' is the positive orthant <math>\mathbb R_+^m</math>. Let <math>g(x) = -\sum_{i=1}^m \ln x_i</math> is an ''m''-SCB for ''G.''

We can now apply the substitution rule. We get that, for the polytope defined by the linear inequalities ''a_j''^T''x'' ≤ ''b_j'' for ''j'' in 1,...,''m'', if it satisfies [[Slater's condition]], then <math>f(x) = -\sum_{i=1}^m \ln (b_j-a_j^T x)</math> is an ''m''-SCB. The linear functions <math>b_j-a_j^T x</math> can be replaced by [[quadratic function]]s.

=== Intersection rule === Let ''G''₁,...,''G_m'' be closed convex domains in ''Rⁿ''. For each ''i'' in 1,...,''m'', let ''g_i'' be an ''M''_i-SCB for ''G_i'', and ''r_i'' a real number. Let ''G'' be the intersection of all ''G_i'', and suppose its interior is nonempty. Let ''g'' := sum''_i r_i*g_i''. Then, ''g'' is a SCB for ''G'', with parameter sum''_i r_i*M_i''.<ref name=":1" />{{Rp|location=Prop.3.1.1}}

Therefore, if ''G'' is defined by a list of constraints, we can find a SCB for each constraint separately, and then simply sum them to get a SCB for ''G''.

For example, suppose the domain is defined by ''m'' linear constraints of the form ''a_j^Tx'' ≤ ''b_j'', for ''j'' in 1,...,''m''. Then we can use the Intersection rule to construct the ''m''-SCB <math>f(x) = -\sum_{i=1}^m \ln (b_j-a_j^T x)</math> (the same one that we previously computed using the Cartesian [[product rule]]).

=== SCBs for epigraphs === The [[Epigraph (mathematics)|epigraph]] of a function ''f''(''x'') is the area above the graph of the function, that is, <math>\{ (x,t) \in \mathbb{R}^2: t\geq f(x) \} </math>. The epigraph of ''f'' is a [[convex set]] [[if and only if]] ''f'' is a [[convex function]]. The following theorems present some functions ''f'' for which the epigraph has an SCB.

Let ''g''(''t'') be a 3-times continuously differentiable [[concave function]] on ''t''>0, such that <math>t\cdot | g'''(t)| / |g''(t)| </math> is bounded by a constant (denoted 3*''b'') for all ''t''>0. Let ''G'' be the 2-dimensional convex domain: <math>G=\text{closure}(\{ (x,t) \in \mathbb{R}^2: t>0, x \leq g(t) \}). </math>Then, the function ''f''(''x'',''t'') = -ln(f(t)-x) - max[1,b²]*ln(t) is a self-concordant barrier for ''G'', with parameter (1+max[1,b²]).<ref name=":1" />{{Rp|location=Prop.9.2.1}}

Examples:

* Let ''g''(''t'') = ''t''^1/''p'', for some ''p''≥1, and ''b''=(2''p''-1)/(3''p''). Then <math>G_1=\{ (x,t) \in \mathbb{R}^2: (x_+)^p \leq t \} </math> has a 2-SCB. Similarly, <math>G_2=\{ (x,t) \in \mathbb{R}^2: ([-x]_+)^p \leq t \} </math> has a 2-SCB. Using the Intersection rule, we get that <math>G = G_1\cap G_2= \{ (x,t) \in \mathbb{R}^2: |x|^p \leq t \} </math> has a 4-SCB. * Let ''g''(''t'')=ln(''t'') and ''b''=2/3. Then <math>G=\{ (x,t) \in \mathbb{R}^2: e^x \leq t \} </math> has a 2-SCB. We can now construct a SCB for the problem of minimizing the ''p''-norm: <math>\min_x \sum_{j=1}^n |v_j - x^T u_j|^p </math>, where ''v_j'' are constant scalars, ''u_j'' are constant vectors, and ''p''>0 is a constant. We first convert it into minimization of a linear objective: <math>\min_x \sum_{j=1}^n t_j </math>, with the constraints: <math>t_j \geq |v_j - x^T u_j|^p </math>for all ''j'' in [''m'']. For each constraint, we have a 4-SCB by the affine substitution rule. Using the Intersection rule, we get a (4''n'')-SCB for the entire feasible domain.

Similarly, let ''g'' be a 3-times continuously differentiable convex function on the ray ''x''>0, such that: <math>x\cdot |g'''(x)| / |g''(x)| \leq 3 b </math> for all ''x''>0. Let ''G'' be the 2-dimensional convex domain: closure({ (''t,x'') in R²: x>0, ''t'' ≥ ''g''(''x'') }). Then, the function ''f''(''x'',''t'') = -ln(t-f(x)) - max[1,b²]*ln(x) is a self-concordant barrier for G, with parameter (1+max[1,b²]).<ref name=":1" />{{Rp|location=Prop.9.2.2}}

Examples:

* Let ''g''(''x'') = ''x''^−''p'', for some ''p''>0, and b=(2+''p'')/3. Then <math>G_1=\{ (x,t) \in \mathbb{R}^2: x^{-p} \leq t, x\geq 0 \} </math> has a 2-SCB. * Let ''g''(''x'')=''x'' ln(''x'') and ''b''=1/3. Then <math>G=\{ (x,t) \in \mathbb{R}^2: x\ln x \leq t, x\geq 0 \} </math> has a 2-SCB.

=== SCBs for cones === * For the [[Second-order cone programming|second order cone]] <math>\{ (x,y) \in \mathbb R^{n-1} \times \mathbb R \mid \| x \| \leq y \}</math>, the function <math>f(x,y) = -\log(y^2 - x^T x)</math> is a self-concordant barrier. * For the cone of [[Positive semidefinite matrices|positive semidefinite]] of m*m symmetric matrices, the function <math>f(A) = - \log \det A</math> is a self-concordant barrier. * For the quadratic region defined by <math>\phi(x) > 0</math> where <math>\phi(x) = \alpha +\langle a, x \rangle - \frac{1}{2} \langle Ax, x \rangle</math> where <math>A = A^T \geq 0</math> is a [[positive semidefinite matrix|positive semi-definite]] [[symmetric matrix]], the logarithmic barrier <math>f(x) = -\log \phi(x)</math> is self-concordant with <math>M = 2</math> * For the [[exponential cone]] <math>\{ (x,y,z) \in \mathbb R^3 \mid ye^{x/y} \leq z, y > 0 \}</math>, the function <math>f(x,y,z) = -\log (y \log(z/y) - x) - \log z - \log y</math> is a self-concordant barrier. * For the [[power cone]] <math>\{ (x_1,x_2,y) \in \mathbb R_+^2 \times \mathbb R \mid |y| \leq x_1^{\alpha} x_2^{1-\alpha} \}</math>, the function <math>f(x_1,x_2,y) = -\log(x_1^{2\alpha} x_2^{2(1-\alpha)} - y^2) - \log x_1 - \log x_2</math> is a self-concordant barrier.

== History == As mentioned in the "Bibliography Comments"<ref>{{Cite book|last1=Nesterov|first1=Yurii|url=https://epubs.siam.org/doi/pdf/10.1137/1.9781611970791.bm|title=Interior-Point Polynomial Algorithms in Convex Programming (Bibliography Comments)|last2=Nemirovskii|first2=Arkadii|date=January 1994|publisher=Society for Industrial and Applied Mathematics|isbn=978-0-89871-319-0|language=en|doi=10.1137/1.9781611970791.bm}}</ref> of their 1994 book,<ref name=siam /> self-concordant functions were introduced in 1988 by [[Yurii Nesterov]]<ref>Yu. E. NESTEROV, Polynomial time methods in linear and quadratic programming, Izvestija AN SSSR, Tekhnitcheskaya kibernetika, No. 3, 1988, pp. 324-326. (In Russian.)</ref><ref>Yu. E. NESTEROV, Polynomial time iterative methods in linear and quadratic programming, Voprosy kibernetiki, Moscow,1988, pp. 102-125. (In Russian.)</ref> and further developed with [[Arkadi Nemirovski]].<ref>Y.E. Nesterov and A.S. Nemirovski, Self–concordant functions and polynomial–time methods in convex programming, Technical report, Central Economic and Mathematical Institute, USSR Academy of Science, Moscow, USSR, 1989.</ref> As explained in<ref>{{Cite book|last=Nesterov, I︠U︡. E.|title=Introductory lectures on convex optimization : a basic course|date=December 2013 |isbn=978-1-4419-8853-9|location=Boston|oclc=883391994}}</ref> their basic observation was that the Newton method is affine invariant, in the sense that if for a function <math>f(x)</math> we have Newton steps <math>x_{k+1} = x_k - [f''(x_k)]^{-1}f'(x_k)</math> then for a function <math>\phi(y) = f(Ay)</math> where <math>A</math> is a non-degenerate linear transformation, starting from <math>y_0 = A^{-1} x_0</math> we have the Newton steps <math>y_k = A^{-1} x_k</math> which can be shown recursively

: <math>y_{k+1} = y_k - [\phi''(y_k)]^{-1} \phi'(y_k) = y_k - [A^T f''(A y_k) A]^{-1} A^T f'(A y_k) = A^{-1} x_k - A^{-1}[f''(x_k)]^{-1} f'(x_k) = A^{-1} x_{k+1}</math>.

However, the standard analysis of the Newton method supposes that the Hessian of <math>f</math> is [[Lipschitz continuity|Lipschitz continuous]], that is <math>\|f''(x) - f''(y)\| \leq M\| x-y \|</math> for some constant <math>M</math>. If we suppose that <math>f</math> is 3 times continuously differentiable, then this is equivalent to

: <math>| \langle f'''(x)[u]v, v \rangle | \leq M \|u\| \|v\|^2</math>for all <math>u,v \in \mathbb{R}^n</math>

where <math>f'''(x)[u] = \lim_{\alpha \to 0} \alpha^{-1} [f''(x + \alpha u) - f''(x)]</math> . Then the left hand side of the above inequality is invariant under the [[affine transformation]] <math>f(x) \to \phi(y) = f(A y), u \to A^{-1} u, v \to A^{-1} v</math>, 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 <math>f</math> defined as <math>\| w \|_{f''(x)} = \langle f''(x)w, w \rangle^{1/2}</math> for <math>w \in \mathbb R^n</math>. They then arrive at the definition of a self concordant function as

: <math>| \langle f'''(x)[u]u, u \rangle | \leq M \langle f''(x) u, u \rangle^{3/2}</math>.

== Properties ==

=== Linear combination === If <math>f_1</math> and <math>f_2</math> are self-concordant with constants <math>M_1</math> and <math>M_2</math> and <math>\alpha,\beta>0</math>, then <math>\alpha f_1 + \beta f_2</math> is self-concordant with constant <math>\max(\alpha^{-1/2} M_1, \beta^{-1/2} M_2)</math>.

=== Affine transformation === If <math>f</math> is self-concordant with constant <math>M</math> and <math>Ax + b</math> is an affine transformation of <math>\mathbb R^n</math>, then <math>\phi(x) = f(Ax+b)</math> is also self-concordant with parameter <math>M</math>.

=== Convex conjugate === If <math>f</math> is self-concordant, then its [[convex conjugate]] <math>f^*</math> is also self-concordant.<ref name=siam>{{cite book |last1=Nesterov |first1=Yurii |last2=Nemirovskii |first2=Arkadii |date=1994 |title=Interior-Point Polynomial Algorithms in Convex Programming |volume=13|series=Studies in Applied and Numerical Mathematics |doi=10.1137/1.9781611970791 |isbn=978-0-89871-319-0 |oclc=29310677}}{{page needed|date=October 2024}}</ref><ref>{{cite journal |last1=Sun |first1=Tianxiao |last2=Tran-Dinh |first2=Quoc |title=Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods |journal=Mathematical Programming |date=2018 |page=Proposition 6 |arxiv=1703.04599 }}</ref>

=== Non-singular Hessian === If <math>f</math> is self-concordant and the domain of <math>f</math> contains no straight line (infinite in both directions), then <math>f''</math> is non-singular.

Conversely, if for some <math>x</math> in the domain of <math>f</math> and <math>u \in \mathbb R^n, u \neq 0</math> we have <math>\langle f''(x) u, u \rangle = 0</math>, then <math>\langle f''(x + \alpha u) u, u \rangle = 0</math> for all <math>\alpha</math> for which <math>x + \alpha u</math> is in the domain of <math>f</math> and then <math>f(x + \alpha u)</math> is linear and cannot have a maximum so all of <math>x + \alpha u, \alpha \in \mathbb R</math> is in the domain of <math>f</math>. We note also that <math>f</math> 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 function]]s used in [[interior point method]]s 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 <math>\mathbb R^n</math>.

Self-concordant barrier functions

* are a class of functions that can be used as barriers in constrained optimization methods * can be minimized using the Newton algorithm with provable convergence properties analogous to the usual case (but these results are somewhat more difficult to derive) * to have both of the above, the usual constant bound on the third derivative of the function (required to get the usual convergence results for the Newton method) is replaced by a bound relative to the Hessian

=== 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 <math>f</math> is a ''standard'' self-concordant function, that is it is self-concordant with parameter <math>M = 2</math>.

We define the ''Newton decrement'' <math>\lambda_f(x)</math> of <math>f</math> at <math>x</math> as the size of the Newton step <math>[f''(x)]^{-1} f'(x)</math> in the local norm defined by the Hessian of <math>f</math> at <math>x</math> :<math>\lambda_f(x) = \langle f''(x) [f''(x)]^{-1} f'(x), [f''(x)]^{-1} f'(x) \rangle^{1/2} = \langle [f''(x)]^{-1} f'(x), f'(x) \rangle^{1/2}</math> Then for <math>x</math> in the domain of <math>f</math>, if <math>\lambda_f(x) < 1</math> then it is possible to prove that the Newton iterate : <math>x_+ = x - [f''(x)]^{-1}f'(x)</math> will be also in the domain of <math>f</math>. This is because, based on the self-concordance of <math>f</math>, it is possible to give some finite bounds on the value of <math>f(x_+)</math>. We further have : <math>\lambda_f(x_+) \leq \Bigg( \frac{\lambda_f(x)}{1-\lambda_f(x)} \Bigg)^2</math>

Then if we have : <math>\lambda_f(x) < \bar\lambda = \frac{3-\sqrt 5}{2}</math> then it is also guaranteed that <math>\lambda_f(x_+) < \lambda_f(x)</math>, so that we can continue to use the Newton method until convergence. Note that for <math>\lambda_f(x_+) < \beta</math> for some <math>\beta \in (0, \bar\lambda)</math> we have quadratic convergence of <math>\lambda_f</math> to 0 as <math>\lambda_f(x_+) \leq (1-\beta)^{-2} \lambda_f(x)^2</math>. This then gives quadratic convergence of <math>f(x_k)</math> to <math>f(x^*)</math> and of <math>x</math> to <math>x^*</math>, where <math>x^* = \arg\min f(x)</math>, by the following theorem. If <math>\lambda_f(x) < 1</math> then : <math>\omega(\lambda_f(x)) \leq f(x)-f(x^*) \leq \omega_*(\lambda_f(x))</math> : <math>\omega'(\lambda_f(x)) \leq \| x-x^* \|_x \leq \omega_*'(\lambda_f(x))</math> with the following definitions : <math>\omega(t) = t - \log(1+t)</math> : <math>\omega_*(t) = -t-\log(1-t)</math> : <math>\| u \|_x = \langle f''(x) u, u \rangle^{1/2} </math>

If we start the Newton method from some <math>x_0</math> with <math>\lambda_f(x_0) \geq \bar\lambda</math> then we have to start by using a ''damped Newton method'' defined by :<math>x_{k+1} = x_k - \frac{1}{1+\lambda_f(x_k)}[f''(x_k)]^{-1}f'(x_k)</math> For this it can be shown that <math>f(x_{k+1}) \leq f(x_k) - \omega(\lambda_f(x_k))</math> with <math>\omega </math> as defined previously. Note that <math>\omega(t)</math> is an increasing function for <math>t > 0</math> so that <math>\omega(t) \geq \omega(\bar\lambda)</math> for any <math>t \geq \bar\lambda</math>, so the value of <math>f</math> is guaranteed to decrease by a certain amount in each iteration, which also proves that <math>x_{k+1}</math> is in the domain of <math>f</math>.

== References == {{Reflist}}

[[Category:Functions and mappings]]