[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

Mathematical Programming Seminars

CORE, UCL, April 24, 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 for conic optimization Weak duality. b^{T} y ≤ c^{T} x for every feasible x and y, with equality iff x^{T} s = 0 ⇒ p^{∗} − d^{∗} ≥ 0 is called the duality gap (always nonnegative). Strong duality (Slater condition) Definition: x is strictly feasible ⇔ x is feasible and x ∈ int C ∃ strictly feasible point for primal ⇒ zero duality gap, i.e. p^{∗} = d^{∗}. Moreover, if dual is feasible, d^{∗} is attained, i.e. d^{∗} = max b^{T} y Corollary If both the primal and the dual have a strictly feasible point, the duality gap is zero and both optimal values are attained. Our approach: Use these general theorems to prove duality properties for specific classes of problems

[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. But not convex (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 ⋄ No duality gap !

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

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

⇒ dual conic problem with variables (ỹ, s̃), data (Ã, b̃, c̃) and cone C^{∗}

ỹ = y, s̃ = (\begin{matrix}s \\ v \end{matrix}) , Ã = (A 0) , b̃ = b, c̃ = (\begin{matrix}c \\ e \end{matrix}) , C^{∗} = G^{n_{1}}×⋯×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

[figure]

Duality in geometric optimization

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

b^{T} y ≤ 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}} .

Equality occurs if and only if

(∑_{i∈I_{k}} x_{i})e^{a_{i}^{T} y−c_{i}} = x_{i} for all i ∈ I_{k}, k ∈ R .

Proof. Use weak duality theorem on conic primal-dual pair and extend objective values to the geometric optimization problems.

⋄ This proof and the corresponding classical proof are not difficult. ⋄ This property is a merely a consequence of convexity

[figure]

Strong duality If the primal and the dual are feasible, their optimum objective values are equal (but not necessarily attained). This strong duality property is not valid for all convex problems but depends on the specific structure of geometric optimization. Proof. Proceed by proving the existence of a strictly feasible point for the dual conic program ⇔ z_{k} > ∑_{i∈I_{k}} x_{i} log _{\frac{x_{i}}{∑_{i∈I_{k}} x_{i}}} and x_{i} > 0 ∀i.

But the linear constraints Ax = b may force x_{i} = 0 for some i for every feasible solution ! ⇒ detect these zero x_{i} components and form a restricted primal-dual pair without these variables ⇒ strong duality holds

[figure]

Strategy diagram

(P) ≡ (ConeP) ⟷^{Weak duality}  (ConeD)  ≡ (D)

↕^{∗}  ↕

(RestrP)

Strong duality

⟷ (RestrD)

↑

(Slater condition)

[figure]

Detection. Use the following linear problem

min 0 s.t. Ax = b and x ≥ 0

Define N = set of indices i such that x_{i} is identically zero on the feasible region and B the set of the other indices: (B, N) is the optimal partition of this linear problem (Goldman-Tucker theorem). Strategy: Remove variables x_{i} for all i ∈ N ⇒ restricted primal-dual conic pair ⇒ the dual has a strictly feasible solution ⇒ zero duality gap. We still have to prove that

⋄ Optimal objective values are equal for restricted and original dual problems (easy)

⋄ Optimal values are equal for restricted and original primal (more difficult: need to perturb optimal solution ⇒ attainment is lost)

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

[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, κ) | x^{T} x^{∗} ≤ κ for all x_{i}^{∗} ∈ dom f_{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.

[figure]

Separable convex optimization Use K^{f} and (K^{f})^{∗} in a primal-dual conic pair of problems ⇒ 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 + F z = b and z ≥ 0 .

⋄ Gen. linear, quadratic, geometric, entropy, l_{p}-norm optimization ⋄ Mix different types of constraints ⋄ Hints towards a primal-dual setting ⋄ Links (?) with extended geometric opt. (Peterson), Young opt.

[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, 1/p + 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]

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

[figure]

Concluding remarks

⋄ A very wide class of problems can be formulated (links with extended geometric optimization [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 (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])