[figure]

Strong duality in geometric optimization using a conic formulation

François Glineur

                     Francois.Glineur@fpms.ac.be

Faculté Polytechnique de Mons

INFORMS Spring 2000 Meeting

Salt Lake City, Utah May 8, 2000

Strong duality in geometric optimization using a conic formulation

[figure]

[figure: Outline]

Introduction

⋄ Geometric optimization

Conic optimization

⋄ Primal-dual pair ⋄ Duality theorems

The geometric cone

⋄ Definition and properties ⋄ Dual cone

Geometric optimization

⋄ Formulation with geometric cone ⋄ Weak duality ⋄ Strong duality

Concluding remarks

François Glineur, FPMs  Page 2  INFORMS2000, Salt Lake City, Utah

[figure]

[figure]

Introduction

Convex optimization

Let f_{i} : ℝ^{n} ↦ ℝ convex functions, i = 0, …, m

inf_{x∈ℝ^{n}} f_{0}(x) s.t. f_{i}(x) ≤ 0 for i = 1, …, m

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

Conic optimization

Let K ⊆ ℝ^{n} be a convex cone

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

Equivalent to convex optimization. Nice form for the dual:

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

where K^{∗} is the dual cone. Example: for LO, we have K = ℝ_{+}^{n} = K^{∗}.

François Glineur, FPMs  Page 3  INFORMS2000, Salt Lake City, Utah

[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. Optimize m variables in vector t ∈ ℝ_{++}^{m}:

inf G_{0}(t) s.t. G_{k}(t) ≤ 1 ∀k ∈ R

where G_{k}’s are posynomials:

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

with 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{t_{2}^{2/3}}{3t_{1}t_{3}^{3}} .

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 4  INFORMS2000, Salt Lake City, Utah

[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 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) We optimize m free variables y ∈ ℝ^{m}. Problem data is b ∈ ℝ^{m}, c ∈ ℝ^{n}, A ∈ ℝ^{m×n}. 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 5  INFORMS2000, Salt Lake City, Utah

[figure]

[figure]

Conic optimization

Let K ⊆ ℝ^{n} be a solid, pointed, closed convex cone. Its dual cone is defined by

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

and is also convex, solid, pointed and closed.

Primal-dual pair

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

Let p^{∗} and d^{∗} be their optimum objective values (not necessarily attained).

Duality theorems

Weak duality. We have b^{T} y ≤ c^{T} x for every feasible x and y. Equality occurs iff x^{T} s = 0 (orthogonality condition). Hence we have in general d^{∗} ≤ p^{∗} ⇒ p^{∗} − d^{∗} is called the duality gap (always nonnegative).

François Glineur, FPMs  Page 6  INFORMS2000, Salt Lake City, Utah

[figure]

Definition: x is strictly feasible ⇔ x is feasible and x ∈ int K Strong duality (Slater condition) If the primal has a strictly feasible point, the duality gap is zero, i.e. p^{∗} = d^{∗}. Moreover, if the dual is feasible, its maximum objective value d^{∗} is attained, i.e. d^{∗} = max b^{T} y (a dualized result also holds) 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

Geometric optimization has nice duality properties, somewhere between the general convex case and linear optimization. We are going to prove these duality properties using these general theorems ⇒ we have to find a suitable convex cone.

François Glineur, FPMs  Page 7  INFORMS2000, Salt Lake City, Utah

[figure]

[figure]

The geometric cone

\overline{Definition}

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

This cone will enable us to express geometric optimization in a conic form. Useful tool: Let x ∈ ℝ_{++}^{n}, δ ∈ ℝ_{+}^{n} such that ∑_{i=1}^{n} δ_{i} = 1. We have

∏_{i=1}^{n} x_{i}^{δ_{i}} ≤ ∑_{i=1}^{n} δ_{i}x_{i} ,

equality occurring iff all x_{i}’s are equal. (a.k.a. weighted arithmetic-geometric mean inequality)

François Glineur, FPMs  Page 8  INFORMS2000, Salt Lake City, Utah

[figure]

\overline{Properties}

⋄ Special cases: G^{0} = ℝ_{+} and G^{1} = ℝ_{+}^{2} ⋄ If (x, θ) ∈ G^{n}, (x′, θ′) ∈ G^{n} and λ ≥ 0 we

have λ(x, θ) ∈ G^{n} and (x + x′, θ + θ′) ∈ G^{n} ⇒ G^{n} is a convex cone.

⋄ G^{n} is closed, solid and pointed ⋄ The interior of G^{n} is (→ Slater condition)

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

\overline{Dual cone}

The dual cone (G^{n})^{∗} is given by

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

It is the epigraph of

f_{n} : ℝ_{+}^{n} ↦ ℝ : x ↦ ∑_{x_{i}^{∗}>0} x_{i}^{∗} log \frac{x_{i}^{∗}}{∑_{i=1}^{n} x_{i}^{∗}}

François Glineur, FPMs  Page 9  INFORMS2000, Salt Lake City, Utah

[figure]

⋄ Special cases: (G^{0})^{∗} = ℝ_{+} and (G^{1})^{∗} = ℝ_{+}^{2}

(but G^{n} is not self-dual for n > 1) ⋄ It is also convex, closed, solid and pointed. ⋄ ((G^{n})^{∗})^{∗} = G^{n} (since G^{n} is closed). ⋄ ℝ_{+}^{n+1} ⊆ (G^{n})^{∗} (since G^{n} ⊆ ℝ_{+}^{n+1}) ⋄ The interior of (G^{n})^{∗} is given by

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

Orthogonality conditions

Let v = (x, θ) ∈ G^{n} and v^{∗} = (x^{∗}, θ^{∗}) ∈ (G^{n})^{∗}. We always have v^{T} v^{∗} ≥ 0, while v^{T} v^{∗} = 0 occurs if and only if

θ = 0 and x_{i}x_{i}^{∗} = 0 for all i

or

θ > 0 and \{ \begin{matrix}θ^{∗} = ∑_{x_{i}^{∗}>0} x_{i}^{∗} log w_{i}^{∗} \\ (∑_{i=1}^{n} x_{i}^{∗})e^{− \frac{x_{i}}{θ}} = x_{i}^{∗} for all i \end{matrix}

François Glineur, FPMs  Page 10  INFORMS2000, Salt Lake City, Utah

[figure]

François Glineur, FPMs  Page 11  INFORMS2000, Salt Lake City, Utah

[figure]

We are now ready to apply the general duality theory for conic primal-dual pairs, using our dual cones G^{n} and (G^{n})^{∗}, to derive the duality properties of the geometric optimization primal-dual pairs.

Notation: v_{I} (resp. M_{I}) ≡ restriction of vector v (resp. matrix M) to indices belonging to I.

Strategy diagram

(P G) ≡ (CP G) ⟷^{Weak} (CDG) ≡ (DG)
↕^{∗}  ↕
(RP G) ⟷^{Strong} (RDG)

{↑ \atop (Slater)}

François Glineur, FPMs  Page 12  INFORMS2000, Salt Lake City, Utah

[figure]

[figure]

Geometric optimization

Formulation with G^{n} cone

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. This is a standard conic problem with variables (ỹ, s̃), data (Ã, b̃, c̃) and a cone K^{∗}

François Glineur, FPMs  Page 13  INFORMS2000, Salt Lake City, Utah

[figure]

Indeed we have

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

c̃ = (\begin{matrix}c \\ e \end{matrix}) and K^{∗} = 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 14  INFORMS2000, Salt Lake City, Utah

[figure]

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 optimization primal-dual pair and extend objective values to the geometric optimization primal-dual pair.

⋄ This proof and the corresponding classical proof are not too difficult.

⋄ This property is a merely a consequence of convexity

François Glineur, FPMs  Page 15  INFORMS2000, Salt Lake City, Utah

[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 this class of problems. 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 (which had no influence on the objective/constraints anyway).

François Glineur, FPMs  Page 16  INFORMS2000, Salt Lake City, Utah

[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. There remains to prove that

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

⋄ Optimal values are equal for restricted and original primal problems (more difficult). Moreover, attainment is lost in the process.

François Glineur, FPMs  Page 17  INFORMS2000, Salt Lake City, Utah

[figure]

Restricted problems Dual

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

Convert solution to original dual (which has additional variables): let x_{i} = 0 for all i ∈ N ⇒ same objective. Primal

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

with

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

Convert solution to original dual is not straightforward because feasibility cannot be guaranteed: posynomials have additional terms ! We need to modify the optimal solution of the restricted dual.

François Glineur, FPMs  Page 18  INFORMS2000, Salt Lake City, Utah

[figure]

Strategy Perturb the optimal solution ỹ of the restricted primal with a well-chosen vector. The Goldman-Tucker theorem implies the existence of a strictly complementary solution to any primal-dual pair of linear problems. ⇒ applied to our detection program and its dual, this guarantees the existence of a vector ȳ such that

A_{B}^{T} ȳ = 0 and A_{N}^{T} ȳ < 0 .

These properties imply that y = ỹ + λȳ is asymptotically feasible for the original primal when λ tends to +∞, while keeping the same objective value as ỹ. Combining with another trick (mixing with a feasible solution) leads to the expected result ⇒ the original primal optimum objective value is equal to the original dual optimum objective value.

François Glineur, FPMs  Page 19  INFORMS2000, Salt Lake City, Utah

[figure]

[figure]

Concluding remarks

⋄ These proofs are shorter than the classical ones. All the specificity of the problems is confined to the pair of dual cones

⋄ Other classical results can also be recovered easily (posynomial objective, notion of subinfimum, etc.)

⋄ This strategy can be applied to other types of convex problems, i.e. entropy optimization and l_{p}-norm optimization

⋄ Finding a computable self-concordant barrier for the G^{n} cone provides an algorithm with polynomial complexity (short-step path-following interior-point method, Nesterov & Nemirovsky)

⋄ This primal-dual pair of cones might prove helpful in designing efficient algorithms (cf. self-scaled cones)

François Glineur, FPMs  Page 20  INFORMS2000, Salt Lake City, Utah