[figure]

Deriving duality for l_{p}-norm optimization using conic optimization

François Glineur

                     Francois.Glineur@fpms.ac.be

Faculté Polytechnique de Mons Delft University of Technology

LP 99 Copenhagen, August 28, 1999

Deriving Duality for lp-norm Optimization Using Conic Optimization

[figure]

[figure: Outline]

Introduction

⋄ l_{p}-norm optimization

Conic optimization

⋄ Primal-dual pair ⋄ Duality theorems

\overline{The L^{p} cone}

⋄ Definition ⋄ Properties

l_{p}-norm optimization

⋄ Formulation with L^{p} cone ⋄ Weak duality ⋄ Strong duality

Concluding remarks

François Glineur, FPMs  Page 2  LP 99, Copenhagen

[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  LP 99, Copenhagen

[figure]

l_{p}-norm optimization

Let K = {1, 2, …, r} and I = {1, 2, …, n}. Let {I_{k}}_{k∈K} be a partition of I into r classes. Data: A ∈ ℝ^{m×n}, B ∈ ℝ^{m×r}, η ∈ ℝ^{m}, c ∈ ℝ^{n} and d ∈ ℝ^{r}. Variables x ∈ ℝ^{n}, z ∈ ℝ^{r}, y ∈ ℝ^{m}. Primal:

inf ψ(x, z) = c^{T} x + d^{T} z + ∑_{k=1}^{r} z_{k} ∑_{i∈I_{k}} \frac{1}{p_{i}} |\frac{x_{i}}{z_{k}} |^{p_{i}}
s.t. Ax + Bz = η and z ≥ 0

Dual: (with \frac{1}{p_{i}} + \frac{1}{q_{i}} = 1)

sup η^{T} y
s.t. ∑_{i∈I_{k}} \frac{1}{q_{i}} |c_{i} − a_{i}^{T} y|^{q_{i}} ≤ d_{k} − b_{k}^{T} y ∀k ∈ K

Includes linear optimization, convex quadratic optimization, l_{p}-norm approximation. Properties (Peterson and Ecker, 1967)

⋄ Convex program ⇒ weak duality ⋄ No duality gap and dual attainment

François Glineur, FPMs  Page 4  LP 99, Copenhagen

[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 5  LP 99, Copenhagen

[figure]

Definition: x is strictly feasible ⇔ x is feasible and x ∈ int K

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 (the same result holds for the dual)

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 l_{p}-norm 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 6  LP 99, Copenhagen

[figure]

[figure: The L^{p} cone]

\overline{Definition}

Let p ∈ ℝ^{n} with p_{i} > 1. We define the function

f_{p} : ℝ^{n} × ℝ_{+} ↦ ℝ_{+} ∪ {+∞}
: (x, θ) ↦ ∑_{i=1}^{n} \frac{|x_{i}|^{p_{i}}}{p_{i}θ^{p_{i}−1}}

with the convention

\frac{|x|}{0} = \begin{cases}+∞ & if x ≠ 0 \\ 0 & if x = 0 \end{cases}

Properties ⋄ dom f_{p} = ℝ^{n} × ℝ_{++} ∪ (0, 0) ⋄ f_{p}(λx, λθ) = λf_{p}(x, θ) for λ ≥ 0, i.e. f_{p} is

positively homogeneous ⋄ f_{p}(x + x′, θ + θ′) ≤ f_{p}(x, θ) + f_{p}(x′, θ′), i.e.

f_{p} is subadditive ⇒ f_{p} is convex

François Glineur, FPMs  Page 7  LP 99, Copenhagen

[figure]

We define the cone L^{p} by

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

i.e. L^{p} is the epigraph of f_{p}. This cone will enable us to express l_{p}-norm optimization in a conic form.

\overline{Properties}

⋄ L^{p} is a convex cone

⋄ The interior of L^{p} is int L^{p} = int epi f_{p} = {(x, θ, κ) | (x, θ) ∈ int dom f_{p} and f_{p}(x, θ) < κ}

⋄ Special case: when p_{i} = 2 for all i we have

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

i.e. the hyperbolic or rotated second-order cone.

François Glineur, FPMs  Page 8  LP 99, Copenhagen

[figure]

\overline{Dual cone}

Define the switched cone L_{s}^{p} as L^{p} with its last two components exchanged, i.e.

(x, θ, κ) ∈ L_{s}^{p} ⇔ (x, κ, θ) ∈ L^{p}

Theorem. Let p, q ∈ ℝ^{n} such that p_{i}, q_{i} > 1 and \frac{1}{p_{i}} + \frac{1}{q_{i}} = 1 for each i. The dual of L^{p} is L_{s}^{q}. The proof relies on the following Lemma. Let a, b ∈ ℝ_{+}, α, β > 1 and \frac{1}{α} + \frac{1}{β} = 1. We have the inequality

\frac{a^{α}}{α} + \frac{b^{β}}{β} ≥ ab ,

with equality if and only if a^{α} = b^{β}. Corollaries

⋄ (L_{s}^{p})^{∗} = L^{q}, (L^{q})^{∗} = L_{s}^{p} and (L_{s}^{q})^{∗} = L^{p}.

⋄ L^{p} and L_{s}^{q} are closed.

François Glineur, FPMs  Page 9  LP 99, Copenhagen

[figure]

Orthogonality conditions If v = (x, θ, κ) ∈ L^{p} and v^{∗} = (x^{∗}, θ^{∗}, κ^{∗}) ∈ L_{s}^{q}, we have

⋄ v^{T} v^{∗} ≥ 0

⋄ v^{T} v^{∗} = 0 if and only if

\{  \begin{matrix}κ^{∗}(f_{p}(x, θ) − κ) & = 0 \\ θ(f_{q}(x^{∗}, κ^{∗}) − θ^{∗}) & = 0 \\ κ^{∗} \frac{|x_{i}|^{p_{i}}}{θ^{p_{i}−1}} & = θ \frac{|x_{i}^{∗}|^{q_{i}}}{κ^{∗}^{q_{i}−1}} \\ x_{i}x_{i}^{∗} & ≤ 0 for all i . \end{matrix}

We are now ready to apply the general duality theory for conic primal-dual pairs, using our dual cones L^{p} and L_{s}^{q}, to derive the duality properties of the l_{p}-norm optimization primal-dual pairs.

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

François Glineur, FPMs  Page 10  LP 99, Copenhagen

[figure]

[figure]

l_{p}-norm optimization

Formulation with L^{p} cone

Primal

inf ψ(x, z) = c^{T} x + d^{T} z + ∑_{k=1}^{r} z_{k} ∑_{i∈I_{k}} \frac{1}{p_{i}} |\frac{x_{i}}{z_{k}} |^{p_{i}}
s.t. Ax + Bz = η and z ≥ 0
⇕
inf ψ̄(x, z, v) = c^{T} x + d^{T} z + e^{T} v
s.t. Ax + Bz = η, z ≥ 0 and

z_{k} ∑_{i∈I_{k}} \frac{1}{p_{i}} |\frac{x_{i}}{z_{k}} |^{p_{i}} ≤ v_{k} ∀k ∈ K

⇕

inf ψ̄(x, z, v) = c^{T} x + d^{T} z + e^{T} v
s.t. Ax + Bz = η and

(x_{I_{k}}, z_{k}, v_{k}) ∈ L^{p_{I_{k}}} ∀k ∈ K

where e is the all-one vector.

François Glineur, FPMs  Page 11  LP 99, Copenhagen

[figure]

⇒ mechanically derive the dual, using that

(A B)^{T} = (\begin{matrix}A^{T} \\ B^{T} \end{matrix} )

and

(L^{p})^{∗} = L_{s}^{q}

Dual

sup η^{T} y
s.t. A^{T} y + x^{∗} = c, B^{T} y + z^{∗} = d, v^{∗} = e
and (x_{I_{k}}^{∗}, z_{k}^{∗}, v_{k}^{∗}) ∈ L_{s}^{q_{I_{k}}} ∀k ∈ K

⇕

sup η^{T} y
s.t. (c_{I_{k}} − A_{I_{k}}^{T}y, 1, d_{k} − b_{k}^{T} y) ∈ L^{q_{I_{k}}} ∀k ∈ K

⇕

sup η^{T} y
s.t. ∑_{i∈I_{k}} \frac{1}{q_{i}} |c_{i} − a_{i}^{T} y|^{q_{i}} ≤ d_{k} − b_{k}^{T} y ∀k ∈ K

where a_{i} is a shorthand notation for A_{{i}}^{T}

François Glineur, FPMs  Page 12  LP 99, Copenhagen

[figure]

Weak duality

If (x, z) is feasible for the primal and y is feasible for the dual, we have η^{T} y ≤ ψ(x, z). Equality occurs if and only if we have, for all k ∈ K and i ∈ I_{k},

z_{k}(∑_{i∈I_{k}} \frac{1}{q_{i}} |c_{i} − a_{i}^{T} y|^{q_{i}} + b_{k}^{T} y − d_{k}) = 0,

x_{i}(c_{i} − a_{i}^{T} y) ≤ 0, \frac{|x_{i}|^{p_{i}}}{z_{k}^{p_{i}−1}} = z_{k} |c_{i} − a_{i}^{T} y|^{q_{i}}

Proof. Use weak duality theorem on conic optimization primal-dual pair and extend objective values to the l_{p}-norm optimization primal-dual pair. This proof and the corresponding classical proof are not too difficult.

The classical proof of the strong duality properties is much more involved.

François Glineur, FPMs  Page 13  LP 99, Copenhagen

[figure]

Strong duality

If the primal and the dual are feasible, the dual optimum objective is attained with a zero duality gap, i.e.

d^{∗} = max η^{T} y s.t. ∑_{i∈I_{k}} \frac{1}{q_{i}} |c_{i} − a_{i}^{T} y|^{q_{i}} ≤ d_{k} − b_{k}^{T} y

= inf ψ(x, z) s.t. Ax + Bz = η and z ≥ 0 = p^{∗}

Proof. Existence of a strictly feasible point for the primal conic program ⇔ v_{k} > f_{p_{I_{k}}} (x_{I_{k}}, z_{k}) and z_{k} > 0 for all k ∈ K. But the linear constraints may force z_{k} = 0 for some k for every feasible solution ! ⇒ detect these zero z_{k} components and form a restricted primal-dual pair without these variables.

François Glineur, FPMs  Page 14  LP 99, Copenhagen

[figure]

Detection. Use the following linear problem

min 0 s.t. Ax + Bz = η and z ≥ 0

Define Z = set of indices k such that z_{k} is identically zero on the feasible region and N the set of the other indices. (Z, N) is the optimal partition of this linear problem. Strategy. Remove variables z_{k} and x_{I_{k}} for all k ∈ Z ⇒ restricted primal-dual conic pair ⇒ the primal has a strictly feasible solution ⇒ zero duality gap and dual attainment. It remains to prove that

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

⋄ Optimal values are equal for restricted dual and original dual and attainment is preserved (more difficult)

François Glineur, FPMs  Page 15  LP 99, Copenhagen

[figure]

Restricted problems Primal

inf c_{I_{N}}^{T} x_{I_{N}} + d_{N}^{T}z_{N} + e^{T} v_{N}
s.t. A_{I_{N}} x_{I_{N}} + B_{N}z_{N} = η and
(x_{I_{k}}, z_{k}, v_{k}) ∈ L^{p_{I_{k}}} ∀k ∈ N

Convert solution to original primal (which has additional variables) : let z_{k} = 0 and x_{I_{k}} = 0 for all k ∈ Z ⇒ same objective. Dual

sup η^{T} y
s.t. A_{I_{N}}^{T} y + x_{I_{N}}^{∗} = c_{I_{N}} , B_{N}^{T}y + z_{N}^{∗} = d_{N},

v_{N}^{∗} = e and (x_{I_{k}}^{∗}, z_{k}^{∗}, v_{k}^{∗}) ∈ L^{q_{I_{k}}} ∀k ∈ N

Convert solution to original dual (which has additional constraints): not straightforward because feasibility cannot be guaranteed ! We need to modify the optimal solution of the restricted dual.

François Glineur, FPMs  Page 16  LP 99, Copenhagen

[figure]

Strategy Perturb the optimal solution ỹ of the restricted dual 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

η^{T} ȳ = 0, A^{T} ȳ = 0, B_{N}^{T} ȳ ≤ 0 and B_{Z}^{T} ȳ < 0

These properties imply that y = ỹ + λȳ is feasible for the original dual for a sufficiently large value of λ, while keeping the same objective value as ỹ. ⇒ the original dual optimum objective value is attained and equal to the original primal optimum objective value.

François Glineur, FPMs  Page 17  LP 99, Copenhagen

[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

⋄ This approach couldn’t be applied with the simpler regular p-cone

𝕃_{p}^{n} = {(x, κ) ∈ ℝ^{n} × ℝ_{+} | ∑_{i=1}^{n} x_{i}^{p} ≤ κ^{p}}

⋄ This strategy can be applied to other types of convex problems, i.e. entropy optimization and geometric optimization

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

⋄ The approximate self-duality might prove helpful in designing efficient algorithms (cf. self-scaled cones)

François Glineur, FPMs  Page 18  LP 99, Copenhagen