Self-concordant functions in structured convex optimization

Image Technical Report 0007

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.

October 2000

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

Abstract

This paper provides a self-contained introduction to the theory of self-concordant functions [8] and applies it to several classes of structured convex optimization problems. We describe the classical short-step interior-point method and optimize its parameters to provide its best possible iteration bound. We also discuss the necessity of introducing two parameters in the definition of self-concordancy, how they react to addition and scaling and which one is the best to fix. A lemma from [2] is improved and allows us to review several classes of structured convex optimization problems and evaluate their algorithmic complexity, using the self-concordancy of the associated logarithmic barriers.

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

Contents

1 Introduction 3 1.1 Convex optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Interior-point methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Purpose and organization of the paper . . . . . . . . . . . . . . . . . . . . . . 5

2 Self-concordancy 6 2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Short-step method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Optimal complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Proving self-concordancy 12 3.1 Barrier calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Fixing a parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Two useful lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4 Application to structured convex problems 20 4.1 Extended entropy optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 Dual geometric optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 l_{p}-norm optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5 Concluding remarks 23

1 Introduction

1.1 Convex optimization

Convex optimization deals with the following problem

inf_{x∈ℝ^{n}} f_{0}(x) s.t. x ∈ C ,  (C)

where C ⊆ ℝ^{n} is a closed convex set and f_{0} : C ↦ ℝ is a convex function defined on C. Convexity of f_{0} and C plays a very important role in this problem, since it is responsible for the following two important properties [11, 13]:

⋄ Any local optimum for (C) is also a global optimum, which implies that the objective value is equal for all local optima. Moreover, all these optima can be shown to form a convex set.

⋄ It is possible to use Lagrange duality to derive a dual problem strongly related to (C). Namely, this pair of problems satisfies a weak duality property (the objective value of any feasible solution for one of these problems provides a bound on the optimum objective value for the dual problem) and, under a Slater-type condition, a strong duality property (equality and attainment of the optimum objective values for the two problems).

We first note that it can be assumed with any loss of generality that the objective function f_{0} is linear, so that we can define it as f_{0}(x) = c^{T} x using a vector c ∈ ℝ^{n}. Indeed, it is readily seen that problem (C) is equivalent to the following problem with a linear objective:

min_{x∈ℝ^{n+1}} x_{n+1} s.t. x ∈ C̄ ,

where C̄ ⊆ ℝ^{n+1} is suitably defined as

C̄ = {(x, t) ∈ ℝ^{n+1} | x ∈ C and f(x) ≤ t} .

We will thus consider in the rest of this paper the problem

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

It is interesting to ask ourselves how one can specify the data of a problem cast in such a form, i.e. how one can describe its objective function and feasible set. While specifying the objective function is easily done by providing vector c, describing the convex set C, which is responsible for the structure of problem (CL), can be done in several manners.

a. The traditional way to proceed in nonlinear optimization is to provide list of convex constraints defining C, i.e.

C = {x ∈ ℝ^{n} | f_{i}(x) ≤ 0 ∀i ∈ I = {1, 2, …, m}} ,  (1.1)

where each of the m functions f_{i} : ℝ^{n} ↦ ℝ is convex. This guarantees the convexity of C, as an intersection of convex level sets. b. An alternative approach consists in considering the domain of a convex function. More

precisely, we require the interior of C to be equal to the domain of a convex function. Extending the real line ℝ with the quantity +∞, we introduce the convex function F : ℝ^{n} ↦ ℝ ∪ {+∞} and define C as the closure of its effective domain, i.e.

C = cl dom F = cl {x ∈ ℝ^{n} | F (x) < +∞} .

Most of the time, we will require in addition F to be a barrier function for the set C, according to the following definition.

Definition 1.1 A function F is a barrier function for the convex set C if and only if it satisfies the following assumptions:

(a) F is smooth (three times continuously differentiable for our purpose),

(b) F is strongly convex, i.e. ∇^{2}F is positive definite,

(c) F (x) tends to +∞ whenever x tends to ∂C, the boundary of C (this is the barrier property).

Note 1.1 We also note that it is often possible to provide a suitable barrier function F for a convex set C given by a functional description (1.1) using the logarithmic barrier [5] defined as

F : ℝ^{n} ↦ ℝ : x ↦ F (x) = − ∑_{i∈I} log(−f_{i}(x)) ,

where we define log x = +∞ whenever x ≤ 0. We have indeed to check that f is strongly convex and is a barrier function for C, which is not always the case (for example, in the case of C = ℝ_{+}, taking f_{1}(x) = |x| − x does not lead to a strongly convex F while f_{1}(x) = −x^{x} leads to F (x) = −x log x, which does not possess the barrier property).

c. It may also be worthwhile to consider the special case where C can be described as the intersection of a convex cone K ⊆ ℝ^{n} and an affine subspace b + L (where L is a linear subspace)

C = K ∩ (b + L) = {x ∈ K | x − b ∈ L} .

The resulting class of problems is known as conic optimization, and can be easily shown to be equivalent to convex optimization [8] (in practice, subspace b+L would be defined with a set of linear equalities).

Special treatment for the linear constraints, i.e. their representation as an intersection with an affine subspace, can be justified by the fact that these constraints are easier to handle than general nonlinear constraints. In particular, let us mention that it is usually easy for algorithms to preserve feasibility with respect to these constraints, and that they cannot cause a nonzero duality gap, i.e. strong duality is valid without a Slater-type assumption for linear optimization. However, we will not need to use this approach in this paper.

1.2 Interior-point methods

Among the different types of algorithms that can be applied to solve problem (CL), the socalled interior-point methods have gained a lot of popularity in the last two decades. This is mainly due to the following facts:

⋄ it is not only possible to prove convergence of these methods to an optimal solution but also to give a polynomial bound on the number of arithmetic operations needed to reach a solution within a given accuracy,

⋄ these methods can be implemented and applied successfully to solve real-world problems, especially in the fields of linear (where they compare favourably with the simplex method), quadratic and semidefinite optimization.

A fundamental ingredient in the elaboration of these methods is the above-mentioned notion of barrier function F for the set C. Namely, let us consider the following parameterized family of unconstrained minimization problems:

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

where parameter μ belongs to ℝ_{++} and is called the barrier parameter. The constraint x ∈ C of the original problem (CL) has been replaced by a penalty term F (x) in the objective function, which tends to +∞ as x tends to the boundary of C and whose purpose is to avoid that the iterates leave the feasible set (see the classical monograph [4]). Assuming existence of a minimizer x(μ) for each of these problems (strong convexity of F ensures uniqueness of such a minimizer), we call the set {x(μ) | μ > 0} ⊆ C the central path for problem (CL).

It is intuitively clear that as μ tends to zero, the first term proportional to the original objective \frac{c^{T} x}{μ} becomes preponderant in the sum, which implies that the central path converges to a solution that is optimal for the original problem. The principle behind interior-point methods will thus be to follow this central path until an iterate that is sufficiently close to the optimum is found.

However, two questions remain pending: how do we compute x(μ) and how do we choose a suitable barrier F. The first question is readily answered: interior-point methods rely on Newton’s method to compute these minimizers, which leads us to a refined version of the second question: is it possible to choose a barrier function F such that Newton’s method is provably efficient in solving subproblems (CL_{μ}) and has an algorithmic complexity that can be estimated. This crucial question is thoroughly answered by the remarkable theory of self-concordant functions, first developed by Nesterov and Nemirovsky [8], which we will present in the next section.

1.3 Purpose and organization of the paper

The purpose of this paper is to give a self-contained introduction to the theory of selfconcordant functions and to apply it to several classes of structured convex optimization problems. Section 2 introduces a definition of self-concordant functions and presents several equivalent conditions. A short-step interior-point method using these functions is then presented along with an explanation of how the proof of polynomiality works. Our contribution at this stage is the computation of the best possible iteration bound for this method.

Section 3 deals with the construction of self-concordant functions. Scaling and addition of self-concordant functions are considered, as well as a discussion on the utility of two parameters in the definition of self-concordancy and how to fix one of them in the best possible way. We then present an improved version of a lemma from [2]. This lemma is the main tool used in Section 4, where we review several classes of structured convex optimization problems and prove self-concordancy of the corresponding logarithmic barriers, improving the complexity results found in[2]. We conclude in Section 5 with some comments.

2 Self-concordancy

2.1 Definitions

Let us start with a definition of a self-concordant function.

Definition 2.1 A function F : C ↦ R is called (κ, ν)-self-concordant for the convex set C ⊆ ℝ^{n} if and only if F is a barrier function according to Definition 1.1 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)

(note that the square root in (2.1) is well defined since its argument ∇^{2}F (x)[h, h] is positive because of the requirement that F is convex).

This definition does not exactly match the original definition of a self-concordant barrier in [8], but merely corresponds to the notion of strongly non-degenerate κ^{−2}-self-concordant barrier functional with parameter ν, that is general enough for our purpose.

Note 2.1 We would like to point out that no absolute value is needed in (2.1): while some authors usually require the apparently stronger condition

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

this is not needed since it suffices to notice that inequality (2.1) also has to hold in the direction opposite to h, which gives

∇^{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}}

(using the fact that the n^{th}-order differential is homogeneous with degree n), which combined with (2.1) gives condition (2.3).

It is possible to reformulate conditions (2.1) and (2.2) into several equivalent inequalities that may prove easier to handle in some cases. However, before we list them, we would like to make a few comments about the use of inner products in our setting, following the line of thought of Renegar’s monograph [10].

It is indeed important to realize that the definitions of gradient and Hessian, i.e. firstorder and second-order differentials are in fact dependent from inner product that is being used. Nevertheless, in most texts, it is customary to use the dot product^{1} as standard inner product. This has the disadvantage to make all developments a priori dependent from the coordinate system. However, Renegar notices that it is possible to develop the theory of selfconcordant functions in a completely coordinate-free manner, i.e. independently of a reference inner product. The is due to the fact that the two principal objects in this theory are indeed independent from the coordinate system: the Newton step n(x) and the intrinsic inner product ⟨·, ·⟩_{x}. Given a barrier function F and a point x belonging to its domain, these two objects are defined according to:

1The dot product of two vector x and y whose coordinates are (α_{1}, α_{2}, …, α_{n}) and (β_{1}, β_{2}, …, β_{n}) in a given coordinate system is equal to ∑_{i=1}^{n} α_{i}β_{i}.

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

It is also convenient to introduce the intrinsic norm ∥·∥_{x} based on the intrinsic inner product ⟨·, ·⟩_{x} according to the usual definition ∥a∥_{x} = \sqrt{⟨a, a⟩_{x}}.

Let x ∈ int C and h ∈ ℝ^{n} and let us introduce the one-dimensional function F_{x,h} : ℝ ↦ ℝ : t ↦ F (x + th), the restriction of F along the line {x + th | t ∈ ℝ}. We are now in position to state several reformulations of conditions (2.1) and (2.2), grouped in the following two theorems:

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. Proving these equivalences is a little more involved than for the previous theorem. We start by showing that condition (2.5b) implies condition (2.5a). We can write

∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x) = ∇F (x)[(∇^{2}F (x))^{−1}∇F (x)] = F′_{x,(∇^{2}F (x))^{−1}∇F (x)}(0)
≤ \sqrt{ν}\sqrt{F′′_{x,(∇^{2}F (x))^{−1}∇F (x)}(0)} using condition (2.5b)
= \sqrt{ν}\sqrt{∇^{2}F (x)[(∇^{2}F (x))^{−1}∇F (x), (∇^{2}F (x))^{−1}∇F (x)]}
= \sqrt{ν}\sqrt{∇F (x)^{T} (∇^{2}F (x))^{−1}∇^{2}F (x)(∇^{2}F (x))^{−1}∇F (x)}
= \sqrt{ν}\sqrt{∇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)[h])^{2} = (∇F (x)^{T} h)^{2}
= (∇F (x)^{T} (∇^{2}F (x))^{−1}∇^{2}F (x)h)^{2} = ⟨(∇^{2}F (x))^{−1}∇F (x), h⟩_{x}^{2}
≤ ∥(∇^{2}F (x))^{−1}∇F (x)∥_{x}^{2} ∥h∥_{x}^{2} (using the Cauchy-Schwarz inequality)
= (∇F (x)^{T} (∇^{2}F (x))^{−1}∇^{2}F (x)(∇^{2}F (x))^{−1}∇F (x)) (h^{T} ∇^{2}F (x)h)
≤ ν∇^{2}F (x)[h, h] using condition (2.5a)
= ν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 [8, 7, 10]. Conditions (2.4d) and (2.5d) are less commonly used and were independently presented in [1].

2.2 Short-step method

As outlined in the introduction, interior-point methods for convex optimization rely on a barrier function and the associated central path to solve problem (CL). Ideally, we would like our iterates to be a sequence of points on the central path x(μ_{0}), x(μ_{1}), …, x(μ_{k}), … for a sequence of barrier parameters μ_{k} tending to zero (and thus x(μ_{k}) tending to an optimal solution).

We already mentioned that Newton’s method, applied to problems (CL_{μ}), will be the workhorse to compute those minimizers. However, it would be too costly to compute each of these points with high accuracy, so that interior-point methods require instead their iterates to lie in a prescribed neighbourhood of the central path and its exact minimizers.

Let x_{k}, the k^{th} iterate, be an approximation of x(μ_{k}). A good proximity measure would be ∥x_{k} − x(μ_{k})∥ or, to be independent from the coordinate system, ∥x_{k} − x(μ_{k})∥_{x_{k}}. However, this quantity involve the unknown central point x(μ_{k}), and is therefore difficult to work with. Nevertheless, another elegant proximity measure can be used for that purpose. Let us define n_{μ}(x) to be the Newton step trying to minimize the objective in problem (CL_{μ}), which is thus aiming at x(μ_{k}). Since this objective is equal to F_{μ}(x) = \frac{c^{T} x}{μ} + F (x), we have

n_{μ}(x) = −(∇^{2}F_{μ}(x))^{−1}∇F_{μ}(x) = −(∇^{2}F (x))^{−1}(\frac{c}{μ} + ∇F (x)) = −\frac{1}{μ}(∇^{2}F (x))^{−1}c + n(x) .

Let us now define δ(x, μ), a measure of the proximity of x to the central point x(μ), as the intrinsic norm of the newton step n_{μ}(x), i.e. δ(x, μ) = ∥n_{μ}(x)∥_{x}. This quantity is indeed a good candidate to measure how far x lies from the minimizer x(μ), since the Newton step at x targeting x(μ) is supposed to be a good approximation of x(μ) − x. The goal of a shortstep interior-point method will be to trace the central path approximately, ensuring that the proximity δ(x_{k}, μ_{k}) is kept below a predefined bound for each iterate.

We are now in position to sketch a short-step algorithm. Given a problem of type (CL), a barrier function F for 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:

μ_{k+1} ← μ_{k}(1 − θ)
x_{k+1} ← x_{k} + n_{μ_{k+1}}(x_{k})
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. This is the moment where the selfconcordancy of the barrier function F comes into play. Indeed, it is precisely this property that will guarantee that such a choice is always possible.

2.3 Optimal complexity

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) = n_{μ}(x) − θn(x)
⇒ (1 − θ) ∥n_{μ^{+}}(x)∥_{x} ≤ ∥n_{μ}(x)∥_{x} + θ ∥n(x)∥_{x}
⇒ (1 − θ)δ(x, μ^{+}) ≤ δ(x, μ) + θ\sqrt{ν} ,

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

∥n(x)∥_{x} = \sqrt{⟨n(x), n(x)⟩_{x}} = \sqrt{∇F (x)^{T} (∇^{2}F (x))^{−1}∇^{2}F (x)(∇^{2}F (x))^{−1}∇F (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 [8, 7, 10]).

Note 2.2 It is now clear why the self-concordancy property relies on two separate conditions: 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 function, we are now going to find a suitable pair of parameters τ and θ . Moreover, we will optimize this choice of parameters, i.e. try to provide the greatest reduction for the parameter μ at each iteration, in other words maximize θ 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{κτ}}

(this 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 C = κ\sqrt{ν} and β = \sqrt{κτ} we have

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

which means finally that we have to choose θ such that

θ ≤ \frac{1 − β − β^{2}}{1 + C + \frac{C}{β}}  (2.7)

in order to guarantee δ^{+} ≤ τ. We are now in position to optimize the value of θ, i.e. find the value of β that maximizes this upper bound. However, this value is likely to depend on C (and thus on κ and ν) in a complex way. We are therefore going to work with the following slightly worse upper bound, which has the advantage of allowing the optimization of β independently of C (we use the fact that C = κ\sqrt{ν} ≥ 1, see [8])

θ ≤ \frac{1}{C} (\frac{1 − β − β^{2}}{2 + \frac{1}{β}} ) = \frac{f(β)}{C} ( ≤ \frac{1 − β − β^{2}}{1 + C + \frac{C}{β}} ) .

It is now straightforward to maximize f(β): computing the derivative shows there is a unique maximizer when β ≈ 0.273 (the exact value is the real root of 1 − 2β − 5β^{2} − 4β^{3}) and our upper bound in (2.7) becomes \frac{0.65}{1+4.66C}. Translating back into our original quantities τ, κ and ν we find that we can choose

τ = \frac{β^{2}}{κ} ≈ \frac{1}{13.42κ} and θ = \frac{1 − β − β^{2}}{1 + C + \frac{C}{β}} ≈ \frac{1}{1.53 + 7.15κ\sqrt{ν}} ,  (2.8)

which is the best result obtainable if we want β to be independent from κ and ν. This improves several results from the literature, e.g. θ = \frac{1}{9κ\sqrt{ν}} in [7] and θ = \frac{1}{1+8κ\sqrt{ν}} in [10].

Before we conclude this section with a global complexity result, let us say a few words about termination of the algorithm. The most practical stopping criteria is a small target value μ_{e} for the barrier parameter, which gives the iteration bound (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^{∗}

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

(proof of this fact is omitted here and can easily be obtained combining Theorems 2.2.5 and 2.3.3 in [10]). 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 and an initial iterate x_{0} such that δ(x_{0}, μ_{0}) < \frac{1}{13.42κ}, one can find a solution with accuracy ϵ in

⌈(1.03 + 7.15κ\sqrt{ν}) log \frac{1.29μ_{0}κ\sqrt{nu}}{ϵ}⌉ iterations.

Proof. Using our optimal values for θ and τ from (2.8) and the bound on the objective accuracy in (2.9), we find that the stopping threshold on the barrier parameter μ_{e} must satisfy

\frac{μ_{e}}{1 − 3/13.42}κ\sqrt{ν} ≤ ϵ ⇔ 1.29μ_{e}κ\sqrt{ν} ≤ ϵ ⇔ μ_{e} ≤ \frac{ϵ}{1.29κ\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.29μ_{0}κ\sqrt{ν}}
= −\frac{1}{log(1 − θ)} log \frac{1.29μ_{0}κ\sqrt{ν}}{ϵ}
≤ (\frac{1}{θ} − \frac{1}{2}) log \frac{1.29μ_{0}κ\sqrt{ν}}{ϵ}
= (1.03 + 7.15κ\sqrt{ν}) log \frac{1.29μ_{0}κ\sqrt{ν}}{ϵ} ,

as announced (the third line uses the inequality \frac{1}{log(1−θ)} ≥ \frac{1}{2} − \frac{1}{θ}, which can be easily derived using the Taylor series of log x around 1). □

3 Proving 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 in [8] 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 they provide in their proof is defined as a volume integral over an n-dimensional convex body, and is therefore difficult to evaluate in practice, even for simple sets in lowdimensional spaces. Another potential problem with this approach is that evaluating this barrier (and/or its gradient and Hessian) might take a number of arithmetic operations that grows exponentially with n, which would lead to an exponential algorithmic complexity for the short-step method, despite the polynomial iteration bound.

Another approach to find self-concordant function is to combine basic self-concordant functions using operations that are known to preserve self-concordancy (this approach is called barrier calculus in [8]). We are now going to 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, strong convexity and the barrier property are obviously preserved by scaling). Looking at the restrictions (λF)_{x,h} = λF_{x,h}, we also have that

(λF)′_{x,h} = λF′_{x,h}, (λF)′′_{x,h} = λF′′_{x,h} and (λF)′′′_{x,h} = λF′′′_{x,h} .

Since F is (κ, ν)-self-concordant, we have (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) for all x ∈ int C and h ∈ ℝ^{n} .

This is 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) for all x ∈ int C and h ∈ ℝ^{n} ,

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

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}. Looking at the restrictions (F + G)_{x,h}, we also have that

(F + G)′_{x,h} = F′_{x,h} + G′_{x,h}, (F + G)′′_{x,h} = F′′_{x,h} + G′′_{x,h} and (F + G)′′′_{x,h} = F′′′_{x,h} + G′′′_{x,h} .

We can write thus

(F + G)′′′_{x,h} = F′′′_{x,h} + 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′′_{x,h} + G′′_{x,h})^{\frac{3}{2}} = 2 max\{κ_{1}, κ_{2}\}(F + G)′′_{x,h}

(where we used for the third inequality the easily proven fact x^{\frac{3}{2}} +y^{\frac{3}{2}} ≤ (x+y)^{\frac{3}{2}} for x, y ∈ ℝ_{++}) and

|(F + G)′_{x,h}| = |F′_{x,h} + 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′′_{x,h} + G′′_{x,h}} = \sqrt{ν_{1} + ν_{2}}\sqrt{(F + G)′′_{x,h}}

(where we used for the third inequality the Cauchy-Schwarz inequality applied to vectors (\sqrt{ν_{1}}, \sqrt{ν_{2}}) and (\sqrt{F′′_{x,h}}, \sqrt{G′′_{x,h}})), which is precisely 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 [2, 12, 6, 3] 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 functional description like (1.1), i.e.

min_{x∈ℝ^{n}} c^{T} x s.t. f_{i}(x) ≤ 0 ∀i ∈ I .

In order to apply the interior-point method methodology, a barrier function is needed and it is customary to use the logarithmic barrier as described in Note 1.1

F : ℝ^{n} ↦ ℝ : x ↦ F (x) = − ∑_{i∈I} log(−f_{i}(x)) .

The following lemma will prove useful.

Lemma 3.1 Let f : ℝ^{n} ↦ ℝ be a convex function and define F : ℝ^{n} ↦ ℝ ∪ {+∞} : x ↦ − log(−f(x)), whose effective domain is the set C = {x ∈ ℝ^{n} | f(x) < 0}. 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 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 implies that F satisfies the second self-concordancy condition (2.2) with ν = 1. □

Since the complete logarithmic barrier 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 ν = |I| = 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. [8, 10, 7]), and we propose to 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 (κ, 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 makes us 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 become completely irrelevant and do not 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 well depending on the parameters of all the terms of the logarithmic barrier.

3.3 Two useful lemmas

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 two lemmas that can help us in that regard.

The first one deals with the second condition of self-concordancy with logarithmically homogeneous barriers [8].

Lemma 3.2 Let us suppose F is a logarithmically homogeneous function with parameter α, i.e.

F (tx) = F (x) − α log t .  (3.1)

We have that F satisfies the second condition of self-concordancy (2.2) with parameter ν = α.

Proof. This fact admits the following straightforward proof. We start by differentiating both sides of (3.1) with respect to t, to find

∇F (tx)[x] = −\frac{α}{t} .

Fixing t = 1 gives

∇F (x)[x] = ∇F (x)^{T} x = −α .  (3.2)

Differentiating this last equality again, this time with respect to x, leads to

∇F (x) + ∇^{2}F (x)x = 0 ⇔ ∇F (x) = −∇^{2}F (x)x .  (3.3)

Looking now at the left-hand side in (2.2) we have

∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x) = −∇F (x)^{T} (∇^{2}F (x))^{−1}∇^{2}F (x)x = −∇F (x)^{T} x = α

(using successively (3.3) and (3.2)), which implies immediately that F satisfies the second condition of self-concordancy (2.2) with ν = α. □

The second lemma we are going to present deals with the first self-concordancy condition. Let us first introduce two auxiliary functions r_{1} and r_{2}, whose graphs are depicted in Figure 3.3:

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 +∞.

Lemma 3.3 Let us suppose F is a convex function with effective domain 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.4)

We have that

F_{1} : 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 C and

F_{2} : C × ℝ ↦ ℝ : (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 epi F = {(x, u) | F (x) ≤ u}.

Note 3.2 A similar lemma is proved in [2], with parameters κ_{1} and κ_{2} both equal to 1 + γ. The second result is improved in [7], with κ_{2} equal to max{1, γ}, as a special case of a more general compatibility theory developed in [8]. 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 r_{2}), with an asymptotical ratio of \sqrt{3} when γ tends to +∞.

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

Proof. We follow the lines of [2] 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 ≥ 0 and b ≥ 0 such that

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

(convexity of F guarantees that a is real), we can rewrite inequality (3.4) as ∇^{3}F_{1}(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.5)

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 quantity 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 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 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.5)
= −\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.4) .

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

While the lemma we have just proved is useful to tackle the first condition of selfconcordancy (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.3. Then the second barrier

F_{2} : C × ℝ ↦ ℝ : (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.3, 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.4) is 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).

To conclude this section, we mention that since condition (3.4) is invariant with respect to positive scaling of F, the results from Lemma 3.3 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.

4 Application to structured convex problems

In this section we rely on the work in [2], where several classes of structured convex optimization problems are shown to admit a self-concordant logarithmic barrier. However, Lemma 3.3 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} : ℝ_{+} ↦ ℝ are required to satisfy

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

(which by the way implies their convexity). Classical entropy optimization results as a special case when g_{i}(x) = x ln x (in that case, it is straightforward to see that condition (4.1) holds with κ_{i} = 1).

Let us use Lemma 3.3 with F_{i} : x_{i} ↦ g_{i}(x_{i}) and γ = \frac{κ_{i}}{3} . Indeed, checking condition (3.4) 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^{2}. However, in order to use this barrier to solve problem (EEO), we need to reformulate it as

min_{x∈ℝ^{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.

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 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 [2] that condition (3.4) 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.4 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).

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

4.3 l_{p}-norm optimization

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

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

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

f_{i} : 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}} η^{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} ≤ u_{i} and c_{i} − a_{i}^{T} x ≤ u_{i}. Once again, a self-concordant function 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.4) with γ = \frac{2p_{i}−1}{3p_{i}} < 1, which implies in the same fashion as above that

− log(t_{i}^{1/p_{i}} − u_{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(u_{i} − a_{i}^{T} x + c_{i}) − ∑_{i=1}^{m} log(u_{i} + a_{i}^{T} x − c_{i}) − ∑_{i=1}^{m} log(t_{i}^{1/p_{i}} − u_{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 [2], where Lemma 3.3 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 conclude this section by mentioning that very similar results hold for the dual l_{p}-norm optimization problem^{3}.

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

5 Concluding remarks

We have presented in this paper an introduction to 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.2). 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.3 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: Lemmas 3.1 and 3.2 deal with the second self-concordancy condition (2.2), while our improved Lemma 3.3 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

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

which is satisfied with C = κ\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 [9], an attempt at generalizing self-concordant functions.

⋄ 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)})′ ≤ 2C − 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] J. Brinkhuis, Communication at the International Symposium on Mathematical Programming, Atlanta, August 2000.

[2] 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.

[3] 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.

[4] 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.

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

[6] 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.

[7] , 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.

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

[9] 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.

[10] J. Renegar, A mathematical view of interior-point methods in convex optimization, to be published by in the MPS/SIAM Series on Optimization, SIAM, New York, 2000.

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

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

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