Improving complexity of structured convex optimization problems using self-concordant barriers

Image Technical Report 0102

François Glineur^{∗}

Service de Mathématique et de Recherche Opérationnelle,

Faculté Polytechnique de Mons, Rue de Houdain, 9, B-7000 Mons, Belgium,

 Francois.Glineur@fpms.ac.be.

August 2001

∗The author is supported by a grant from the F.N.R.S. (Belgian National Fund for Scientific Research).

Abstract

The purpose of this paper is to provide improved complexity results for several classes of structured convex optimization problems using to the theory of self-concordant functions developed in [11]. We describe the classical short-step interior-point method and optimize its parameters in order to provide the best possible iteration bound. We also discuss the necessity of introducing two parameters in the definition of self-concordancy and which one is the best to fix. A lemma from [3] is improved, which allows us to review several classes of structured convex optimization problems and improve the corresponding complexity results.

Keywords. convex optimization, self-concordant barriers, interior-point methods, entropy optimization, geometric optimization, l_{p}-norm optimization.

Contents

1 Introduction 3

2 Self-concordancy and a polynomial short-step method 4 2.1 Equivalent definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Optimal complexity of a short-step method . . . . . . . . . . . . . . . . . . . 6

3 Using self-concordancy 10 3.1 Barrier calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Fixing a parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 A useful lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Application to structured convex problems 17 4.1 Extended entropy optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Dual geometric optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 l_{p}-norm optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5 Concluding remarks 20

1 Introduction

Convex optimization deals with the minimization of a convex function on a convex set, see e.g. [15, 18]. It is well-known that a problem involving a nonlinear objective function can be rewritten using a linear objective function, an additional constraint and one more variable, so that one can consider without loss of generality the following formulation

inf_{x∈ℝ^{n}} c^{T} x s.t. x ∈ C ,  (CL)

where the feasible set C ⊆ ℝ^{n} is convex and vector c ∈ ℝ^{n} defines the objective function.

We will also assume that C is full-dimensional, i.e. possesses a nonempty interior. This can be again be done without loss of generality, since a suitable change of variables can make the feasible set full-dimensional when the affine hull of C is a linear subspace different from ℝ^{n} (namely, supposing the dimension of the affine hull of the feasible set is equal to m < n, one can use any affine transformation mapping aff C to ℝ^{m}, see e.g. [15]).

Among the different types of algorithms that can be applied to solve problem (CL), interior-point methods have gained a lot of popularity in the last two decades, mainly because one can both give a polynomial bound on the number of arithmetic operations they need to reach a solution within a given accuracy and implement them to solve successfully real-world problems, especially in the fields of linear [1] (where they compare favourably with the simplex method on large-scale problems), quadratic and semidefinite optimization.

One traditional way to define C is to provide a list of convex constraints, i.e. C = {x ∈ ℝ^{n} | f_{i}(x) ≤ 0 ∀1 ≤ i ≤ m} where each of the m functions f_{i} : ℝ^{n} ↦ ℝ is convex. However, interior-point methods rely instead on the notion of barrier function for the feasible set C, according to the following definition.

Definition 1.1 Let C be a full-dimensional convex subset of ℝ^{n}. A function F : int C ↦ ℝ is a barrier function for the set C if and only if F is three times continuously differentiable, strictly convex and F (x) tends to +∞ whenever x tends to ∂C, the boundary of C.

Note that it is often possible to provide a suitable barrier function for a convex set C defined by convex constraints, using the logarithmic barrier [7] defined as

F : int C ↦ ℝ : x ↦ F (x) = − ∑_{i=1}^{m} log(−f_{i}(x)) .

We have however to make sure the resulting function satisfies all the properties of a barrier function (for example, defining C = ℝ_{+} with a single convex constraint using f_{1} : ℝ_{+} ↦ ℝ : x ↦ −x^{x} leads to F (x) = −x log x, which does not possess the barrier property).

Problem (CL) is thus replaced by a family of unconstrained minimization problems relying on the barrier function

inf_{x∈ℝ^{n}} \frac{c^{T} x}{μ} + F (x) ,  (CL_{μ})

parameterized by a barrier parameter μ ∈ ℝ_{++} (see the classical monograph [6]). Most interior-point methods then follow the so-called central path, i.e. the set of minimizers x(μ) of each of these problems^{1}, while decreasing μ to zero, which under some mild conditions leads them to an optimal solution of (CL).

1Uniqueness of these minimizers is guaranteed by the strict convexity of F, while their existence requires some additional assumptions, see [6].

Interior-point methods rely on Newton’s method to compute these minimizers, so that the following question becomes of interest: is it possible to choose a barrier function F such that Newton’s method is provably efficient in solving subproblems (CL_{μ}), leading to a polynomial algorithm for problem (CL) ? This crucial question is thoroughly answered by the theory of self-concordancy, first developed by Nesterov and Nemirovsky [11], which we will introduce in the next Section 2.

2 Self-concordancy and a polynomial short-step method

2.1 Equivalent definitions

Let us first present a definition of a self-concordant barrier^{2}.

Definition 2.1 Let C be a full-dimensional convex subset of ℝ^{n}. A function F : int C ↦ R is called a (κ, ν)-self-concordant barrier for C if and only if F is a barrier function for C and the following two conditions hold for all x ∈ int C and h ∈ ℝ^{n}:

∇^{3}F (x)[h, h, h] ≤ 2κ (∇^{2}F (x)[h, h])^{\frac{3}{2}} ,  (2.1)
∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x) ≤ ν  (2.2)

(the square root in (2.1) is well defined because of the requirement that F is convex).

We point out that no absolute value is needed in the left-hand side of (2.1): the apparently stronger condition

|∇^{3}F (x)[h, h, h]| ≤ 2κ (∇^{2}F (x)[h, h])^{3/2}  (2.3)

required by some authors is not needed since inequality (2.1) also has to hold in the direction opposite to h, which gives (using the fact that the n^{th}-order differential is homogeneous with degree n)

∇^{3}F (x)[−h, −h, −h] ≤ 2κ (∇^{2}F (x)[−h, −h])^{\frac{3}{2}} ⇔ −∇^{3}F (x)[h, h, h] ≤ 2κ (∇^{2}F (x)[h, h])^{\frac{3}{2}}

and shows that conditions (2.1) and (2.3) are equivalent.

Given a barrier function F and a point x belonging to its domain, it will be convenient to introduce the Newton step n(x) and the intrinsic inner product ⟨·, ·⟩_{x}^{3}:

n(x) = −(∇^{2}F (x))^{−1}∇F (x) and ⟨α, β⟩_{x} = ⟨α, ∇^{2}F (x)β⟩ .

The intrinsic norm ∥·∥_{x} will also be used according to the usual definition ∥a∥_{x} = \sqrt{⟨a, a⟩_{x}}.

Conditions (2.1) and (2.2) admit several equivalent reformulations, sometimes easier to work with, based on the restriction of F along a line. Let x ∈ int C and h ∈ ℝ^{n}, defining the line {x + th | t ∈ ℝ} and let us introduce the one-dimensional function F_{x,h} : ℝ ↦ ℝ : t ↦ F (x + th).

2This definition does not exactly match the definition of a self-concordant barrier originally stated in [11], but corresponds in fact to the notion of strongly non-degenerate κ^{−2}-self-concordant barrier functional with parameter ν. Our main restriction with respect to the original theory of [11] is the requirement that F be strictly convex, equivalent to the notion of non-degeneracy in [11], which is essentially needed for technical reasons and does not really reduce the generality of the approach (see the discussion at the end of [14, Chapter 2.5]).

3Renegar [14] points out that while the gradient and Hessian of F, i.e. its first- and second-order differentials do depend from the choice of reference inner product used in their definition, the intrinsic norm and inner products as well as the Newton step are in fact independent from this choice, so that their use leads to an essentially coordinate-free development of the theory.

Theorem 2.1 The following four conditions are equivalent:

∇^{3}F (x)[h, h, h] ≤ 2κ (∇^{2}F (x)[h, h])^{\frac{3}{2}} for all x ∈ int C and h ∈ ℝ^{n}  (2.4a)
F′′′_{x,h}(0) ≤ 2κF′′_{x,h}(0)^{\frac{3}{2}} for all x ∈ int C and h ∈ ℝ^{n}  (2.4b)
F′′′_{x,h}(t) ≤ 2κF′′_{x,h}(t)^{\frac{3}{2}} for all x + th ∈ int C and h ∈ ℝ^{n}  (2.4c)
(−\frac{1}{\sqrt{F′′_{x,h}(t)}})′ ≤ κ for all x + th ∈ int C and h ∈ ℝ^{n} .  (2.4d)

Proof . Since F_{x,h}(t) = F (x + th), we can write

F′_{x,h}(t) = ∇F (x + th)[h], F′′_{x,h}(t) = ∇^{2}F (x + th)[h, h] and F′′′_{x,h}(t) = ∇^{3}F (x + th)[h, h, h] .

Condition (2.4b) is thus simply condition (2.4a) written differently. Moreover, condition (2.4c) is equivalent to condition (2.4a) written for x + th instead of x. Finally, we note that

(−\frac{1}{\sqrt{F′′_{x,h}(t)}})′ ≤ κ ⇔ \frac{1}{2}F′′_{x,h}(t)^{− \frac{3}{2}} F′′′_{x,h}(t) ≤ κ ⇔ F′′′_{x,h}(t) ≤ 2κF′′_{x,h}(t)^{\frac{3}{2}} ,

which shows that (2.4d) and (2.4c) are equivalent. □

Theorem 2.2 The following four conditions are equivalent:

∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x) ≤ ν for all x ∈ int C  (2.5a)
F′_{x,h}(0)^{2} ≤ νF′′_{x,h}(0) for all x ∈ int C and h ∈ ℝ^{n}  (2.5b)
F′_{x,h}(t)^{2} ≤ νF′′_{x,h}(t) for all x + th ∈ int C and h ∈ ℝ^{n} (2.5c)
(−\frac{1}{F′_{x,h}(t)})′ ≥ \frac{1}{ν} for all x + th ∈ int C and h ∈ ℝ^{n} .  (2.5d)

Proof . We first show that condition (2.5b) implies condition (2.5a).

(∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x))^{2} = F′_{x,n(x)}(0)^{2}
≤ νF′′_{x,n(x)}(0) = ν∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x) ,

which implies condition (2.5a). Considering now the reverse implication, we have

F′_{x,h}(0)^{2} = (∇F (x)^{T} h)^{2} = (∇F (x)^{T} (∇^{2}F (x))^{−1}∇^{2}F (x)h)^{2} = ⟨n(x), h⟩_{x}^{2}
≤ ∥(n(x)∥_{x}^{2} ∥h∥_{x}^{2} (using the Cauchy-Schwarz inequality)
= (∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x)) (h^{T} ∇^{2}F (x)h) ≤ νF′′_{x,h}(0) .

Condition (2.5c) is condition (2.5b) written for x + th instead of x, and we finally note that

(−\frac{1}{F′_{x,h}(t)})′ ≥ \frac{1}{ν} ⇔ F′_{x,h}(t)^{−2}F′′_{x,h}(t) ≥ \frac{1}{ν} ⇔ νF′′_{x,h}(t) ≥ F′_{x,h}(t)^{2} ,

which shows that (2.5d) and (2.5c) are equivalent. □

The first three reformulations for each condition are well-known and can be found for example in [11, 10, 14]. Conditions (2.4d) and (2.5d) are less commonly seen (they were however mentioned in [2]).

2.2 Optimal complexity of a short-step method

Interior-point methods for convex optimization rely on a barrier function and the associated central path to solve problem (CL). Iterates x_{k} will be required to lie in a prescribed neighbourhood of the central path (since computing points that lie exactly on the central is too costly) while the barrier parameter μ_{k} will tend to zero.

A good measure of the proximity to the central path would be ∥x_{k} − x(μ_{k})∥_{x_{k}}, but the fact it involves the unknown central point x(μ_{k}) makes it difficult to use in the analysis. We will instead rely on the following elegant proximity measure: we define δ(x, μ), a measure of the proximity of x to the central point x(μ), to be the intrinsic norm of n_{μ}(x), the Newton step trying to minimize the objective in problem (CL_{μ}) (aiming thus at x(μ_{k})), i.e.

n_{μ}(x) = −(∇^{2}F (x))^{−1}(\frac{c}{μ} + ∇F (x)) = −\frac{1}{μ}(∇^{2}F (x))^{−1}c + n(x) and δ(x, μ) = ∥n_{μ}(x)∥_{x}

(note that both n_{μ}(x) and ∥n_{μ}(x)∥_{x} are independent of the coordinate system).

The principle lying behind a short-step interior-point method is to trace the central path approximately, ensuring that the proximity δ(x_{k}, μ_{k}) at each iteration is kept below a predefined bound. Given a problem of type (CL), a barrier function F for the feasible set C, an upper bound on the proximity measure τ > 0, a decrease parameter 0 < θ < 1 and an initial iterate x_{0} such that δ(x_{0}, μ_{0}) < τ, we set k ← 0 and perform the following main loop:

(1) μ_{k+1} ← μ_{k}(1 − θ) (decrease the barrier parameter)
(2) x_{k+1} ← x_{k} + n_{μ_{k+1}}(x_{k}) (take a Newton step)
(3) k ← k + 1

The key is to choose parameters τ and θ such that δ(x_{k}, μ_{k}) < τ implies δ(x_{k+1}, μ_{k+1}) < τ, so that proximity to the central path is preserved at each iteration. Indeed, it is precisely the self-concordancy of the barrier function that will guarantee that such a choice is possible. Our goal now is to find optimal values for this pair of parameters, i.e. leading to a minimum number of iterations.

In order to relate the two proximities δ(x_{k}, μ_{k}) and δ(x_{k+1}, μ_{k+1}), it is useful to introduce an intermediate quantity δ(x_{k}, μ_{k+1}), the proximity from an iterate to its next target on the central path. We have the following two properties:

Theorem 2.3 Let F be a barrier function satisfying (2.2), x ∈ dom F and μ^{+} = (1 − θ)μ. We have

δ(x, μ^{+}) ≤ \frac{δ(x, μ) + θ\sqrt{ν}}{1 − θ} .

Proof . We have

μ^{+}n_{μ^{+}}(x) − μ^{+}n(x) = −(∇^{2}F (x))^{−1}c = μn_{μ}(x) − μn(x)
(dividing by μ) ⇔ (1 − θ)n_{μ^{+}}(x) − (1 − θ)n(x) = n_{μ}(x) − n(x)
⇒ (1 − θ) ∥n_{μ^{+}}(x)∥_{x} ≤ ∥n_{μ}(x)∥_{x} + θ ∥n(x)∥_{x}
⇒ (1 − θ)δ(x, μ^{+}) ≤ δ(x, μ) + θ\sqrt{ν} ,

which implies the desired inequality, where the last implication used the fact that

∥n(x)∥_{x} = \sqrt{∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x)} ≤ \sqrt{ν} ,

because of condition (2.2). □

Theorem 2.4 Let F be a barrier function satisfying (2.1) and x ∈ dom F. Let us suppose δ(x, μ) < \frac{1}{κ}. We have that x + n_{μ}(x) ∈ dom F and

δ(x + n_{μ}(x), μ) ≤ \frac{κδ(x, μ)^{2}}{(1 − κδ(x, μ))^{2}} .

(this proof is more technical and is omitted here ; it can be found in [10, 11, 14]).

Note 2.1 The reason why the self-concordancy property relies on two separate conditions becomes clear: one of them is responsible for the control of the increase of the proximity measure when the target on the central path is updated (Theorem 2.3), while the other guarantees that the proximity to the target can be restored, i.e. sufficiently decreased when taking a Newton step (Theorem 2.4).

Assuming for the moment that τ and θ can be chosen such that the proximity to central path is preserved at each iteration, we see that the number of iterations needed to attain a certain value of the barrier parameter μ_{e} depends solely on the ratio \frac{μ_{0}}{μ_{e}} and the value of θ. Namely, since μ_{k} = (1 − θ)^{k}μ_{0}, it is readily seen that this number of iterations is equal to

⌈log_{(1−θ)} \frac{μ_{e}}{μ_{0}} ⌉ = ⌈\frac{1}{log(1 − θ)} log \frac{μ_{e}}{μ_{0}} ⌉ .  (2.6)

Given a (κ, ν)-self-concordant barrier, we are now going to find a suitable pair of parameters τ and θ providing the greatest reduction for the parameter μ at each iteration, in other words maximizing θ in order to get the lowest possible total iteration count. Letting δ = δ(x_{k}, μ_{k}), δ′ = δ(x_{k}, μ_{k+1}) and δ^{+} = δ(x_{k+1}, μ_{k+1}) and assuming δ ≤ τ, we have to satisfy δ^{+} ≤ τ with the greatest possible value for θ.

Let us assume first that δ′ < \frac{1}{κ}. Using Theorem 2.4, we find that

δ^{+} ≤ \frac{κδ′^{2}}{(1 − κδ′)^{2}} and therefore require that \frac{κδ′^{2}}{(1 − κδ′)^{2}} ≤ τ .

This is equivalent to

(\frac{κδ′}{1 − κδ′} )^{2} ≤ κτ ⇔ (\frac{1}{κδ′} − 1)^{2} ≥ \frac{1}{κτ} ⇔ \frac{1}{κδ′} ≥ 1 + \frac{1}{\sqrt{κτ}}

(which also shows that the assumption κδ′ < 1 we made in the beginning was valid). Using now Theorem 2.3, we know that

δ′ ≤ \frac{δ + θ\sqrt{ν}}{1 − θ} ⇒ δ′ ≤ \frac{τ + θ\sqrt{ν}}{1 − θ} ⇔ \frac{1}{κδ′} ≥ \frac{1 − θ}{κτ + θκ\sqrt{ν}}

and thus require that

\frac{1 − θ}{κτ + θκ\sqrt{ν}} ≥ 1 + \frac{1}{\sqrt{κτ}} .

Letting β = \sqrt{κτ} and Γ = κ\sqrt{ν} (we call this quantity the complexity value of the barrier since it plays an important role in the complexity analysis), we have

\frac{1 − θ}{β^{2} + θΓ} ≥ 1 + \frac{1}{β} ⇔ 1 − θ ≥ (1 + \frac{1}{β})(β^{2} + Γθ) ⇔ 1 − β − β^{2} ≥ θ (1 + Γ + \frac{Γ}{β}) ,

which finally means that maximum the value of θ that guarantees δ^{+} ≤ τ is given by

θ = \frac{1 − β − β^{2}}{1 + Γ + \frac{Γ}{β}} .  (2.7)

Computing the derivative of this quantity with respect to β shows that it is maximum when β satisfies 2β^{3}(1 + Γ) + β^{2}(1 + 4Γ) + 2βΓ − Γ = 0 or equivalently when

Γ = −\frac{β^{2}(2β + 1)}{2β^{3} + 4β^{2} + 2β − 1} ,  (2.8)

the corresponding graph being depicted on Figure 1. Possible values for Γ ranging from 1 to +∞ (proof of the nontrivial fact that Γ is never less than 1 can be found in [11]), straightforward computations show that the corresponding values of β range from β_{−} ≈ 0.273 to β^{+} ≈ 0.297 (satisfying respectively 4β_{−}^{3} +5β_{−}^{2} +2β_{−} −1 = 0 and 2β_{+}^{3} +4β_{+}^{2} +2β_{+} −1 = 0). Unfortunately, the corresponding explicit analytical expression β = h(Γ) is too complicated^{4} to be stated here. However, leaving β as a function of Γ, we can evaluate the maximal value of θ as follows: plugging the value of Γ given by (2.8) into (2.7) gives after some manipulations the simple expression θ = 1 − 2β − 4β^{2} − 2β^{3}, which using again (2.8) provides the equality

θ = \frac{β^{2}(2β + 1)}{Γ} ,  (2.9)

which will prove useful later.

Figure 1: Graph of the relation β = h(Γ).

Before we state our final complexity result, we have to discuss termination of the algorithm. The most practical stopping criterion is a small target value μ_{e} for the barrier parameter, which directly relates to the iteration bound given in (2.6). Our final iterate x_{e} will thus satisfy δ(x_{e}, μ_{e}) ≤ τ, which tells us it is not too far from x(μ_{e}), itself not too far from the optimum since μ_{e} is small. Indeed, using again the self-concordancy property of F, it is possible to derive the following bound on the accuracy of the final objective c^{T} x_{e}, i.e. its deviation from the optimal objective c^{T} x^{∗}

4It is indeed the real root of a cubic equation and can be computed without effort for any value of Γ.

c^{T} x_{e} − c^{T} x^{∗} ≤ \frac{μ_{e}}{1 − 3κτ} κ\sqrt{ν}  (2.10)

(proof of this fact is omitted here and can easily be obtained combining Theorems 2.2.5 and 2.3.3 in [14]). We are now ready to state our final complexity result:

Theorem 2.5 Given a convex optimization problem (CL), a (κ, ν)-self-concordant barrier F for C, a constant β = h(κ\sqrt{ν}) and an initial iterate x_{0} such that δ(x_{0}, μ_{0}) < \frac{β^{2}}{κ}, one can find a solution with accuracy ϵ in

⌈(\frac{κ\sqrt{ν}}{β^{2}(2β + 1)} − \frac{1}{2}) log \frac{μ_{0}κ\sqrt{ν}}{ϵ(1 − 3β^{2})}⌉ iterations.

Proof . Using the optimal value β = h(κ\sqrt{ν}), the maximal value for θ given by (2.7), the fact that κτ = β^{2} and the bound on the objective accuracy in (2.10), we find that the stopping threshold on the barrier parameter μ_{e} must satisfy

\frac{μ_{e}}{1 − 3β^{2}} κ\sqrt{ν} ≤ ϵ ⇔ μ_{e} ≤ \frac{ϵ(1 − 3β^{2})}{κ\sqrt{ν}} .

Plugging this value into (2.6) we find that the total number of iterations can be bounded by (omitting the rounding bracket for clarity)

\frac{1}{log(1 − θ)} log \frac{μ_{e}}{μ_{0}} ≤ \frac{1}{log(1 − θ)} log \frac{ϵ(1 − 3β^{2})}{μ_{0}κ\sqrt{ν}} = −\frac{1}{log(1 − θ)} log \frac{μ_{0}κ\sqrt{ν}}{ϵ(1 − 3β^{2})}
≤ (\frac{1}{θ} − \frac{1}{2}) log \frac{μ_{0}κ\sqrt{ν}}{ϵ(1 − 3β^{2})} = (\frac{κ\sqrt{ν}}{β^{2}(2β + 1)} − \frac{1}{2}) log \frac{μ_{0}κ\sqrt{ν}}{ϵ(1 − 3β^{2})} ,

as announced (the second inequality uses the fact that \frac{1}{log(1−θ)} ≥ \frac{1}{2} − \frac{1}{θ}, which can be easily derived using the Taylor series of log x around 1, while the equality uses equation (2.9)). □

This result is not very explicit since it still involves the constant β. However, using the fact that β is lower bounded by β_{−} ≈ 0.273, one can easily derive the following corollary:

Corollary 2.1 Given a convex optimization problem (CL), a (κ, ν)-self-concordant barrier F for C and an initial iterate x_{0} such that δ(x_{0}, μ_{0}) < \frac{1}{13.42κ}, one can find a solution with accuracy ϵ in

⌈(8.68κ\sqrt{ν} − \frac{1}{2}) log \frac{1.29μ_{0}κ\sqrt{ν}}{ϵ} ⌉ iterations.

It is also interesting to note that the value of the coefficient of κ\sqrt{ν} in the leading factor of the number of iterations can be further lowered if a larger lower bound on κ\sqrt{ν} is assumed. Indeed, coefficient 8.68 becomes 7.90 if κ\sqrt{ν} ≥ 2, 7.43 if κ\sqrt{ν} ≥ 5, 7.27 if κ\sqrt{ν} ≥ 10 and tends to 7.10 when κ\sqrt{ν} tends to +∞. This improves several similar results from the literature, e.g. 9κ\sqrt{ν} in [10] and 1 + 8κ\sqrt{ν} in [14].

Moreover, one can compare these values with the corresponding ones valid in the special case of linear optimization. Recalling that κ\sqrt{ν} is equal to \sqrt{n} in the case of a linear optimization problem involving n nonnegative variables and equipped with the standard logarithmic barrier, we see that a similar short-step algorithm described in [17, Theorem II.24]^{5} achieves an iteration bound featuring a leading factor equal to 3\sqrt{n}, noticeably lower than our result for the general convex case.

3 Using self-concordancy

3.1 Barrier calculus

The previous section has made clear that the self-concordancy property of the barrier function F is essential to derive a polynomial bound on the number of iterations of the short-step method. Moreover, smaller values for parameters κ and ν imply a lower total complexity. The next question we may ask ourselves is how to find self-concordant barriers (ideally with low parameters).

An impressive result contained in [11] states that every convex set in ℝ^{n} admits a (K, n)- self-concordant barrier, where K is a universal constant (independent of n). However, the universal barrier exhibited in their proof is defined as a volume integral over an n-dimensional convex body, and is therefore very difficult to evaluate in practice, even for simple sets in low-dimensional spaces. Another potential problem with this approach is that evaluating this barrier (and/or its gradient and Hessian) might very well take a number of arithmetic operations that grows exponentially with n, which would lead to an exponential total algorithmic complexity for the short-step method, despite the polynomial iteration bound.

Another approach to find self-concordant barriers, termed barrier calculus in [11], consists in combining basic self-concordant barriers using operations that are known to preserve selfconcordancy. We now proceed to briefly describe two of these self-concordancy preserving operations, positive scaling and addition, and examine how the associated parameters are affected in the process.

Let us start with positive scalar multiplication.

Theorem 3.1 Let F be a (κ, ν)-self-concordant barrier for C ⊆ ℝ^{n} and λ ∈ ℝ_{++} a positive scalar. Then (λF) is also a self-concordant barrier for C with parameters (\frac{κ}{\sqrt{λ}}, λν).

Proof . It is clear that (λF) is also a barrier function (i.e. smoothness, strict convexity and the barrier property are obviously preserved by scaling). Since F is (κ, ν)-self-concordant, we have for all x ∈ int C and h ∈ ℝ^{n} (using Theorems 2.1 and 2.2)

F′′′_{x,h}(0) ≤ 2κF′′_{x,h}(0)^{\frac{3}{2}} and F′_{x,h}(0)^{2} ≤ νF′′_{x,h}(0)

which is clearly equivalent to

(λF)′′′_{x,h}(0) ≤ 2\frac{κ}{\sqrt{λ}}((λF)′′_{x,h}(0))^{\frac{3}{2}} and ((λF)′_{x,h}(0))^{2} ≤ λν(λF)′′_{x,h}(0) ,

which is precisely stating that (λF) is (\frac{κ}{\sqrt{λ}}, λν)-self-concordant. □

This theorem show that self-concordancy is preserved by positive scalar multiplication, but that parameters κ and ν are both modified. It is interesting to note that these parameters do not occur individually in the iteration bound of Theorem 2.5 but are rather always appearing together in the expression κ\sqrt{ν}. This quantity, which we call the complexity value of the barrier, is solely responsible for the polynomial iteration bound. Looking at what happens to it when F is scaled by λ, we find that the scaled complexity value is equal to \frac{κ}{\sqrt{ν}} \sqrt{λν} = κ\sqrt{ν}, i.e. that the complexity value is invariant to scaling. This means in fine that scaling a selfconcordant barrier does not influence the algorithmic complexity of the associated short-step method, a property than could reasonably be expected from the start.

5Using a primal-dual algorithm, [17, Remark II.54] further lowers this bound to achieve a leading factor equal to \sqrt{n} as soon as n ≥ 8.

Let us now examine what happens when two self-concordant barriers are added.

Theorem 3.2 Let F be a (κ_{1}, ν_{1})-self-concordant barrier for C_{1} ⊆ ℝ^{n} and G be a (κ_{2}, ν_{2})- self-concordant barrier for C_{2} ⊆ ℝ^{n}. Then (F + G) is a self-concordant barrier for C_{1} ∩ C_{2} (provided this intersection is nonempty) with parameters (max{κ_{1}, κ_{2}}, ν_{1} + ν_{2}).

Proof . It is straightforward to see that (F + G) is a barrier function for C_{1} ∩ C_{2}. We write

(F + G)′′′_{x,h} ≤ 2κ_{1}F′′_{x,h}^{\frac{3}{2}} + 2κ_{2}G′′_{x,h}^{\frac{3}{2}}
≤ 2 max\{κ_{1}, κ_{2}\}(F′′_{x,h}^{\frac{3}{2}} + G′′_{x,h}^{\frac{3}{2}} ) ≤ 2 max\{κ_{1}, κ_{2}\}(F + G)′′_{x,h}^{\frac{3}{2}}

and

|(F + G)′_{x,h}| ≤ |F′_{x,h}| + |G′_{x,h}| ≤ \sqrt{ν_{1}}\sqrt{F′′_{x,h}} + \sqrt{ν_{2}}\sqrt{G′′_{x,h}} ≤ \sqrt{ν_{1} + ν_{2}}\sqrt{(F + G)′′_{x,h}}

which is exactly stating that (F + G) is (max{κ_{1}, κ_{2}}, ν_{1} + ν_{2})-self-concordant. □

3.2 Fixing a parameter

As mentioned above, scaling a barrier function with a positive scalar does not affect its selfconcordancy, i.e. its suitability as a tool for convex optimization, and leaves its complexity value unchanged. One can thus make the decision to fix one of the two parameters κ and ν arbitrarily and only work with the corresponding subclass of barrier, without any real loss of generality. We describe now two choices of this kind that have been made in the literature.

First choice. Some authors [3, 4, 9, 16] choose to work with the second parameter ν fixed to one. However, this choice is not made explicitly but results from the particular structure of the barrier functions that are considered. Indeed, these authors consider convex optimization problems whose feasible sets are given by a list convex constraints and rely on the logarithmic barrier described in the introduction. The following lemma will prove useful.

Lemma 3.1 Let f : ℝ^{n} ↦ ℝ ∪ {+∞} be a convex function, C = {x ∈ ℝ^{n} | f(x) ≤ 0} and define the logarithmic barrier F : int C ↦ ℝ ∪ {+∞} : x ↦ − log(−f(x)). We have that F satisfies the second condition of self-concordancy (2.2) with parameter ν = 1.

Proof . Using the equivalent condition (2.5b) of Theorem 2.2, we have to evaluate the following quantities for x ∈ int C, h ∈ ℝ^{n} and t = 0

F′_{x,h}(t) = −\frac{∇f(x + th)[h]}{f(x + th)} and F′′_{x,h}(t) = \frac{∇f(x + th)[h]^{2} − ∇^{2}f(x + th)[h, h]f(x + th)}{f(t + th)^{2}} ,

which implies

F′_{x,h}(0)^{2} = \frac{∇f(x)[h]^{2}}{f(x)^{2}} ≤ \frac{∇f(x)[h]^{2} − ∇^{2}f(x)[h, h]f(x)}{f(x)^{2}} = F′′_{x,h}(0)

(where we have used the fact that ∇^{2}f(x)[h, h] ≥ 0 because f is convex and f(x) ≤ 0 because x belongs to the feasible set C), which states that F satisfies the second self-concordancy condition (2.2) with ν = 1. □

Since the logarithmic barrier corresponding to a set defined by several convex constraints is a sum of terms for which this lemma is applicable, we can use Theorem 3.2 to find that it satisfies the same condition with ν = m, the number of constraints.

This means that we only have to check the first condition (2.1) involving κ to establish selfconcordancy for the logarithmic barrier. Assuming that each individual term − log(−f_{i}(x)) can be shown to satisfy it with κ = κ_{i}, we have that the whole logarithmic barrier is (max_{i∈I}\{κ_{i}\}, m)-self-concordant, which leads to a complexity value equal to ∥κ∥_{∞} \sqrt{m}, where we have defined κ = (κ_{1}, κ_{2}, …, κ_{m}).

Second choice. Another arbitrary choice of self-concordance parameters that one encounters frequently in the literature consists in fixing κ = 1 in the first self-concordancy condition (2.1). This approach has been used increasingly in the recent years (see e.g. [10, 11, 14]), and we give here a justification of its superiority over the alternative presented above.

Let us consider the same logarithmic barrier, and suppose again that each individual term F_{i} : x ↦ − log(−f_{i}(x)) has been shown to satisfy the first self-concordancy condition (2.1) with κ = κ_{i}. Our previous discussion implies thus that F_{i} is (κ_{i}, 1)-self-concordant. Multiplying now F_{i} with κ_{i}^{2}, Theorem 3.1 implies that κ_{i}^{2}F_{i} is (1, κ_{i}^{2})-self-concordant. The corresponding complete scaled logarithmic barrier

F̃ : x ↦ − ∑_{i∈I} κ_{i}^{2} log(−f_{i}(x))

is then (1, ∑_{i∈I} κ_{i}^{2})-self-concordant by virtue of Theorem 3.2, which leads finally to a com-

plexity value equal to \sqrt{∑_{i∈I} κ_{i}^{2}} = ∥κ∥_{2}. This quantity is always lower than the complexity value for the standard logarithmic barrier considered above because of the well-known norm inequality ∥κ∥_{2} ≤ \sqrt{m} ∥κ∥_{∞}, which proves the superiority of this second approach (the only case where they are equivalent is when all parameters κ_{i}’s are equal).

Note 3.1 The fundamental reason why the first approach is less efficient is that it may combine barriers with different κ parameters, with the consequence that only the largest value max_{i∈I}{κ_{i}} appears in the final complexity value (the other smaller values becoming completely irrelevant cannot influence the final complexity at all). The second approach avoids this situation by ensuring that κ is always equal to one, which means that κ’s are equal for each combination and that the final complexity is really depending on the parameters of all the terms of the logarithmic barrier.

3.3 A useful lemma

We have seen so far how to construct self-concordant barrier by combining simpler functionals but still have no tool to prove self-concordancy of these basic barriers. The purpose of this section is to present a lemma that can help us in that regard. Let us first introduce two auxiliary functions r_{1} and r_{2}, whose graphs are depicted in Figure 2:

r_{1} : ℝ ↦ ℝ : γ ↦ max\{1, \frac{γ}{\sqrt{3 − 2/γ}} \} and r_{2} : ℝ ↦ ℝ : γ ↦ max\{1, \frac{γ + 1 + 1/γ}{\sqrt{3 + 4/γ + 2/γ^{2}}} \} .

Both of these functions are equal to 1 for γ ≤ 1 and strictly increasing for γ ≥ 1, with the asymptotic approximations r_{1}(γ) ≈ \frac{γ}{\sqrt{3}} and r_{2}(γ) ≈ \frac{γ+1}{\sqrt{3}} when γ tends to +∞.

Figure 2: Graphs of functions r_{1} and r_{2}

Lemma 3.2 Let us suppose F is a convex function defined on int C ⊆ ℝ_{++}^{n} and that there exists a constant γ such that

∇^{3}F (x)[h, h, h] ≤ 3γ∇^{2}F (x)[h, h]\sqrt{∑_{i=1}^{n} \frac{h_{i}^{2}}{x_{i}^{2}}} for all x ∈ int C and h ∈ ℝ^{n} .  (3.1)

We have that

F_{1} : int C ↦ ℝ : x ↦ F (x) − ∑_{i=1}^{n} log x_{i}

satisfies the first condition of self-concordancy (2.1) with parameter κ_{1} = r_{1}(γ) on its domain and, defining epi F = {(x, u) ∈ C × ℝ| F (x) ≤ u}

F_{2} : int epi F ↦ ℝ : (x, u) ↦ − log(u − F (x)) − ∑_{i=1}^{n} log x_{i}

satisfies the first condition of self-concordancy (2.1) with parameter κ_{2} = r_{2}(γ) on its domain.

Note 3.2 This lemma originates from a similar result is proved in [3] with parameters κ_{1} and κ_{2} both equal to 1 + γ. The second result is improved in [10], with κ_{2} equal to max{1, γ}, as a special case of a more general compatibility theory developed in [11]. However, it is easy to see that our result is better. Indeed, our parameters are strictly lower in all cases for F_{1} and as soon as γ > 1 for F_{2}, with an asymptotical ratio of \sqrt{3} when γ tends to +∞.

Proof . We follow the lines of [3] and start with F_{1}: computing its second and third differentials gives

∇^{2}F_{1}(x)[h, h] = ∇^{2}F (x)[h, h] + ∑_{i=1}^{n} \frac{h_{i}^{2}}{x_{i}^{2}} and ∇^{3}F_{1}(x)[h, h, h] = ∇^{3}F (x)[h, h, h] − 2 ∑_{i=1}^{n} \frac{h_{i}^{3}}{x_{i}^{3}} .

Introducing two auxiliary variables a ∈ ℝ_{+} and b ∈ ℝ_{+} such that

a^{2} = ∇^{2}F [h, h] and b^{2} = ∑_{i=1}^{n} \frac{h_{i}^{2}}{x_{i}^{2}}

(convexity of F ensures that a is real), we rewrite condition (3.1) as ∇^{3}F (x)[h, h, h] ≤ 3γa^{2}b. Combining it with the fact that

|(∑_{i=1}^{n} \frac{h_{i}^{3}}{x_{i}^{3}} )^{\frac{1}{3}} | ≤ (∑_{i=1}^{n} \begin{matrix}|h_{i}| & 3 \\ |x_{i}| & 3 \end{matrix} )^{\frac{1}{3}} ≤ (∑_{i=1}^{n} \frac{h_{i}^{2}}{x_{i}^{2}} )^{\frac{1}{2}} = b ,  (3.2)

where the second inequality comes from the well-known relation ∥·∥_{3} ≤ ∥·∥_{2} applied to vector (\frac{h_{1}}{x_{1}} , …, \frac{h_{n}}{x_{n}}), we find that

\frac{∇^{3}F_{1}(x)[h, h, h]}{2(∇^{2}F_{1}(x)[h, h])^{\frac{3}{2}}} ≤ \frac{3γa^{2}b + 2b^{3}}{2(a^{2} + b^{2})^{\frac{3}{2}}} .

According to (2.1), finding the best parameter κ for F_{1} amounts to maximize this last quantity depending on a and b. Since a ≥ 0 and b ≥ 0, we can write a = r cos θ and b = r sin θ with r ≥ 0 and 0 ≤ θ ≤ \frac{π}{2} , which gives

\frac{3γa^{2}b + 2b^{3}}{2(a^{2} + b^{2})^{\frac{3}{2}}} = \frac{3γ}{2} cos^{2} θ sin θ + sin^{3} θ = h(θ) .

The derivative of h is

h′(θ) = \frac{3γ}{2} cos^{3} θ − 3γ sin^{2} θ cos θ + 3 cos θ sin^{2} θ = 3 cos θ (\frac{γ}{2} cos^{2} θ + (1 − γ) sin^{2} θ) .

When γ ≤ 1, this derivative is clearly always nonnegative, which implies that the maximum is attained for the largest value of θ, which gives h_{max} = h(\frac{π}{2} ) = 1 = r_{1}(γ). When γ > 1, we easily see that h has a maximum when \frac{γ}{2} cos^{2} θ + (1 − γ) sin^{2} θ = 0. This condition is easily seen to imply sin^{2} θ = \frac{γ}{3γ−2}, and h_{max} becomes

h_{max} = 3\frac{γ}{2} cos^{2} θ sin θ + sin^{3} θ = (3(γ − 1) + 1) sin^{3} θ
= (3γ − 2) (\frac{γ}{3γ − 2})^{\frac{3}{2}} = \frac{γ}{\sqrt{3 − 2/γ}} = r_{1}(γ) .

A similar but slightly more technical proof holds for F_{2}. Letting x̃ = (x, u), h̃ = (h, v) and G(x̃) = F (x) − u, we have that F_{2}(x̃) = − log(−G(x̃)) − ∑_{i=1}^{n} log x_{i}. G is easily shown to be convex and negative on int epi F, the domain of F_{2}. Since F and G only differ by a linear term, we also have that ∇^{2}F (x)[h, h] = ∇^{2}G(x̃)[h̃, h̃] and ∇^{3}F (x)[h, h, h] = ∇^{3}G(x̃)[h̃, h̃, h̃]. Looking now at the second differential of F_{2} we find

∇^{2}F_{2}(x̃)[h̃, h̃] = \frac{∇G(x̃)[h]^{2}}{G(x̃)^{2}} − \frac{∇^{2}G(x̃)[h̃, h̃]}{G(x̃)} + ∑_{i=1}^{n} \frac{h_{i}^{2}}{x_{i}^{2}} .

Let us again define for convenience a ∈ ℝ_{+}, b ∈ ℝ_{+} and c ∈ ℝ with

a^{2} = −\frac{∇^{2}G(x̃)[h̃, h̃]}{G(x̃)}, b^{2} = ∑_{i=1}^{n} \frac{h_{i}^{2}}{x_{i}^{2}} and c = −\frac{∇G(x̃)[h]}{G(x̃)}

(convexity of G and the fact that it is negative on the domain of F_{2} guarantee that a is real), which implies ∇^{2}F_{2}(x)[h̃, h̃] = a^{2} + b^{2} + c^{2}. We can now evaluate the third differential

∇^{3}F_{2}(x̃)[h̃, h̃, h̃] = −\frac{∇^{3}G(x̃)[h̃, h̃, h̃]}{G(x̃)} + 3\frac{∇^{2}G(x̃)[h̃, h̃]∇G(x̃)[h̃]}{G(x̃)^{2}} − 2\frac{∇G(x̃)[h̃]^{3}}{G(x̃)^{3}} − 2 ∑_{i=1}^{n} \frac{h_{i}^{3}}{x_{i}^{3}}

= −\frac{∇^{3}G(x̃)[h̃, h̃, h̃]}{G(x̃)} + 3a^{2}c + 2c^{3} − 2 ∑_{i=1}^{n} \frac{h_{i}^{3}}{x_{i}^{3}}

≤ −\frac{∇^{3}G(x̃)[h̃, h̃, h̃]}{∇^{2}G(x̃)[h̃, h̃]} \frac{∇^{2}G(x̃)[h̃, h̃]}{G(x̃)} + 3a^{2}c + 2c^{3} + 2b^{3} using again (3.2)
= −\frac{∇^{3}F (x)[h, h, h]}{∇^{2}F (x)[h, h]} \frac{∇^{2}G(x̃)[h̃, h̃]}{G(x̃)} + 3a^{2}c + 2c^{3} + 2b^{3}
≤ 3γa^{2}b + 3a^{2}c + 2c^{3} + 2b^{3} using condition (3.1) .

According to (2.1), finding the best parameter κ for F_{2} amounts to maximize the following ratio

\frac{∇^{3}F_{2}(x̃)}{2(∇^{3}F_{2}(x̃))^{\frac{3}{2}}} ≤ \frac{3γa^{2}b + 3a^{2}c + 2c^{3} + 2b^{3}}{2(a^{2} + b^{2} + c^{2})^{\frac{3}{2}}} = \frac{\frac{3γ}{2} a^{2}b + \frac{3}{2}a^{2}c + c^{3} + b^{3}}{(a^{2} + b^{2} + c^{2})^{\frac{3}{2}}} .

Since this last quantity is homogeneous of degree 0 with respect to variables a, b and c, we can assume that a^{2} + b^{2} + c^{2} = 1, which gives

\frac{3γ}{2} a^{2}b + \frac{3}{2}a^{2}c + c^{3} + b^{3} = \frac{3}{2}a^{2}(γb + c) + c^{3} + b^{3} = \frac{3}{2}(1 − b^{2} − c^{2})(γb + c) + b^{3} + c^{3} .

Calling this last quantity m(b, c), we can now compute its partial derivatives with respect to b and c and find

\frac{∂m}{∂b} = −\frac{3}{2} ((3γ − 2)b^{2} + γc^{2} + 2bc − γ) and \frac{∂m}{∂c} = −\frac{3}{2} (b^{2} + c^{2} + 2bcγ − 1) .

We have now to equate those two quantities to zero and solve the resulting system. We can for example write \frac{∂m}{∂b} − γ \frac{∂m}{∂c} = 0, which gives (g − 1)b(b − c(γ + 1)) = 0, and explore the resulting three cases. The solutions we find are

(b, c) = (0, ±1) and (\frac{γ + 1}{\sqrt{3γ^{2} + 4γ + 2}}, \frac{1}{\sqrt{3γ^{2} + 4γ + 2}})

with an additional special case b + c = 1 when γ = 1. Plugging these values into m(b, c), one finds after some computations the following potential maximum values

±1 and \frac{γ^{2} + γ + 1}{\sqrt{3γ^{2} + 4γ + 2}} = \frac{γ + 1 + 1/γ}{\sqrt{3 + +4/γ + 2/γ^{2}}}

(and 1 in the special case γ = 1). One concludes that the maximum we seek is equal to r_{2}(γ), as announced. □

Because it does not involve a fractional power of hessian (namely ∇^{2}F (x)[h, h]) to the power \frac{3}{2}), condition (3.1) is usually much easier to check than the original inequality (2.1), as will be demonstrated in the next section. While the lemma we have just proved is useful to tackle the first condition of self-concordancy (2.1), it does not say anything about the second condition (2.2). The following Corollary about the second barrier F_{2} might prove useful in this respect.

Corollary 3.1 Let F satisfy the assumptions of Lemma 3.2. Then the second barrier

F_{2} : int epi F ↦ ℝ : (x, u) ↦ − log(u − F (x)) − ∑_{i=1}^{n} log x_{i}

is (r_{2}(γ), n + 1)-self-concordant.

Proof . Since G(x, u) = F (x) − u is convex, − log(u − F (x)) = − log(−G(x, u)) is known to satisfy the second self-concordancy condition (2.2) with ν = 1 by virtue of Lemma 3.1. Moreover, it is straightforward to check that each term − log x_{i} also satisfies that second condition with parameter ν = 1. Using the addition Theorem 3.2 and combining with the result of Lemma 3.2, we can conclude that F_{2} is (r_{2}(γ), n + 1)-self-concordant. □

Note 3.3 We would like to point out that no similar result can hold for the first function F_{1}, since we know nothing about the status of the second self-concordancy condition (2.2) on its first term F (x). Indeed, taking the case of F : ℝ_{+} ↦ ℝ : x ↦ \frac{1}{x}, we can check that ∇^{2}F (x)[h, h] = 2\frac{h^{2}}{x^{3}} and ∇^{3}F (x)[h, h, h] = −6\frac{h^{3}}{x^{4}} , which implies that condition (3.1) holds with γ = 1 since

−6\frac{h^{3}}{x^{4}} ≤ 3 × 2\frac{h^{2}}{x^{3}} \frac{|h|}{x} ⇔ −h^{3} ≤ h^{2} |h|

is satisfied. On the other hand, the second self-concordancy condition (2.2) cannot hold for F_{1} : ℝ_{+} ↦ R : x ↦ \frac{1}{x} − log x, since

∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x) = \frac{F′_{1}(x)^{2}}{F′′_{1}(x)} = \frac{\frac{(x+1)^{2}}{x^{4}}}{\frac{(2+x)}{x^{3}}} = \frac{(x + 1)^{2}}{x(x + 2)}

does not admit an upper bound (it tends to +∞ when x → 0).

We point out that since condition (3.1) is invariant with respect to positive scaling of F, the results from Lemma 3.2 hold for barriers F_{λ,1}(x) = λF (x) − ∑_{i=1}^{n} log x_{i} and F_{λ,2}(x, u) = − log(u − λF (x)) − ∑_{i=1}^{n} log x_{i}, where λ is a positive constant.

To conclude this section, we present an extension of Lemma 3.2.

Definition 3.1 A convex function F defined on int C ⊆ ℝ_{++}^{n} is called [γ; I]-compatible if and only if there exists a constant γ and a set I ⊆ {1, 2, …, n} such that

∇^{3}F (x)[h, h, h] ≤ 3γ∇^{2}F (x)[h, h]\sqrt{∑_{i∈I} \frac{h_{i}^{2}}{x_{i}^{2}}} for all x ∈ int C and h ∈ ℝ^{n} .  (3.3)

This definition is a simple extension of the condition that was underlying Lemma 3.2, where we only require a subset of the n variables to enter the sum under the square root. A straightforward adaptation of Lemma 3.2 and Corollary 3.1 leads to the following:

Lemma 3.3 Let F be a [γ; I]-compatible convex function defined on int C ⊆ ℝ_{++}^{n}. We have that

F_{1} : int C ↦ ℝ : x ↦ F (x) − ∑_{i∈I} log x_{i}

satisfies the first condition of self-concordancy (2.1) with parameter κ_{1} = r_{1}(γ) and

F_{2} : int epi F ↦ ℝ : (x, u) ↦ − log(u − F (x)) − ∑_{i∈I} log x_{i}

satisfies the first and second conditions of self-concordancy (2.1)-(2.2) with parameter (κ_{2}, ν_{2}) = (r_{2}(γ), |I| + 1) on its domain.

An interesting property is that the sum of two [γ; I]-compatible functions is still [γ; I]- compatible. More precisely, we have the following theorem.

Theorem 3.3 Let F_{1} be a [γ_{1}; I_{1}]-compatible convex function defined on int C_{1} ⊆ ℝ_{++}^{n} and F_{2} be a [γ_{2}; I_{2}]-compatible convex function defined on int C_{2} ⊆ ℝ_{++}^{n}. Then F_{1} + F_{2} is a [max{γ_{1}, γ_{2}}; I_{1} ∪ I_{2}]-compatible convex function on int C_{1} ∩ int C_{2}.

Proof . Using the definition of [γ; I]-compatibility, we write for all x ∈ int C and h ∈ ℝ^{n}

∇^{3}(F_{1} + F_{2})(x)[h, h, h] ≤ 3γ_{1}∇^{2}F_{1}(x)[h, h]\sqrt{∑i∈I_{1} \frac{h_{i}^{2}}{x_{i}^{2}}} + 3γ_{2}∇^{2}F_{2}(x)[h, h]\sqrt{∑i∈I_{2} \frac{h_{i}^{2}}{x_{i}^{2}}}
≤ 3 max\{γ_{1}, γ_{2}\}(∇^{2}F_{1}(x)[h, h]\sqrt{∑i∈I_{1} \frac{h_{i}^{2}}{x_{i}^{2}}} + ∇^{2}F_{2}(x)[h, h]\sqrt{∑i∈I_{2} \frac{h_{i}^{2}}{x_{i}^{2}}} )
≤ 3 max\{γ_{1}, γ_{2}\}∇^{2}(F_{1} + F_{2})(x)[h, h]\sqrt{∑i∈I_{1}∪I_{2} \frac{h_{i}^{2}}{x_{i}^{2}}} ,

which is the desired property. □

4 Application to structured convex problems

In this section we rely on the work in [3], where several classes of structured convex optimization problems are shown to admit a self-concordant logarithmic barrier. However, Lemma 3.2 will allow us to improve the self-concordancy parameters and lower the resulting complexity values.

4.1 Extended entropy optimization

Let c ∈ ℝ^{n}, b ∈ ℝ^{m} and A ∈ ℝ^{m×n}. We consider the following problem

min_{x∈ℝ^{n}} c^{T} x + ∑_{i=1}^{n} g_{i}(x_{i}) s.t. Ax = b and x ≥ 0  (EEO)

where scalar functions g_{i} : ℝ_{+} ↦ ℝ : z ↦ g_{i}(z) are required to satisfy

|g′′′_{i}(z)| ≤ κ_{i} \frac{g′′_{i}(z)}{z} ∀z > 0  (4.1)

(which by the way implies their convexity). This class of problems is studied in [8, 13]. Classical entropy optimization results as a special case when g_{i}(z) = z ln z (in that case, it is straightforward to see that condition (4.1) holds with κ_{i} = 1). Another simplex example of problems in this class involve functions g_{i}(z) = z^{l_{i}}, which is easily shown to satisfy condition (4.1) with κ_{i} = l_{i} − 2.

Let us use Lemma 3.2 with F_{i} : x_{i} ↦ g_{i}(x_{i}) and γ = \frac{κ_{i}}{3} . Indeed, checking condition (3.1) amounts to write

h^{3}g′′′_{i}(x) ≤ 3\frac{κ_{i}}{3} h^{2}g′′_{i}(x)\frac{|h|}{x} ⇔ \frac{h}{|h|}g′′′_{i}(x) ≤ κ_{i} \frac{g′′_{i}(x)}{x} ,

which is guaranteed by condition (4.1). Using the second barrier and Corollary 3.1, we find that

F_{i} : (x_{i}, u_{i}) ↦ − log(u_{i} − g_{i}(x_{i})) − log x_{i}

is (r_{2}(\frac{κ_{i}}{3} ), 2)-self-concordant^{6}. However, in order to use this barrier to solve problem (EEO), we need to reformulate it as

min_{x∈ℝ^{n}, u∈ℝ^{n}} c^{T} x + ∑_{i=1}^{n} u_{i} s.t. Ax = b, g_{i}(x_{i}) ≤ u_{i} and x ≥ 0 ,

which is clearly equivalent. We are now able to write the complete logarithmic barrier

F : (x, u) ↦ − ∑_{i=1}^{n} log(u_{i} − g_{i}(x_{i})) − ∑_{i=1}^{n} log x_{i} ,

which is (r_{2}(\frac{max\{κ_{i}\}}{3}), 2n)-self-concordant by virtue of Theorem 3.2. In light of Note 3.1, we can even do better with a different scaling of each term, to get

F̃ : (x, u) ↦ − ∑_{i=1}^{n} r_{2}(\frac{κ_{i}}{3} )^{2} log(u_{i} − g_{i}(x_{i})) − ∑_{i=1}^{n} r_{2}(\frac{κ_{i}}{3} )^{2} log x_{i}

which is then (1, \sqrt{2 ∑_{i=1}^{n} r_{2}(\frac{κ_{i}}{3} )^{2}})-self-concordant. In the case of classical entropy optimiza-

tion, these parameters become (1, \sqrt{2n}) , since r_{2}(\frac{1}{3}) = 1.

6This corrects the statement in [3] where it is mentioned that g_{i}(x_{i}) − log x_{i}, i.e. the first barrier in Lemma 3.2, is self-concordant. As it is made clear in Note 3.3, this cannot be true in general.

4.2 Dual geometric optimization

Let {I_{k}}_{k=1...r} be a partition of {1, 2, …, n}, c ∈ ℝ^{n}, b ∈ ℝ^{m} and A ∈ ℝ^{m×n}. The dual geometric optimization problem [5] is

min_{x∈ℝ^{n}} c^{T} x + ∑_{k=1}^{r} [∑_{i∈I_{k}} x_{i} log(\frac{x_{i}}{∑_{i∈I_{k}} x_{i}})]
s.t. Ax = b and x ≥ 0 .  (DGO)

It is shown in [3] that condition (3.1) holds for

F_{k} : (x_{i})_{i∈I_{k}} ↦ ∑_{i∈I_{k}} x_{i} log(\frac{x_{i}}{∑_{i∈I_{k}} x_{i}})

with γ = 1, so that the corresponding second barrier in Lemma 3.1 is (1, |I_{k}| + 1)-self-concordant. Using the same trick as for problem (EEO), we introduce additional variables u_{k} to find that the following barrier

F : (x, u) ↦ ∑_{k=1}^{r} − log(u_{k} − ∑_{i∈I_{k}} x_{i} log(\frac{x_{i}}{∑_{i∈I_{k}} x_{i}})) − ∑_{i=1}^{n} log x_{i}

is a (1, n + r)-self-concordant barrier for a suitable reformulation of problem (DGO).

4.3 l_{p}-norm optimization

Let {I_{k}}_{k=1...r} be a partition of {1, 2, …, m}, η ∈ ℝ^{n}, a_{i} ∈ ℝ^{n} for 1 ≤ i ≤ m, b_{k} ∈ ℝ^{n} for 1 ≤ k ≤ r, c ∈ ℝ^{m}, d ∈ ℝ^{r} and p ∈ ℝ^{m} such that p_{i} ≥ 1. The primal l_{p}-norm optimization problem [19] is

max_{x∈ℝ^{n}} η^{T} x s.t. f_{k}(x) ≤ 0 for all k = 1, …, r ,  (LPO)

where functions f_{k} : ℝ^{n} ↦ ℝ are defined according to

f_{k} : x ↦ ∑_{i∈I_{k}} \frac{1}{p_{i}} |a_{i}^{T} x − c_{i}|^{p_{i}} + b_{k}^{T} x − d_{k} .

This problem can be reformulated as

max_{x∈ℝ^{n}, s∈ℝ^{m}, t∈ℝ^{m}} η^{T} x s.t. \{ \begin{matrix}|a_{i}^{T} x − c_{i}| & ≤ & s_{i} & ∀i = 1, …, m \\ s_{i} & ≤ & t_{i}^{1/p_{i}} & ∀i = 1, …, m \\ ∑i∈I_{k} \frac{t_{i}}{p_{i}} & ≤ & d_{k} − b_{k}^{T} x & ∀k = 1, …, r \end{matrix}

where each of the m constraints involving an absolute value is indeed equivalent to a pair of linear constraints a_{i}^{T} x−c_{i} ≤ s_{i} and c_{i}−a_{i}^{T} x ≤ s_{i}. Once again, a self-concordant barrier can be found for the difficult part of the constraints, i.e. the nonlinear inequality s_{i} ≤ t_{i}^{1/p_{i}}. Indeed, it is straightforward to check that f_{i} : t_{i} ↦ −t_{i}^{1/p_{i}} satisfies condition (3.1) with γ = \frac{2p_{i}−1}{3p_{i}} < 1, which implies in the same fashion as above that

− log(t_{i}^{1/p_{i}} − s_{i}) − log t_{i}

is (1, 2)-self-concordant. Combining with the logarithmic barrier for the linear constraints, we have that

− ∑_{i=1}^{m} log(s_{i} − a_{i}^{T} x + c_{i}) − ∑_{i=1}^{m} log(s_{i} + a_{i}^{T} x − c_{i}) − ∑_{i=1}^{m} log(t_{i}^{1/p_{i}} − s_{i}) …

… − ∑_{i=1}^{m} log t_{i} − ∑_{k=1}^{r} log(d_{k} − b_{k}^{T} x − ∑_{i∈I_{k}} \frac{t_{i}}{p_{i}} )

is (1, 4m + r)-self-concordant for our reformulation of problem (LPO) (since each linear constraint is (1, 1)-self-concordant).

Let us mention that another reformulation is presented in [3], where Lemma 3.2 is applicable to the nonlinear constraint with parameter γ = \frac{|p_{i}−2|}{3}, with the disadvantage of having a parameter that depends on p_{i} (although r_{2}(γ) will stay at its lowest value as long as p_{i} ≤ 5). We also mention that very similar results hold for the dual l_{p}-norm optimization problem^{7}.

5 Concluding remarks

In this paper, we recalled a few basic facts about the theory of self-concordant functions. We would like to point out that this very powerful framework relies on two different conditions (2.1) and (2.2) and the two corresponding parameters κ and ν, each with its own purpose (see the discussion in Note 2.1). However, the important quantity is the resulting complexity value κ\sqrt{ν}, which is of the same order as the number of iterations that is needed to reduce the barrier parameter by a constant factor by the short-step interior-point algorithm.

It is possible to scale self-concordant barriers such that one of the parameters is arbitrarily fixed without any real loss of generality. We have shown that this is best done fixing parameter κ, considering the way the complexity value is affected when adding several self-concordant barriers. However, it is in our opinion better to keep two parameters all the time, in order to simplify the presentation (for example, Lemma 3.2 intrinsically deals with the κ parameter and would need a rather awkward reformulation to be written for parameter ν with κ fixed to 1).

Several important results help us prove self-concordancy of barrier functions: Lemma 3.1 deals with the second self-concordancy condition (2.2), while our improved Lemma 3.2 pertains to the first self-concordancy condition (2.1). They are indeed responsible for most of the analysis carried out in Section 4, which is dedicated to several classes of structured convex optimization problems. Namely, it is proved that nearly all the nonlinear (i.e. corresponding to the nonlinear constraints) terms in the associated logarithmic barriers are self-concordant with κ = 1 (the exception being extended entropy optimization, which encompasses a very broad class of problems). We would also like to mention that since all the barriers that are presented are polynomially computable, as well as their gradient and Hessian, the short-step method applied to any of these problems would need to perform a polynomial number of arithmetic operations to provide a solution with a given accuracy.

To conclude, we would like to speculate on the possibility of replacing the two selfconcordancy conditions by a single inequality. Indeed, since the complexity value κ\sqrt{ν} is the only quantity that really matters in the final complexity result, one could imagine to consider the following inequality

7However, we would like to point out that the nonlinear function involved in these developments is wrongly stated to satisfy condition (3.1) with γ = \sqrt{2}(q_{i} + 1)/(3q_{i}), while the correct value is \sqrt{5q_{i}^{2} − 2q_{i} + 2}/(3q_{i}).

\frac{F′′′_{x,h}(0)F′_{x,h}(0)}{F′′_{x,h}(0)^{2}} ≤ 2Γ for all x ∈ int C and h ∈ ℝ^{n} ,  (5.1)

which is satisfied with Γ = κ\sqrt{ν} for (κ, ν)-self-concordant barriers (to see that, simply multiply condition (2.4b) by the square root of condition (2.5b)). We point out the following two intriguing facts and leave their investigation for further research:

⋄ Condition (5.1) appears to be central in the recent theory of self-regular functions [12], an attempt at generalizing self-concordant barriers.

⋄ Following the same principles as for (2.4d) and (2.5d), condition (5.1) can be reformulated as

(−\frac{F′_{x,h}(t)}{F′′_{x,h}(t)})′ ≤ 2Γ − 1 ,

where the quantity on the left-hand side is the derivative of the Newton step applied to the restriction F_{x,h}.

References

[1] E. D. Andersen, J. Gondzio, C. Mészáros, and X. Xu, Implementation of interior-point methods for large scale linear programs, Interior Point Methods of Mathematical Programming (T. Terlaky, ed.), Applied Optimization, vol. 5, Kluwer Academic Publishers, 1996, pp. 189–252.

[2] J. Brinkhuis, Communication at the International Symposium on Mathematical Programming, Atlanta, August 2000.

[3] D. den Hertog, F. Jarre, C. Roos, and T. Terlaky, A sufficient condition for selfconcordance with application to some classes of structured convex programming problems, Mathematical Programming, Series B 69 (1995), no. 1, 75–88.

[4] D. den Hertog, C. Roos, and T. Terlaky, On the classical logarithmic barrier method for a class of smooth convex programming problems, Journal of Optimization Theory and Applications 73 (1992), no. 1, 1–25.

[5] R. J. Duffin, E. L. Peterson, and C. Zener, Geometric programming, John Wiley & Sons, New York, 1967.

[6] A. V. Fiacco and G. P. McCormick, Nonlinear programming: Sequential unconstrained minimization techniques, John Wiley & Sons, New York, 1968, Reprinted in SIAM Classics in Applied Mathematics, SIAM Publications, 1990.

[7] K. R. Frisch, The logarithmic potential method of convex programming, Tech. report, University Institute of Economics, Oslo, Norway, 1955.

[8] C. Han, P. Pardalos, and Y. Ye, Implementation of interior-point algorithms for some entropy optimization problems, Optimization Methods and Software 1 (1992), 71–80.

[9] F. Jarre, The method of analytic centers for smooth convex programs, Dissertation, Institut für Angewandte Mathematik und Statistik, Universität Wärzburg, Germany, 1989.

[10] , Interior-point methods for classes of convex programs, Interior Point Methods of Mathematical Programming (T. Terlaky, ed.), Applied Optimization, vol. 5, Kluwer Academic Publishers, 1996, pp. 255–296.

[11] Y. E. Nesterov and A. S. Nemirovsky, Interior-point polynomial methods in convex programming, SIAM Studies in Applied Mathematics, SIAM Publications, Philadelphia, 1994.

[12] J. Peng, C. Roos, and T. Terlaky, Self-regular proximities and new search directions for linear and semidefinite optimization, Technical report, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, March 2000, submitted to Mathematical Programming.

[13] F. Potra and Y. Ye, A quadratically convergent polynomial interior-point algorithm for solving entropy optimization problems, SIAM Journal on Optimization 3 (1993), 843–860.

[14] J. Renegar, A mathematical view of interior-point methods in convex optimization, MPS/SIAM Series on Optimization, SIAM, New York, 2001.

[15] R. T. Rockafellar, Convex analysis, Princeton University Press, Princeton, N. J., 1970.

[16] C. Roos and T. Terlaky, Nonlinear optimization, Delft University of Technology, The Netherlands, 1998, Course WI387.

[17] C. Roos, T. Terlaky, and J.-Ph. Vial, Theory and algorithms for linear optimization. an interior point approach, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Chichester, UK, 1997.

[18] J. Stoer and Ch. Witzgall, Convexity and optimization in finite dimensions I, Springer Verlag, Berlin, 1970.

[19] T. Terlaky, On l_{p} programming, European Journal of Operations Research 22 (1985), 70–100.