[figure]

A conic approach for separable convex optimization

François Glineur

Aspirant F.N.R.S.

                     Francois.Glineur@fpms.ac.be

Faculté Polytechnique de Mons

Journées du 3ème cycle F.N.R.S. en programmation mathématique

Han-sur-Lesse, February 2, 2001

A conic approach for separable convex optimization

[figure]

[figure: Outline]

Introduction

⋄ Conic optimization ⋄ Geometric optimization

Geometric optimization

⋄ The geometric cone ⋄ A conic formulation

Generalization

⋄ The separable cone ⋄ Separable convex optimization

Concluding remarks

François Glineur, FPMs  Page 2  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

[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 ⋄ All local optima are global ⋄ Optimum set is convex ⋄ Lagrange duality ⇒ related dual problem ⋄ Efficient interior-point methods

Conic optimization

Let C ⊆ ℝ^{n} a closed convex cone

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

Equivalent to convex optimization

François Glineur, FPMs  Page 3  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

Primal-dual pair

Dual cone

C^{∗} = {x^{∗} ∈ ℝ^{n} | x^{T} x^{∗} ≥ 0 for all x ∈ C} is also a closed convex cone ⇒ symmetrical 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

François Glineur, FPMs  Page 4  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

Geometric optimization

Let R = {0, 1, 2, …, r}, I = {1, 2, …, n} ; {I_{k}}_{k∈R} a partition of I into r + 1 classes. A posynomial is a sum of positive monomials

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

defined by data a_{ij} ∈ ℝ and C_{i} ∈ ℝ_{++} Example: G(t_{1}, t_{2}, t_{3}) = 2\frac{t_{1}^{2}}{t_{2}} + 3\sqrt{t_{2}} + \frac{1}{3} \frac{t_{2}^{2/3}}{t_{1}t_{3}^{3}} Optimize m variables in vector t ∈ ℝ_{++}:

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

where G_{k}’s are posynomials: . Many applications, especially in engineering (optimizing design parameters). Generalization of linear optimization. Not convex (take G_{0}(t) = \sqrt{t_{1}}) but can be convexified with a change of variables.

François Glineur, FPMs  Page 5  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

Convexification

W.l.o.g. we consider a linear objective and let

t_{j} = e^{y_{j}} for all j ∈ {1, 2, …, m} Primal:

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

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

(let c_{i} = − log C_{i} ⇒ g_{k}(y) = G_{k}(t) equivalence) 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 ⋄ No duality gap !

François Glineur, FPMs  Page 6  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

[figure]

The geometric cone

Objective: model geometric optimization within the conic framework

Definition [Gl. 99]

Let n ∈ ℕ. We define G^{n} as

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

with the convention when θ = 0

e^{− \frac{x_{i}}{0}} = 0

\overline{Properties}

⋄ Special cases: G^{0} = ℝ_{+} and G^{1} = ℝ_{+}^{2} ⋄ G^{n} is a closed convex cone. ⋄ (G^{n})^{∗} ⊆ ℝ_{+}^{n} × ℝ is

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

François Glineur, FPMs  Page 7  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

François Glineur, FPMs  Page 8  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

[figure]

Geometric optimization

Formulation with G^{n} cone

Notation: v_{I} (resp. M_{I}) ≡ restriction of vector v (resp. matrix M) to indices belonging to 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 ∀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}} for all k ∈ R

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

François Glineur, FPMs  Page 9  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

This is a standard conic problem with variables (ỹ, s̃), data (Ã, b̃, c̃) and a cone C^{∗}

ỹ = y, s̃ = (\begin{matrix}s \\ v \end{matrix}) , Ã = (A 0) , b̃ = b,

c̃ = (\begin{matrix}c \\ e \end{matrix}) and C^{∗} = G^{n_{1}} × G^{n_{2}} × ⋯ × G^{n_{r}} .

⇒ we can mechanically derive the dual !

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

⇕

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

⇔  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

François Glineur, FPMs  Page 10  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

[figure]

Generalizing our 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}} ≤ κ\}

François Glineur, FPMs  Page 11  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

The separable cone [Gl. 00]

Consider a set of n scalar closed proper convex functions

f_{i} : ℝ ↦ ℝ

and define K^{f} as

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

⋄ K^{f} generalizes L^{p} and G_{2}^{n} ⋄ K^{f} is a closed convex cone ⋄ The dual (K^{f})^{∗} ⊆ ℝ^{n} × ℝ_{++} × ℝ is

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

using the conjugate functions

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

(also closed, proper and convex)

François Glineur, FPMs  Page 12  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

Separable convex optimization

Primal-dual conic pair with K^{f} and (K^{f})^{∗} → 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 ∈ K

Dual

inf \{c^{T} x + d^{T} z + ∑_{k∈K|z_{k}>0} z_{k} ∑_{i∈I_{k}} f_{i}^{∗}(−\frac{x_{i}}{z_{k}} )

− ∑_{k∈K|z_{k}=0} inf_{x_{I_{k}}^{∗} ∈dom f_{I_{k}}} x_{I_{k}}^{T}x_{I_{k}}^{∗} }

s.t. Ax + Gz = b and z ≥ 0 .

⋄ Generalizes linear, quadratic, geometric,

entropy, l_{p}-norm optimization and others ... ⋄ Mix different types of constraints ⋄ Justification for conventions when θ = 0 ⋄ Hints towards a primal-dual setting

François Glineur, FPMs  Page 13  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

Some other types of constraints

⋄

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}}

⋄

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

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

⋄

f_{3} : x ↦ \begin{cases}−\frac{1}{2} − log x & if x > 0 \\ +∞ & if x ≤ 0 \end{cases}

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

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

François Glineur, FPMs  Page 14  3ème cycle F.N.R.S., Han-sur-Lesse

[figure]

[figure]

Concluding remarks

⋄ A very wide class of problems can be formulated (links with extended geometric programming [Peterson 80])

⋄ Using this setting, duality properties can be obtained easily (weak and strong duality without Slater condition)

⋄ Finding a computable self-concordant barrier for the K^{f} cone 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])

François Glineur, FPMs  Page 15  3ème cycle F.N.R.S., Han-sur-Lesse