[figure]

A conic approach for separable convex optimization

François Glineur

F.N.R.S. Postodoctoral Researcher

                                  Francois.Glineur@fpms.ac.be

Faculté Polytechnique de Mons

INFORMS Annual Meeting 2001

Miami Beach, November 5, 2001

[figure]

Outline

Introduction

⋄ Convex and conic optimization, duality theorems ⋄ Geometric optimization: A special case of separable optimization

Geometric optimization

⋄ The geometric cone ⋄ Conic formulation and duality

Generalization to separable optimization

⋄ The separable cone ⋄ Separable convex optimization ⋄ Interior-point methods and self-concordant barriers

Concluding remarks

[figure]

Introduction

Convex optimization Let f_{0} : ℝ^{n} ↦ ℝ a convex function and C ⊆ ℝ^{n} a convex set

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

Properties ⋄ Local optima ⇒ global, form a convex optimal set ⋄ Lagrange duality ⇒ related (asymmetric) dual problem ⋄ Efficient interior-point methods (self-concordant barriers) Conic optimization Let C ⊆ ℝ^{n} a solid, pointed, closed convex cone :

inf_{x∈ℝ^{n}} c^{T} x s.t. Ax = b and x ∈ C ⇒ Equivalent setting

[figure]

Primal-dual pair Dual cone is also a solid pointed closed convex cone

C^{∗} = {x^{∗} ∈ ℝ^{n} | x^{T} x^{∗} ≥ 0 for all x ∈ C}

⇒ pair of primal-dual problems

inf_{x∈ℝ^{n}} c^{T} x s.t. Ax = b and x ∈ C
sup_{(y,s)∈ℝ^{m+n}} b^{T} y s.t. A^{T} y + s = c and s ∈ C^{∗}

Examples: C = ℝ_{+}^{n} = C^{∗} ⇒ linear optimization, C = 𝕊_{+}^{n} = C^{∗} ⇒ semidefinite optimization (self-duality) Advantages over classical formulation

⋄ Remarkable primal-dual symmetry

⋄ Special handling of (easy) linear equality constraints

[figure]

Duality theorems Weak duality Every feasible primal (resp. dual) solution is an upper (resp. lower) bound on all feasible dual (resp. primal) solutions. (Conic case : b^{T} y ≤ c^{T} x for all feasible x, y) ⇒ p^{∗} − d^{∗} ≥ 0 is called the duality gap (always nonnegative). This is valid even when no convexity is present. Strong duality (Slater condition) The duality gap is guaranteed to be zero (p^{∗} = d^{∗}) if

⋄ Both problems are convex and

⋄ ∃ a Slater point, i.e. a strictly feasible (interior) solution (Conic case : x is strictly feasible ⇔ x is feasible and x ∈ int C) But sometimes strong duality holds without Slater condition

[figure]

Strong duality with no Slater point ... Can fail: Using the second-order cone 𝕃^{n} = {(x_{1}, …, x_{n+1}) ∈ ℝ^{n} × ℝ_{+} | ∑_{i=1}^{n} x_{i}^{2} ≤ x_{n+1}^{2}}

inf x_{2} s.t. (x_{1}, x_{2}, x_{3}) ∈ 𝕃^{2} and x_{1} − x_{3} = 0

sup 0 y s.t. (x_{1}^{∗}, x_{2}^{∗}, x_{3}^{∗}) ∈ 𝕃^{2} and (\begin{matrix}1 \\ 0 \\ −1 \end{matrix}) y + (\begin{matrix}x_{1}^{∗} \\ x_{2}^{∗} \\ x_{3}^{∗} \end{matrix}) = (\begin{matrix}0 \\ 1 \\ 0 \end{matrix})

We have p^{∗} = 0 and d^{∗} = −∞ ⇒ infinite duality gap

Can hold: Linear optimization always features a zero duality gap (except when both problems are infeasible: we have then p^{∗} = +∞ and d^{∗} = −∞ ⇒ infinite duality gap)

[figure]

Separable convex optimization

Goal: study a large well-behaved subset of convex optimization \overline{Definition} Consider n scalar closed proper convex functions f_{i} : ℝ ↦ ℝ ∪ {+∞}, K = {1, …, r} and a partition {I_{k}}_{k∈R} of {1, …, n}

sup b^{T} y s.t. ∑_{i∈I_{k}} f_{i}(c_{i} − a_{i}^{T} y) ≤ d_{k} − g_{k}^{T} y ∀k ∈ R

⋄ Linear, quadratic, geometric, entropy, l_{p}-norm optimization ⋄ Mix different types of constraints ⋄ Linear objective without loss of generality ⋄ Links with Young optimization

[figure]

Geometric optimization

Optimize positive vector using posynomials as objective/constraints

inf_{t∈ℝ_{++}^{m}} G_{0}(t) s.t. G_{k}(t) ≤ 1 ∀k ∈ R with posynomials G_{i}’s

A posynomial is a sum of positive monomials : 2\frac{t_{1}^{2}}{t_{2}} + 3\sqrt{t_{2}} + \frac{1}{3} \frac{t_{2}^{2/3}}{t_{1}t_{3}^{3}}

Formally: monomials indexed by i ∈ I = {1, …, n}, posynomials indexed by k ∈ R = {0, 1, …, r} using a partition {I_{k}}_{k∈R} of I.

G_{k} : ℝ_{++}^{m} ↦ ℝ_{++} : t ↦ ∑_{i∈I_{k}} C_{i} ∏_{j=1}^{m} t_{j}^{a_{ij}} with a_{ij} ∈ ℝ and C_{i} ∈ ℝ_{++}

Many applications (e.g. in engineering: model or approximate relations), generalizes linear optimization. Not convex in this form (take G_{0}(t) = \sqrt{t_{1}}) but can be convexified !

[figure]

Convexification W.l.o.g. we consider a linear objective and let t_{j} = e^{y_{j}} for all j Primal:

sup_{y∈ℝ^{m}} b^{T} y s.t. g_{k}(y) ≤ 1 for all k ∈ R

using c_{i} = − log C_{i} and g_{k}(y) such that g_{k}(y) = G_{k}(t), i.e.

g_{k} : ℝ^{m} ↦ ℝ_{++} : y ↦ ∑_{i∈I_{k}} e^{a_{i}^{T} y−c_{i}}

Dual: (Lagrangean)

inf c^{T} x + ∑_{k∈R} ∑_{\begin{matrix}i∈I_{k} \\ x_{i}>0 \end{matrix}} x_{i} log \frac{x_{i}}{∑_{i∈I_{k}} x_{i}} s.t. Ax = b and x ≥ 0

Results (Duffin, Peterson and Zener, 1967)

⋄ Convex problem, weak duality, strong duality with a Slater point ⋄ Never a duality gap ! ⇒ strong duality without a Slater point

[figure]

The geometric cone

Objective: model geometric optimization with cones Definition [Gl. 99] Let n ∈ ℕ. We define G^{n} as

G^{n} = \{(x, θ) ∈ ℝ_{+}^{n} × ℝ_{+} | ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} ≤ 1\} (taking e^{− \frac{x_{i}}{0}} = 0)

\overline{Properties} ⋄ G^{0} = ℝ_{+}, G^{1} = ℝ_{+}^{2}, G^{n} is a solid, pointed, closed convex cone. ⋄ int G^{n} can be computed (replace ≤ by < and ℝ_{+} by ℝ_{++}). ⋄ Dual cone (G^{n})^{∗} can be computed explicitly (and is an epigraph)

(G^{n})^{∗} = \{(x^{∗}, θ^{∗}) ∈ ℝ_{+}^{n} × ℝ | θ^{∗} ≥ ∑_{x_{i}^{∗}>0} x_{i}^{∗} log \frac{x_{i}^{∗}}{∑_{i=1}^{n} x_{i}^{∗}} \}

[figure]

A conic formulation for geometric optimization

Formulation with G^{n} cone v_{I}/M_{I} ≡ restriction of vector v/matrix M to subset of indices I Primal

sup b^{T} y s.t. g_{k}(y) ≤ 1 for all k ∈ R

Introducing variables s_{i} = c_{i} − a_{i}^{T} y for all i ∈ I we get

sup b^{T} y s.t. s = c − A^{T} y and ∑_{i∈I_{k}} e^{−s_{i}} ≤ 1 for all k ∈ R

⇕

sup b^{T} y s.t. (\begin{matrix}A^{T} \\ 0 \end{matrix} ) y + (\begin{matrix}s \\ v \end{matrix}) = (\begin{matrix}c \\ e \end{matrix}) and (s_{I_{k}}, v_{k}) ∈ G^{n_{k}} ∀k ∈ R

e is the all-one vector, n_{k} = #I_{k} and v_{i}’s are fictitious variables.

[figure]

Advantages of the conic approach

⋄ The dual problem can be very easily formulated once the dual cone is computed

⋄ Duality properties can be derived from the general duality theorems of conic optimization, in particular:

– Proving weak duality is straightforward

– Proving strong duality with a Slater point is also simple

– In the case of geometric optimization, there is no duality gap, even in the absence of a Slater point: this can also be shown using the conic duality theorem (and gives simpler proofs and more insight than the classical techniques)

[figure]

Generalizing this conic framework

Comparing cones

G^{n} = \{(x, θ) ∈ ℝ_{+}^{n} × ℝ_{+} | ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} ≤ 1\}

L^{p} = \{(x, θ, κ) ∈ ℝ^{n} × ℝ_{+}^{2} | ∑_{i=1}^{n} \frac{|x_{i}|^{p_{i}}}{p_{i}θ^{p_{i}−1}} ≤ κ\}

\overline{Variants}

G_{2}^{n} = \{(x, θ, κ) ∈ ℝ_{+}^{n} × ℝ_{+}^{2} | θ ∑_{i=1}^{n} e^{− \frac{x_{i}}{θ}} ≤ κ\}

L^{p} = \{(x, θ, κ) ∈ ℝ^{n} × ℝ_{+}^{2} | θ ∑_{i=1}^{n} \frac{1}{p_{i}} |\frac{x_{i}}{θ} |^{p_{i}} ≤ κ\}

[figure]

The separable cone [Gl. 00]

Consider a set of n scalar closed proper convex functions f_{i} : ℝ ↦ ℝ

K^{f} = cl K^{∘f} = cl\{(x, θ, κ) ∈ ℝ^{n} × ℝ_{++} × ℝ | θ ∑_{i=1}^{n} f_{i}(\frac{x_{i}}{θ}) ≤ κ\}

⋄ K^{f} is a closed convex cone and K^{f} ⊆ ℝ^{n} × ℝ_{+} × ℝ ⋄ K^{f} generalizes L^{p} and G_{2}^{n} (case θ = 0 handled with cl operation) ⋄ The dual can be computed: very symmetric formulation

(K^{f})^{∗} = cl\{(x^{∗}, θ^{∗}, κ^{∗}) ∈ ℝ^{n} × ℝ_{++} × ℝ | κ^{∗} ∑_{i=1}^{n} f_{i}^{∗}(−\frac{x_{i}^{∗}}{κ^{∗}}) ≤ θ^{∗}\}

using the conjugate functions (also closed, proper and convex)

f_{i}^{∗} : ℝ ↦ ℝ : x^{∗} ↦ sup_{x∈ℝ^{n}} {xx^{∗} − f_{i}(x)}

[figure]

Additional properties

⋄ int K^{f} can be identified (⇒ Slater condition): int K^{f} = int K^{∘f} =

\{(x, θ, κ) ∈ ℝ^{n}×ℝ_{++}×ℝ | x_{i} ∈ int dom f_{i} and θ ∑_{i=1}^{n} f_{i}(\frac{x_{i}}{θ}) < κ\} .

⋄ If we require in addition that int dom f_{i} ≠ ∅ and int dom f_{i}^{∗} ≠ ∅, we have that K^{f} and (K^{f})^{∗} are solid and pointed

⋄ Points with θ = 0 can be identified

K^{f} \ K^{∘f} = \{(x, 0, κ) | ∑_{i=1}^{n} lim_{θ→0} θf_{i}(\frac{x_{i}}{θ}) ≤ κ\} .

⋄ l_{p}-norm optimization: f_{i} : x ↦ \frac{1}{p_{i}} |x|^{p_{i}} and f_{i}^{∗} : x^{∗} ↦ \frac{1}{q_{i}} |x^{∗}|^{q_{i}}

⋄ Geometric optimization: f_{i} : x ↦ e^{−x} and f_{i}^{∗} : ℝ_{+} ↦ ℝ : x^{∗} ↦ x^{∗}(1 − log(−x^{∗})) for x^{∗} < 0, 0 for x^{∗} = 0, +∞ for x^{∗} > 0.

[figure]

Formulation with K^{f} cone Primal

sup b^{T} y s.t. ∑_{i∈I_{k}} f_{i}(c_{i} − a_{i}^{T} y) ≤ d_{k} − g_{k}^{T} y ∀k ∈ R

Introducing variables x_{i}^{∗} = c_{i} − a_{i}^{T} y and z_{k}^{∗} = d_{k} − g_{k}^{T} y we get

sup b^{T} y s.t. x^{∗} = c − A^{T} y, z^{∗} = d − G^{T} y, ∑_{i∈I_{k}} f_{i}(x_{i}^{∗}) ≤ z_{k}^{∗} ∀k ∈ R

⇕

sup b^{T} y s.t. (\begin{matrix}A^{T} \\ G^{T} \\ 0 \end{matrix} ) y+(\begin{matrix}x^{∗} \\ z^{∗} \\ v^{∗} \end{matrix}) = (\begin{matrix}c \\ d \\ e \end{matrix}) , (x_{I_{k}}^{∗}, v_{k}^{∗}, z_{k}^{∗}) ∈ K^{f_{I_{k}}} ∀k ∈ R

(e is the all-one vector and v_{i}’s are fictitious variables)

[figure]

⇒ standard dual conic problem based on data (Ã, b̃, c̃) and cone C^{∗}

Ã = (A G 0) , b̃ = b, c̃ = (\begin{matrix}c \\ d \\ e \end{matrix}) , C^{∗} = K^{f_{I_{1}}} × ⋯ × K^{f_{Ir}} .

⇒ we can mechanically derive the dual !

inf (\begin{matrix}c \\ d \\ e \end{matrix})^{T} (\begin{matrix}x \\ z \\ v \end{matrix}) s.t. (A G 0) (\begin{matrix}x \\ z \\ v \end{matrix}) = b and (x_{I_{k}}, v_{k}, z_{k}) ∈ (K^{f_{I_{k}}})^{∗}

⇕

inf c^{T} x+d^{T} z+e^{T} v s.t. Ax+Gz = b, z ≥ 0 and v_{k} ≥ z_{k} ∑_{i∈I_{k}} f_{i}^{∗}(−\frac{x_{i}}{z_{k}})

⇔ inf c^{T} x+d^{T} z+ ∑_{k∈R} z_{k} ∑_{i∈I_{k}} f_{i}^{∗}(−\frac{x_{i}}{z_{k}}) s.t. Ax+Gz = b and z ≥ 0

(taking the limit if necessary when z_{k} = 0)

François Glineur, FPMs  Page 17  INFORMS Annual Meeting 2001

[figure]

Some other types of constraints ⋄ Model circle/ellipses in ℝ^{2}

f_{1} : x ↦ \begin{cases}−\sqrt{a^{2} − x^{2}} & if |x| ≤ a \\ +∞ & if |x| > a \end{cases} f_{1}^{∗} : x^{∗} ↦ a\sqrt{1 + x^{∗2}}

⋄ CES functions (consumer theory), 0 < p < 1, q < 0, \frac{1}{p} + \frac{1}{q} = 1

f_{2} : x ↦ \begin{cases}−\frac{1}{p}x^{p} & if x ≥ 0 \\ +∞ & if x < 0 \end{cases} f_{2}^{∗} : x^{∗} ↦ \begin{cases}−\frac{1}{q}(−x^{∗})^{q} & if x^{∗} < 0 \\ +∞ & if x^{∗} ≥ 0 \end{cases}

⋄ Logarithms (with property that f^{∗}(x^{∗}) = f(−x^{∗}))

f_{3} : x ↦ \begin{cases}−\frac{1}{2} − log x & x > 0 \\ +∞ & x ≤ 0 \end{cases} f_{3}^{∗} : x^{∗} ↦ \begin{cases}−\frac{1}{2} − log(−x^{∗}) & x^{∗} < 0 \\ +∞ & x^{∗} ≥ 0 \end{cases}

[figure]

Duality in separable optimization

Weak duality If y is feasible for the primal and (x, z) is feasible for the dual, we have

b^{T} y ≤ c^{T} x + d^{T} z + ∑_{k∈R} z_{k} ∑_{i∈I_{k}} f_{i}^{∗}(−\frac{x_{i}}{z_{k}}) .

Strong duality If the primal and the dual are feasible, their optimum objective values are equal (but not necessarily attained) ⇒ zero duality gap without Slater condition.

[figure]

Interior-point methods and self-concordant barriers

According to [Nesterov & Nemirovsky], a convex problem in conic format is solvable by a primal short-step interior-point algorithm in polynomial time if C admits a computable self-concordant barrier. A solution of accuracy ϵ can be reached in O (\sqrt{ν} log \frac{1}{ϵ}) iterations. Definition: A function F : int C ↦ ℝ is called a self-concordant barrier with parameter ν on C iff

⋄ F is convex and three times differentiable

⋄ F (x) → +∞ when x → ∂C

⋄ 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}}
∇F (x)^{T} (∇^{2}F (x))^{−1}∇F (x) ≤ ν

[figure]

Application to separable optimization Given a self-concordant barrier F_{i} with parameter ν_{i} for each two-dimensional epigraph epi f_{i}, 1 ≤ i ≤ n (easy to find), there exists a self-concordant barrier F for K^{f} with parameter O (∑_{i=1}^{n} ν_{i}) Outline of the proof

1. Form the Cartesian product X = epi f_{1} × ⋯ × epi f_{n}

X = {(x, y) ∈ ℝ^{2n} | f_{i}(x_{i}) ≤ y_{i} ∀i}

⇒ F_{X}(x, y) = ∑_{i=1}^{n} F_{i}(x_{i}, y_{i}) is s.c. for X with ν_{X} = ∑_{i=1}^{n} ν_{i}

2. Extend X with a linear variable to

X′ = {(x, y, κ) ∈ ℝ^{2n+1} | f_{i}(x_{i}) ≤ y_{i} ∀i and κ = ∑_{i=1}^{n} y_{i}}

This additional variable κ links the epigraphs,

F′_{X}(x, y, κ) = F (x, y) is still s.c. for X′ with ν_{X′} = ∑_{i=1}^{n} ν_{i}

[figure]

3. Consider the closed conic hull of X′ (introducing a homogenizing variable θ)

Y = cl{(x, y, κ, θ) ∈ ℝ^{2n+2} | (x/θ, y/θ, κ/θ) ∈ X′}

There exists a s.c. barrier F_{Y} for Y with ν_{Y} = O (ν_{X′})

4. The projection of Y on the space (x, κ, θ) is exactly equal to K^{f} ⇒ we have a s.c.b. for K^{f} with parameter O (∑_{i=1}^{n} ν_{i})

Indeed, we have

(x/θ, y/θ, κ/θ) ∈ X′ ⇔ f_{i}(\frac{x_{i}}{θ}) ≤ \frac{y_{i}}{θ} ∀i and \frac{κ}{θ} = ∑_{i=1}^{n} \frac{y_{i}}{θ}

which clearly shows that (x, κ, θ) ∈ K^{f} ⇔ ∃y ∈ ℝ^{n} | (x, y, κ, θ) ∈ Y

⇒ separable problems can be solved in O (\sqrt{∑_{i=1}^{n} ν_{i}} log \frac{1}{ϵ}) iterations (→ polynomial time if each F_{i} is computable in polynomial time)

[figure]

Concluding remarks

⋄ A very wide class of separable convex problems can be formulated (including linear, quadratic, entropy, l_{p}-norm and geometric optimization)

⋄ Using this setting, interesting duality properties can be obtained in a seamless way (weak and strong duality without Slater condition)

⋄ Finding a computable self-concordant barrier for the K^{f} cone (which can be done using self-concordant barriers on 2-dimensional epigraphs of scalar functions f_{i}) provides a primal algorithm with polynomial complexity (short-step path-following interior-point method, [Nesterov & Nemirovsky 83])

⋄ Primal-dual formulation ⇒ first step towards true primal-dual algorithms (self-regular barriers, [Peng et al. 00])