[figure]

Self-concordant barriers for structured convex problems

François Glineur

                     Francois.Glineur@fpms.ac.be

Faculté Polytechnique de Mons

Interior-Point Methods Workshop

Budapest, Hungary July 14, 2000

Self-concordant barriers for structured convex problems

[figure]

[figure: Outline]

Introduction

⋄ Convex optimization ⋄ Barrier function

Self-concordancy

⋄ A matter of definitions ⋄ Two approaches

A useful lemma

⋄ Statement ⋄ Proof

Structured convex problems

⋄ Extended entropy optimization ⋄ Geometric optimization ⋄ l_{p}-norm optimization

Concluding remarks

François Glineur, FPMs  Page 2  IPM2000, Budapest, Hungary

[figure]

[figure]

Introduction

Convex optimization

Let f_{0} : ℝ^{n} ↦ ℝ be a convex function, C ⊆ ℝ^{n} be a convex set : optimize a vector x ∈ ℝ^{n}

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

Properties ⋄ All local optima are global ⋄ Lagrange duality ⇒ nice dual problem

Different ways to describe C: a. Nonlinear functions Let f_{i} : ℝ^{n} ↦ ℝ be m convex functions, i = 1, 2, …, m, we define C by C = {x ∈ ℝ^{n} | f_{i}(x) ≤ 0 for all i = 1, 2, …, m} (intersection of convex level sets), which gives inf_{x∈ℝ^{n}} f_{0}(x) s.t. f_{i}(x) ≤ 0 for all i = 1, 2, …, m

(NLO)

François Glineur, FPMs  Page 3  IPM2000, Budapest, Hungary

[figure]

b. Conic setting Let two vectors b, c ∈ ℝ^{n}, a matrix A ∈ ℝ^{m×n} and a convex cone K ⊆ ℝ^{n} and define

⋄ f_{0}(x) = c^{T} x, a linear objective ⋄ L = {x ∈ ℝ^{n} | Ax = b}, an affine subspace ⋄ C = K ∩ L, the intersection of a convex

cone and an affine subspace which gives

inf_{x∈ℝ^{n}} c^{T} x s.t. x ∈ K and Ax = b (CO)

Barrier function

F : ℝ^{n} ↦ ℝ is a barrier function for C if ⋄ it is smooth ⋄ it is strongly convex on int C ⋄ F (x) → +∞ when x → ∂C

Idea: approximate a constrained problem by a family of unconstrained problems based on F

François Glineur, FPMs  Page 4  IPM2000, Budapest, Hungary

[figure]

Let μ ∈ ℝ_{++} be a parameter and consider

inf_{x∈ℝ^{n}} f_{0}(x) + μF (x)  (P_{μ})

We have

x_{μ}^{∗} → x^{∗} when μ ↘ 0

where ⋄ x_{μ}^{∗} is the (unique) solution of (P_{μ}) ⋄ x^{∗} is a solution of the original problem (P)

Ingredients ⋄ A method for unconstrained optimization ⋄ A barrier function

Interior-point methods choose ⋄ Newton’s method ⋄ Logarithmic barrier function

When C is defined with nonlinear functions:

F (x) = − ∑_{i=1}^{n} ln(−f_{i}(x))

(other types of unconstrained approximations are possible, e.g. the method of centers)

François Glineur, FPMs  Page 5  IPM2000, Budapest, Hungary

[figure]

[figure]

Self-concordant barriers

A matter of definitions

Question: What is a good barrier, i.e. a barrier for which Newton’s method is efficient ? Answer: A self-concordant barrier A function F : int C ↦ ℝ is called (κ, ν)-self-concordant on C iff

⋄ F is convex ⋄ F is three times differentiable ⋄ F (x) → +∞ when x → ∂C ⋄ the following two conditions hold

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

∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x) ≤ ν

for all x ∈ int C and h ∈ ℝ^{n} [Nesterov & Nemirovsky, 1988]

François Glineur, FPMs  Page 6  IPM2000, Budapest, Hungary

[figure]

Alternative definition. Let x ∈ int C and h ∈ ℝ^{n} and define

F_{x,h}(t) : ℝ ↦ ℝ : t ↦ F (x + th) Replace conditions involving differentials by

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

for all x ∈ int C and h ∈ ℝ^{n} Geometric interpretation Using local Hessian-based norms

⋄ Variation of the Hessian bounded ⋄ Size of the Newton step bounded

Scaling Let λ ∈ ℝ_{+} be a positive scalar

F is (κ, ν)-SC ⇔ λF is (\frac{κ}{\sqrt{λ}}, λν)-SC

Summation Let F_{1} be (κ_{1}, ν_{1})-SC and F_{2} be (κ_{2}, ν_{2})-SC

F_{1} + F_{2} is (max{κ_{1}, κ_{2}}, ν_{1} + ν_{2})-SC

François Glineur, FPMs  Page 7  IPM2000, Budapest, Hungary

[figure]

Main result Self-concordant barrier ⇒ polynomial number of iterations to solve (P) Let F be a (κ, ν)-self-concordant barrier for C and let x_{0} ∈ int C be a starting point, a short-step interior-point algorithm can solve problem (P) up to ϵ accuracy within

O (κ\sqrt{ν} log \frac{c^{T} x_{0} − p^{∗}}{ϵ} ) iterations,

such that at each iteration the self-concordant barrier and its first and second derivatives have to be evaluated and a linear system has to be solved in ℝ^{n}. Complexity invariant w.r.t. to scaling of F Corollary F, ∇F and ∇^{2}F polynomially computable ⇒ problem (P) can be solved in polynomial time. Existence There is a universal SC barrier with parameter (κ = 1, ν = O(n)) (not necessarily computable)

François Glineur, FPMs  Page 8  IPM2000, Budapest, Hungary

[figure]

Two approaches

Scaling doesn’t change complexity ⇒ one of the two constants κ and ν can be arbitrarily fixed If there exists a (κ, ν)-SC barrier F for C then it can be scaled to get a

⋄ (κ\sqrt{ν}, 1)-SC barrier or a ⋄ (1, κ^{2}ν)-SC barrier

Comparison When dealing with problem (NLO), it was typical to

⋄ consider each f_{i} separately ⋄ use the first scaling (ν = 1)

Indeed, if

F_{i} : ℝ^{n} ↦ ℝ : x ↦ − ln(−f_{i}(x))

satisfies the first condition with κ = κ_{i} then

F_{i} is (κ_{i}, 1)-self-concordant

because the second ν condition is automatically satisfied with ν = 1 if f_{i} is convex.

François Glineur, FPMs  Page 9  IPM2000, Budapest, Hungary

[figure]

This implies in the end that

F = ∑_{i=1}^{m} F_{i} is (κ, m)-SC with κ = max_{i=1,...,m} κ_{i}

and that problem (NLO) can be solved in

O(\sqrt{m} max_{i=1,...,m} κ_{i}) = O(\sqrt{m} ∥κ∥_{∞}) iterations

However, second scaling (κ = 1) is superior ! Indeed, we have then that F_{i} is (1, κ_{i}^{2})-SC which implies that

F = ∑_{i=1}^{m} F_{i} is (1, ν)-SC with ν = ∑_{i=1}^{m} κ_{i}^{2}

and that problem (NLO) can be solved in

O(\sqrt{∑_{i=1}^{m} κ_{i}^{2}}) = O(∥κ∥_{2}) iterations which is always better since

∥κ∥_{2} ≤ \sqrt{m} ∥κ∥_{∞}

(strict inequality when κ_{i}’s not all equal)

François Glineur, FPMs  Page 10  IPM2000, Budapest, Hungary

[figure]

[figure]

A useful lemma

Proving self-concordancy not always an easy task → helpful lemma :

\overline{Statement}

[Den Hertog et al.] Let F : ℝ^{n} ↦ ℝ be a convex three times differentiable function on C. If there is a γ ∈ ℝ_{+} 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}}}

then the following barrier functions

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

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

satisfy the first condition on κ with

κ_{1} = γ + 1  for F_{1} on C
κ_{2} = γ + 1 for F_{2} on epi F = {(x, u) | F (x) ≤ u}

François Glineur, FPMs  Page 11  IPM2000, Budapest, Hungary

[figure]

Improvement It is possible to lower κ_{1} and κ_{2} : let

r_{1} : ℝ ↦ ℝ : γ ↦ \begin{cases}1 & when γ ≤ 1 \\ \frac{γ}{\sqrt{3−2/γ}} & when γ ≥ 1 \end{cases}

and

r_{2} : ℝ ↦ ℝ : γ ↦ \begin{cases}1 & when γ ≤ 1 \\ \frac{γ+1+1/γ}{\sqrt{3+4/γ+2/γ^{2}}} & when γ ≥ 1 \end{cases}

We have in fact κ_{1} = r_{1}(γ) and κ_{2} = r_{2}(γ)

Figure 1: Graphs of functions r_{1} and r_{2} Note that r_{1,2}(γ) ≥ 1 with equality when γ ≤ 1 and r_{1,2}(γ) ∼ \frac{γ}{\sqrt{3}} when γ → +∞

François Glineur, FPMs  Page 12  IPM2000, Budapest, Hungary

[figure]

\overline{Proof}

For the case of barrier F_{1} and parameter κ_{1}: let

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

After some manipulations we obtain

∇^{2}F_{1}[h, h] = a^{2} + b^{2}

and

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

We wish to show that

∇^{3}F_{1}(x)[h, h, h] ≤ 2κ_{1}(∇^{2}F_{1}(x)[h, h])^{\frac{3}{2}} which means we have

κ_{1} = sup_{a,b} \frac{3γa^{2}b + 2b^{3}}{2(a^{2} + b^{2})^{\frac{3}{2}}}

which can be shown (after some elementary calculus) to be equal to r_{1}(γ) A similar proof holds for F_{2} and κ_{2}

François Glineur, FPMs  Page 13  IPM2000, Budapest, Hungary

[figure]

[figure]

Structured convex problems

Extended entropy optimization

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

where scalar functions g_{i} : ℝ ↦ ℝ satisfy

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

(which implies convexity) Special case: classical entropy optimization when g_{i}(x) = x ln x ⇒ κ_{i} = 1 Use Lemma with F (x_{i}) = g_{i}(x_{i}) to prove that

− ln(t_{i} − g_{i}(x_{i})) − ln(x_{i}) is (r_{2}(\frac{κ_{i}}{3} ), 2)-SC

Total complexity of extended entropy opt. is

O(\sqrt{2 ∑_{i=1}^{n} r_{2}(\frac{κ_{i}}{3} )^{2}}) iterations

or O(\sqrt{2n}) iterations for entropy optimization

François Glineur, FPMs  Page 14  IPM2000, Budapest, Hungary

[figure]

Geometric optimization

Let {I_{k}}_{k=1...r} be a partition of {1, 2, …, n}. The dual geometric optimization problem is

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

Applying the Lemma with γ = 1 and

F (x_{I_{k}}) = ∑_{i∈I_{k}} x_{i} ln(\frac{x_{i}}{∑_{i∈I_{k}} x_{i}})

we find that the following barrier

− ln(t_{k} − ∑_{i∈I_{k}} x_{i} ln(\frac{x_{i}}{∑_{i∈I_{k}} x_{i}})) − ∑_{i∈I_{k}} ln x_{i}

is (1, |I_{k}| + 1)-self-concordant → global complexity for (DGO) is

O(\sqrt{n + r}) iterations

François Glineur, FPMs  Page 15  IPM2000, Budapest, Hungary

[figure]

l_{p}-norm optimization

Let {I_{k}}_{k=1...r} be a partition of {1, 2, …, m} and p_{i} ≥ 1. The primal l_{p}-norm optimization problem is

max η^{T} x s.t. f_{i}(x) ≤ 0 for all k = 1, …, r

with

f_{i}(x) = ∑_{i∈I_{k}} \frac{1}{p_{i}} |a_{i}^{T} x − c_{i}|^{p_{i}} + b_{k}^{T} x − d_{k}

which can be reformulated as

max η^{T} x s.t. \{ \begin{matrix}|a_{i}^{T} x − c_{i}| & ≤ & s_{i} (≡ 2× lin.) \\ s_{i} & ≤ & ti^{\frac{1}{p_{i}}} \\ ∑i∈I_{k} \frac{t_{i}}{p_{i}} & ≤ & d_{k} − b_{k}^{T} x \end{matrix}

Using F (t_{i}) = ti^{\frac{1}{p_{i}}} and γ = \frac{2− \frac{1}{p_{i}}}{3} we find that

− ln(ti^{\frac{1}{p_{i}}} − s_{i}) − ln t_{i} is (1, 2)-self-concordant

→ global complexity is O(\sqrt{4m + r}) iterations

(a similar result holds for the dual)

François Glineur, FPMs  Page 16  IPM2000, Budapest, Hungary

[figure]

[figure]

Concluding remarks

⋄ Definition of self-concordancy involves two parameters (κ, ν)

⋄ Complexity of IPMs proportional to κ\sqrt{ν}

⋄ Scaling affects κ and ν but not complexity ⇒ one of them can be arbitrarily fixed

⋄ However, when combining (adding) SC barriers with different parameters, it is best to scale them such that all κ’s are equal, e.g. (κ_{i}, 1) gives ∥κ∥_{2} instead of \sqrt{m} ∥κ∥_{∞}

⋄ Den Hertog et al’s lemma has been improved when γ ≥ 1

⋄ This lemma alone is sufficient to prove self-concordancy of the logarithmic barrier for many classes of structured convex problems

François Glineur, FPMs  Page 17  IPM2000, Budapest, Hungary